title: Topological sorting in PHP
body: <p>I found this topological sorting function for PHP:</p>
  
  <p>Source: <a href="http://www.calcatraz.com/blog/php-topological-sort-function-384/" rel="noreferrer">http://www.calcatraz.com/blog/php-topological-sort-function-384/</a></p>
  
  <pre><code>function topological_sort($nodeids, $edges) {
      $L = $S = $nodes = array();
      foreach($nodeids as $id) {
          $nodes[$id] = array('in'=&gt;array(), 'out'=&gt;array());
          foreach($edges as $e) {
              if ($id==$e[0]) { $nodes[$id]['out'][]=$e[1]; }
              if ($id==$e[1]) { $nodes[$id]['in'][]=$e[0]; }
          }
      }
      foreach ($nodes as $id=&gt;$n) { if (empty($n['in'])) $S[]=$id; }
      while (!empty($S)) {
          $L[] = $id = array_shift($S);
          foreach($nodes[$id]['out'] as $m) {
              $nodes[$m]['in'] = array_diff($nodes[$m]['in'], array($id));
              if (empty($nodes[$m]['in'])) { $S[] = $m; }
          }
          $nodes[$id]['out'] = array();
      }
      foreach($nodes as $n) {
          if (!empty($n['in']) or !empty($n['out'])) {
              return null; // not sortable as graph is cyclic
          }
      }
      return $L;
  }
  </code></pre>
  
  <p>I looks nice and short. Anyways, for some input - I get duplicate lines in the output - see <a href="http://codepad.org/thpzCOyn" rel="noreferrer">http://codepad.org/thpzCOyn</a></p>
  
  <p>Generally the sorting seems to be correct if I remove the duplicates with <code>array_unique()</code></p>
  
  <p>I checked the function with two examples and the sorting itself looks correct.</p>
  
  <p>Should I just call <code>array_unique()</code> on the result?</p>