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.
What you are looking at is comparability graph. This class of graph is also known as "transitively orientable graphs", but this is not the most common name. For recognition of this class, look at the graphclasses website.
