Differential D20597 Diff 49148 src/utils/__tests__/AbstractDirectedGraphTestCase.php

Changeset View

Standalone View

src/utils/tests/AbstractDirectedGraphTestCase.php

Show First 20 Lines • Show All 71 Lines • ▼ Show 20 Lines	try {
$raised = $ex;		$raised = $ex;
}		}

$this->assertTrue(		$this->assertTrue(
(bool)$raised,		(bool)$raised,
pht('Exception raised by unloadable edges.'));		pht('Exception raised by unloadable edges.'));
}		}

public function testTopographicSortTree() {		public function testTopologicalOrder() {
$graph = array(		$graph = array(
'A' => array('B', 'C'),		'A' => array('B', 'C'),
'B' => array('D', 'E'),		'B' => array('D', 'E'),
'C' => array(),		'C' => array(),
'D' => array(),		'D' => array(),
'E' => array(),		'E' => array(),
);		);

$sorted = $this->getTopographicSort($graph);		$sorted = $this->getTopologicalOrder($graph);

$this->assertEqual(		$this->assertEqual(
array('A', 'C', 'B', 'E', 'D'),		array('A', 'C', 'B', 'E', 'D'),
$sorted,		$sorted,
pht('Topographically sorted tree.'));		pht('Topologically sorted tree.'));

$graph = array(		$graph = array(
'A' => array('B', 'C'),		'A' => array('B', 'C'),
'B' => array('C'),		'B' => array('C'),
'C' => array('D', 'E'),		'C' => array('D', 'E'),
'D' => array('E'),		'D' => array('E'),
'E' => array(),		'E' => array(),
);		);

$sorted = $this->getTopographicSort($graph);		$sorted = $this->getTopologicalOrder($graph);

$this->assertEqual(		$this->assertEqual(
array('A', 'B', 'C', 'D', 'E'),		array('A', 'B', 'C', 'D', 'E'),
$sorted,		$sorted,
pht('Topographically sorted tree with nesting.'));		pht('Topologically sorted tree with nesting.'));
}		}

public function testBestEffortTopographicSortTree() {		public function testRoughTopologicalOrder() {
$graph = array(		$graph = array(
'A' => array('B', 'C'),		'A' => array('B', 'C'),
'B' => array('D', 'E'),		'B' => array('D', 'E'),
'C' => array(),		'C' => array(),
'D' => array(),		'D' => array(),
'E' => array(),		'E' => array(),
'F' => array('H'),		'F' => array('H'),
'G' => array('F', 'E'),		'G' => array('F', 'E'),
'H' => array('G'),		'H' => array('G'),
);		);

$sorted = $this->getBestEffortTopographicSort($graph);		$sorted = $this->getRoughTopologicalOrder($graph);

$this->assertEqual(count($graph), count($sorted));		$this->assertEqual(count($graph), count($sorted));

$this->assertEqual('C', $sorted[0]['node']);		$this->assertEqual('C', $sorted[0]['node']);
$this->assertEqual('D', $sorted[1]['node']);		$this->assertEqual('D', $sorted[1]['node']);
$this->assertEqual('E', $sorted[2]['node']);		$this->assertEqual('E', $sorted[2]['node']);
$this->assertEqual('B', $sorted[3]['node']);		$this->assertEqual('B', $sorted[3]['node']);
$this->assertEqual('A', $sorted[4]['node']);		$this->assertEqual('A', $sorted[4]['node']);
Show All 23 Lines	final class AbstractDirectedGraphTestCase extends PhutilTestCase {
private function findGraphCycle(array $graph, $seed = 'A', $search = 'A') {		private function findGraphCycle(array $graph, $seed = 'A', $search = 'A') {
$detector = new TestAbstractDirectedGraph();		$detector = new TestAbstractDirectedGraph();
$detector->setTestData($graph);		$detector->setTestData($graph);
$detector->addNodes(array_select_keys($graph, array($seed)));		$detector->addNodes(array_select_keys($graph, array($seed)));
$detector->loadGraph();		$detector->loadGraph();
return $detector->detectCycles($search);		return $detector->detectCycles($search);
}		}

private function getTopographicSort(array $graph, $seed = 'A') {		private function getTopologicalOrder(array $graph, $seed = 'A') {
$detector = new TestAbstractDirectedGraph();		$detector = new TestAbstractDirectedGraph();
$detector->setTestData($graph);		$detector->setTestData($graph);
$detector->addNodes(array_select_keys($graph, array($seed)));		$detector->addNodes(array_select_keys($graph, array($seed)));
$detector->loadGraph();		$detector->loadGraph();
return $detector->getTopographicallySortedNodes();		return $detector->getNodesInTopologicalOrder();
}		}

private function getBestEffortTopographicSort(array $graph) {		private function getRoughTopologicalOrder(array $graph) {
$detector = new TestAbstractDirectedGraph();		$detector = new TestAbstractDirectedGraph();
$detector->setTestData($graph);		$detector->setTestData($graph);
$detector->addNodes(array_keys($graph));		$detector->addNodes(array_keys($graph));
return $detector->getBestEffortTopographicallySortedNodes();		return $detector->getNodesInRoughTopologicalOrder();
}		}

}		}