Structures_Graph Tutorial
A first tour of graph datastructure manipulation
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:
and passing the constructor a flag telling it whether the graph should be directed. A directed graph will always be directed during its lifetime. It's a permanent characteristic.
To fill out the graph, we'll need to create some nodes, and then call Graph::addNode.
addNode(&$nodeOne);
$directedGraph->addNode(&$nodeTwo);
$directedGraph->addNode(&$nodeThree);
]]>
and then setup the arcs:
connectTo($nodeTwo);
$nodeOne->connectTo($nodeThree);
]]>
Note that arcs can only be created after the nodes have been inserted into the graph.
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.
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:
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:
inDegree());
print("NodeOne's outDegree: " . $nodeOne->outDegree());
// and naturally, nodes can report on their arcs
$arcs = $nodeOne->getNeighbours();
for ($i=0;$igetData());
}
]]>