7. Documentation

The following methods are available in the gcol graph coloring library. All methods containing the word color in their name can also be invoked using the alternative spelling colour.

7.1. Edge Coloring

Edge coloring functions.

gcol.edge_coloring.chromatic_index(G)

Return the chromatic index of the graph G.

The chromatic index of a graph \(G\) is the minimum number of colors needed to color the edges so that no two adjacent edges have the same color (a pair of edges is considered adjacent if and only if they share a common endpoint). The chromatic index is commonly denoted by \(\chi'(G)\). Equivalently, \(\chi'(G)\) is the minimum number of matchings needed to partition the edges of \(G\). According to Vizing’s theorem [1], \(\chi'(G)\) is equal to either \(\Delta(G)\) or \(\Delta(G) + 1\), where \(\Delta(G)\) is the maximum degree in \(G\).

Determining the chromatic index of a graph is NP-hard. The approach used here is based on the backtracking algorithm of [2]. This is exact but operates in exponential time. It is therefore only suitable for graphs that are small, or that have topologies suited to its search strategies.

In this implementation, edge colorings of a graph \(G\) are determined by forming \(G\)’s line graph \(L(G)\) and then passing \(L(G)\) to the chromatic_number() method.

Parameters:

GNetworkX graph

The chromatic index for this graph will be calculated.

Returns:

int

A nonnegative integer that gives the chromatic index of G.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

See also

gcol.node_coloring.chromatic_number()

gcol.node_coloring.node_coloring()

Notes

The backtracking approach used here is an implementation of the exact algorithm described in [2]. It has exponential runtime and halts only when the chromatic index has been determined. Further details of this algorithm are given in the notes section of the node_coloring() method.

The above algorithm is described in detail in [2]. The c++ code used in [2] and [3] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Vizing’s Theorem <https://en.wikipedia.org/wiki/Vizing%27s_theorem>

[2] (1,2,3,4)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[3]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> chi = gcol.chromatic_index(G)
>>> print("Chromatic index is", chi)
Chromatic index is 3

gcol.edge_coloring.edge_coloring(G, strategy='dsatur', opt_alg=None, it_limit=0, verbose=0)

Return a coloring of a graph’s edges.

An edge coloring of a graph is an assignment of colors to edges so that adjacent edges have different colors (a pair of edges is considered adjacent if and only if they share a common endpoint). The aim is to use as few colors as possible. A set of edges assigned to the same color corresponds to a matching; hence the equivalent aim is to partition the graph’s edges into a minimum number of matchings.

The smallest number of colors needed for coloring the edges of a graph \(G\) is known as the graph’s chromatic index, denoted by \(\chi'(G)\). Equivalently, \(\chi'(G)\) is the minimum number of matchings needed to partition the nodes of a simple graph \(G\). According to Vizing’s theorem [1], \(\chi'(G)\) is either \(\Delta(G)\) or \(\Delta(G) + 1\), where \(\Delta(G)\) is the maximum degree in \(G\).

Determining an edge coloring that minimizes the number of colors is an NP-hard problem. This method therefore includes options for using an exponential-time exact algorithm (based on backtracking), or a choice of four polynomial-time heuristic algorithms (based on local search). The exact algorithm is generally only suitable for graphs that are small, or that have topologies suited to its search strategies. In all other cases, the local search algorithms are more appropriate.

In this implementation, edge colorings of a graph \(G\) are determined by forming \(G\)’s line graph \(L(G)\), and then passing \(L(G)\) to the node_coloring() method. All parameters are therefore the same as the latter. (Note that, if a graph \(G=(V,E)\) has \(n\) nodes and \(m\) edges, its line graph \(L(G)\) will have \(m\) nodes and \(\frac{1}{2}\sum_{v\in V} \deg(v)^2 - m\) edges.)

Parameters:

GNetworkX graph

The edges of this graph will be colored.

strategystring, optional (default=’dsatur’)

A string specifying the method used to generate the initial solution. It must be one of the following:

• 'random' : Randomly orders \(L(G)\)’s nodes and then applies the greedy algorithm for graph node coloring [2].

• 'welsh-powell' : Orders \(L(G)\)’s nodes by decreasing degree, then applies the greedy algorithm.

• 'dsatur' : Uses the DSatur algorithm for graph node coloring on \(L(G)\) [3].

• 'rlf' : Uses the recursive largest first (RLF) algorithm for graph node coloring on \(L(G)\) [4].

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors. It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes in \(L(G)\) to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in \(L(G)\), \(m\) is the number of edges in \(L(G)\), and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes in \(L(G)\) to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing edges and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). The number of colors being used in a solution c is therefore max(c.values()) + 1.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If strategy is not among the supported options.

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

See also

chromatic_index

edge_k_coloring

gcol.node_coloring.node_coloring()

Notes

As mentioned, in this implementation, edge colorings of a graph \(G\) are determined by forming \(G\)’s line graph \(L(G)\) and then passing \(L(G)\) to the node_coloring() method. All details are therefore the same as those in the latter, where they are documented more fully.

All the above algorithms and bounds are described in detail in [5]. The c++ code used in [5] and [6] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Vizing’s Theorem <https://en.wikipedia.org/wiki/Vizing%27s_theorem>

[2]

Wikipedia: Greedy Coloring <https://en.wikipedia.org/wiki/Greedy_coloring>

[3]

Wikipedia: DSatur <https://en.wikipedia.org/wiki/DSatur>

[4]

Wikipedia: Recursive largest first (RLF) algorithm <https://en.wikipedia.org/wiki/Recursive_largest_first_algorithm>

[5] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[6]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.edge_coloring(G)
>>> print("Coloring is", c)
Coloring is {(11, 12): 0, (11, 18): 1, ..., (7, 8): 0}
>>>
>>> print("Number of colors =", max(c.values()) + 1)
Number of colors = 3
>>>
>>> c = gcol.edge_coloring(G, strategy="rlf", opt_alg=2, it_limit=1000)
>>> print("Coloring is", c)
Coloring is {(3, 4): 0, (17, 18): 0, ..., (7, 14): 2}
>>>
>>> print("Number of colors =", max(c.values()) + 1)
Number of colors = 3

gcol.edge_coloring.edge_k_coloring(G, k, opt_alg=None, it_limit=0, verbose=0)

Attempt to color the edges of a graph G using k colors.

This is done so that adjacent edges have different colors (a pair of edges is considered adjacent if and only if they share a common endpoint). A set of edges assigned to the same color corresponds to a matching; hence the equivalent aim is to partition the graph’s edges into k matchings.

The smallest number of colors needed for coloring the edges of a graph \(G\) is known as the graph’s chromatic index, denoted by \(\chi'(G)\). Equivalently, \(\chi'(G)\) is the minimum number of matchings needed to partition the nodes of a simple graph \(G\). According to Vizing’s theorem [1], \(\chi'(G)\) is either \(\Delta(G)\) or \(\Delta(G) + 1\), where \(\Delta(G)\) is the maximum degree in \(G\). The problem of determining an edge \(k\)-coloring is polynomially solvable for any \(k > \Delta(G)\). Similarly, it is certain no edge \(k\)-coloring exists for \(k < \Delta(G)\). For \(k = \Delta(G)\), however, the problem is NP-hard.

This method therefore includes options for using an exact exponential-time algorithm (based on backtracking), or a choice of four polynomial-time heuristic algorithms (based on local search). The exact algorithm is generally only suitable for larger values of \(k\), for graphs that are small, or graphs that have topologies suited to its search strategies. In all other cases, the local search algorithms are more appropriate.

This method follows the steps used by the node_k_coloring() method. That is, edge \(k\)-colorings of a graph \(G\) are determined by forming \(G\)’s line graph \(L(G)\) and then passing \(L(G)\) to the node_k_coloring() method. All parameters are therefore the same as the latter. (Note that, if a graph \(G=(V,E)\) has \(n\) nodes and \(m\) edges, its line graph \(L(G)\) will have \(m\) nodes and \(\frac{1}{2}\sum_{v\in V}\deg(v)^2 - m\) edges.)

If an edge \(k\)-coloring cannot be determined by the algorithm, a ValueError exception is raised. Otherwise, an edge \(k\)-coloring is returned.

Parameters:

GNetworkX graph

The edges of this graph will be colored.

kint

The number of colors to use.

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors (if this is seen to be greater than \(k\)). It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when the existence of an edge \(k\)-coloring has been proved or disproved.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes in \(L(G)\) to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in \(L(G)\), \(m\) is the number of edges in \(L(G)\), and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes in \(L(G)\) to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing edges and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots,k-1\).

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If k is not a nonnegative integer.

If a clique larger than k is observed in the line graph of \(G\).

If k is less than the maximum degree in G.

If an edge \(k\)-coloring could not be determined.

See also

edge_coloring

equitable_edge_k_coloring

gcol.node_coloring.node_k_coloring()

Notes

As mentioned, in this implementation, edge colorings of a graph \(G\) are determined by forming \(G\)’s line graph \(L(G)\) and then passing \(L(G)\) to the node_k_coloring() method. All details are therefore the same as those in the latter. The routine halts immediately once an edge \(k\)-coloring has been achieved.

All the above algorithms and bounds are described in detail in [2]. The c++ code used in [2] and [3] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Vizing’s Theorem <https://en.wikipedia.org/wiki/Vizing%27s_theorem>

[2] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[3]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.edge_k_coloring(G, 4)
>>> print(c)
{(11, 12): 0, (11, 18): 1, (10, 11): 2, ..., (6, 7): 2}
>>>
>>> c = gcol.edge_k_coloring(G, 3)
>>> print(c)
{(11, 12): 0, (11, 18): 1, (10, 11): 2, ..., (7, 8): 0}

gcol.edge_coloring.edge_list_coloring(G, allowed_cols=None, strategy='dsatur', opt_alg=None, it_limit=0, verbose=0)

Return a solution to the edge list coloring problem on G.

In the edge list coloring problem, each edge \(\{u,v\}\) is associated with a list of allowed colors \(L(\{u,v\})\). A solution is an assignment of colors to all edges so that adjacent edges have different colors, and the color of each edge \(\{u,v\}\) belongs to the list \(L(\{u,v\})\).

The list coloring problem is NP-hard. This method therefore includes options for using an exponential-time exact algorithm (based on backtracking), or a choice of four polynomial-time heuristic algorithms (based on local search). The exact algorithm is generally only suitable for graphs that are small, or that have topologies suited to its search strategies. In all other cases, the local search algorithms are more appropriate.

In this implementation, colors are defined using labels belonging to \(\{0,1,2,\ldots\}\). Assuming \(k\) is the largest color label appearing across all lists, the aim is to find a solution using at most \(k\) colors. If this cannot be achieved, an exception is raised (see below).

Here, edge colorings of a graph \(G\) are determined by forming \(G\)’s line graph \(L(G)\) and then passing \(L(G)\) to the node_list_coloring() method. All parameters are therefore the same as the latter. (Note that, if a graph \(G=(V,E)\) has \(n\) nodes and \(m\) edges, its line graph \(L(G)\) will have \(m\) nodes and \(\frac{1}{2}\sum_{v\in V} \deg(v)^2 - m\) edges.)

Parameters:

GNetworkX graph

The edges of this graph will be colored.

allowed_colsNone or dict, optional (default=None)

A dictionary keyed by the edges of G. allowed_cols[(u, v)] should be a list of (nonnegative integer) colors that give the permissible colors for edge (u, v). If None, an edge coloring with the minimum number of colors is returned.

strategystring, optional (default=’dsatur’)

A string specifying the method used to generate the initial solution. It must be one of the following:

• 'random' : Randomly orders \(L(G)\)’s nodes and then applies the greedy algorithm for graph node coloring [1].

• 'welsh-powell' : Orders \(L(G)\)’s nodes by decreasing degree, then applies the greedy algorithm.

• 'dsatur' : Uses the DSatur algorithm for graph node coloring on \(L(G)\) [2].

• 'rlf' : Uses the recursive largest first (RLF) algorithm for graph node coloring on \(L(G)\) [3].

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used.

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes in \(L(G)\) to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in \(L(G)\), \(m\) is the number of edges, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes in \(L(G)\) to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing edges and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). If c[(u,v)]==j then j is an element of allowed_cols[(u, v)].

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If strategy is not among the supported options.

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If allowed_cols has an edge not in G, or is missing an entry for an edge in G.

