Bilateral chart (undirected)
I am taking input for example. 4 1 3 1 2 2 4
The first line is the number of nodes followed by edges. I have to try to color the graph, and if I cannot, I need to indicate the cycle on the graph that is causing the error.
So far this is fine, except for one of the graphs containing 1,000,000 nodes. Every time I try to use it I get an error although I simplified it and increased the max eclipse heap size to 1024m.
I am not asking for code, just asking if I am doing something clearly wrong in order to keep getting errors.
Perhaps you could optimize the loop detection algorithm. This might help you: http://en.wikipedia.org/wiki/Cycle_detection
Also, a million nodes plus an adjacency matrix can also be too complex to handle right away, so there might be a way to just load parts of the graph in one go.
source to share
If it is a bipartite graph, you can always color it with only two colors (for example, the first section is white and the second black).
Usually, when you think about coloring a chart, it should indicate the number of colors. You can always color the graph by assigning a different color to each node. Another example: Only four colors are required for planar graphs. However, for most graphs, the [chromatic number] of the graph is [NP].
[NP] http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems
[chromatic number] http://en.wikipedia.org/wiki/Graph_coloring
source to share