CODEWITHSUNDEEP
pythonigraphdigraphsgirth
Qise
Qise

Reputation: 276

igraph, Python - directed girth seems to not work

I'm working with randomly generated digraphs. I need to verify that the graphs I have have a girth of at least, say 3.

The solution I used is the following:

  1. I generate a random adjacency matrix
  2. I create an igraph.Graph instance from the matrix
  3. I call .girth() method to check the girth is correct.
  4. If correct, I keep my process; otherwise I return to step 1.

However; sometimes I have graphs that definitly should not pass the girth check but they do. For instance: Graph with girth 2. have an girth 2: there are two pairs of vertices (a,b) with a,b, and b,a in the arcs.

My theory is that igraph do not understand these pair of vertices as a proper cycle; if that is the case how do I fix this?

For the record: here how goes my random generation:

M = np.zeros((n,n))
    for i in range(n):
        pick_list = [j for j in range(n) if j!=i]
        x = random.sample(pick_list, outdegree)
        for j in x:
            M[i][j] = 1

Upvotes: 0

Views: 99

Answers (1)

Qise
Qise

Reputation: 276

So apparently the .girth() does not work properly for digraph. I did this to solve my problem:

    D_k = copy.deepcopy(D)

    for k in range(2, girth):
        D_k = D_k.dot(D)
        if sum([D_k[i][i] for i in range(n)]) != 0: # equivalent to: trace of D_k
            return False
    return True

A bad solution but at least it is correct.

Upvotes: 0

Related Questions