If allowed_cols contains a color label that is not a nonnegative integer.

If allowed_cols contains a list that is empty.

If allowed_cols contains a pair of adjacent edges that have the same single allowed color.

If allowed_cols contains entries for the same edges \((u, v)\) and \((v, u)\).

If an edge list coloring could not be determined (the lists of allowed colors are too restrictive).

TypeError

If allowed_cols is not a dict.

See also

gcol.node_coloring.node_coloring()

gcol.edge_coloring.edge_precoloring()

gcol.node_coloring.node_list_coloring()

Notes

All the above algorithms and bounds are described in detail in [1]. The c++ code used in [1] and [5] forms the basis of this library’s Python implementations.

References

[1] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[2]

Wikipedia: Greedy Coloring <https://en.wikipedia.org/wiki/Greedy_coloring>

[3]

Wikipedia: DSatur <https://en.wikipedia.org/wiki/DSatur>

[4]

Wikipedia: Recursive largest first (RLF) algorithm <https://en.wikipedia.org/wiki/Recursive_largest_first_algorithm>

[5]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.cycle_graph(4)
>>> E = {(0, 1): [0, 1], (1, 2): [1, 2], (2, 3): [1], (3, 0): [0, 1]}
>>> c = gcol.edge_list_coloring(G, E)
>>> print("Coloring is", c)
Coloring is {(0, 3): 0, (2, 3): 1, (0, 1): 1, (1, 2): 0}

gcol.edge_coloring.edge_precoloring(G, precol=None, strategy='dsatur', opt_alg=None, it_limit=0, verbose=0)

Return a coloring of a graph’s edges where some edges are precolored.

An edge coloring of a graph is an assignment of colors to edges so that adjacent edges have different colors. In the edge precoloring problem, some of the edges have already been assigned colors. Colors are defined using labels belonging to the set \(\{0,1,2,\ldots\}\). Assuming \(k\) is the largest color label used in the precoloring, the aim is to color all remaining edges using \(l\) colors, where \(l\) is minimized and \(k\leq l\).

The edge precoloring problem is NP-hard. This method therefore includes options for using an exponential-time exact algorithm (based on backtracking), or a choice of four polynomial-time heuristic algorithms (based on local search). The exact algorithm is generally only suitable for graphs that are small, or that have topologies suited to its search strategies. In all other cases, the local search algorithms are more appropriate.

In this implementation, edge colorings of a graph \(G\) are determined by forming \(G\)’s line graph \(L(G)\) and then passing \(L(G)\) to the node_precoloring() method. All parameters are therefore the same as the latter. (Note that, if a graph \(G=(V,E)\) has \(n\) nodes and \(m\) edges, its line graph \(L(G)\) will have \(m\) nodes and \(\frac{1}{2}\sum_{v\in V} \deg(v)^2 - m\) edges.)

Parameters:

GNetworkX graph

The edges of this graph will be colored.

precolNone or dict, optional (default=None)

A dictionary that specifies the colors of any precolored edges.

strategystring, optional (default=’dsatur’)

A string specifying the method used to generate the initial solution. It must be one of the following:

• 'random' : Randomly orders \(L(G)\)’s nodes and then applies the greedy algorithm for graph node coloring [1].

• 'welsh-powell' : Orders \(L(G)\)’s nodes by decreasing degree, then applies the greedy algorithm.

• 'dsatur' : Uses the DSatur algorithm for graph node coloring on \(L(G)\) [2].

• 'rlf' : Uses the recursive largest first (RLF) algorithm for graph node coloring on \(L(G)\) [3].

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors. It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes in \(L(G)\) to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in \(L(G)\), \(m\) is the number of edges, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes in \(L(G)\) to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing edges and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). If precol[(u,v)]==j then c[(u,v)]==j.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If strategy is not among the supported options.

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If precol contains an edge that is not in G.

If precol contains a color label that is not a nonnegative integer.

If precol contains a pair of adjacent edges assigned to the same color.

If precol contains entries for the same edges (u, v) and (v, u).

TypeError

If precol is not a dict.

See also

edge_coloring

gcol.node_coloring.node_precoloring()

gcol.node_coloring.node_coloring()

Notes

All the above algorithms and bounds are described in detail in [4]. The c++ code used in [4] and [5] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Greedy Coloring <https://en.wikipedia.org/wiki/Greedy_coloring>

[2]

Wikipedia: DSatur <https://en.wikipedia.org/wiki/DSatur>

[3]

Wikipedia: Recursive largest first (RLF) algorithm <https://en.wikipedia.org/wiki/Recursive_largest_first_algorithm>

[4] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[5]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> p = {(0, 1):0, (8, 9): 1, (10, 11): 2, (11, 12): 3}
>>> c = gcol.edge_precoloring(G, precol=p)
>>> print("Coloring is",c)
Coloring is {(0, 1): 0, (8, 9): 1, ..., (5, 6): 2}

gcol.edge_coloring.equitable_edge_k_coloring(G, k, weight=None, opt_alg=None, it_limit=0, verbose=0)

Attempt to color the edges of a graph using k colors.

This is done so that (a) adjacent edges have different colors, and (b) the weight of each color class is equal. (A pair of edges is considered adjacent if and only if they share a common endpoint.) If weight=None, the weight of a color class is the number of edges assigned to that color; otherwise, it is the sum of the weights of the edges assigned to that color.

Equivalently, this routine seeks to partition the graph’s edges into \(k\) matchings so that the weight of each matching is equal.

This method first follows the steps used by the edge_k_coloring() method to try and find an edge \(k\)-coloring. That is, edge colorings of a graph \(G\) are determined by forming \(G\)’s line graph \(L(G)\) and then passing \(L(G)\) to the node_k_coloring() method. All parameters are therefore the same as the latter. (Note that, if a graph \(G=(V,E)\) has \(n\) nodes and \(m\) edges, its line graph \(L(G)\) will have \(m\) nodes and \(\frac{1}{2}\sum_{v\in V}\deg(v)^2 - m\) edges.)

If an edge \(k\)-coloring cannot be determined by the algorithm, a ValueError exception is raised. Otherwise, once an edge \(k\)-coloring has been formed, the algorithm uses a bespoke local search operator to reduce the standard deviation in weights across the \(k\) colors. In solutions returned by this method, adjacent edges always receive different colors; however, the coloring is not guaranteed to be equitable, even if an equitable edge \(k\)-coloring exists.

Parameters:

GNetworkX graph

The edges of this graph will be colored.

kint

The number of colors to use.

weightNone or string, optional (default=None)

If None, every edge is assumed to have a weight of 1. If a string, this should correspond to a defined edge attribute. Edge weights must be positive.

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors (if this is seen to be greater than k). It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when the existence of an edge \(k\)-coloring has been proved or disproved.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes in \(L(G)\) to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in \(L(G)\), \(m\) is the number of edges in \(L(G)\), and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes in \(L(G)\) to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing edges and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots,k-1\).

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If k is not a nonnegative integer.

If a clique larger than k is observed in the line graph of \(G\).

If k is less than the maximum degree in G.

If an edge \(k\)-coloring could not be determined.

If an edge with a non-positive weight is specified.

KeyError

If an edge does not have the attribute defined by weight

See also

edge_k_coloring

gcol.node_coloring.node_k_coloring()

gcol.node_coloring.equitable_node_k_coloring()

gcol.node_coloring.kempe_chain()

Notes

As mentioned, in this implementation edge colorings of a graph \(G\) are determined by forming \(G\)’s line graph \(L(G)\) and then following the same steps as the node_k_coloring() method to try and find a node \(k\)-coloring of \(L(G)\); however, it also takes edge weights into account if needed. If an edge \(k\)-coloring is achieved, a bespoke local search operator (based on steepest descent) is then used to try to reduce the standard deviation in weights across the \(k\) color classes. This follows the same steps as the equitable_node_k_coloring() method, using \(L(G)\). Further details on this optimization method can be found in Chapter 7 of [2], or in [3].

All the above algorithms are described in detail in [2]. The c++ code used in [2] and [4] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Vizing’s Theorem <https://en.wikipedia.org/wiki/Vizing%27s_theorem>

[2] (1,2,3)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[3]

Lewis, R. and F. Carroll (2016) ‘Creating Seating Plans: A Practical Application’. Journal of the Operational Research Society, vol. 67(11), pp. 1353-1362.

[4]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.equitable_edge_k_coloring(G, 4)
>>> P = gcol.partition(c)
>>> print(P)
[[(11, 12), (18, 19), (16, 17), (9, 10), ..., (5, 6)]]
>>> print("Size of smallest color class =", min(len(j) for j in P))
Size of smallest color class = 7
>>> print("Size of biggest color class =", max(len(j) for j in P))
Size of biggest color class = 8
>>>
>>> #Now add some (arbitrary) weights to the edges
>>> for e in G.edges():
>>>     G.add_edge(e[0], e[1], weight = abs(e[0]-e[1]))
>>> c = gcol.equitable_edge_k_coloring(G, 5, weight="weight")
>>> P = gcol.partition(c)
>>> print(P)
[[(11, 12), (18, 19), (4, 17), (13, 14), ..., (2, 6)]]
>>> print(
...     "Weight of lightest color class =",
...     min(sum(G[u][v]["weight"] for u, v in j) for j in P)
... )
Weight of lightest color class = 23
>>> print(
...     "Weight of heaviest color class =",
...     max(sum(G[u][v]["weight"] for u, v in j) for j in P)
... )
Weight of heaviest color class = 25

7.2. Face Coloring

Face coloring functions.

gcol.face_coloring.dual_graph(G, pos)

Return the dual graph of the specified planar embedding of G.

The dual graph \(G^*\) of a planar graph \(G\) has a node for each face in the supplied embedding of \(G\), including the external face. Each edge in \(G^*\) corresponds to a pair of faces in \(G\) that share a boundary. According to Euler’s formula, \(G\) has \(f=m-n+2\) faces, where \(n\) is its number of nodes and \(m\) is the number of edges. Consequently, \(G^*\) has \(f\) nodes.

The graph G must be planar. The embedding is defined by pos, which should give valid \((x,y)\) coordinates for all nodes in G so that none of its edges (expressed as straight lines) cross. G should also be connected and have no bridges.

