Iterators

The primary means of interacting with a graph's structure is through iteration. Graphs being the tricky beasts they are, though, there are number of different ways to iterate through them. This page explores the different basic iteration mechanisms Gliph guarantees via its interfaces.

While there are a lot of ways to enumerate a graph, care has been taken to ensure that these ways follow a easily-predictable pattern. The goal is for them to be obvious enough that this documentation starts seeming redundant before you even finish reading it.

Undirected Iteration

Undirected graphs are the more general case, and have only four iterators, so they’re the simpler place to start. Let’s create one as follows:

<?php

use Gliph\Graph\UndirectedAdjacencyList;

class Vertex {
    public $val;

    public function __construct($val) {
        $this->val = $val;
    }
}

$vertices = array(
    'a' => new Vertex('a'),
    'b' => new Vertex('b'),
    'c' => new Vertex('c'),
    'd' => new Vertex('d'),
    'e' => new Vertex('e'),
    'f' => new Vertex('f'),
);

$g = new UndirectedAdjacencyList();

foreach ($vertices as $vertex) {
    $g->ensureVertex($vertex);
}

$g->ensureArc($vertices['a'], $vertices['b']);
$g->ensureArc($vertices['b'], $vertices['c']);
$g->ensureArc($vertices['a'], $vertices['c']);
$g->ensureArc($vertices['d'], $vertices['a']);
$g->ensureArc($vertices['d'], $vertices['e']);

Here’s that graph, drawn out:

Iterators mostly come in pairs - for each type of walk, you can generally receive either vertices or edges.

All the things

First is Graph::vertices(), which enumerates all the vertices in the graph.

foreach ($g->vertices() as $vertex) {
    // called once for each vertex in the graph
}

(Visited objects are marked in blue)

The edge equivalent is Graph::edges(), which enumerates all edges in the graph.

foreach ($g->edges() as $edge) {
    // called once for each edge in the graph
}

Note that it is an implicit guarantee that there will be exactly one pass through the loop for each relevant datum - calling code should never have to deduplicate vertices or edges.

Note also, however, that there is no guarantee as to the order in which an iterator produces results. Reliance on a particular order is an implicit bug.

Adjacency and Incidence

Graph::adjacentTo() is next. It traverses the set of vertices that are adjacent to the provided vertex.

foreach ($g->adjacentTo($vertices[‘a’]) as $vertex) {
    // called once for each vertex adjacent to ‘a’ - 3 times.
}

Next is Graph::incidentTo(), which explores the same relationship, but returns the edge information instead.

foreach ($g->incidentTo($vertices[‘a’]) as $vertex) {
    // called once for each edge incident to ‘a’ - 3 times.
}

Directed Iteration

Digraphs have four iterators on top of vertices(), edges(), adjacentTo() and incidentTo() that specifically exploit directedness. Here’s the same graph again, but this time with a directed flavor:

<?php

use Gliph\Graph\DirectedAdjacencyList;

class Vertex {
    public $val;

    public function __construct($val) {
        $this->val = $val;
    }
}

$vertices = array(
    'a' => new Vertex('a'),
    'b' => new Vertex('b'),
    'c' => new Vertex('c'),
    'd' => new Vertex('d'),
    'e' => new Vertex('e'),
    'f' => new Vertex('f'),
);

$g = new DirectedAdjacencyList();

foreach ($vertices as $vertex) {
    $g->ensureVertex($vertex);
}

$g->ensureArc($vertices['a'], $vertices['b']);
$g->ensureArc($vertices['b'], $vertices['c']);
$g->ensureArc($vertices['a'], $vertices['c']);
$g->ensureArc($vertices['d'], $vertices['a']);
$g->ensureArc($vertices['d'], $vertices['e']);

Even though we have this extra directedness information, the behavior of the four main iterators is the same:

foreach ($g->vertices() as $vertex) {
    // called once for each vertex in the graph
}

foreach ($g->edges() as $edge) {
    // called once for each arc in the graph
}

foreach ($g->adjacentTo($vertices[‘a’]) as $vertex) {
    // called once for each vertex adjacent to ‘a’ - 3 times.
    // edge direction has no effect.
}

foreach ($g->incidentTo($vertices[‘a’]) as $vertex) {
    // called once for each edge incident to ‘a’ - 3 times.
    // edge direction has no effect.
}

Outbound

Digraphs have a pair of methods for dealing with outbound arcs. For vertices, it is Digraph::successorsOf():

foreach ($g->successorsOf($vertices[‘a’]) as $vertex) {
    // called once for each vertex successor to ‘a’ - 2 times.
}

To get the edges in that same relationship, you call Digraph::arcsFrom():

foreach ($g->arcsFrom($vertices[‘a’]) as $vertex) {
    // called once for each arc outbound from ‘a’ - 2 times.
}

Inbound

Digraphs also have a pair of methods for dealing with inbound arcs. For vertices, it is Digraph::predecessorsOf();

foreach ($g->predecessorsOf($vertices[‘a’]) as $vertex) {
    // called once for each vertex predecessor to ‘a’ - 1 time.
}

And for the edges, you call Digraph::arcsTo():

foreach ($g->arcsTo($vertices[‘a’]) as $vertex) {
    // called once for each arc inbound from ‘a’ - 1 time.
}