CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithmdepth-first-search
DarkLeafyGreen
DarkLeafyGreen

Reputation: 70416

Count cycles of length 3 using DFS

Let G=(V,E) be an undirected graph. How can we count cycles of length 3 exactly once using following DFS:

DFS(G,s):
    foreach v in V do
        color[v] <- white; p[v] <- nil
    DFS-Visit(s)

DFS-Visit(u)
    color[u] <- grey
    foreach v in Adj[u] do
        if color[v] = white then 
            p[v] = u; DFS-Visit(v)
    color[u] <- black

There is a cycle whenever we discover a node that already has been discovered (grey). The edge to that node is called back edge. The cycle has length 3 when p[p[p[v]]] = v, right? So

DFS-Visit(u)
    color[u] <- grey
    foreach v in Adj[u] do
        if color[v] = grey and p[p[p[v]]] = v then
            // we got a cycle of length 3
        else if color[v] = white then 
            p[v] = u; DFS-Visit(v)
    color[u] <- black

However how can I create a proper counter to count the number of cycles and how can I count each cycle only once?

Upvotes: 2

Views: 5142

Answers (2)

Lucas Sampaio
Lucas Sampaio

Reputation: 316

If a solution without using DFS is okay, there is an easy solution which runs in O(NMlog(N³)) where N is the number of vertices in the graph and M is the number of edges.

We are going to iterate over edges instead of iterating over vertices. For every edge u-v, we have to find every vertex which is connected to both u and v. We can do this by iterating over every vertex w in the graph and checking if there is an edge v-w and w-u. Whenever you find such vertex, order u,v,w and add the ordered triplet to a BBST that doesn't allow repetitions (eg: std::set in C++). The count of length 3 cycles will be exactly the size of the BBST (amount of elements added) after you check every edge in the graph.

Let's analyze the complexity of the algorithm:

  1. We iterate over every edge. Current complexity is O(M)

  2. For each edge, we iterave over every vertex. Current complexity is O(NM)

  3. For each (edge,vertex) pair that forms a cycle, we are going to add a triplet to a BBST. Adding to a BBST has O(log(K)) complexity where K is the size of the BST. In worst case, every triplet of vertices forms a cycle, so we may add up to O(N³) elements to the BST, and the complexity to add some element can get as high as O(log(N³)). Final complexity is O(NMlog(N³)) then. This may sound like a lot, but in worst case M = O(N²) so the complexity will be O(N³log(N³)). Since we may have up to O(N³) cycles of length 3, our algorithm is just a log factor away from an optimal algorithm.

Upvotes: 0

md5
md5

Reputation: 23699

I'm not sure to understand how your condition parent[parent[parent[v]]] == v works. IMO it should never be true as long as parent represents a structure of tree (because it should correspond to the spanning tree associated with the DFS).

Directed graphs

Back edges, cross edges and forward edges can all "discover" new cycles. For example:

Cycle with cross edge

We separate the following possibilities (let's say you reach a u -> v edge):

  • Back edge: u and v belongs to the same 3-cycle iff parent[parent[u]] = v.
  • Cross edge: u and v belongs to the same 3-cycle iff parent[u] = parent[v].
  • Forward edge: u and v belongs to the same 3-cycle iff parent[parent[v]] = u.

Undirected graphs

There are no more cross edges. Back edges and forward edges are redundant. Therefore you only have to check back edges: when you reach a u -> v back edge, u and v belongs to the same 3-cycle iff parent[parent[u]] = v.

def dfs(u):
    color[u] = GREY
    for v in adj[u]:
        # Back edge
        if color[v] == GREY:
            if parent[parent[u]] == v: 
                print("({}, {}, {})".format(v + 1, parent[u] + 1, u + 1))
        # v unseen
        elif color[v] == WHITE:
            parent[v] = u
            dfs(v)
    color[u] = BLACK

If you want to test it:

WHITE, GREY, BLACK = 0, 1, 2
nb_nodes, nb_edges = map(int, input().split())
adj = [[] for _ in range(nb_nodes)]
for _ in range(nb_edges):
    u, v = map(int, input().split())
    adj[u - 1].append(v - 1) 
    adj[v - 1].append(u - 1) 
parent = [None] * nb_nodes
color = [WHITE] * nb_nodes

Upvotes: 1

Related Questions