brrcrites / graph-coloring Goto Github PK

The hybrid algorithms that were originally implemented were not implemented correctly, and so they have been refactored to be functional but essentially useless in their current form. Right now, they run either LMXRLF or DSATUR to find an initial coloring, and then use that coloring number as a condition to the Tabucol algorithm. The problem is that when that happens, Tabucol re-colors the entire graph to try and meet (and iteratively beat) the original coloring that was found. Instead, it should use the coloring that is generated from LMXRLF or DSATUR as an input, and then attempt to run tabu iterations on that initial graph rather than the random initialization that tabu would normally provide.

This will require a refactor of the Tabucol algorithm to have a separate initialization step, tabu step, and post-processing step. This way steps can be called when issuing a generic color() function call and a subset of steps can be called within other algorithms. We may want to make the tabu part public in case other people want to perform this process.

Edge list test cases require a -e flag in the input to parse correctly, these need to be added to all test_cases.mk edge list tests

Currently write_graph() uses graph_colors.h to choose the colors that each node gets in the .dot output file. This means that we cannot display graphs that require more colors than there are colors in graph_colors.h. Find a way to have write_graph() choose the colors (or some other representation) so we can write graphs with a (near)infinite number of colors.

The klmxrlf algorithm colors vertices -1. It also colors vertices that are connected the same color. Each time this algorithm is run on the wheel_8 test it produces a different result, such that two vertices having the error is different every time. Here is some sample error output code of the Vertex colors and the two Vertices with the error:

Running Wheel Test Suite (Default)
Running test_cases/wheel_8.txt
LMXRLF Chromatic Number: 2
v7 is colored: 0
v1 is colored: 1
v2 is colored: 0
v3 is colored: -1
-----Error, these edges have the same color: v3 v8
Graph is not colored correctly

Running Wheel Test Suite (Default)
Running test_cases/wheel_8.txt
LMXRLF Chromatic Number: 2
v7 is colored: -1
v1 is colored: 0
v2 is colored: 1
v3 is colored: 0
v4 is colored: 1
v5 is colored: 0
v6 is colored: 1
v7 is colored: -1
-----Error, these edges have the same color: v7 v8
Graph is not colored correctly

I think the algorithm is not reaching the 8th vertex maybe? I will do more testing with this algorithm on other test cases to see if this is a consistent problem.

The refactored main program for testing different coloring algorithms against input files has on way to designate a directory of files to run. Additionally we may want to switch to a new naming convention (or do some file analysis) to allow for the file type to be detected before running the file rather than having it designated (which would be hard in a mixed file type directory like Benchmarks/).

When testing the algorithms, Hybrid had a single instance of a better coloring than previously known. This is likely an error, so the Hybrid algorithm needs to be hand verified with the paper.

Need to create a more robust and logical input parser that is better attuned to different input cases and is less likely to break because of small errors in input files.

Since the test cases were moved during the initial commit, the test_cases.mk was updated so the Makefile would continue working, but it should be refactored so it references a single directory

After creating a test that uses the K5 kuratowski subgraph to verify that all the algorithms are able to color it using exactly 5 colors, the LMXRLF algorithms is shown to be generating an incorrect coloring. This is likely an issue where the -1 which is used to represent a blank color is being counted as a correct color (since it isn't equal to any neighbors) and the algorithm is terminating prematurely.

This also lead to an update in the is_valid() function which now catches the case that some nodes are left uncolored but the graph was being counted as correctly colored.

Allow for a "make benchmark" keyword that cleans, compiles with optimizations, and runs user specified test sets.

When the Tabucol algorithm is called with a single node (or any type of call which causes it not to do a tabu iteration) the colors do not have any method for reduction. This is especially problematic when the condition that is set is large compared to the graph size. There are a few remidies, some or all of which could help aleviate this issue.

• Force a better condition, such that any condition asking for a number of colors > the graph size is ignored and the graph size is instead used (the graph can always be colored with a number of colors = number of nodes)
• Post-process the colors so that no matter which colors are originally chosen they are down processed into the first N contiguous colors where N is the number of colors needed

Remove legacy -t (test, actually matrix parse before edge list existed) and -e (edge list) flags and replace them with the more obvious -m (matrix) and -l (edge list)

Replace deprecated atoi in graph.cc with cross-compatible code.

Refactor the code so that the coloring algorithms inherit from an ABC and are set into the graph class as a strategy pattern, with standard color() call and standardized return.

There is an implementation optimization described in the reference paper for MCS algorithm. The optimization description is pasted to the top of mcs.cc.

Dear,

I'm interested in using your software for a research related problem involving graph coloring. However, when I tried to install it in my Mac with the provided instructions "cmake . ; make" the following happens:

1. Cmake complains about gflags/ and googletest/ folder as they are empty. Hence, I commented out the corresponding two ADD_SUBDIRECTORY lines in ./CMakeLists.txt
2. After this, cmake succeeds but now make fails. The source main.cpp includes gflags/gflags.h but that folder is empty, and main.cpp won't compile if the corresponding include directive is commented out.

Please, advice...

Thanks!

Blai Bonet

Received the following error when running the test case r1000.5.col with the DSATUR algorithm

graphColoring(72423,0x7fff7824d310) malloc: ***
mach_vm_map(size=8385532581712789504) failed (error code=3)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
libc++abi.dylib: terminating with uncaught exception of type std::bad_alloc: std::bad_alloc
/bin/sh: line 1: 72423 Abort trap: 6           ./graphColoring $test -l

Need to update the README to be more user friendly, should convert it to a GitHub Markdown during the rewrite

Break test_cases.mk into lists of different test sets, then add the ability for user to test on entire sets.

split() was updated to run on linux and was inadvertently broken by a contributor because of a lack of testing.

Make a new phony target that creates a graphColoring share object file

Implement the lsII algorithm as well as the lmxRLF/lsII Hybrid algorithm from the paper Efficient Coloring of a Large Spectrum of Graphs by Kirkovski et al.