Parameters:

GNetworkX graph

A bridge-free, connected planar graph.

posdict

A dictionary of positions keyed by node. All positions should be \((x,y)\) coordinates, and none of the edges in the resultant embedding should be crossing.

Returns:

NetworkX graph

The dual graph in which nodes are labelled using integers from 0 upwards. Node 0 corresponds to the single external face of G; the remainder correspond to the internal faces.

list

The \(i\)th element in the list is a tuple giving the sequence of nodes that surround the \(i\)th face in G. This face corresponds to node \(i\) in the returned dual graph. The first element in this list defines the external face; the remainder define the internal faces. For internal faces, the nodes are listed in a counterclockwise order. For the external face, the nodes are listed in a clockwise order.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

If G is not connected or is a singleton.

TypeError

If pos is not a dictionary.

ValueError

If pos has missing or invalid entries.

If pos does not specify a valid planar embedding of G.

If G is not planar or contains bridges.

See also

face_chromatic_number

face_coloring

Notes

The structure of a dual graph \(G^*\) depends on the coordinates of the nodes in \(G\). That is, different planar embeddings of \(G\) can lead to different dual graphs.

If the graph G contains no articulation points, all faces will be cycles. If G does contain any articulation points, these can occur more than once on the boundary of a face; hence, some faces may be circuits.

At present, this method does not allow self-loops, disconnected graphs (including faces with holes), or multi-edges. Multi-edges can be simulated by using paths of degree-two nodes with suitable coordinates.

Examples

>>> import gcol
>>> import networkx as nx
>>>
>>> G = nx.dodecahedral_graph()
>>> pos = nx.planar_layout(G)
>>> H, faces = gcol.dual_graph(G, pos)
>>> print(H)
Graph with 12 nodes and 30 edges
>>> print(faces)
[(0, 10, 9, 8, 1), ..., (13, 12, 16, 15, 14)]

gcol.face_coloring.equitable_face_k_coloring(G, pos, k, opt_alg=None, it_limit=0, verbose=0)

Attempt to color the faces of a planar graph G using k colors.

This is done so that (a) adjacent faces have different colors, and (b) the number of faces with each color is equal. (A pair of faces is adjacent if and only if they share a bordering edge.) The graph G must be planar, and pos should give valid \((x,y)\) coordinates for all nodes.

This method first follows the steps used by the face_k_coloring() method. All parameters are therefore the same as the latter. If a face \(k\)-coloring cannot be determined by the algorithm, a ValueError exception is raised. Otherwise, once a face \(k\)-coloring has been formed, the algorithm uses a bespoke local search operator to reduce the standard deviation in the number of faces in each color class.

In solutions returned by this method, adjacent faces always receive different colors; however, the coloring is not guaranteed to be equitable, even if an equitable face \(k\)-coloring exists.

According to the four color theorem [1], face colorings never require more than four colors. In this implementation, face colorings of a graph \(G\) are determined by forming \(G\)’s dual graph.

Parameters:

GNetworkX graph

A bridge-free, connected planar graph. Its faces will be colored.

kint

The number of colors to use.

posdict

A dictionary of positions keyed by node. All positions should be \((x,y)\) coordinates, and none of the edges in the resultant embedding should be crossing.

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors. It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes in the dual to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in the dual, \(m\) is the number of edges in the dual, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes in the dual to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing faces and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). The number of colors being used in a solution c is therefore max(c.values()) + 1. Each face (key) is a tuple that gives the sequence of nodes that surround it. The first element in c defines the external face; the remainder defines the internal faces. For internal faces, the nodes are listed in a counterclockwise order; for the external face, the nodes are listed in a clockwise order.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

If G is not connected or is a singleton.

TypeError

If pos is not a dictionary.

ValueError

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If pos has missing or invalid entries.

If pos does not specify a valid planar embedding of G.

If G is not planar or contains bridges.

If k is not a nonnegative integer.

If a clique larger than k is observed in the dual graph of \(G\).

If a face \(k\)-coloring could not be determined.

See also

face_coloring

gcol.node_coloring.equitable_node_k_coloring()

Notes

As mentioned, in this implementation face colorings of a graph \(G\) are determined by forming its dual and then passing this to the node_k_coloring() method. If a face \(k\)-coloring is achieved, a bespoke local search operator (based on steepest descent) is then used to try to reduce the standard deviation in sizes across the \(k\) color classes. This follows the same steps as the equitable_node_k_coloring() method, using the dual of G. Further details on this optimization method can be found in Chapter 7 of [2].

All the above algorithms and bounds are described in detail in [2]. The c++ code used in [2] and [3] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Four Color Theorem <https://en.wikipedia.org/wiki/Four_color_theorem>

[2] (1,2,3)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[3]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import gcol
>>> import networkx as nx
>>>
>>> G = nx.dodecahedral_graph()
>>> pos = nx.planar_layout(G)
>>> c = gcol.equitable_face_k_coloring(G, pos, 5)
>>> print(c)
{(1, 0, 10, 9, 8): 0, (10, 0, 19, 18, 11): 2, ..., (13, 12, 16, 15, 14): 0}

gcol.face_coloring.face_chromatic_number(G)

Return the face chromatic number of the planar graph G.

The face chromatic number of a planar graph \(G\) is the minimum number of colors needed to color its faces so that no two adjacent faces have the same color (a pair of faces is considered adjacent if and only if they share a common bordering edge). According to the four color theorem [1], it will never exceed four.

The approach used here is based on the backtracking algorithm of [2]. This is exact but operates in exponential time in the worst case. In this implementation, the solution is found for \(G\) by determining a planar embedding, forming the dual graph, and then passing this to the chromatic_number() method.

Parameters:

GNetworkX graph

The face chromatic number for this graph will be calculated. It must be bridge-free, connected, and planar.

Returns:

int

A nonnegative integer that gives the face chromatic number of G.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

If G is not connected or is a singleton.

ValueError

If G is not planar or has bridges.

See also

face_coloring

gcol.node_coloring.chromatic_number()

Notes

The backtracking approach used here is an implementation of the exact algorithm described in [2]. It has exponential runtime and halts only when the face chromatic number has been determined. Further details of this algorithm are given in the notes section of the node_coloring() method.

The above algorithm is described in detail in [2]. The c++ code used in [2] and [3] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Four Color Theorem <https://en.wikipedia.org/wiki/Four_color_theorem>

[2] (1,2,3,4)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[3]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import gcol
>>> import networkx as nx
>>>
>>> G = nx.dodecahedral_graph()
>>> print(gcol.face_chromatic_number(G))
4

gcol.face_coloring.face_coloring(G, pos, strategy='dsatur', opt_alg=None, it_limit=0, verbose=0)

Return a coloring of a planar graph’s faces.

A face coloring is an assignment of colors to the faces of a graph’s planar embedding so that adjacent faces have different colors (a pair of faces is adjacent if and only if they share a bordering edge). The aim is to use as few colors as possible. Face colorings are only possible in planar embeddings; hence the graph G must be planar, and pos should give valid \((x,y)\) coordinates for all nodes.

The smallest number of colors needed to face color a graph is known as its face chromatic number. According to the four color theorem [1], face colorings never require more than four colors. In this implementation, face colorings of a graph \(G\) are determined by forming \(G\)’s dual graph, and then coloring the dual’s nodes using the node_coloring() method. All parameters are therefore the same as the latter. If \(G\) has \(n\) nodes and \(m\) edges, its embedding has exactly \(m-n+2\) faces, including the external face.

Parameters:

GNetworkX graph

A bridge-free, connected planar graph. Its faces will be colored.

posdict

A dictionary of positions keyed by node. All positions should be \((x,y)\) coordinates, and none of the edges in the resultant embedding should be crossing.

strategystring, optional (default=’dsatur’)

A string specifying the method used to generate the initial solution. It must be one of the following:

• 'random' : Randomly orders the dual’s nodes and then applies the greedy algorithm for graph node coloring [2].

• 'welsh-powell' : Orders the dual’s nodes by decreasing degree, then applies the greedy algorithm.

• 'dsatur' : Uses the DSatur algorithm for graph node coloring on the dual [3].

• 'rlf' : Uses the recursive largest first (RLF) algorithm for graph node coloring on the dual [4].

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors. It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes in the dual to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in the dual, \(m\) is the number of edges in the dual, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes in the dual to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing faces and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). The number of colors being used in a solution c is therefore max(c.values()) + 1. Each face (key) is a tuple that gives the sequence of nodes that surround it. The first element in c defines the external face; the remainder defines the internal faces. For internal faces, the nodes are listed in a counterclockwise order; for the external face, the nodes are listed in a clockwise order.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

If G is not connected or is a singleton.

TypeError

If pos is not a dictionary.

ValueError

If strategy is not among the supported options.

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If pos has missing or invalid entries.

If pos does not specify a valid planar embedding of G.

If G is not planar or contains bridges.

See also

face_chromatic_number

gcol.node_coloring.node_coloring()

Notes

As mentioned, in this implementation face colorings of a graph \(G\) are determined by forming its dual and then passing this to the node_coloring() method. All details are therefore the same as those in the latter method, where they are documented more fully.

All the above algorithms and bounds are described in detail in [5]. The c++ code used in [5] and [6] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Four Color Theorem <https://en.wikipedia.org/wiki/Four_color_theorem>

[2]

Wikipedia: Greedy Coloring <https://en.wikipedia.org/wiki/Greedy_coloring>

[3]

Wikipedia: DSatur <https://en.wikipedia.org/wiki/DSatur>

[4]

Wikipedia: Recursive largest first (RLF) algorithm <https://en.wikipedia.org/wiki/Recursive_largest_first_algorithm>

[5] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[6]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import gcol
>>> import networkx as nx
>>>
>>> G = nx.dodecahedral_graph()
>>> pos = nx.planar_layout(G)
>>> c = gcol.face_coloring(G, pos)
>>> print(c)
{(1, 0, 10, 9, 8): 0, (10, 0, 19, 18, 11): 2, ..., (13, 12, 16, 15, 14): 2}

gcol.face_coloring.face_k_coloring(G, pos, k, opt_alg=None, it_limit=0, verbose=0)

Attempt to color the faces of a planar graph G using k colors.

This is done so that adjacent faces have different colors (a pair of faces is adjacent if and only if they share a bordering edge). The graph G must be planar, and pos should give valid \((x,y)\) coordinates for all nodes.

According to the four color theorem [1], face colorings never require more than four colors. In this implementation, face colorings of a graph \(G\) are determined by forming \(G\)’s dual graph, and then coloring the dual’s nodes using the node_k_coloring() method. All parameters are therefore the same as the latter. If \(G\) has \(n\) nodes and \(m\) edges, its embedding has exactly \(m-n+2\) faces, including the external face.

If a face \(k\)-coloring cannot be determined by the algorithm, a ValueError exception is raised. Otherwise, a face \(k\)-coloring is returned.

Parameters:

GNetworkX graph

A bridge-free, connected planar graph. Its faces will be colored.

kint

The number of colors to use.

posdict

