Finding vertices in graph that are separated by one vertex

Question

Do you know some algorithm(better than brute-force) which can find vertex in the graph that are separated by one vertex and aren't connected between each other. Example:

In this graph found paths would be:

• 1 - 4
• 2 - 4
• 3 - 5

The best would be c++ code which uses array of stl lists as a graph representation but code in any other procedural language or pseudocode would also be fine.

Answer 1

One simple and intuitive solution to this problem lies in the adjacency matrix. As we know, (i,j) th element of the nth power of an adjacency matrix lists all the paths of length exactly n between i and j.
So i just read in A, the adjacency matrix and then calculate A^2. Finally, i list all the pairs which have exactly one path of length 2 between them.

//sg
#include<stdio.h>
#define MAX_NODE 10
int main()
{
    int a[MAX_NODE][MAX_NODE],c[MAX_NODE][MAX_NODE];
    int i,j,k,n;
    printf("Enter the number of nodes : ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    for(j=0;j<=i;j++)
    {
        printf("Edge from %d to %d (1 yes/0 no) ? : ",i+1,j+1);
        scanf("%d",&a[i][j]);
        a[j][i]=a[i][j]; //undirected graph
    }
    //dump the graph
    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    {
        c[i][j]=0;
        printf("%d",a[i][j]);
    }
    printf("\n");
    }
    printf("\n");

    //multiply
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    for(k=0;k<n;k++)
    {
        c[i][j]+=a[i][k]*a[k][j];
    }
    //result of the multiplication
    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    {
        printf("%d",c[i][j]);
    }
    printf("\n");
    }
    for(i=0;i<n;i++)
    for(j=0;j<=i;j++)
    {
        if(c[i][j]==1&&(!a[i][j])&&(i!=j)) //list the paths
        {
            printf("\n%d - %d",i+1, j+1 );

        }
    }
    return 0;
}

Sample Run For Your Graph

[aman@aman c]$ ./Adjacency2 
Enter the number of nodes : 5
Edge from 1 to 1 (1 yes/0 no) ? : 0
Edge from 2 to 1 (1 yes/0 no) ? : 1
Edge from 2 to 2 (1 yes/0 no) ? : 0
Edge from 3 to 1 (1 yes/0 no) ? : 1
Edge from 3 to 2 (1 yes/0 no) ? : 1
Edge from 3 to 3 (1 yes/0 no) ? : 0
Edge from 4 to 1 (1 yes/0 no) ? : 0
Edge from 4 to 2 (1 yes/0 no) ? : 0
Edge from 4 to 3 (1 yes/0 no) ? : 1
Edge from 4 to 4 (1 yes/0 no) ? : 0
Edge from 5 to 1 (1 yes/0 no) ? : 0
Edge from 5 to 2 (1 yes/0 no) ? : 0
Edge from 5 to 3 (1 yes/0 no) ? : 0
Edge from 5 to 4 (1 yes/0 no) ? : 1
Edge from 5 to 5 (1 yes/0 no) ? : 0
01100
10100
11010
00101
00010

21110
12110
11301
11020
00101

4 - 1
4 - 2
5 - 3

Analysis
For n vertices :

• Time : O(n^3) . Can be reduced to O(n^2.32), which is very good.

• Space : O(n^2).

Answer 2

You can do this with a adapted version of Warshall's algorithm. The algorithm in the following code example uses the adjacency matrix of your graph and prints i j if there is a edge from i to k and a edge from k to j but no direct way from i to j.

#include <iostream>

int main() {
    // Adjacency Matrix of your graph
    const int n = 5;
    bool d[n][n] = {
       { 0, 1, 1, 0, 0 },
       { 0, 0, 1, 0, 0 }, 
       { 0, 0, 0, 1, 0 },
       { 0, 0, 0, 0, 1 },
       { 0, 0, 0, 0, 0 },
    };

    // Modified Warshall Algorithm
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            if (d[i][k])
                for (int j = 0; j < n; j++)
                    if (d[k][j] && !d[i][j])
                        std::cout << i + 1 << " " j + 1 << std::endl;
}

You can view the result online.

Answer 3

One way would be based on a breadth-first-style search, where for each vertex i in the graph, we scan the vertices adjacent to those adjacent to i (i.e. two levels of adjacency!).

mark = array[0..n-1] of 0
flag = 1

for i = nodes in graph do

// mark pattern of nodes adjacent to i 
    mark[i] = flag
    for j = nodes adjacent to i do
        mark[j] = flag
    endfor

// scan nodes adjacent to those adjacent to i
// (separated by one vertex!)
    for j = nodes adjacent to i do
    for k = nodes adjacent to j do
        if mark[k] != flag  and k > i then
        // i,k are separated by another vertex
        // and there is no edge i,k

        // prevent duplicates
            mark[k] = flag
        endif
    endfor
    endfor

// implicit unmarking of current pattern
    flag += 1

endfor

If the graph had m edges per vertex, this would be an O(n * m^2) algorithm that requires O(n) extra space.