Pratik Koirala Pratik Koirala - 5 months ago 20
Java Question

How to check if there is a transitive orientation for a given undirected graph?

An undirected graph has a transitive orientation if its edges can be oriented in such a way that if (x, y) and (y, z) are two edges in the resulting directed graph, there also exists an edge (x, z) in the resulting directed graph.

I am working with real food web networks and I need to check if a dense undirected graph (which models competition in the food web) has a transitive orientation. The undirected graph is represented as an adjacency matrix in Java.

EDIT:

For example,
for this undirected graph,

We can orient the edges in this way. So, this graph has a transitive orientation.

Answer

First of all, the undirected graph has a transition orientation if and only if every connected component of it has this property. So here, I only consider one connected component. Fix some edge e = {s, t} between vertices of s and t. This edge has only two possible directions. We try both possiblities. If any of them lead to a proper orientation this component has a proper orientation, otherwise, it doesn't. Note that by analysing the if conditions in the for loop in our algorithm, we can show that fixing only one edge will result in all other edges to take a certain direction.

Algorithm:

Make a new matrix D, NxN to keep track of the directed assignments we make
Note that D[i][j] = 1 if the edge i->j is assigned, and it is 0 otherwise

1) Fix the direction of e={s, t} (e.g. s->t)

While(there is some edge unassinged){
    look for some unassigned edge {x, y} so that at least one of x or y are the endpoint of some assigned edge
    Let's first consider x to be the endpoint of some assingned edge
    for(all nodes u connected to x such that {u, x} has an assinged value){ //it means either D[u][x] or D[x][u] is 1
        if({u, x} = u->x and undirected graph has edge {u, y}) {
            D[x][y] = 1 and D[u][y] = 1; //any other assignments will result in contradiction
            if(D[y][x] == 1 || D[y][u] == 1){
                print "Assignment impossible"
                go to step 1 and fix the other direction
            }
        }
        if({u, x} = u->x and undirected graph does not have edge {u, y}){
            D[y][x] = 1; //any other assignments will result in contradiction
            if(D[x][y] == 1){
                print "Assignment impossible", 
            }
        }
        if({u, x} = x->u and undirected graph has edge {u, y}) {
            D[y][x] = 1 and D[y][u] = 1; //any other assignments will result in contradiction
            if(D[x][y] == 1 || D[u][y] == 1){
                print "Assignment impossible"
                go to step 1 and fix the other direction
            }
        }
        if({u, x} = x->u and undirected graph does not have edge {u, y}) {
            D[x][y] = 1; //any other assignments will result in contradiction
            if(D[y][x] == 1){
                print "Assignment impossible"
                go to step 1 and fix the other direction
            }
        }
    }
    if(y is also the endpoint of some unassigned edge){
        repeat a for loop similar to that of x this time for y
    }
}

if(no contradiction found){
    This component has a successful assignment with this fixed value for e={s,t}
}

If we keep an array of size N to mark the nodes that are endpoint of some assigned edges, the complexity of the algorithm is O(MN) where N is the number of nodes and M is the number of edges; O(M) for the while loop and O(N) for the for loop.