Number of paths between two nodes in a Directed Cyclic Graph

Question

I want to find the number of paths between vertex 1 and vertex n in a directed graph. The graph contains cycles. If any path between vertex 1 and vertex n has a cycle, then the result should be "INFINITE PATHS" else the number of paths. This is what I tried.

---

1) I modified the DFS algorithm, it starts with node 1, All nodes are white initially.
2) If a gray node is visited, it means that there is a cycle.
3) A path array which records the vertices visited is used to backtrack the nodes in cycle.
4) For each node in cycle unmodified DFS is used to search the nth vertex from that node.
5) If DFS succeeds from any one of the node, then a cycle exists in path between vertex 1 and vertex n so it returns else the algo continues calculating number of paths.

c++ implementation

---

#include <stdio.h>
#include <malloc.h>
#include <vector>
#include <algorithm>

#define WHITE 0
#define GRAY 1
#define BLACK 2

using namespace std;
typedef struct vertexstruct{
   int color;
   vector<int> edgelist;
}vertex;

int ordinarydfs(int v,vertex *vertices,int numvertices){
    if(v == numvertices){
        return 1;       
    }

    if(vertices[v].color == WHITE){
         vertices[v].color = GRAY;
         for(int i=0;i<vertices[v].edgelist.size();i++){
             int x = ordinarydfs(vertices[v].edgelist[i],vertices,numvertices);
             if(x ==1) return 1;
         }
         vertices[v].color = BLACK; 
     }
     return 0;
}

int checkcycle(int v,vector<int>path,vertex *vertices,int numvertices){
    vector<int>::iterator it;
    vector<int>::iterator x;
    it = find (path.begin(), path.end(), v);
    for(x =it;x<path.end();x++)
        vertices[*x].color = WHITE;
    for(x =it;x<path.end();x++){
        if(ordinarydfs(*x,vertices,numvertices))
            return 1;   
    }
    for(x =it;x<path.end();x++)
        vertices[*x].color = GRAY;

    return 0;

}

long dfs(int v,vertex *vertices,int numvertices,vector<int> path){
    long paths = 0;
    if(v == numvertices){
            return 1;       
    }
    if(vertices[v].color == GRAY) {
         if(checkcycle(v,path,vertices,numvertices)) return -1;
    }   
    if(vertices[v].color == WHITE){
        vertices[v].color = GRAY;
        path.push_back(v);
        for(int i=0;i<vertices[v].edgelist.size();i++){     
            long x = dfs(vertices[v].edgelist[i],vertices,numvertices,path);
            vertices[vertices[v].edgelist[i]].color = WHITE;
            if(x == -1) return -1;
            paths += x;
        }
        vertices[v].color = BLACK;  
    }
    return paths % 1000000000;
}

void numpaths(int numvertices,int numedges,vertex *vertices){
    vector<int> path;
    long numpaths = 0;
    numpaths = dfs(1,vertices,numvertices,path);
    if(numpaths == -1)
        printf("INFINITE PATHS\n");
    else
        printf("%ld\n",numpaths);
}



int main(){
    int edgecount=0;
    int  numverts,numedges;
    fscanf(stdin,"%d %d",&numverts,&numedges);
   vertex verts[numverts+1];
   for(int i =1;i<=numverts;i++)
       verts[i].color = WHITE;
   edgecount = 0; 
   int a,b;
   while(edgecount < numedges){
       scanf("%d %d",&a,&b);
       verts[a].edgelist.push_back(b);
       edgecount++;
       }
   numpaths(numverts,numedges,verts);
}

---

The algorithm is too slow for large graphs. Is there a correct approach for this problem? Share your thoughts. Thank you.

Answer 1

A completely different approach would be to represent your graph as an adjacency matrix A[i][j]=1 if (i,j) is an edge, 0 otherwise. Then A^i[s][t] counts the number of paths from s to t, which are of length i (this can be proven by induction. Think of what A^2 represents). Sum A[s][t] for the powers 1..|V|, and you have all of the possible paths of length up to |V|. To check if a cycle exists, see (by multiplying the matrix again) if a path of length |V|+1,...,2|V| exists.

Does this help?