search

rostam / GTea

Online version of GraphTea
http://www.graphtheorysoftware.com/
4 stars 4 forks source link

Chromatic number is never 1 #5

Closed HKH515 closed 7 years ago

HKH515 commented 7 years ago

Given a disconnected graph, or just a single vertex graph, it reports the chromatic number as 2, should be 1.

rostam commented 7 years ago

I think this error happens only when the graph does not have any edge. So I compute this case separately and return 1: https://github.com/rostam/GTea/commit/ec455b5f062d17ad4ef8abcfe3b6e49eedec99a7

Is there any other example that does not work?

HKH515 commented 7 years ago

no i think this only happens when there are no edge, if i find any more I'll let you know

rostam commented 7 years ago

Just in case, the vertex coloring is NP-Complete as you may know. So, this algorithm would take long for large graphs. If you need an estimation of chromatic number and coloring for large graphs, we can simply implement a heuristic.

HKH515 commented 7 years ago

One solution would to cache results when running algorithms, and when a graph is drawn again we can check for isomorphisms for the computation results, but that is quite a drastic change to the codebase.

rostam commented 7 years ago

Checking graph isomorphism is also a hard problem. My suggestion is to use heuristics. They have convincing results in a reasonable time. The implementation is also very easy: https://en.wikipedia.org/wiki/Greedy_coloring

HKH515 commented 7 years ago

That sounds like a good way to do it, but it does not always give correct results, right?

rostam commented 7 years ago

It always gives a valid coloring which means no connected vertices have the same color. However, the number of colors can be higher than the correct chromatic number.

I implemented a greedy coloring here: https://github.com/rostam/GTea/blob/master/src/main/java/graphtea/extensions/reports/GreedyColoring.java

Watch the following video which shows that the results are convincing: https://www.dropbox.com/s/ib7wnsl6ykt8j6s/coloring.ogv?dl=0 or https://www.dropbox.com/s/20koe0twoofxfcn/coloring.mp4?dl=0

I also add a small button which shows that coloring on the graph. You can see what I mean in that video.

HKH515 commented 7 years ago

Looks good, but yeah what I meant by not giving always a correct results is that it doesn't always give the lowest possible number of colors, this is just something that i noticed and wanted to bring up since we are implementing directed/undirected drawing in GTea.

rostam commented 7 years ago

Yes. It is great that you mentioned it. I think we can close this issue. What do you think?

HKH515 commented 7 years ago

yeah