Pratik Koirala - 1 year ago 50

Java Question

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 Source

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.