A dictionary of positions keyed by node. All positions should be \((x,y)\) coordinates, and none of the edges in the resultant embedding should be crossing.

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors. It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes in the dual to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in the dual, \(m\) is the number of edges in the dual, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes in the dual to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing faces and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). The number of colors being used in a solution c is therefore max(c.values()) + 1. Each face (key) is a tuple that gives the sequence of nodes that surround it. he first element in c defines the external face; the remainder defines the internal faces. For internal faces, the nodes are listed in a counterclockwise order; for the external face, the nodes are listed in a clockwise order.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

If G is not connected or is a singleton.

TypeError

If pos is not a dictionary.

ValueError

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If pos has missing or invalid entries.

If pos does not specify a valid planar embedding of G.

If G is not planar or contains bridges.

If k is not a nonnegative integer.

If a clique larger than k is observed in the dual graph of \(G\).

If a face \(k\)-coloring could not be determined.

See also

face_coloring

gcol.node_coloring.node_k_coloring()

Notes

As mentioned, in this implementation face colorings of a graph \(G\) are determined by forming its dual and then passing this to the node_k_coloring() method. All details are therefore the same as those in the latter method, where they are documented more fully. The routine halts immediately once a face \(k\)-coloring has been achieved.

All the above algorithms and bounds are described in detail in [2]. The c++ code used in [2] and [3] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Four Color Theorem <https://en.wikipedia.org/wiki/Four_color_theorem>

[2] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[3]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import gcol
>>> import networkx as nx
>>>
>>> G = nx.dodecahedral_graph()
>>> pos = nx.planar_layout(G)
>>> c = gcol.face_k_coloring(G, pos, 5)
>>> print(c)
{(1, 0, 10, 9, 8): 0, (10, 0, 19, 18, 11): 2, ..., (13, 12, 16, 15, 14): 0}

gcol.face_coloring.face_list_coloring(G, pos, allowed_cols=None, strategy='dsatur', opt_alg=None, it_limit=0, verbose=0)

Return a solution to the face list coloring problem on G.

A face coloring is an assignment of colors to the faces of a graph’s planar embedding so that adjacent faces have different colors. In the face list coloring problem, each face \(f\) is associated with a list of allowed colors \(L(f)\). A solution is an assignment of colors to all faces so that adjacent faces have different colors, and the color of each face \(f\) belongs to the list \(L(f)\).

Face colorings are only possible in planar embeddings; hence the graph G must be planar, and pos should give valid \((x,y)\) coordinates for all nodes.

Here, colors are defined using labels belonging to \(\{0,1,2,\ldots\}\). Assuming \(k\) is the largest color label appearing across all lists, the aim is to find a solution using at most \(k\) colors. If this cannot be done, an exception is raised (see below).

In this implementation, face colorings of a graph \(G\) are determined by forming \(G\)’s dual graph, and then passing the dual to the node_list_coloring() method. All parameters are therefore the same as the latter.

Parameters:

GNetworkX graph

A bridge-free, connected planar graph. Its faces will be colored.

posdict

A dictionary of positions keyed by node. All positions should be \((x,y)\) coordinates, and none of the edges in the resultant embedding should be crossing.

allowed_colsNone or dict, optional (default=None)

A dictionary, keyed by faces, that specifies the allowed colors of each face. Faces are identified using a tuple of nodes. Each internal face is characterized by the series of nodes that surround it in a counterclockwise direction; the one external face is identified by the series of nodes, traveling in a clockwise direction. Each value in allowed_cols should be a list of (nonnegative integer) colors that give the permissible colors for the corresponding face. If None, a face coloring with the minimum number of colors is returned.

strategystring, optional (default=’dsatur’)

A string specifying the method used to generate the initial solution. It must be one of the following:

• 'random' : Randomly orders the dual’s nodes and then applies the greedy algorithm for graph node coloring [1].

• 'welsh-powell' : Orders the dual’s nodes by decreasing degree, then applies the greedy algorithm.

• 'dsatur' : Uses the DSatur algorithm for graph node coloring on the dual [2].

• 'rlf' : Uses the recursive largest first (RLF) algorithm for graph node coloring on the dual [3].

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used.

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes in the dual to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in the dual, \(m\) is the number of edges in the dual, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes in the dual to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing faces and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). Each face (key) is a tuple that gives the sequence of nodes that surround it. The first element in c defines the external face; the remainder define the internal faces. For internal faces, the nodes are listed in a counterclockwise order; for the external face, the nodes are listed in a clockwise order. Keys in the dict are rotated so that the node with minimal label appears first.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If strategy is not among the supported options.

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If allowed_cols has a face not in the calculated embedding of G.

If allowed_cols contains a color label that is not a nonnegative integer.

If allowed_cols contains a pair of adjacent faces that have the same single allowed color.

If a face list k-coloring could not be determined (the lists of allowed colors are too restrictive).

TypeError

If allowed_cols is not a dict.

See also

gcol.node_coloring.node_coloring()

gcol.node_coloring.node_list_coloring()

face_coloring

Notes

All the above algorithms and bounds are described in detail in [1]. The c++ code used in [1] and [5] forms the basis of this library’s Python implementations.

References

[1] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[2]

Wikipedia: Greedy Coloring <https://en.wikipedia.org/wiki/Greedy_coloring>

[3]

Wikipedia: DSatur <https://en.wikipedia.org/wiki/DSatur>

[4]

Wikipedia: Recursive largest first (RLF) algorithm <https://en.wikipedia.org/wiki/Recursive_largest_first_algorithm>

[5]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.cycle_graph(4)
>>> G.add_edge(0, 2)
>>> pos = {0: (0, 0), 1: (1, 0), 2: (1, 1), 3: (0, 1)}
>>> F = {(0, 3, 2, 1): [0, 1], (0, 2, 3): [0, 2], (2, 0, 1): [0]}
>>> c = gcol.face_list_coloring(G, pos, F)
>>> print(c)
{(0, 3, 2, 1): 1, (0, 2, 3): 2, (0, 1, 2): 0}

gcol.face_coloring.face_precoloring(G, pos, precol=None, strategy='dsatur', opt_alg=None, it_limit=0, verbose=0)

Give a face coloring of a planar graph where some faces are precolored.

A face coloring is an assignment of colors to the faces of a graph’s planar embedding so that adjacent faces have different colors. In the face precoloring problem, some of the faces have already been assigned colors. Colors are defined using labels belonging to the set \(\{0,1,2,\ldots\}\). Assuming \(k\) is the largest color label used in the precoloring, the aim is to color all remaining faces using \(l\) colors, where \(l\) is minimized and \(k\leq l\).

Face colorings are only possible in planar embeddings; hence the graph G must be planar, and pos should give valid \((x,y)\) coordinates for all nodes.

In this implementation, face colorings of a graph \(G\) are determined by forming \(G\)’s dual graph, and then passing the dual to the node_precoloring() method. All parameters are therefore the same as the latter.

Parameters:

GNetworkX graph

A bridge-free, connected planar graph. Its faces will be colored.

posdict

A dictionary of positions keyed by node. All positions should be \((x,y)\) coordinates, and none of the edges in the resultant embedding should be crossing.

precolNone or dict, optional (default=None)

A dictionary, keyed by faces, that specifies the colors of the precolored faces. Faces are identified using a tuple of nodes. Each internal face is characterized by the series of nodes that surround it in a counterclockwise direction; the one external face is identified by the series of nodes, traveling in a clockwise direction.

strategystring, optional (default=’dsatur’)

A string specifying the method used to generate the initial solution. It must be one of the following:

• 'random' : Randomly orders the dual’s nodes and then applies the greedy algorithm for graph node coloring [1].

• 'welsh-powell' : Orders the dual’s nodes by decreasing degree, then applies the greedy algorithm.

• 'dsatur' : Uses the DSatur algorithm for graph node coloring on the dual [2].

• 'rlf' : Uses the recursive largest first (RLF) algorithm for graph node coloring on the dual [3].

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors. It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes in the dual to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in the dual, \(m\) is the number of edges in the dual, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes in the dual to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing faces and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). Each face (key) is a tuple that gives the sequence of nodes that surround it. The first element in c defines the external face; the remainder define the internal faces. For internal faces, the nodes are listed in a counterclockwise order; for the external face, the nodes are listed in a clockwise order.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

If G is not connected or is a singleton.

TypeError

If pos is not a dictionary.

ValueError

If strategy is not among the supported options.

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If precol contains a face that is not in the embedding of G.

If precol contains a color label that is not a nonnegative integer.

If precol contains a pair of adjacent faces assigned to the same color.

If pos has missing or invalid entries.

If pos does not specify a valid planar embedding of G.

If G is not planar or contains bridges.

TypeError

If precol is not a dict.

See also

face_coloring

dual_graph

gcol.node_coloring.node_precoloring()

Notes

As mentioned, in this implementation face colorings of a graph \(G\) are determined by forming its dual and then passing this to the node_precoloring() method. All details are therefore the same as those in the latter method, where they are documented more fully.

All the above algorithms and bounds are described in detail in [4]. The c++ code used in [4] and [5] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Greedy Coloring <https://en.wikipedia.org/wiki/Greedy_coloring>

[2]

Wikipedia: DSatur <https://en.wikipedia.org/wiki/DSatur>

[3]

Wikipedia: Recursive largest first (RLF) algorithm <https://en.wikipedia.org/wiki/Recursive_largest_first_algorithm>

[4] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[5]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> pos = nx.planar_layout(G)
>>> precol = {(0, 10, 9, 8, 1): 0, (6, 5, 4, 3, 2): 1}
>>> c = gcol.face_precoloring(G, pos, precol)
>>> print(c)
{(0, 10, 9, 8, 1): 0, (0, 19, 18, 11, 10): 1,..., (2, 6, 5, 4, 3): 1}

7.3. Node Coloring

Node coloring functions.

gcol.node_coloring.chromatic_number(G)

Return the chromatic number of the graph G.

The chromatic number of a graph \(G\) is the minimum number of colors needed to color the nodes so that no two adjacent nodes have the same color. It is commonly denoted by \(\chi(G)\). Equivalently, \(\chi(G)\) is the minimum number of independent sets needed to partition the nodes of \(G\).

Determining the chromatic number is NP-hard. The approach used here is based on the backtracking algorithm of [1]. This is exact but operates in exponential time. It is therefore only suitable for graphs that are small, or that have topologies suited to its search strategies.

Parameters:

GNetworkX graph

The chromatic number for this graph will be calculated.

Returns:

int

A nonnegative integer that gives the chromatic number of G.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

See also

node_coloring

gcol.edge_coloring.chromatic_index()

Notes

The backtracking approach used here is an implementation of the exact algorithm described in [1]. It has exponential runtime and halts only when the chromatic number has been determined. Further details of this algorithm are given in the notes section of the node_coloring() method.

The above algorithm is described in detail in [1]. The c++ code used in [1] and [2] forms the basis of this library’s Python implementations.

References

[1] (1,2,3,4)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[2]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> chi = gcol.chromatic_number(G)
>>> print("Chromatic number is", chi)
Chromatic number is 3

gcol.node_coloring.equitable_node_k_coloring(G, k, weight=None, opt_alg=None, it_limit=0, verbose=0)

Attempt to color the nodes of a graph using k colors.

This is done so that (a) all adjacent nodes have different colors, and (b) the weight of each color class is equal. If weight=None, the weight of a color class is the number of nodes assigned to that color; otherwise, it is the sum of the weights of the nodes assigned to that color.

