Graph vertex coloring algorithm taking too long. Passing arguments as reference

[Quadrup]

I had a similar question recently and the answer was that I should pass the arguments by reference. Which I now did and the code seems to be working much faster with 8 or 9 vertices.

However, once I try to run this algorithm with a bigger graph that has 10 or more vertices, the time is increased drastically.

For example with 9 vertices ~ 5 seconds. 10 vertices ~ 1 minute. Tried with 11 vertices however, the algorithm has been running for like 10 minutes now and still not done.

I was wondering whether I have still missed something and if there are any more ways to increase the speed of this algorithm.

Maybe I passed the arguments as reference incorrectly?

The algorithm colors the vertices of a graph using a recursive backtracking function. To input a graph, I am using a function that generates a random adjacency matrix according to the given n (vertex count)

Here is my code

  bool canColor(int &v, vector<bool> &graph, int colors[], int &j, int &vertex_count)
{
    for (int i = 0; i < vertex_count; i++)
        if (
            //graph[v][i] && j == colors[i]
            graph[v*vertex_count+i] && j == colors[i])
            return false;
    return true;
}

void recursiveColor(vector<bool> &graph, int &used_colors, int colors[], int v, int &vertex_count)
{
    if(v == vertex_count)
        return;

    for(int j = 1; j <= used_colors; j++)
    {
        if(canColor(v, graph, colors, j, vertex_count))
        {
            colors[v] = j;

            recursiveColor(graph, used_colors, colors, v+1, vertex_count);

        }
    }
}

void graphColor(vector<bool> graph, int used_colors, int vertex_count)
{
    clock_t start;
    double duration;
    start = clock();

    int v = 0;
    int colors[vertex_count];

    for(int i = 0; i < vertex_count; i++)
    {
        colors[i] = 0;
    }

    recursiveColor(graph, used_colors, colors, v, vertex_count);

    for (int i = 0; i < vertex_count; i++)
        cout<< "Vertex " << i+1 << " Color: "<< colors[i]<<endl;


    duration = ( clock() - start ) / (double) CLOCKS_PER_SEC;
    cout<<"time taken: "<< duration <<endl;

}

[seeplus]

L28. graph is passed by value and not by ref

What's the O() of the algorithm? If the algorithm is say O(n^4), then irrespective of any local code optimisation, the larger n the much, much larger is going to be the runtime. In this case only an algorithm improvement can improve the perforamnce.

[salem c]

> For example with 9 vertices ~ 5 seconds. 10 vertices ~ 1 minute.
> Tried with 11 vertices however, the algorithm has been running for like 10 minutes now and still not done.
What you need is a better algorithm, not better code.
https://en.wikipedia.org/wiki/Analysis_of_algorithms
From the look of things, your algorithm is O(n²).
Every +1 to n you add is magnifying the amount of time it takes.

But it doesn't look hopeful in the general case.
https://en.wikipedia.org/wiki/Graph_coloring#Algorithms

From 9 to 10, you basically multiplied the time by 10 (5 seconds to 1 minute)
From 10 to 11, you basically multiplied the time by 10 (1 minute to 10 minutes)
12 would be a couple of hours.
13 would be a day.
14 would be 2 weeks.
15 would be 6 months.

[markyrocks]

I'd like to see more of the code.

[jonnin]

things like graphs and trees benefit greatly from having some lightweight redundant storage. If you only had a vector of pointers to each vertex, you can suddenly do a lot that would otherwise require all kinds of iteration to access. Would something like that get it done, or is the coloring tied to the depth or location within the graph or something that requires all the iteration??

I prefer the reverse, a vector of vertices and the graph allocates more via a push-back, and the connections are elsewhere. It keeps the actual data in a solid block of memory, is the only real reason.

I code in a simple, even barbaric at times, style that relies on directly accessing things as much as humanly possible rather than hunting for data over and over. Hunting for data that you already touched once (when you loaded it into your systems) is a big slowdown and often completely avoidable esp with all the memory we have today.

[markyrocks]

I'm honestly wondering if a recursive function is necessary here and might be a big source of the slowdown. I also agree with Jonin that there's most likely opportunity for optimizations here that aren't being taken but there's no way to know bc we can't see all of it...