August 15, 2012

How many paths of given length in a graph?

A graph is given and also a value N where N is the path length between two nodes in a graph.  Every edge is considered to be of length one. We've to tell how many different paths of given length could be in graph.
    Well, there's a easy solution to this. We've to build an adjacency matrix for the given graph and then raise this matrix up to the power N. Now just get the value of matrix[X][Y] where X is starting node and Y is ending node. That's it.
    E.g. There's an ant at top of tetrahedron and can go to any other vertex connected to it. Moving from one vertex to another increases the traversed length by one. Value of path length is given, say L. We've to tell in how many ways the ant can return to the vertex from where it started after traversing length L. Technically we've to find out the number of different cyclic paths with the length of L from starting vertex to itself.
   As it's a tetrahedron so this is a regular graph of degree 3. Just build the adjacency matrix and raise it to the power L.

Problem Statement:
My solution:

public class tetrahedron{
    final static int MOD = 1000000007;
    final static int dim = 4;
    public static void main (String []args)throws IOException{
        BufferedReader br = new BufferedReader (new InputStreamReader(;
        int T, N;
        long array[][] = new long[4][4];
        array[0][0] = 0;
        array[0][1] = 1;
        array[0][2] = 1;
        array[0][3] = 1;
        array[1][0] = 1;
        array[1][1] = 0;
        array[1][2] = 1;
        array[1][3] = 1;
        array[2][0] = 1;
        array[2][1] = 1;
        array[2][2] = 0;
        array[2][3] = 1;
        array[3][0] = 1;
        array[3][1] = 1;
        array[3][2] = 1;
        array[3][3] = 0;
        N = Integer.parseInt(br.readLine());
        long [][] ans = power_fun(array,N);
        long result = ans[3][3]%MOD;

    private static long [][] mul (long [][] A, long [][]B){
        long [][]res = new long [dim][dim];
        for (int I=0; I<dim;I++){
            for (int J=0;J<dim;J++){
                for (int K=0;K<dim;K++){
                    res[I][J] += (A[I][K]*B[K][J])%MOD;
                    res[I][J] %= MOD;
        return res;

    private static long [][] power_fun (long [][] base, int pow){
        if (pow == 1 )return base;
        long [][] temp = new long[dim][dim];
        temp = mul (base, base);
        temp = power_fun (temp, pow>>1);
        if ((pow &1) ==1)
            temp = mul (temp,base);
        return temp;

No comments:

Post a Comment