Diviner Arcanist Tech Docs AbstractDirectedGraph

abstract class AbstractDirectedGraph
Arcanist Technical Documentation ()

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

public function __get($name)
public function __set($name, $value)
public function current()
public function key()
public function next()
public function rewind()
public function valid()
private function throwOnAttemptedIteration()
public function getPhobjectClassConstant($key, $byte_limit) — Read the value of a class constant.
final public function getNodes()
final public function getNodesInTopologicalOrder() — Get the nodes in topological order.
final public function getNodesInRoughTopologicalOrder() — Get the nodes in topological order, or some roughly similar order if the graph contains cycles.

Methods

public function __get($name)
Inherited

This method is not documented.

Parameters

$name

Return

wild

public function __set($name, $value)
Inherited

This method is not documented.

Parameters

	$name
	$value

Return

wild

public function current()
Inherited

This method is not documented.

Return

wild

public function key()
Inherited

This method is not documented.

Return

wild

public function next()
Inherited

This method is not documented.

Return

wild

public function rewind()
Inherited

This method is not documented.

Return

wild

public function valid()
Inherited

This method is not documented.

Return

wild

private function throwOnAttemptedIteration()
Inherited

This method is not documented.

Return

wild

public function getPhobjectClassConstant($key, $byte_limit)
Inherited

Phobject

Read the value of a class constant.

This is the same as just typing self::CONSTANTNAME, but throws a more useful message if the constant is not defined and allows the constant to be limited to a maximum length.

Parameters

string	$key	Name of the constant.
int\|null	$byte_limit	Maximum number of bytes permitted in the value.

Return

string

Value of the constant.

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

$nodes

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.

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

$nodes

A 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

$node

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.

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	$node	The node to walk from.
list	$visited	Previously visited nodes.

Return

null|list

Null if no cycles are found, or a list of nodes which cycle.

Defined: src/utils/AbstractDirectedGraph.php:31
Extends: Phobject

abstract class AbstractDirectedGraphArcanist Technical Documentation ()

Tasks

Graph Construction

Cycle Detection

Graph Exploration

Other Methods

Methods

public function __get($name)Inherited

public function __set($name, $value)Inherited

public function current()Inherited

public function key()Inherited

public function next()Inherited

public function rewind()Inherited

public function valid()Inherited

private function throwOnAttemptedIteration()Inherited

public function getPhobjectClassConstant($key, $byte_limit)Inherited

abstract protected function loadEdges($nodes)

final public function addNodes($nodes)

final public function getNodes()

final public function getNodesInTopologicalOrder()

final public function getNodesInRoughTopologicalOrder()

final public function loadGraph()

final public function detectCycles($node)

private function performCycleDetection($node, $visited)

abstract class AbstractDirectedGraph
Arcanist Technical Documentation ()

public function __get($name)
Inherited

public function __set($name, $value)
Inherited

public function current()
Inherited

public function key()
Inherited

public function next()
Inherited

public function rewind()
Inherited

public function valid()
Inherited

private function throwOnAttemptedIteration()
Inherited

public function getPhobjectClassConstant($key, $byte_limit)
Inherited