Note: There is an active PR for including this algorithm in
networkx at networkx/#3127.
Equitable coloring for networkX graphs.
In graph theory [..] an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that
- No two adjacent vertices have the same color, and
- The numbers of vertices in any two color classes differ by at most one.
Kierstead et. al. have provided a fast polynomial time algorithm for uncovering an equitable coloring using
r + 1 colors for a graph with maximum degree
This package is an implementation of the algorithm for networkX graphs.
- Free software: MIT license
pip install equitable-coloring
>>> import networkx as nx >>> from equitable_coloring import equitable_color >>> from equitable_coloring.utils import is_equitable >>> G = nx.cycle_graph(4) >>> d = equitable_color(G, num_colors=3) >>> is_equitable(G, d) True
To run the all tests run:
pip install pytest-cov # Needed the first time. python setup.py test
Or, you can use