bug report in greedy coloring

[chakpongchung]

I found this in https://networkx.github.io/documentation/latest/reference/algorithms/generated/networkx.algorithms.coloring.greedy_color.html#networkx.algorithms.coloring.greedy_color :

"Attempts to color a graph using as few colors as possible, where no neighbours of a node can have same color as the node itself. "

import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
edge_list = [[7, 6], [6, 5], [6, 4], [6, 3], [
    5, 4], [5, 3], [4, 2], [3, 1], [1, 2], [2, 0]]
print('edge_list: ', edge_list)
edge_list.reverse()
print('edge_list: ', edge_list)
edge_list = [edge[::-1]for edge in edge_list]
print('edge_list: ', edge_list)

G.add_edges_from(edge_list)

coloring = nx.coloring.greedy_color(G, strategy='largest_first')
# coloring = nx.coloring.greedy_color(G, strategy='independent_set')

print('coloring: ', coloring)
max_value = max(coloring.values())  # maximum value

print('nums of color: ', len(frozenset(coloring.values())))

nx.draw_networkx(G)

plt.axis("off")
# plt.show()
plt.savefig("tc.png")

the result for the coloring shows:

coloring:  {6: 0, 2: 0, 3: 1, 4: 1, 5: 1, 1: 0, 0: 1, 7: 0}

which shows node 3 and node 5 shares the same color. This is not correct since node 3 and node 5 are neighbors.

However, this returns the correct result:

coloring = nx.coloring.greedy_color(G, strategy='independent_set')

[dschult]

Did you mean for this to be a directed graph? Looking at the code, I think that is what is giving the troublesome result. While the code does not explicitly restrict to undirected graphs, it looks like it doesn't handle directed graphs the way you are expecting.

[chakpongchung]

@dschult I expect the coloring algorithm to be applicable to general graph, including the special case: DAG.

[dschult]

Why do you expect it to work for a directed graph? What definition of coloring do you want to use? These algorithms don't work with directed graphs. You can of course, convert to undirected using G.to_undirected() and then it should work fine.

[chakpongchung]

I am using it for vertex coloring.

I understand that Graph Coloring is usually for undirected graph. Then why these implementation allow taking directed graph as input? Is it appropriate to convert any directed graph input to undirected version inside these implementation? I do not see the motivation yet we chose implementation treating directed graph separately.

[dschult]

If you are using coloring with a desire that connected nodes not have the same color, then you are using the definition for undirected coloring and it is appropriate to convert the DiGraph to a Graph. If copying the DiGraph is too slow, you can use DiGraph.to_undirected(as_view=True) which doesn't copy the graph, but results in a read-only view of the DiGraph using a Graph interface (either direction of an edge in the DiGraph implies an edge in the Graph).