Tutorial :pseudo code for finding closed paths in a graph



Question:

I have an adjaceny matrix for a graph which tracks the edges between the nodes by having a 1 in the corresponding adjMat[i,j] = 1; Through this adjaceny matrix i wish to find out all the closed paths of length 4 which exists in the graph. Can anyone please provide me with a pseudo code. thank u


Solution:1

This sounds like homework, so I won't give the whole thing away. But here's a hint: since you are interested in finding cycles of length 4, take the 4th power of the adjacency matrix and scan along the diagonal. If any entry M[i,i] is nonzero, there is a cycle containing vertex i.


Solution:2

Perhaps it is not the optimal way to compute it ( it's O(n^4) ), but a very straightforward way is scan through the all the vertices

a, b, c, d such that b > a, c > b, d > c  

You can check then check for each of the following cycles:

   1. ([a,b] && [b,c] && [c,d] && [d,a])   2. ([a,b] && [b,d] && [d,c] && [c,a])    3. ([a,d] && [d,b] && [b,c] && [c,a])     1:         2:        3:   A---B      A---B     A   B   |   |       \ /      |\ /|   |   |        X       | X |   |   |       / \      |/ \|   D---C      D---C     C   D  

You're basically checking every ordered set of vertices (a,b,c,d) for the 3 ways that they could form a cycle.

So the pseudo code would be:

for a = 0 to <lastVertex>   for b = a + 1 to <lastVertex>    for c = b + 1 to <lastVertex>     for d = c + 1 to <lastVertex>        if(IsCycle(a,b,c,d)) AddToList([a,b,c,d])      if(IsCycle(a,b,d,c)) AddToList([a,b,d,c])      if(IsCycle(a,c,b,d)) AddToList([a,c,b,d])       next d    next c   next b      next a  


Solution:3

Apply a depth-limited depth-first-search to every node and record nodes where the DFS finds the starting node. For the search, see pseudo-code here: http://en.wikipedia.org/wiki/Depth-limited_search. You just need to add something like

if(node' == node && node'.depth==4) memorize(node)  

to the beginning of the loop.


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »