Page Menu
Home
Phorge
Search
Configure Global Search
Log In
Files
F2680414
AbstractDirectedGraph.php
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Award Token
Flag For Later
Advanced/Developer...
View Handle
View Hovercard
Size
10 KB
Referenced Files
None
Subscribers
None
AbstractDirectedGraph.php
View Options
<?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 $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.
* @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 $nodes 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 $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.
* @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 $node The node to walk from.
* @param list $visited 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
;
}
}
File Metadata
Details
Attached
Mime Type
text/x-php
Expires
Thu, Dec 19, 17:02 (22 h, 10 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
1014870
Default Alt Text
AbstractDirectedGraph.php (10 KB)
Attached To
Mode
rARC Arcanist
Attached
Detach File
Event Timeline
Log In to Comment