Equivalently, this routine seeks to partition the graph’s nodes into k independent sets so that the weight of each independent set is equal.

Determining an equitable node \(k\)-coloring is NP-hard. This method first follows the steps used by the node_k_coloring() method to try and find a node \(k\)-coloring. If this is achieved, the algorithm then uses a bespoke local search operator to reduce the standard deviation in weights across the \(k\) colors.

If a node \(k\)-coloring cannot be determined by the algorithm, a ValueError exception is raised. Otherwise, a node \(k\)-coloring is returned in which the standard deviation in weights across the \(k\) color classes has been minimized. In solutions returned by this method, neighboring nodes always receive different colors; however, the coloring is not guaranteed to be equitable, even if an equitable node \(k\)-coloring exists.

Parameters:

GNetworkX graph

The nodes of this graph will be colored.

kint

The number of colors to use.

weightNone or string, optional (default=None)

If None, every node is assumed to have a weight of 1. If string, this should correspond to a defined node attribute. Node weights must be positive.

opt_algint, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors (if this is seen to be greater than \(k\)). It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when the existence of a node \(k\)-coloring has been proved or disproved.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in the modified graph, \(m\) is the number of edges, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing nodes and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots,k-1\).

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If k is not a nonnegative integer.

If a clique larger than k is observed in the graph.

If a node \(k\)-coloring could not be determined.

If a node with a non-positive weight is specified.

KeyError

If a node does not have the attribute defined by weight

See also

node_k_coloring

kempe_chain

gcol.edge_coloring.equitable_edge_k_coloring()

Notes

This method first follows the same steps as the node_k_coloring() method to try and find a node \(k\)-coloring; however, it also takes node weights into account if needed. If a node \(k\)-coloring is achieved, a bespoke local search operator (based on steepest descent) is then used to try to reduce the standard deviation in weights across the \(k\) color classes. This process involves evaluating each Kempe-chain interchange in the current solution [1] and performing the interchange that results in the largest reduction in standard deviation. This process repeats until there are no interchanges that reduce the standard deviation. Each iteration of this local search process takes \(O(n^2)\) time. Further details on this optimization method can be found in Chapter 7 of [2], or in [3].

All the above algorithms are described in detail in [2]. The c++ code used in [2] and [4] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Kempe Chain <https://en.wikipedia.org/wiki/Kempe_chain>

[2] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[3]

Lewis, R. and F. Carroll (2016) ‘Creating Seating Plans: A Practical Application’. Journal of the Operational Research Society, vol. 67(11), pp. 1353-1362.

[4]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.equitable_node_k_coloring(G, 4)
>>> P = gcol.partition(c)
>>> print(P)
[[0, 2, 9, 5, 14], [1, 3, 11, 7, 17], ..., [10, 18, 4, 12, 15]]
>>> print("Size of smallest color class =", min(len(j) for j in P))
Size of smallest color class = 5
>>> print("Size of biggest color class =", max(len(j) for j in P))
Size of biggest color class = 5
>>>
>>> #Now do similar with a node-weighted graph
>>> G = nx.Graph()
>>> G.add_node(0, weight=20)
>>> G.add_node(1, weight=9)
>>> G.add_node(2, weight=25)
>>> G.add_node(3, weight=10)
>>> G.add_edges_from([(0,2), (1,2), (3, 2)])
>>> c = gcol.equitable_node_k_coloring(G, 3, weight="weight")
>>> P = gcol.partition(c)
>>> print(P)
[[2], [0], [1, 3]]
>>>
>>> print(
...     "Weight of lightest color class =",
...     min(sum(G.nodes[v]['weight'] for v in j) for j in P)
... )
Weight of lightest color class = 19
>>>
>>> print(
...     "Weight of heaviest color class =",
...     max(sum(G.nodes[v]['weight'] for v in j) for j in P)
... )
Weight of heaviest color class = 25

gcol.node_coloring.kempe_chain(G, c, v, i, j)

Return the set of nodes in a Kempe chain.

Given a proper node coloring of graph \(G\), a Kempe chain is a connected component in the graph induced by nodes of color \(i\) and \(j\). This method returns the Kempe chain containing the prescribed node \(v\), where the color of \(v\) is \(i\). Any uncolored nodes (i.e., those whose colors are set to -1) are ignored [1].

The colors \(i\) and \(j\) alternate along any path in a Kempe chain. In a proper coloring, interchanging the colors of all nodes in a Kempe chain creates a new proper coloring. Two \(k\)-colorings of a graph are considered Kempe equivalent if one can be obtained from the other through a series of Kempe chain interchanges. It is known that, if \(k\) is larger than the degeneracy of the graph \(G\), then all \(k\)-colorings of \(G\) are Kempe equivalent [2].

Parameters:

GNetworkX graph

The graph that we want to compute a Kempe chain for.

cdict

A node coloring of G. Pairs of adjacent nodes cannot be allocated to the same color. Any uncolored nodes u should have c[u] set to -1.

vnode

The node the Kempe chain is generated from.

iint

The first color to use. This is the current color of v.

jint

The second color to use. Must be different to i.

Returns:

set

The set of nodes in the corresponding Kempe chain.

Raises:

ValueError

If i and j are equal.

If v is not assigned to color i in c.

If v is not present in G.

See also

s_chain

equitable_node_k_coloring

Notes

A Kempe chain is simply an \(s\)-chain using \(s=2\) colors. As such, this method applies the s_chain() method.

Kempe-chains can also be constructed for edge and face colorings of a graph \(G\) by using the corresponding node colorings of the line graph \(L(G)\) and dual graph \(G^*\), respectively.

References

[1]

Wikipedia: Kempe Chain <https://en.wikipedia.org/wiki/Kempe_chain>

[2]

Cranston, D. (2024) Graph Coloring Methods <https://graphcoloringmethods.com/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.node_coloring(G)
>>> C = gcol.kempe_chain(G, c, 0, 0, 1)
>>> print("Kempe chain =", C)
Kempe chain = {0, 1, 2, 4, 6, 8, 10, 17, 18, 19}

gcol.node_coloring.max_independent_set(G, weight=None, it_limit=0, verbose=0)

Attempt to identify the largest independent set of nodes in a graph.

Here, nodes can also be allocated weights if desired.

The maximum independent set in a graph \(G\) is the largest subset of nodes in which none are adjacent. The size of the largest independent in a graph \(G\) is known as the independence number of \(G\) and is often denoted by \(\alpha(G)\). Similarly, the maximum-weighted independent set in \(G\) is the subset of mutually nonadjacent nodes whose weight-total is maximized.

The problem of determining a maximum(-weighted) independent set of nodes is NP-hard. Consequently, this method makes use of a polynomial-time heuristic based on local search. It will always return an independent set but offers no guarantees as to whether this is an optimal solution. The algorithm halts once the iteration limit has been reached.

Note that the similar problem of determining the maximum(-weighted) independent set of edges is equivalent to finding a maximum(-weighted) matching in a graph. This is a polynomially solvable problem and can be solved by the Blossom algorithm.

Parameters:

GNetworkX graph

An independent set of nodes in this graph will be returned.

weightNone or string, optional (default=None)

If None, every node is assumed to have a weight of 1. If a string, this should correspond to a defined node attribute. All node weights must be positive.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Each iteration has a complexity \(O(m + n)\), where \(n\) is the number of nodes and \(m\) is the number of edges.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. In this output, the cost refers to the number of nodes not in the independent set.

Returns:

list

A list containing the nodes belonging to the independent set.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If a node with a non-positive weight is specified.

KeyError

If a node does not have the attribute defined by weight.

See also

node_k_coloring

node_coloring

Notes

This method uses the PartialCol algorithm for node \(k\)-coloring using \(k=1\). The set of nodes assigned to this color corresponds to the independent set. PartialCol is based on tabu search. Here, each iteration of PartialCol has complexity \(O(n + m)\). It also occupies \(O(n + m)\) of memory space.

The above algorithm is described in detail in [1]. The c++ code used in [1] and [2] forms the basis of this library’s Python implementations.

References

[1] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[2]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> S = gcol.max_independent_set(G, it_limit=1000)
>>> print("Independent set =", S)
Independent set = [19, 10, 2, 8, 5, 12, 14, 17]
>>>
>>> # Do similar with a node-weighted graph
>>> G = nx.Graph()
>>> G.add_node(0, weight=20)
>>> G.add_node(1, weight=9)
>>> G.add_node(2, weight=25)
>>> G.add_node(3, weight=10)
>>> G.add_edges_from([(0,2), (1,2), (3, 2)])
>>> S = gcol.max_independent_set(G, weight="weight", it_limit=1000)
>>> print("Independent set =", S)
Independent set = [0, 1, 3]

gcol.node_coloring.min_cost_k_coloring(G, k, weight=None, weights_at='nodes', it_limit=0, HEA=False, verbose=0)

Color the nodes of the graph using k colors.

This is done so that a cost function is minimized. Equivalently, this routine partitions a graph’s nodes while attempting to minimize a specific cost function.

This routine will always produce a \(k\)-coloring. However, this solution may include some clashes (that is, instances of adjacent nodes having the same color), or uncolored nodes. The aim is to minimize the number (or total weight) of these occurrences.

Determining a minimum cost solution to these problems is NP-hard. This routine employs polynomial-time heuristic algorithms based on local search.

Parameters:

GNetworkX graph

The nodes of this graph will be colored.

kint

The number of colors to use.

weightNone or string, optional (default=None)

If None, every node and edge is assumed to have a weight of 1. If string, this should correspond to a defined node or edge attribute. All node and edge weights must be positive.

weights_atstring, optional (default=’nodes’)

A string that must be one of the following:

• 'nodes' : Here, nodes can be left uncolored in a solution. If weight=None, the method seeks a \(k\)-coloring in which the number of uncolored nodes is minimized; otherwise, the method seeks a \(k\)-coloring that minimizes the sum of the weights of the uncolored nodes. Clashes are not permitted in a solution. The algorithm halts when a zero-cost solution has been determined (this corresponds to a full, proper node \(k\)-coloring), or when the iteration limit is reached.

• 'edges' : Here, clashes are permitted in a solution. If weight=None, the method seeks a \(k\)-coloring in which the number of clashes is minimized; otherwise, the method seeks a coloring that minimizes the sum of the weights of edges involved in a clash. Uncolored nodes are not permitted in a solution. The algorithm halts when a zero-cost solution has been determined (this corresponds to a full, proper node \(k\)-coloring), or when the iteration limit is reached.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes, \(m\) is the number of edges, and \(k\) is the number of colors.

HEAbool, optional (default=False)

If set to True, a hybrid evolutionary algorithm is used in conjunction with local search; otherwise, only local search is used.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process.

Returns:

dict

A dictionary with keys representing nodes and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots,k-1\). Uncolored nodes are given a value of -1.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If weights_at is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If k is not a nonnegative integer.

If a node/edge with a non-positive weight is specified.

KeyError

If weights_at=='nodes' and a node does not have the attribute defined by weight.

If weights_at=='edges' and an edge does not have the attribute defined by weight.

See also

node_k_coloring

Notes

If weights_at='edges', the TabuCol algorithm is used. This algorithm is based on tabu search and operates using \(k\) colors, allowing clashes to occur. The aim is to alter the color assignments so that the number of clashes (or the total weight of all clashing edges) is minimized. Each iteration of TabuCol has complexity \(O(nk + m)\). The process also uses \(O(nk + m)\) memory.

