Page MenuHomePhabricator
Diviner Arcanist Tech Docs ArcanistDifferentialDependencyGraph

final class ArcanistDifferentialDependencyGraph
Arcanist Technical Documentation ()

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

Methods

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.
ArcanistDifferentialDependencyGraph
This method is not documented.
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)
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$nodesA 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$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)
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$nodeThe node to walk from.
list$visitedPreviously visited nodes.
Return
null|listNull if no cycles are found, or a list of nodes which cycle.

public function setStartPHID($start_phid)

This method is not documented.
Parameters
$start_phid
Return
wild

public function getStartPHID()

This method is not documented.
Return
wild

public function setRepositoryAPI($repository_api)

This method is not documented.
Parameters
ArcanistRepositoryAPI$repository_api
Return
wild

public function getRepositoryAPI()

This method is not documented.
Return
wild

public function setConduit($conduit)

This method is not documented.
Parameters
ConduitClient$conduit
Return
wild

public function getConduit()

This method is not documented.
Return
wild

private function getCommitHashFromDict($dict)

This method is not documented.
Parameters
$dict
Return
wild
Defined
src/differential/ArcanistDifferentialDependencyGraph.php:3
Extends
AbstractDirectedGraph
Phabricator · Built by Phacility