File Manager

Editing File: /home/ubuntu/code_review/arcanist/src/utils/AbstractDirectedGraph.php

<?php

/**
 * Models a directed graph in a generic way that works well with graphs stored
 * in a database, and allows you to perform operations like cycle detection.
 *
 * To use this class, seed it with a set of edges (e.g., the new candidate
 * edges the user is trying to create) using @{method:addNodes}, then
 * call @{method:loadGraph} to construct the graph.
 *
 *   $detector = new ExamplePhabricatorGraphCycleDetector();
 *   $detector->addNodes(
 *     array(
 *       $object->getPHID() => $object->getChildPHIDs(),
 *     ));
 *   $detector->loadGraph();
 *
 * Now you can query the graph, e.g. by detecting cycles:
 *
 *   $cycle = $detector->detectCycles($object->getPHID());
 *
 * If ##$cycle## is empty, no graph cycle is reachable from the node. If it
 * is nonempty, it contains a list of nodes which form a graph cycle.
 *
 * NOTE: Nodes must be represented with scalars.
 *
 * @task build Graph Construction
 * @task cycle Cycle Detection
 * @task explore Graph Exploration
 */
abstract class AbstractDirectedGraph extends Phobject {

private $knownNodes   = array();
  private $graphLoaded  = false;

/* -(  Graph Construction  )------------------------------------------------- */

/**
   * Load the edges for a list of nodes. You must override this method. You
   * will be passed a list of nodes, and should return a dictionary mapping
   * each node to the list of nodes that can be reached by following its the
   * edges which originate at it: for example, the child nodes of an object
   * which has a parent-child relationship to other objects.
   *
   * The intent of this method is to allow you to issue a single query per
   * graph level for graphs which are stored as edge tables in the database.
   * Generally, you will load all the objects which correspond to the list of
   * nodes, and then return a map from each of their IDs to all their children.
   *
   * NOTE: You must return an entry for every node you are passed, even if it
   * is invalid or can not be loaded. Either return an empty array (if this is
   * acceptable for your application) or throw an exception if you can't satisfy
   * this requirement.
   *
   * @param   list  A list of nodes.
   * @return  dict  A map of nodes to the nodes reachable along their edges.
   *                There must be an entry for each node you were provided.
   * @task build
   */
  abstract protected function loadEdges(array $nodes);

/**
   * Seed the graph with known nodes. Often, you will provide the candidate
   * edges that a user is trying to create here, or the initial set of edges
   * you know about.
   *
   * @param   dict  A map of nodes to the nodes reachable along their edges.
   * @return  this
   * @task build
   */
  final public function addNodes(array $nodes) {
    if ($this->graphLoaded) {
      throw new Exception(
        pht(
          'Call %s before calling %s. You can not add more nodes '.
          'once you have loaded the graph.',
          __FUNCTION__.'()',
          'loadGraph()'));
    }

$this->knownNodes += $nodes;
    return $this;
  }

final public function getNodes() {
    return $this->knownNodes;
  }

/**
   * Get the nodes in topological order.
   *
   * This method requires the graph be acyclic. For graphs which may contain
   * cycles, see @{method:getNodesInRoughTopologicalOrder}.
   */
  final public function getNodesInTopologicalOrder() {
    $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;
  }

/**
   * 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 getNodesInRoughTopologicalOrder() {
    $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.
   *
   * @return this
   * @task build
   */
  final public function loadGraph() {

$new_nodes = $this->knownNodes;
    while (true) {
      $load = array();
      foreach ($new_nodes as $node => $edges) {
        foreach ($edges as $edge) {
          if (!isset($this->knownNodes[$edge])) {
            $load[$edge] = true;
          }
        }
      }

if (empty($load)) {
        break;
      }

$load = array_keys($load);

$new_nodes = $this->loadEdges($load);
      foreach ($load as $node) {
        if (!isset($new_nodes[$node]) || !is_array($new_nodes[$node])) {
          throw new Exception(
            pht(
              '%s must return an edge list array for each provided '.
              'node, or the cycle detection algorithm may not terminate.',
              'loadEdges()'));
        }
      }

$this->addNodes($new_nodes);
    }

$this->graphLoaded = true;
    return $this;
  }

/* -(  Cycle Detection  )---------------------------------------------------- */

/**
   * Detect if there are any cycles reachable from a given node.
   *
   * If cycles are reachable, it returns a list of nodes which create a cycle.
   * Note that this list may include nodes which aren't actually part of the
   * cycle, but lie on the graph between the specified node and the cycle.
   * For example, it might return something like this (when passed "A"):
   *
   *    A, B, C, D, E, C
   *
   * This means you can walk from A to B to C to D to E and then back to C,
   * which forms a cycle. A and B are included even though they are not part
   * of the cycle. When presenting information about graph cycles to users,
   * including these nodes is generally useful. This also shouldn't ever happen
   * if you've vetted prior edges before writing them, because it means there
   * is a preexisting cycle in the graph.
   *
   * NOTE: This only detects cycles reachable from a node. It does not detect
   * cycles in the entire graph.
   *
   * @param   scalar    The node to walk from, looking for graph cycles.
   * @return  list|null Returns null if no cycles are reachable from the node,
   *                    or a list of nodes that form a cycle.
   * @task cycle
   */
  final public function detectCycles($node) {
    if (!$this->graphLoaded) {
      throw new Exception(
        pht(
          'Call %s to build the graph out before calling %s.',
          'loadGraph()',
          __FUNCTION__.'()'));
    }
    if (!isset($this->knownNodes[$node])) {
      throw new Exception(
        pht(
          "The node '%s' is not known. Call %s to seed the graph with nodes.",
          $node,
          'addNodes()'));
    }

$visited = array();
    return $this->performCycleDetection($node, $visited);
  }

/**
   * Internal cycle detection implementation. Recursively walks the graph,
   * keeping track of where it's been, and returns the first cycle it finds.
   *
   * @param   scalar      The node to walk from.
   * @param   list        Previously visited nodes.
   * @return  null|list   Null if no cycles are found, or a list of nodes
   *                      which cycle.
   * @task cycle
   */
  private function performCycleDetection($node, array $visited) {
    $visited[$node] = true;
    foreach ($this->knownNodes[$node] as $edge) {
      if (isset($visited[$edge])) {
        $result = array_keys($visited);
        $result[] = $edge;
        return $result;
      }
      $result = $this->performCycleDetection($edge, $visited);
      if ($result) {
        return $result;
      }
    }
    return null;
  }

}

Back to Directory File Manager