1. class
  2. Drupal
  3. \
  4. Component
  5. \
  6. Graph
  7. \
  8. Graph

Graph

class Graph (View source)

Directed acyclic graph manipulation.

Properties

protected $graph

Holds the directed acyclic graph.

Methods

__construct($graph)

Instantiates the depth first search object.

The
searchAndSort()

Performs a depth-first search and sort on the directed acyclic graph.

depthFirstSearch($state, $start, $component = NULL)

Performs a depth-first search on a graph.

Details

at line 40
__construct($graph)

Instantiates the depth first search object.

Parameters

$graph

A three dimensional associated array, with the first keys being the names of the vertices, these can be strings or numbers. The second key is 'edges' and the third one are again vertices, each such key representing an edge. Values of array elements are copied over.

Example: @code $graph[1]['edges'][2] = 1; $graph[2]['edges'][3] = 1; $graph[2]['edges'][4] = 1; $graph[3]['edges'][4] = 1; @endcode

On return you will also have: @code $graph[1]['paths'][2] = 1; $graph[1]['paths'][3] = 1; $graph[2]['reverse_paths'][1] = 1; $graph[3]['reverse_paths'][1] = 1; @endcode

at line 58
The searchAndSort()

Performs a depth-first search and sort on the directed acyclic graph.

Return Value

The

given $graph with more secondary keys filled in:

  • 'paths': Contains a list of vertices than can be reached on a path from this vertex.
  • 'reverse_paths': Contains a list of vertices that has a path from them to this vertex.
  • 'weight': If there is a path from a vertex to another then the weight of the latter is higher.
  • 'component': Vertices in the same component have the same component identifier.

at line 101
protected depthFirstSearch($state, $start, $component = NULL)

Performs a depth-first search on a graph.

Parameters

$state

An associative array. The key 'last_visit_order' stores a list of the vertices visited. The key components stores list of vertices belonging to the same the component.
$start

An arbitrary vertex where we started traversing the graph.
$component

The component of the last vertex.

See also

Graph::searchAndSort