If weights_at='nodes', the PartialCol algorithm is used. This algorithm is also based on tabu search and operates using \(k\) colors, allowing some nodes to be left uncolored. The aim is to make alterations to the color assignments so that the number of uncolored nodes (or the total weight of the uncolored nodes) is minimized. As with TabuCol, each iteration of PartialCol has complexity \(O(nk +m)\). This process also uses \(O(nk + m)\) memory.

Further details on the local search and hybrid evolutionary algorithms, can be found in the notes section of the node_coloring() method.

All the above algorithms are described in detail in [1]. The c++ code used in [1] and [2] forms the basis of this library’s Python implementations.

References

[1] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[2]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> # Unweighted graph
>>> G = nx.dodecahedral_graph()
>>> c = gcol.min_cost_k_coloring(G, 2, weights_at="nodes", it_limit=1000)
>>> P = gcol.partition(c)
>>> print(P)
[[0, 2, 8, 18, 4, 13, 15], [1, 19, 10, 6, 12, 14, 17]]
>>> for u in G:
>>>     if c[u] == -1:
>>>         print("Node", u, "is not colored")
Node 3 is not colored
Node 5 is not colored
Node 7 is not colored
Node 9 is not colored
Node 11 is not colored
Node 16 is not colored
>>>
>>> # Edge-weighted graph (arbitrary weights)
>>> for e in G.edges():
>>>     G.add_edge(e[0], e[1], weight = abs(e[0]-e[1]))
>>> c = gcol.min_cost_k_coloring(G, 2, weights_at="edges", it_limit=1000)
>>> P = gcol.partition(c)
>>> print(P)
[[0, 2, 8, 18, 11, 7, 4, 13, 15, 16], [1, 19, 10, 3, 9, 6, 5, 12, 14, 17]]
>>> for u, v in G.edges():
>>>     if c[u] == c[v]:
>>>         print("Edge", u, v, "( cost =", G[u][v]["weight"], ") clashes")
Edge 3 19 ( cost = 16 ) clashes
Edge 5 6 ( cost = 1 ) clashes
Edge 7 8 ( cost = 1 ) clashes
Edge 9 10 ( cost = 1 ) clashes
Edge 11 18 ( cost = 7 ) clashes
Edge 15 16 ( cost = 1 ) clashes

gcol.node_coloring.node_coloring(G, strategy='dsatur', opt_alg=None, it_limit=0, verbose=0)

Return a coloring of a graph’s nodes.

A node coloring of a graph is an assignment of colors to nodes so that adjacent nodes have different colors. The aim is to use as few colors as possible. A set of nodes assigned to the same color represents an independent set; hence the equivalent aim is to partition the graph’s nodes into a minimum number of independent sets.

The smallest number of colors needed to color the nodes of a graph \(G\) is known as the graph’s chromatic number, denoted by \(\chi(G)\). Equivalently, \(\chi(G)\) is the minimum number of independent sets needed to partition the nodes of \(G\).

Determining a node coloring that minimizes the number of colors is an NP-hard problem. This method therefore includes options for using an exact exponential-time algorithm (based on backtracking), or a choice of four polynomial-time heuristic algorithms (based on local search). The exact algorithm is generally only suitable for graphs that are small, or that have topologies suited to its search strategies. In all other cases, the local search algorithms are more appropriate.

Parameters:

GNetworkX graph

The nodes of this graph will be colored.

strategystring, optional (default=’dsatur’)

A string specifying the method used to generate an initial solution. It must be one of the following:

• 'random' : Randomly orders the graph’s nodes and then applies the greedy algorithm for graph node coloring [1].

• 'welsh-powell' : Orders the graph’s nodes by decreasing degree, then applies the greedy algorithm.

• 'dsatur' : Uses the DSatur algorithm for graph node coloring [2].

• 'rlf' : Uses the recursive largest first (RLF) algorithm for graph node coloring [3].

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors. It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in the graph, \(m\) is the number of edges, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given below.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing nodes and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). The number of colors being used in a solution c is therefore max(c.values()) + 1.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If strategy is not among the supported options.

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

See also

chromatic_number

node_k_coloring

gcol.edge_coloring.edge_coloring()

Notes

Given a graph \(G=(V,E)\) with \(n\) nodes and \(m\) edges, the greedy algorithm for node coloring operates in \(O(n + m)\) time.

The random strategy operates by first randomly permuting the nodes (an \(O(n)\) operation) before applying the greedy algorithm. It is guaranteed to produce a solution with \(k \leq \Delta(G) + 1\) colors, where \(\Delta(G)\) is the highest node degree in the graph \(G\).

The welsh-powell strategy operates by sorting the nodes by decreasing degree (an \(O(n \lg n)\) operation), and then applies the greedy algorithm. Its overall complexity is therefore \(O(n \lg n + m)\). Assuming that the nodes are labelled \(v_1, v_2,\ldots,v_n\) so that \(\deg(v_1) \geq \deg(v_2) \geq \ldots \geq \deg(v_n)\), this method is guaranteed to produce a solution with \(k \leq\max_{i=1,\ldots,n} \min(\deg(v_i)+1, i)\) colors. This bound is an improvement on \(\Delta(G) + 1\).

The dsatur and rlf strategies are exact for bipartite, cycle, and wheel graphs (that is, solutions with the minimum number of colors are guaranteed). The implementation of dsatur uses a priority queue and has a complexity of \(O(n \lg n + m \lg m)\). The rlf implementation has a complexity of \(O(nm)\). In general, the rlf strategy yields the best solutions of the four strategies, though it is computationally more expensive. If expense is an issue, then dsatur is a cheaper alternative that also offers high-quality solutions in most cases. See [2], [3], and [4] for further information.

If an optimization algorithm is used, further efforts are made to reduce the number of colors. The backtracking approach (opt_alg=1) is an implementation of the exact algorithm described in [4]. It has exponential runtime and halts only when an optimum solution has been found. At the start of execution, a large clique \(C\subseteq V\) is identified using the NetworkX function max_clique(G) and the nodes of \(C\) are each assigned to a different color. The main backtracking algorithm is then executed and only halts only when a solution using \(|C|\) colors has been identified, or when the algorithm has backtracked to the root of the search tree. In both cases the returned solution will be optimal (that is, will be using \(\chi(G)\) colors).

If local search is used (opt_alg is set to 2, 3, 4, or 5), the algorithm removes a color class and uses the chosen local search routine to seek a proper coloring using the remaining colors. This process repeats until a solution using \(|C|\) colors has been identified (as above), or until the iteration limit (defined by it_limit) is reached. Fewer colors (but longer run times) occur with larger iteration limits.

If opt_alg=2, the TabuCol algorithm is used. This algorithm is based on tabu search and operates by fixing the number of colors but allowing clashes to occur (a clash is the occurrence of two adjacent nodes having the same color). The aim is to alter the color assignments so that the number of clashes is reduced to zero. Each iteration of TabuCol has a complexity of \(O(nk + m)\), where \(k\) is the number of colors currently being used. The process also uses \(O(nk + m)\) memory.

If opt_alg=3, the PartialCol algorithm is used. This algorithm is also based on tabu search and operates by fixing the number of colors but allowing some nodes to be left uncolored. The aim is to make alterations to the color assignments so that no uncolored nodes remain. As with TabuCol, each iteration of PartialCol has complexity \(O(nk +m)\) and uses \(O(nk + m)\) memory.

If opt_alg is set to 4 or 5, a hybrid evolutionary algorithm (HEA) is used [5]. This method maintains a small population of \(k\)-colored solutions that is evolved using selection, recombination, local search and replacement. Specifically, in each HEA cycle, two parent solutions are selected from the population, and these are used in conjunction with a specialized recombination operator to produce a new offspring solution. Local search is this applied to the offspring for a fixed number of iterations, and the resultant solution is inserted back into the population, replacing its weaker parent. If opt_alg=4, TabuCol is used as the local search operator; if opt_alg=5, PartialCol is used. Each iteration of the HEA has complexity \(O(nk+m)\), as above. Note that the HEA is often able to produce solutions using fewer colors compared to when using opt_alg=2 or opt_alg=3; however, larger iteration limits will usually be needed to see these improvements.

As stated above, if verbose is set to a positive integer, output is produced during the execution of the chosen optimization algorithm. If the backtracking algorithm is being used, the stated iterations refer to the number of calls to its recursive function. Otherwise, iterations refer to the \(O(nk +m)\) processes mentioned above. If no optimization is performed, no output is produced.

All the above algorithms and bounds are described in detail in [4]. The c++ code used in [4] and [6] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: Greedy Coloring <https://en.wikipedia.org/wiki/Greedy_coloring>

[2] (1,2)

Wikipedia: DSatur <https://en.wikipedia.org/wiki/DSatur>

[3] (1,2)

Wikipedia: Recursive largest first (RLF) algorithm <https://en.wikipedia.org/wiki/Recursive_largest_first_algorithm>

[4] (1,2,3,4)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[5]

Galinier, P. and J. Hao (1999). Hybrid Evolutionary Algorithms for Graph Coloring. Journal of Combinatorial Optimization 3, 379–397.

[6]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.node_coloring(G)
>>> print("Coloring is", c)
Coloring is {0: 0, 1: 1, 19: 1, 10: 1, 2: 0, ..., 17: 1}
>>> print("Number of colors =", max(c.values()) + 1)
Number of colors = 3
>>>
>>> print("Partition view =", gcol.partition(c))
Partition view = [[0, 2, 8, 18, 4, 13, 15], ..., [3, 9, 11, 7, 5, 16]]
>>>
>>> # Example with a larger graph and different parameters
>>> G = nx.gnp_random_graph(50, 0.2, seed=1)
>>> c = gcol.node_coloring(G, strategy="dsatur", opt_alg=2, it_limit=1000)
>>> print("Coloring is", c)
Coloring is {18: 0, 31: 2, 2: 4, 20: 1, 10: 3, ..., 27: 2}
>>>
>>> print("Number of colors =", max(c.values()) + 1)
Number of colors = 5

gcol.node_coloring.node_k_coloring(G, k, opt_alg=None, it_limit=0, verbose=0)

Attempt to color the nodes of a graph using k colors.

This is done so that adjacent nodes have different colors. A set of nodes assigned to the same color corresponds to an independent set; hence the equivalent aim is to partition the graph’s nodes into k independent sets.

Determining whether a node \(k\)-coloring exists for \(G\) is NP-complete. This method therefore includes options for using an exact exponential-time algorithm (based on backtracking), or a choice of four polynomial-time heuristic algorithms (based on local search). The exact algorithm is generally only suitable for larger values of \(k\), for graphs that are small, or graphs that have topologies suited to its search strategies. In all other cases, the local search algorithms are more appropriate.

If a node \(k\)-coloring cannot be determined by the algorithm, a ValueError exception is raised. Otherwise, a node \(k\)-coloring is returned.

Parameters:

GNetworkX graph

The nodes of this graph will be colored.

kint

The number of colors to use.

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors (if this is seen to be greater than \(k\)). It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when the existence of a node \(k\)-coloring has been proved or disproved.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in the graph, \(m\) is the number of edges, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing edges and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots,k-1\).

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If k is not a nonnegative integer.

