Structures_Graph Tutorial

Introduction

Structures_Graph is a package for creating and manipulating graph datastructures. A graph is a set of objects, called nodes, connected by arcs. When used as a datastructure, usually nodes contain data, and arcs represent relationships between nodes. When arcs have a direction, and can be travelled only one way, graphs are said to be directed. When arcs have no direction, and can always be travelled both ways, graphs are said to be non directed.

Structures_Graph provides an object oriented API to create and directly query a graph, as well as a set of Manipulator classes to extract information from the graph.

Creating a Graph

Creating a graph is done using the simple constructor:

require_once 'Structures/Graph.php';

$directedGraph =& new Structures_Graph(true);
$nonDirectedGraph =& new Structures_Graph(false);
    

To fill out the graph, we'll need to create some nodes, and then call Graph::addNode.

require_once 'Structures/Graph/Node.php';

$nodeOne =& new Structures_Graph_Node();
$nodeTwo =& new Structures_Graph_Node();
$nodeThree =& new Structures_Graph_Node();

$directedGraph->addNode(&$nodeOne);
$directedGraph->addNode(&$nodeTwo);
$directedGraph->addNode(&$nodeThree);
    

$nodeOne->connectTo($nodeTwo);
$nodeOne->connectTo($nodeThree);
    

Associating Data

Graphs are only useful as datastructures if they can hold data. Structure_Graph stores data in nodes. Each node contains a setter and a getter for its data.

$nodeOne->setData("Node One's Data is a String");
$nodeTwo->setData(1976);
$nodeThree->setData('Some other string');

print("NodeTwo's Data is an integer: " . $nodeTwo->getData());
    

Structure_Graph nodes can also store metadata, alongside with the main data. Metadata differs from regular data just because it is stored under a key, making it possible to store more than one data reference per node. The metadata getter and setter need the key to perform the operation:

$nodeOne->setMetadata('example key', "Node One's Sample Metadata");
print("Metadata stored under key 'example key' in node one: " . $nodeOne->getMetadata('example key'));
$nodeOne->unsetMetadata('example key');
    

Querying a Graph

Structures_Graph provides for basic querying of the graph:

// Nodes are able to calculate their indegree and outdegree
print("NodeOne's inDegree: " . $nodeOne->inDegree());
print("NodeOne's outDegree: " . $nodeOne->outDegree());

// and naturally, nodes can report on their arcs
$arcs = $nodeOne->getNeighbours();
for ($i=0;$i<sizeof($arcs);$i++) {
    print("NodeOne has an arc to " . $arcs[$i]->getData());
}