search

dke-group-23 / DKE-Project

0 stars 2 forks source link

Exact algorithm #3

Closed Isinlor closed 5 years ago

Isinlor commented 6 years ago

Here we can keep track of work related to the exact algorithm.

Just as reminder: exact algorithm is an algorithm that computes the chromatic number exactly.

Isinlor commented 6 years ago

Just as a heads up - finding efficient solution to this problem for difficult graphs is hard, like you win 1 000 000 $ and eternal fame type hard.

For difficult graphs we probably won't be able to do much better than brute forcing it.

Ironically, there is some finesse to brute force too. But really anything will do.

Isinlor commented 6 years ago

Section 1.4.1 Solution Space Growth Rates, page 12 from "A Guide to Graph Colouring Algorithms and Applications" seems to be relevant:

One possible, though perhaps foolhardy, method for solving the graph colouring problem is to check every possible assignment of vertices to colours and then return the best of these (that is, return the solution from the set of all possible assignments that is both feasible and seen to be using the fewest colours). Such a method would indeed be guaranteed to return an optimal solution, but would it work in practice?

Then they go on about solution that would take n^n steps for graphs of size n. For graph of 10 vertices it would be 10 billions steps. Quite a lot.

But as I said there is some finesse to brute force too :).

One can notice that we don't care about which exact color we will use. This allows to reduce search space.

We might now choose to employ an enumeration algorithm that starts by considering k = 1 colour. At each step the algorithm then simply needs to check all {n over k} possible partitions to see if any correspond to a feasible solution (k-colouring). If such a solution is found, the algorithm can halt immediately with the knowledge that an optimal solution has been found. Otherwise, k would need to be incremented by 1, with the process continuing as before.

Isinlor commented 5 years ago

Exact algorithm WIP (Work In Progress) implementation: https://github.com/dke-group-23/DKE-Project/blob/master/ExactAlgorithm.java

Our algorithm works as described above.

Iterating over all partitions have proven to be quite difficult, but this is the only thing still missing.

We have found an easy, but slow way to implement it:

I can't compare different algorithms for doing this but one that comes to mind immediately which is probably not bad is simply to count to b^n in different bases "b" where the base depends on how many partitions you want. So, for instance, if you want partitions of 10 things into 2 different sets, enumerate all 10-digit base 2 numbers: the 0s in a given number correspond to one partition and the 1s correspond to the other. Similarly, for partitions of 10 things into 3 different sets, enumerate all 10-digit base 3 numbers.

Isinlor commented 5 years ago

Exact algorithm seems to be working. Somewhat...

I added comments to the code, so that it's easier to follow what it is doing.

You can see how the counting works here.

As a bonus we have lower bound algorithm.

See the experiments:

isinlor@~/Projects/Studies/Project$ javac ExactAlgorithm.java && java ExactAlgorithm ./graph.txt
// Number of vertices = 6
// Expected number of edges = 7
// Reading edge 1
// Edge: 1 2
// Reading edge 2
// Edge: 2 3
// Reading edge 3
// Edge: 3 1
// Reading edge 4
// Edge: 1 4
// Reading edge 5
// Edge: 4 5
// Reading edge 6
// Edge: 5 6
// Reading edge 7
// Edge: 6 4
Lower bound: 1
Lower bound: 2
Chromatic number: 3
isinlor@~/Projects/Studies/Project$ javac ExactAlgorithm.java && java ExactAlgorithm ./graph4.txt
// Number of vertices = 4
// Expected number of edges = 6
// Reading edge 1
// Edge: 1 2
// Reading edge 2
// Edge: 1 3
// Reading edge 3
// Edge: 1 4
// Reading edge 4
// Edge: 2 3
// Reading edge 5
// Edge: 2 4
// Reading edge 6
// Edge: 3 4
Lower bound: 1
Lower bound: 2
Lower bound: 3
Chromatic number: 4
isinlor@~/Projects/Studies/Project$ javac ExactAlgorithm.java && java ExactAlgorithm ./graph5.txt
// Number of vertices = 5
// Expected number of edges = 10
// Reading edge 1
// Edge: 1 2
// Reading edge 2
// Edge: 1 3
// Reading edge 3
// Edge: 1 4
// Reading edge 4
// Edge: 1 5
// Reading edge 5
// Edge: 2 3
// Reading edge 6
// Edge: 2 4
// Reading edge 7
// Edge: 2 5
// Reading edge 8
// Edge: 3 4
// Reading edge 9
// Edge: 3 5
// Reading edge 10
// Edge: 4 5
Lower bound: 1
Lower bound: 2
Lower bound: 3
Lower bound: 4
Chromatic number: 5

Until it's not working? ...

isinlor@~/Projects/Studies/Project$ javac ExactAlgorithm.java && java ExactAlgorithm ./graphs/graph02.txt
// Number of vertices = 40
// Expected number of edges = 183
bla bla bla ...
Lower bound: 1
Lower bound: 2
Lower bound: 3
Lower bound: 4
Lower bound: 5
Lower bound: 6
Lower bound: 7
Lower bound: 8
Lower bound: 9
Lower bound: 10
Lower bound: 11
Lower bound: 12
Lower bound: 13
Lower bound: 14
Lower bound: 15
Lower bound: 16
Lower bound: 17
Lower bound: 18
Lower bound: 19
Lower bound: 20
Lower bound: 21
Lower bound: 22
Lower bound: 23
Lower bound: 24
Lower bound: 25
Lower bound: 26
Lower bound: 27
Lower bound: 28
Lower bound: 29
Lower bound: 30
Lower bound: 31
Lower bound: 32
Lower bound: 33
Lower bound: 34
Lower bound: 35
Lower bound: 36
Lower bound: 37
Lower bound: 38
Lower bound: 39
Lower bound: 40 <-- WTF? 40 vertices can not be colored with 40 colors?!

There seems to be some bug, also it was IMO quite to fast.

Isinlor commented 5 years ago

Seems like the issue is with integer overflow:

If it overflows, it goes back to the minimum value and continues from there. If it underflows, it goes back to the maximum value and continues from there.

See this line.

long maxPartitions = (long)Math.pow(colors, numberOfVertices);

This will get big, like stupidly big e.g. 40 colors on 40 vertices it's 40^40 ...

Isinlor commented 5 years ago

The way partitions are iterated can be vastly improved.

What we currently have is x^y, where x is number of colors and y is number of vertices.

While based on Stirling numbers of the second kind:

In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets

We know that we can do mach better.

As an example, see graph by wolfram alpha for iterating from 1 to 20 colors over 20 vertices: http://www.wolframalpha.com/input/?i=plot+StirlingS2%5B20,+x%5D,+x%3D1+to+20

It maxes out at at 8 colors at 10^13 partitions.

While x^20, maxes out at x=20 i.e. 10^26

So for 20 vertices we have at least 13 orders of magnitude improvement to make (10^26 vs 10^13).