How to find the universal sink of a directed graph with an adjacency-matrix representation

Question

I'm working on an excercise (self-study): "Show how to determine whether a directed graph G contains a universal link - a vertex with in-degree (V-1) (V is the number of vertices) and out-degree 0 in time O(V), given an adjacency matrix for G. I have written the code here:

    int UniversalSink(const int *a, int N)
{
    int i,j,i1,j1,q;
    i=0;


    i=0;
    q=YES;
    j=-1;
    do
    {
    j++;
    if (j==N)
        break;

    while ( (*(a+i*MAX+j)) ==0 )
    {
        j++;
        if (j==N)
        {

        break;
        }
    }
    if (j==N)
        break;
    q= YES;

    for (; i<j; i++)
        if ( (*(a+i*MAX+j)) ==0 )
        {
           i=j,j=i-1;
           q= NO;
           break;
        }
    if (q==NO)
        continue;
    q=YES;

    /*
    for (i=0; i<=j; i++ )
        if (a[j][i] ==1 )
        {
        i=j;
        q=NO;
        ok=NO;
        trai = NO;
        break;

        }
    if (q==NO)
        continue;
    */
    q=YES;

    for (i1= j+1; i1<N; i1++)
        if ((*(a + i1*MAX +j)) ==0 )
        {
        i=i1, j=i-1;
        q=NO;
        break;

        }
    if (q==NO)
        continue;
    }
    while (j<N);

    {
    i1=i;
    for (j1=0; j1<N;j1++)
        if ( (*(a + i1*MAX +j1 ))  ==1 )
        return -1;
    j1=i;
    for (i1=0; i1<N;i1++)
    {
        if (i1==j1)
        continue;
        if ( (*(a + i1*MAX +j1))==0)
        return -1;
    }
    return i;

    }
  

It takes a N-N matrix and returns the position of the universal sink (0 to N-1 if it exists and -1 if it doesn't) However I don't really know if it is O(V) or not, and in fact I'm not sure if it will always compute the desired result at all

(Feel free to comment on any other aspect of my code e.g. using too many breaks)

Answer 1

You can use the following code:

int DetectSink(matrix G, int V) {
    int i = 0;
    int j = 0;
    while (i < V && j < V)
        if (G[i][j])
             i = i + 1;
        else j = j + 1;
    if (i < V && IsSink(G, i)) return i;
    return -1;
}

If k is an universal sink, then the k-th row of the adjacency-matrix ( G ) will be all 0s, and the k-th column will be all 1s (except G[k][k] = 0).

OBS: We can conclude that there is at most one sink.

If an univeral sink k exist in G, then eventually, we get to position (i = k, j) or (i, j = k).

            k
  +---+---+---+---+---+
  |   |   | 1 |   |   |
  +---+---+---+---+---+
  |   |   | 1 |   |   |
  +---+---+---+---+---+
k | 0 | 0 | 0 | 0 | 0 |
  +---+---+---+---+---+
  |   |   | 1 |   |   |
  +---+---+---+---+---+
  |   |   | 1 |   |   |
  +---+---+---+---+---+

If we reach column k (j=k) before row k (i=k), our algorithm excecutes the then block until (i = k, j = k), then it executes the else block until (i = k, j = V). In other case, if k-th row is reached first than k-th column, then the else block excecutes to the end of while loop until (i = k, j = V).

At the end we must check if i is an universal sink, because we know if a sink exist it is i, but we have not idea what our algorithm is going to do if an universal sink is not in G.

The running time is O(V), because in every step we increment i or j, so at most 2V such operations occurrs. The IsSink part is O(V).

There is a nice solution using Divide & Conquer:

In this solution we keep a set of candidates to universal sink and in every step we make pairs of vertexs and discard one of two vertexs, in order to analize one half of the initial candidates.