Page MenuHomePhabricator
Files F14087528

D20597.diff
No OneTemporary
Actions

D20597.diff
View Options

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();
}
}

File Metadata

Mime Type
text/plain
Expires
Sun, Nov 24, 10:23 PM (21 h, 32 m)
Storage Engine
blob
Storage Format
Encrypted (AES-256-CBC)
Storage Handle
6784090
Default Alt Text
D20597.diff (4 KB)

Event Timeline

Phabricator · Built by Phacility