Diviner libphutil Tech Docs TestAbstractDirectedGraph

final class TestAbstractDirectedGraph
libphutil Technical Documentation (Core Utilities)

This class is not documented.

Tasks

Graph Construction

protected function loadEdges($nodes)
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.
public function setTestData($nodes)

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.

protected function loadEdges($nodes)

AbstractDirectedGraph

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.

TestAbstractDirectedGraph

This method is not documented.

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)
Inherited

AbstractDirectedGraph

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()
Inherited

This method is not documented.

Return

wild

final public function getNodesInTopologicalOrder()
Inherited

AbstractDirectedGraph

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()
Inherited

AbstractDirectedGraph

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()
Inherited

AbstractDirectedGraph

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)
Inherited

AbstractDirectedGraph

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)
Inherited

AbstractDirectedGraph

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.

public function setTestData($nodes)

This method is not documented.

Parameters

array

$nodes

Return

wild

Defined: src/utils/__tests__/TestAbstractDirectedGraph.php:3
Extends: PhobjectAbstractDirectedGraph

final class TestAbstractDirectedGraphlibphutil Technical Documentation (Core Utilities)

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

protected function loadEdges($nodes)

final public function addNodes($nodes)Inherited

final public function getNodes()Inherited

final public function getNodesInTopologicalOrder()Inherited

final public function getNodesInRoughTopologicalOrder()Inherited

final public function loadGraph()Inherited

final public function detectCycles($node)Inherited

private function performCycleDetection($node, $visited)Inherited

public function setTestData($nodes)

final class TestAbstractDirectedGraph
libphutil Technical Documentation (Core Utilities)

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

final public function addNodes($nodes)
Inherited

final public function getNodes()
Inherited

final public function getNodesInTopologicalOrder()
Inherited

final public function getNodesInRoughTopologicalOrder()
Inherited

final public function loadGraph()
Inherited

final public function detectCycles($node)
Inherited

private function performCycleDetection($node, $visited)
Inherited