Page MenuHomePhabricator
Diviner libphutil Tech Docs AbstractDirectedGraph

abstract class AbstractDirectedGraph
libphutil Technical Documentation (Core Utilities)

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 addNodes(), then call 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.

Tasks

Graph Construction

  • abstract protected function loadEdges($nodes) — 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.
  • final public function addNodes($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.
  • final public function loadGraph() — 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.

Cycle Detection

  • final public function detectCycles($node) — Detect if there are any cycles reachable from a given node.
  • private function 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.

Graph Exploration

No methods for this task.

Other Methods

Methods

abstract protected function loadEdges($nodes)

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.
Parameters
list$nodesA list of nodes.
Return
dictA map of nodes to the nodes reachable along their edges. There must be an entry for each node you were provided.

final public function addNodes($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.

Parameters
dict$nodesA map of nodes to the nodes reachable along their edges.
Return
this

final public function getNodes()

This method is not documented.
Return
wild

final public function getNodesInTopologicalOrder()

Get the nodes in topological order.

This method requires the graph be acyclic. For graphs which may contain cycles, see getNodesInRoughTopologicalOrder().

Return
wild

final public function getNodesInRoughTopologicalOrder()

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 getNodesInTopologicalOrder().

Return
wild

final public function loadGraph()

Load the graph, building it out so operations can be performed on it. This constructs the graph level-by-level, calling loadEdges() to expand the graph at each stage until it is complete.

Return
this

final public function detectCycles($node)

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.
Parameters
scalar$nodeThe node to walk from, looking for graph cycles.
Return
list|nullReturns null if no cycles are reachable from the node, or a list of nodes that form a cycle.

private function 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.

Parameters
scalar$nodeThe node to walk from.
list$visitedPreviously visited nodes.
Return
null|listNull if no cycles are found, or a list of nodes which cycle.
Defined
src/utils/AbstractDirectedGraph.php:31
Phabricator · Built by Phacility