Page MenuHomePhabricator
Files F13972738

D9956.id.diff
No OneTemporary
Actions

D9956.id.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
@@ -142,6 +142,69 @@
}
/**
+ * Utility function to get the best effort topographically sorted
+ * nodes out of a graph.
+ */
+ final public function getBestEffortTopographicallySortedNodes() {
+ $nodes = $this->getNodes();
+ $edges = $this->loadEdges($nodes);
+
+ $results = array();
+ $completed = array();
+
+ $depth = 0;
+ while (true) {
+ $next = array();
+
+ foreach ($nodes as $node) {
+ if (isset($completed[$node])) {
+ continue;
+ }
+
+ $capable = true;
+ foreach ($edges[$node] as $edge) {
+ if (!isset($completed[$edge])) {
+ $capable = false;
+ break;
+ }
+ }
+
+ if ($capable) {
+ $next[] = $node;
+ }
+ }
+
+ if (count($next) === 0) {
+ // No more nodes to traverse; we are deadlocked if the number
+ // of completed nodes is less than the total number of nodes.
+ break;
+ }
+
+ foreach ($next as $node) {
+ $results[] = array(
+ 'node' => $node,
+ 'depth' => $depth,
+ 'cycle' => false);
+
+ $completed[$node] = true;
+ }
+
+ $depth++;
+ }
+
+ foreach ($nodes as $node) {
+ if (!isset($completed[$node])) {
+ $results[] = array(
+ 'node' => $node,
+ 'depth' => $depth,
+ 'cycle' => true);
+ }
+ }
+
+ return $results;
+ }
+
+ /**
* Load the graph, building it out so operations can be performed on it. This
* constructs the graph level-by-level, calling @{method:loadEdges} to
* expand the graph at each stage until it is complete.
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
@@ -109,6 +109,50 @@
'Topographically sorted tree with nesting.');
}
+ public function testBestEffortTopographicSortTree() {
+ $graph = array(
+ 'A' => array('B', 'C'),
+ 'B' => array('D', 'E'),
+ 'C' => array(),
+ 'D' => array(),
+ 'E' => array(),
+ 'F' => array('H'),
+ 'G' => array('F', 'E'),
+ 'H' => array('G'),
+ );
+
+ $sorted = $this->getBestEffortTopographicSort($graph);
+
+ $this->assertEqual(count($graph), count($sorted));
+
+ $this->assertEqual('C', $sorted[0]['node']);
+ $this->assertEqual('D', $sorted[1]['node']);
+ $this->assertEqual('E', $sorted[2]['node']);
+ $this->assertEqual('B', $sorted[3]['node']);
+ $this->assertEqual('A', $sorted[4]['node']);
+ $this->assertEqual('F', $sorted[5]['node']);
+ $this->assertEqual('G', $sorted[6]['node']);
+ $this->assertEqual('H', $sorted[7]['node']);
+
+ $this->assertEqual(0, $sorted[0]['depth']);
+ $this->assertEqual(0, $sorted[1]['depth']);
+ $this->assertEqual(0, $sorted[2]['depth']);
+ $this->assertEqual(1, $sorted[3]['depth']);
+ $this->assertEqual(2, $sorted[4]['depth']);
+ $this->assertEqual(3, $sorted[5]['depth']);
+ $this->assertEqual(3, $sorted[6]['depth']);
+ $this->assertEqual(3, $sorted[7]['depth']);
+
+ $this->assertEqual(false, $sorted[0]['cycle']);
+ $this->assertEqual(false, $sorted[1]['cycle']);
+ $this->assertEqual(false, $sorted[2]['cycle']);
+ $this->assertEqual(false, $sorted[3]['cycle']);
+ $this->assertEqual(false, $sorted[4]['cycle']);
+ $this->assertEqual(true, $sorted[5]['cycle']);
+ $this->assertEqual(true, $sorted[6]['cycle']);
+ $this->assertEqual(true, $sorted[7]['cycle']);
+ }
+
private function findGraphCycle(array $graph, $seed = 'A', $search = 'A') {
$detector = new TestAbstractDirectedGraph();
$detector->setTestData($graph);
@@ -125,4 +169,11 @@
return $detector->getTopographicallySortedNodes();
}
+ private function getBestEffortTopographicSort(array $graph) {
+ $detector = new TestAbstractDirectedGraph();
+ $detector->setTestData($graph);
+ $detector->addNodes(array_keys($graph));
+ return $detector->getBestEffortTopographicallySortedNodes();
+ }
+
}

File Metadata

Mime Type
text/plain
Expires
Fri, Oct 18, 8:58 PM (2 w, 6 d ago)
Storage Engine
blob
Storage Format
Encrypted (AES-256-CBC)
Storage Handle
6728702
Default Alt Text
D9956.id.diff (4 KB)

Event Timeline

Phabricator · Built by Phacility