D9956.id23974.diff
No OneTemporary
Actions

Size

1 KB

Referenced Files

None

Subscribers

None

D9956.id23974.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,70 @@
	}

	/**
	+ * Utility function to get the best effort of a list of rows of
	+ * topographically sorted nodes out of a graph.
	+ */
	+ final public function getBestEffortTopographicallySortedNodesByRow() {
	+ $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.
	+ $depth++;
	+ break;
	+ }
	+
	+ foreach ($next as $node) {
	+ $results[] = array(
	+ 'node' => $next,
	+ 'depth' => $depth,
	+ 'cycle' => false);
	+
	+ $completed[$node] = true;
	+ }
	+
	+ $depth++;
	+ }
	+
	+ foreach ($nodes as $node) {
	+ if (!isset($completed, $edge)) {
	+ $results[] = array(
	+ 'node' => $next,
	+ 'depth' => $depth,
	+ 'cycle' => false);
	+ }
	+ }
	+
	+ 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.