Generating a connected graph and checking if it has eulerian cycle

So, I wanted to have some fun with graphs and now it’s driving me crazy.

First, I generate a connected graph with a given number of edges. This is the easy part, which became my curse. Basically, it works as intended, but the results I’m getting are quite bizarre (well, maybe they’re not, and I’m the issue here). The algorithm for generating the graph is fairly simple.

I have two arrays, one of them is filled with numbers from 0 to n - 1, and the other is empty.

At the beginning I shuffle the first one move its last element to the empty one.

Then, in a loop, I’m creating an edge between the last element of the first array and a random element from the second one and after that I, again, move the last element from the first array to the other one.

After that part is done, I have to create random edges between the vertexes until I get as many as I need. This is, again, very easy. I just random two numbers in the range from 0 to n - 1 and if there is no edge between these vertexes, I create one.

This is the code:

void generate(int n, double d) {
    initMatrix(n); // <- creates an adjacency matrix n x n, filled with 0s
    int *array1 = malloc(n * sizeof(int));
    int *array2 = malloc(n * sizeof(int));
    int j = n - 1, k = 0;
    for (int i = 0; i < n; ++i) {
        array1[i] = i;
        array2[i] = 0;
    }

    shuffle(array1, 0, n); // <- Fisher-Yates shuffle
    array2[k++] = array1[j--];
    int edges = d * n * (n - 1) * .5;
    if (edges % 2) {
        ++edges;
    }
    while (j >= 0) {
        int r = rand() % k;
        createEdge(array1[j], array2[r]);
        array2[k++] = array1[j--];
        --edges;
    }

    free(array1);
    free(array2);

    while (edges) {
        int a = rand() % n;
        int b = rand() % n;
        if (a == b || checkEdge(a, b)) {
            continue;
        }
        createEdge(a, b);
        --edges;
    }
}

Now, if I print it out, it’s a fine graph. Then I want to find a Hammiltonian cycle. This part works. Then I get to my bane – Eulerian cycle. What’s the problem?

Well, first I check if all vertexes are even. And they are not. Always. Every single time, unless I choose to generate a complete graph.

I now feel destroyed by my own code. Is something wrong? Or is it supposed to be like this? I knew that Eulerian circuits would be rare, but not that rare. Please, help.


Source: c#

Leave a Reply