title: How to check if there is a transitive orientation for a given undirected graph?
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>EDIT:</p>
  
  <p>For example,
  <a href="http://i.stack.imgur.com/tuAzL.jpg" rel="nofollow">for this undirected graph,</a></p>
  
  <p>We can orient the edges in <a href="http://i.stack.imgur.com/cL63n.jpg" rel="nofollow">this way</a>. So, this graph has a transitive orientation.</p>