If a clique larger than k is observed in the graph.

If a node \(k\)-coloring could not be determined.

See also

node_coloring

equitable_node_k_coloring

gcol.edge_coloring.edge_k_coloring()

Notes

This method begins by coloring the nodes in the order determined by the DSatur algorithm [1]. During this process, each node is assigned to the feasible color class \(j\) (where \(0 \leq j \leq k\)) with the fewest nodes. This encourages an equitable spread of nodes across the \(k\) colors. This process has a complexity of \(O((n \lg n) + (nk) + (m \lg m)\). If a node \(k\)-coloring cannot be achieved in this way, further optimization is carried out, if desired. These optimization routines are the same as those used by the node_coloring() method. They also halt immediately once a node \(k\)-coloring has been achieved.

All the above algorithms are described in detail in [2]. The c++ code used in [2] and [3] forms the basis of this library’s Python implementations.

References

[1]

Wikipedia: DSatur <https://en.wikipedia.org/wiki/DSatur>

[2] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[3]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.node_k_coloring(G, 4)
>>> print(c)
{0: 0, 1: 1, 19: 2, 10: 3, 2: 0, ..., 15: 3}
>>>
>>> c = gcol.node_k_coloring(G, 3)
>>> print(c)
{0: 0, 1: 1, 19: 2, 10: 1, 2: 0, ..., 12: 1}

gcol.node_coloring.node_list_coloring(G, allowed_cols=None, strategy='dsatur', opt_alg=None, it_limit=0, verbose=0)

Return a solution to the node list coloring problem on G.

In the list coloring problem, each node \(v\) is associated with a list of allowed colors \(L(v)\). A solution is an assignment of colors to all nodes so that adjacent nodes have different colors, and the color of each node \(v\) belongs to the list \(L(v)\).

The list coloring problem is NP-hard. This method therefore includes options for using an exponential-time exact algorithm (based on backtracking), or a choice of four polynomial-time heuristic algorithms (based on local search). The exact algorithm is generally only suitable for graphs that are small, or that have topologies suited to its search strategies. In all other cases, the local search algorithms are more appropriate.

In this implementation, colors are defined using labels belonging to \(\{0,1,2,\ldots\}\). Assuming \(k\) is the largest color label appearing across all lists \(L(v)\), the aim is to find a solution using at most \(k\) colors. If this cannot be done, an exception is raised (see below).

Here, solutions are found by adding a clique of \(k\) dummy nodes, one for each color. Additional edges are then added between a node \(v\) and a dummy node \(i\) whenever \(i\) does not occur in \(L(v)\). The modified graph is then passed to the node_k_coloring() method. All parameters are therefore the same as the latter. This modification process is described in more detail in Chapter 6 of [1].

Parameters:

GNetworkX graph

The nodes of this graph will be colored.

allowed_colsNone or dict, optional (default=None)

A dictionary, keyed by the nodes of G. allowed_cols[v] should be a list of nonnegative integers that defines the permissible colors for node v. If None, a node coloring with the minimum number of colors is returned.

strategystring, optional (default=’dsatur’)

A string specifying the method used to generate the initial solution. It must be one of the following:

• 'random' : Randomly orders the modified graph’s nodes and then applies the greedy algorithm for graph node coloring [2].

• 'welsh-powell' : Orders the modified graphs nodes by decreasing degree, then applies the greedy algorithm.

• 'dsatur' : Uses the DSatur algorithm for graph node coloring on the modified graph [3].

• 'rlf' : Uses the recursive largest first (RLF) algorithm for graph node coloring on the modified graph [4].

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used.

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in the modified graph, \(m\) is the number of edges, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing nodes and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). If c[v]==j then j is an element of allowed_cols[v].

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If strategy is not among the supported options.

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If G contains a node with the name 'dummy'.

If allowed_cols has a node not in G, or is missing an entry for a node in G.

If allowed_cols contains a color label that is not a nonnegative integer.

If allowed_cols contains a list that is empty.

If allowed_cols contains a pair of adjacent nodes that have the same single allowed color.

If a node list k-coloring could not be determined (the lists of allowed colors are too restrictive).

TypeError

If allowed_cols is not a dict.

See also

node_coloring

gcol.edge_coloring.edge_precoloring()

Notes

As mentioned, in this implementation, solutions are formed by passing a modified version of the graph to the node_k_coloring() method. Details are therefore the same as those in the latter.

All the above algorithms and bounds are described in detail in [1]. The c++ code used in [1] and [5] forms the basis of this library’s Python implementations.

References

[1] (1,2)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[2]

Wikipedia: Greedy Coloring <https://en.wikipedia.org/wiki/Greedy_coloring>

[3]

Wikipedia: DSatur <https://en.wikipedia.org/wiki/DSatur>

[4]

Wikipedia: Recursive largest first (RLF) algorithm <https://en.wikipedia.org/wiki/Recursive_largest_first_algorithm>

[5]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.cycle_graph(4)
>>> V = {0: [0, 1], 1: [1], 2: [0, 3], 3: [0, 1, 3]}
>>> c = gcol.node_list_coloring(G, V)
>>> print(c)
{1: 1, 0: 0, 2: 3, 3: 1}

gcol.node_coloring.node_precoloring(G, precol=None, strategy='dsatur', opt_alg=None, it_limit=0, verbose=0)

Return a coloring of a graph’s nodes where some nodes are precolored.

A node coloring of a graph is an assignment of colors to nodes so that adjacent nodes have different colors. In the node precoloring problem, some of the nodes have already been assigned colors. Colors are defined using labels belonging to the set \(\{0,1,2,\ldots\}\). Assuming \(k\) is the largest color label used in the precoloring, the aim is to color all remaining nodes using \(l\) colors, where \(l\) is minimized and \(k\leq l\). The node precoloring problem can be used to model the Latin square completion problem and Sudoku puzzles [1].

The node precoloring problem is NP-hard. This method therefore includes options for using an exponential-time exact algorithm (based on backtracking), or a choice of four polynomial-time heuristic algorithms (based on local search). The exact algorithm is generally only suitable for graphs that are small, or that have topologies suited to its search strategies. In all other cases, the local search algorithms are more appropriate.

In this implementation, solutions are found by taking all nodes pre-allocated to the same color and merging them into a single super-node. Edges are then added between all pairs of super-nodes, and the modified graph is passed to the node_coloring() method. All parameters are therefore the same as the latter. This modification process is described in more detail in Chapter 6 of [1].

Parameters:

GNetworkX graph

The nodes of this graph will be colored.

precolNone or dict, optional (default=None)

A dictionary that specifies the (nonnegative integer) colors of any precolored nodes.

strategystring, optional (default=’dsatur’)

A string specifying the method used to generate the initial solution. It must be one of the following:

• 'random' : Randomly orders the modified graph’s nodes and then applies the greedy algorithm for graph node coloring [2].

• 'welsh-powell' : Orders the modified graphs nodes by decreasing degree, then applies the greedy algorithm.

• 'dsatur' : Uses the DSatur algorithm for graph node coloring on the modified graph [3].

• 'rlf' : Uses the recursive largest first (RLF) algorithm for graph node coloring on the modified graph [4].

opt_algNone or int, optional (default=None)

An integer specifying the optimization method that will be used to try to reduce the number of colors. It must be one of the following

• 1 : An exact, exponential-time algorithm based on backtracking. The algorithm halts only when an optimal solution has been found.

• 2 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing adjacent nodes to have the same color. Each iteration has a complexity \(O(m + kn)\), where \(n\) is the number of nodes in the modified graph, \(m\) is the number of edges, and \(k\) is the number of colors in the current solution.

• 3 : A local search algorithm that seeks to reduce the number of colors by temporarily allowing nodes to be uncolored. Each iteration has a complexity \(O(m + kn)\), as above.

• 4 : A hybrid evolutionary algorithm (HEA) that evolves a small population of solutions. During execution, when each new solution is created, the local search method used in Option 2 above is applied for a fixed number of iterations. Each iteration of this HEA therefore has a complexity of \(O(m + kn)\), as above.

• 5 : A hybrid evolutionary algorithm is applied (as above), using the local search method from Option 3.

• None : No optimization is performed.

Further details of these algorithms are given in the notes section of the node_coloring() method.

it_limitint, optional (default=0)

Number of iterations of the local search procedure. Not applicable when using opt_alg=1.

verboseint, optional (default=0)

If set to a positive value, information is output during the optimization process. The higher the value, the more information.

Returns:

dict

A dictionary with keys representing nodes and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). If precol[v]==j then c[v]==j.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If strategy is not among the supported options.

If opt_alg is not among the supported options.

If it_limit is not a nonnegative integer.

If verbose is not a nonnegative integer.

If G contains a node with the name 'super'.

If precol contains a node that is not in G.

If precol contains a color label that is not a nonnegative integer.

If precol contains a pair of adjacent nodes assigned to the same color.

TypeError

If precol is not a dict.

See also

node_coloring

gcol.edge_coloring.edge_precoloring()

Notes

As mentioned, in this implementation, solutions are formed by passing a modified version of the graph to node_coloring() method. All details are therefore the same as those in the latter, where they are documented.

All the above algorithms and bounds are described in detail in [1]. The c++ code used in [1] and [5] forms the basis of this library’s Python implementations.

References

[1] (1,2,3)

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. <https://link.springer.com/book/10.1007/978-3-030-81054-2>.

[2]

Wikipedia: Greedy Coloring <https://en.wikipedia.org/wiki/Greedy_coloring>

[3]

Wikipedia: DSatur <https://en.wikipedia.org/wiki/DSatur>

[4]

Wikipedia: Recursive largest first (RLF) algorithm <https://en.wikipedia.org/wiki/Recursive_largest_first_algorithm>

[5]

Lewis, R: Graph Colouring Algorithm User Guide <https://rhydlewis.eu/gcol/>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> p = {0:1, 8:0, 9:1}
>>> c = gcol.node_precoloring(G, precol=p)
>>> print("Coloring is", c)
Coloring is {0: 1, 9: 1, 1: 2, 8: 0, 19: 2, ..., 16: 0}
>>>
>>> p = {i:i for i in range(5)}
>>> c = gcol.node_precoloring(
...     G, precol=p, strategy="dsatur", opt_alg=2, it_limit=1000
... )
>>> print(c)
{0: 0, 4: 4, 1: 1, 2: 2, 3: 3, ..., 12: 2}

gcol.node_coloring.s_chain(G, c, v, L)

Return the set of nodes in an \(s\)-chain.

An \(s\)-chain is a generalization of a Kempe chain that allows more than two colors. Given a proper node coloring of a graph \(G=(V,E)\), an \(s\)-chain is defined by a prescribed node \(v\in V\) and sequence of unique colors \(j_0,j_1,\ldots,j_{s-1}\), where the current color of \(v\) is \(j_0\). The result is the set of nodes that are reachable from \(v\) in the digraph \(G'=(V',A)\) in which:

