diff --git a/src/utils/AbstractDirectedGraph.php b/src/utils/AbstractDirectedGraph.php --- a/src/utils/AbstractDirectedGraph.php +++ b/src/utils/AbstractDirectedGraph.php @@ -91,15 +91,12 @@ } /** - * Utility function to get a list of topographically sorted nodes out of a - * graph. + * Get the nodes in topological order. * - * This could be useful for example to figure out what order you can safely - * apply dependencies. - * - * Note this will loop indefinitely if the graph has a cycle. + * This method requires the graph be acyclic. For graphs which may contain + * cycles, see @{method:getNodesInRoughTopologicalOrder}. */ - final public function getTopographicallySortedNodes() { + final public function getNodesInTopologicalOrder() { $sorted = array(); $nodes = $this->getNodes(); @@ -145,10 +142,17 @@ } /** - * Utility function to get the best effort topographically sorted - * nodes out of a graph. + * Get the nodes in topological order, or some roughly similar order if + * the graph contains cycles. + * + * This method will return an ordering for cyclic graphs. The method will + * attempt to make it look like a topological ordering, but since cyclic + * graphs have no complete toplogical ordering, you might get anything. + * + * If you know the graph is acyclic and want an actual topological order, + * use @{method:getNodesInTopologicalOrder}. */ - final public function getBestEffortTopographicallySortedNodes() { + final public function getNodesInRoughTopologicalOrder() { $nodes = $this->getNodes(); $edges = $this->loadEdges($nodes); diff --git a/src/utils/__tests__/AbstractDirectedGraphTestCase.php b/src/utils/__tests__/AbstractDirectedGraphTestCase.php --- a/src/utils/__tests__/AbstractDirectedGraphTestCase.php +++ b/src/utils/__tests__/AbstractDirectedGraphTestCase.php @@ -77,7 +77,7 @@ pht('Exception raised by unloadable edges.')); } - public function testTopographicSortTree() { + public function testTopologicalOrder() { $graph = array( 'A' => array('B', 'C'), 'B' => array('D', 'E'), @@ -86,12 +86,12 @@ 'E' => array(), ); - $sorted = $this->getTopographicSort($graph); + $sorted = $this->getTopologicalOrder($graph); $this->assertEqual( array('A', 'C', 'B', 'E', 'D'), $sorted, - pht('Topographically sorted tree.')); + pht('Topologically sorted tree.')); $graph = array( 'A' => array('B', 'C'), @@ -101,15 +101,15 @@ 'E' => array(), ); - $sorted = $this->getTopographicSort($graph); + $sorted = $this->getTopologicalOrder($graph); $this->assertEqual( array('A', 'B', 'C', 'D', 'E'), $sorted, - pht('Topographically sorted tree with nesting.')); + pht('Topologically sorted tree with nesting.')); } - public function testBestEffortTopographicSortTree() { + public function testRoughTopologicalOrder() { $graph = array( 'A' => array('B', 'C'), 'B' => array('D', 'E'), @@ -121,7 +121,7 @@ 'H' => array('G'), ); - $sorted = $this->getBestEffortTopographicSort($graph); + $sorted = $this->getRoughTopologicalOrder($graph); $this->assertEqual(count($graph), count($sorted)); @@ -161,19 +161,19 @@ return $detector->detectCycles($search); } - private function getTopographicSort(array $graph, $seed = 'A') { + private function getTopologicalOrder(array $graph, $seed = 'A') { $detector = new TestAbstractDirectedGraph(); $detector->setTestData($graph); $detector->addNodes(array_select_keys($graph, array($seed))); $detector->loadGraph(); - return $detector->getTopographicallySortedNodes(); + return $detector->getNodesInTopologicalOrder(); } - private function getBestEffortTopographicSort(array $graph) { + private function getRoughTopologicalOrder(array $graph) { $detector = new TestAbstractDirectedGraph(); $detector->setTestData($graph); $detector->addNodes(array_keys($graph)); - return $detector->getBestEffortTopographicallySortedNodes(); + return $detector->getNodesInRoughTopologicalOrder(); } }