Page MenuHomePhabricator
Files F15385365

D7315.id16497.diff
No OneTemporary
Actions

D7315.id16497.diff
View Options

Index: src/utils/AbstractDirectedGraph.php
===================================================================
--- src/utils/AbstractDirectedGraph.php
+++ src/utils/AbstractDirectedGraph.php
@@ -86,6 +86,63 @@
return $this;
}
+ final public function getNodes() {
+ return $this->knownNodes;
+ }
+
+ /**
+ * Utility function to get a list of topographically sorted nodes out of a
+ * graph.
+ *
+ * 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.
+ */
+ final public function getTopographicallySortedNodes() {
+ $sorted = array();
+ $nodes = $this->getNodes();
+
+ $inverse_map = array();
+ foreach ($nodes as $node => $edges) {
+ if (!isset($inverse_map[$node])) {
+ $inverse_map[$node] = array();
+ }
+ foreach ($edges as $edge) {
+ if (!isset($inverse_map[$edge])) {
+ $inverse_map[$edge] = array();
+ }
+ $inverse_map[$edge][$node] = $node;
+ }
+ }
+
+ $end_nodes = array();
+ foreach ($inverse_map as $node => $edges) {
+ if (empty($edges)) {
+ $end_nodes[] = $node;
+ }
+ }
+
+ while (!empty($end_nodes)) {
+ $current_node = array_pop($end_nodes);
+ $sorted[] = $current_node;
+ $current_edges = $nodes[$current_node];
+ foreach ($current_edges as $index => $current_edge) {
+ // delete the edge from the normal map
+ unset($nodes[$current_node][$index]);
+ // and from the inverse map which is modestly trickier
+ $inverse_nodes = $inverse_map[$current_edge];
+ unset($inverse_nodes[$current_node]);
+ $inverse_map[$current_edge] = $inverse_nodes;
+ // no more edges means this is an "end node" now
+ if (empty($inverse_map[$current_edge])) {
+ $end_nodes[] = $current_edge;
+ }
+ }
+ }
+
+ return $sorted;
+ }
/**
* Load the graph, building it out so operations can be performed on it. This
Index: src/utils/__tests__/AbstractDirectedGraphTestCase.php
===================================================================
--- src/utils/__tests__/AbstractDirectedGraphTestCase.php
+++ src/utils/__tests__/AbstractDirectedGraphTestCase.php
@@ -81,6 +81,38 @@
'Exception raised by unloadable edges.');
}
+ public function testTopographicSortTree() {
+ $graph = array(
+ 'A' => array('B', 'C'),
+ 'B' => array('D', 'E'),
+ 'C' => array(),
+ 'D' => array(),
+ 'E' => array()
+ );
+
+ $sorted = $this->getTopographicSort($graph);
+
+ $this->assertEqual(
+ array('A', 'C', 'B', 'E', 'D'),
+ $sorted,
+ 'Topographically sorted tree.');
+
+ $graph = array(
+ 'A' => array('B', 'C'),
+ 'B' => array('C'),
+ 'C' => array('D', 'E'),
+ 'D' => array('E'),
+ 'E' => array()
+ );
+
+ $sorted = $this->getTopographicSort($graph);
+
+ $this->assertEqual(
+ array('A', 'B', 'C', 'D', 'E'),
+ $sorted,
+ 'Topographically sorted tree with nesting.');
+ }
+
private function findGraphCycle(array $graph, $seed = 'A', $search = 'A') {
$detector = new TestAbstractDirectedGraph();
$detector->setTestData($graph);
@@ -88,4 +120,12 @@
$detector->loadGraph();
return $detector->detectCycles($search);
}
+
+ private function getTopographicSort(array $graph, $seed = 'A') {
+ $detector = new TestAbstractDirectedGraph();
+ $detector->setTestData($graph);
+ $detector->addNodes(array_select_keys($graph, array($seed)));
+ $detector->loadGraph();
+ return $detector->getTopographicallySortedNodes();
+ }
}

File Metadata

Mime Type
text/plain
Expires
Sat, Mar 15, 10:22 PM (6 d, 17 h ago)
Storage Engine
blob
Storage Format
Encrypted (AES-256-CBC)
Storage Handle
7660528
Default Alt Text
D7315.id16497.diff (3 KB)

Event Timeline

Phabricator · Built by Phacility