• \(V' = \{u \; : \; u \in V \; \wedge \; c(u) \in \{j_0,j_1, \ldots,j_{s-1}\}\}\), and

• \(A = \{(u,w) \; : \; \{u,w\} \in E \; \wedge \; c(u) = j_i \; \wedge \; c(w) = j_{(i+1) \bmod s} \}\),

where \(c(u)\) gives the color of a node \(u\).

In a proper coloring, interchanging the colors of all nodes in an \(s\)-chain via the following mapping

• \(j_i \leftarrow j_{(i+1) \bmod s}\)

results in a new proper coloring [1].

In this method, uncolored nodes are ignored.

Parameters:

GNetworkX graph

The graph that we want to compute an \(s\)-chain for.

cdict

A node coloring of G, where c[u] gives the color of node u. Pairs of adjacent nodes cannot be allocated to the same color. Any uncolored nodes u should have c[u] set to -1.

vnode

The node the \(s\)-chain is to be generated from.

Llist

A sequence of unique colors, represented by integers. The first color in L should be the current color of v.

Returns:

set

The set of nodes in the corresponding \(s\)-chain.

Raises:

NotImplementedError

If G is a directed graph or a multigraph.

If G contains any self-loops.

ValueError

If v is not present in G.

If G has a node that is not present in c.

If c contains a pair of adjacent nodes assigned to the same color.

If L is not a list or tuple, has a length of less than two, or contains repeated values.

If the first value of L is not equal to c[v]

If L contains values that are not in the set \(\{0,1,2,\ldots\}\).

See also

kempe_chain

equitable_node_k_coloring

gcol.face_coloring.dual_graph()

Notes

This method uses a modified version of breadth-first search and operates in \(O(m)\) time.

\(s\)-chains can also be constructed for edge and face colorings of a graph \(G\) by using the corresponding node colorings of the line graph \(L(G)\) and dual graph \(G^*\), respectively.

References

[1]

Morgenstern, C. and H. Shapiro (1990), Coloration Neighborhood Structures for General Graphs <https://dl.acm.org/doi/pdf/10.5555/320176.320202>

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.node_coloring(G)
>>> C = gcol.s_chain(G, c, 0, [0, 1, 2])
>>> print("s-chain =", C)
s-chain = {0, 1, 2, ..., 19}
>>> C = gcol.s_chain(G, c, 0, [0, 2, 1])
>>> print("s-chain =", C)
s-chain = {0}

7.4. Output

Output functions.

gcol.output.coloring_layout(G, c)

Arrange the nodes of the graph in a circle.

Nodes of the same color are put next to each other. This method is designed to be used with the pos argument in the drawing functions of NetworkX (see example below).

Parameters:

GNetworkX graph

The graph we want to visualize.

cdict

A dictionary with keys representing nodes and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). Nodes with negative values are ignored.

Returns:

posdict

A dictionary of positions keyed by node.

See also

get_node_colors

multipartite_layout

Examples

>>> import networkx as nx
>>> import matplotlib.pyplot as plt
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.node_coloring(G)
>>> nx.draw_networkx(
...     G, pos=gcol.coloring_layout(G, c),
...     node_color=gcol.get_node_colors(G, c)
... )
>>> plt.show()

gcol.output.draw_face_coloring(c, pos, external=False, palette=None)

Draw the face coloring defined by c and pos.

The RGB color of each face is determined by its color label in c and the chosen palette. If a face is marked as uncolored (i.e., assigned a value of -1) it is painted white.

Parameters:

cdict

A dictionary where keys represent the sequence of nodes occurring in each face (polygon), and values represent the face’s color. Colors are identified by the integers \(0,1,2,\ldots\). The first element in c defines the external face of the embedding; the remaining elements define the internal faces.

posdict

A dict specifying the (x,y) coordinates of each node in the embedding.

externalbool, optional (default=False)

If set to True, the background (corresponding to the external face of the embedding) is also colored, else it is left blank.

paletteNone or dict, optional (default=None)

A dictionary that maps the integers \(-1,0,1,\ldots\) to RGB values. The in-built options are as follows

• gcol.tableau : A collection of 21 colors provided by Tableau.

• gcol.colorful : A collection of 57 bright colors that are chosen to contrast each other as much as possible.

• gcol.colorblind : A collection of 11 colors, provided by Tableau, that are intended to help colorblind users.

• If None, then gcol.tableau is used.

Returns:

None

Raises:

ValueError

If c uses more colors than available in the palette.

See also

get_set_colors

get_edge_colors

get_node_colors

Notes

User generated palettes can also be passed into this method. In such cases it is good practice to map the value -1 to the color white. Descriptions on how to specify valid colors can be found at [1].

References

[1]

Matplotlib: Specifying colors <https://matplotlib.org/stable/users/explain/colors/colors.html>

Examples

>>> import networkx as nx
>>> import gcol
>>> import matplotlib.pyplot as plt
>>>
>>> # Construct a small planar graph with defined node positions
>>> G = nx.Graph()
>>> G.add_node(0, pos=(0,0))
>>> G.add_node(1, pos=(1,0))
>>> G.add_node(2, pos=(0,1))
>>> G.add_node(3, pos=(1,1))
>>> G.add_edges_from([(0,1),(0,2),(0,3),(1,3),(2,3)])
>>>
>>> # Color the faces of the embedding and draw to the screen
>>> pos = nx.get_node_attributes(G, "pos")
>>> c = face_coloring(G, pos)
>>> draw_face_coloring(c, pos)
>>> plt.show()

gcol.output.get_edge_colors(G, c, palette=None)

Generate an RGB color for each edge in the graph G.

The RGB color of an edge is determined by its color label in c and the chosen palette. This method is designed to be used with the edge_color argument in the drawing functions of NetworkX (see example below). If an edge is marked as uncolored (i.e., assigned a value of -1 , or not present in c), it is painted light grey.

Parameters:

GNetworkX graph

The graph we want to visualize.

cdict

A dictionary with keys representing edges and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\).

paletteNone or dict, optional (default=None)

A dictionary that maps the integers \(-1,0,1,\ldots\) to RGB values. The in-built options are as follows

• gcol.tableau : A collection of 21 colors provided by Tableau.

• gcol.colorful : A collection of 57 bright colors that are chosen to contrast each other as much as possible.

• gcol.colorblind : A collection of 11 colors, provided by Tableau, that are intended to help colorblind users.

• If None, then gcol.tableau is used.

Returns:

dict

list

A sequence of RGB colors in edge order.

Raises:

ValueError

If c uses more colors than available in the palette.

See also

get_set_colors

get_node_colors

Notes

User generated palettes can also be passed into this method. Descriptions on how to specify valid colors can be found at [1].

References

[1]

Matplotlib: Specifying colors <https://matplotlib.org/stable/users/explain/colors/colors.html>

Examples

>>> import networkx as nx
>>> import matplotlib.pyplot as plt
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.edge_coloring(G)
>>> nx.draw_networkx(
...    G, pos=nx.spring_layout(G), edge_color=gcol.get_edge_colors(G, c)
... )
>>> plt.show()

gcol.output.get_node_colors(G, c, palette=None)

Generate an RGB color for each node in the graph G.

The RGB color of a node is determined by its color label in c and the chosen palette. This method is designed to be used with the node_color argument in the drawing functions of NetworkX (see example below). If a node is marked as uncolored (i.e., assigned a value of -1, or is not present in c), it is painted white.

Parameters:

GNetworkX graph

The graph we want to visualize.

cdict

A dictionary with keys representing nodes and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\).

paletteNone or dict, optional (default=None)

A dictionary that maps the integers \(-1,0,1,\ldots\) to RGB values. The in-built options are as follows

• gcol.tableau : A collection of 21 colors provided by Tableau.

• gcol.colorful : A collection of 57 bright colors that are chosen to contrast each other as much as possible.

• gcol.colorblind : A collection of 11 colors, provided by Tableau, that are intended to help colorblind users.

• If None, then gcol.tableau is used.

Returns:

list

A sequence of RGB colors in node order.

Raises:

ValueError

If c uses more colors than available in the palette.

See also

get_set_colors

get_edge_colors

Notes

User generated palettes can also be passed into this method. In such cases it is good practice to map the value -1 to the color white. Descriptions on how to specify valid colors can be found at [1].

References

[1]

Matplotlib: Specifying colors <https://matplotlib.org/stable/users/explain/colors/colors.html>

Examples

>>> import networkx as nx
>>> import matplotlib.pyplot as plt
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.node_coloring(G)
>>> nx.draw_networkx(
...     G, pos=nx.spring_layout(G), node_color=gcol.get_node_colors(G, c)
... )
>>> plt.show()

gcol.output.get_set_colors(G, S, S_color='yellow', other_color='grey')

Generate an RGB color for each node based on if it is in S.

By default, nodes in S are painted yellow and all others are painted grey. This method is designed to be used with the node_color argument in the drawing functions of NetworkX (see example below).

Parameters:

GNetworkX graph

The graph we want to visualize.

Slist or set

A subset of G’s nodes.

S_colorcolor, optional (default=’yellow’)

Desired color of the nodes in S. Other options include 'blue', 'cyan', 'green', 'black', 'magenta', 'red', 'white', and 'yellow'.

other_colorcolor, optional (default=’grey’)

Desired color of the nodes not in S.

Returns:

list

A sequence of RGB colors, in node order

See also

get_node_colors

get_edge_colors

Notes

Descriptions on how to specify valid colors can be found at [1].

References

[1]

Matplotlib: Specifying colors <https://matplotlib.org/stable/users/explain/colors/colors.html>

Examples

>>> import networkx as nx
>>> import matplotlib.pyplot as plt
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> S = gcol.max_independent_set(G, it_limit=1000)
>>> nx.draw_networkx(
...     G, pos=nx.spring_layout(G), node_color=gcol.get_set_colors(G, S)
... )
>>> plt.show()

gcol.output.multipartite_layout(G, c)

Arrange the nodes of the graph into columns.

Nodes of the same color are put in the same column. This method is used with the pos argument in the drawing functions of NetworkX (see example below).

Parameters:

GNetworkX graph

The graph we want to visualize.

cdict

A dictionary with keys representing nodes and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\). Nodes with negative color labels are ignored.

Returns:

posdict

A dictionary of positions keyed by node.

See also

get_node_colors

coloring_layout

Examples

>>> import networkx as nx
>>> import matplotlib.pyplot as plt
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.node_coloring(G)
>>> nx.draw_networkx(
...     G, pos=gcol.multipartite_layout(G, c),
...     node_color=gcol.get_node_colors(G, c)
... )
>>> plt.show()

gcol.output.partition(c)

Convert a coloring into its equivalent partition-based representation.

Negative color labels (signifying uncolored nodes/edges) are ignored.

Parameters:

cdict

A dictionary with keys representing nodes or edges and values representing their colors. Colors are identified by the integers \(0,1,2,\ldots\).

Returns:

list

A list in which each element is a list containing the nodes/edges assigned to a particular color.

Notes

If all nodes in a color class are named by numerical values, the nodes are sorted in ascending order. Otherwise, the nodes of each color class are sorted by their string equivalents.

Examples

>>> import networkx as nx
>>> import gcol
>>>
>>> G = nx.dodecahedral_graph()
>>> c = gcol.node_coloring(G)
>>> print(gcol.partition(c))
[[0, 2, 8, 18, 4, 13, 15], ..., [3, 9, 11, 7, 5, 16]]
>>>
>>> c = gcol.edge_coloring(G)
>>> print(gcol.partition(c))
[[(11, 12), (18, 19), (16, 17), ..., (2, 6), (4, 5)]]