graph algo for calculating a TSL based on a DAG, but respecting optimal groupings

DirectedAdjacencyGraph.php

<?php

namespace Gliph;

class DirectedAdjacencyGraph {
    protected $vertices;

    protected $vertexTypes;

    public function __construct() {
        $this->vertices = new \SplObjectStorage();
    }

    public function addVertex($vertex) {
        if (!$this->hasVertex($vertex)) {
            $this->vertices[$vertex] = new \SplObjectStorage();
        }
    }

    public function addDirectedEdge($from, $to) {
        $this->addVertex($from);
        $this->addVertex($to);
        $this->vertices[$from]->attach($to);
    }

    public function removeVertex($vertex) {
        unset($this->vertices[$vertex]);
        $this->eachVertex(function($v, $outgoing) use ($vertex) {
            if ($outgoing->contains($vertex)) {
                $outgoing->detach($vertex);
            }
        });
    }

    public function removeEdge($from, $to) {
        $this->vertices[$from]->detach($to);
    }

    public function eachAdjacent($vertex, $callback) {
        foreach ($this->vertices[$vertex] as $e) {
            call_user_func($callback, $e);
        }
    }

    public function eachVertex($callback) {
        $this->fev(function ($v, $outgoing) use ($callback) {
            call_user_func($callback, $v, $outgoing);
        });
    }

    public function eachEdge($callback) {
        $edges = array();
        $this->fev(function ($from, $outgoing) use (&$edges) {
            foreach ($outgoing as $to) {
                $arr = new \SplFixedArray(2);
                $arr[0] = $from;
                $arr[1] = $to;
                $edges[] = $arr;
            }
        });

        foreach ($edges as $edge) {
            call_user_func($callback, $edge);
        }
    }

    public function hasVertex($vertex) {
        return $this->vertices->contains($vertex);
    }

    protected function fev($callback) {
        foreach ($this->vertices as $vertex) {
            $outgoing = $this->vertices->getInfo();
            $callback($vertex, $outgoing);
        }
    }

    /**
     * Returns the transpose of this graph.
     *
     * A transpose is identical to the current graph, except that
     * its edges have had their directionality reversed.
     *
     * Also sometimes known as the 'reverse' or 'converse'.
     *
     * @return DirectedAdjacencyGraph
     */
    public function transpose() {
        $graph = new self();
        $this->eachEdge(function($edge) use (&$graph) {
            $graph->addDirectedEdge($edge[1], $edge[0]);
        });

        return $graph;
    }

    public function getCycles() {
        $tarjan = new Tarjan();
        $scc = $tarjan->getCycles($this);
        return $scc->count() > 0 ? $scc : FALSE;
    }
}

example.php

<?php

require_once __DIR__ . '/../vendor/autoload.php';

// Set up some dummy vertices
$a = new stdClass(); $a->val = 'a';
$b = new stdClass(); $b->val = 'b';
$c = new stdClass(); $c->val = 'c';
$d = new stdClass(); $d->val = 'd';
$e = new stdClass(); $e->val = 'e';
$f = new stdClass(); $f->val = 'f';
$g = new stdClass(); $g->val = 'g';
$h = new stdClass(); $h->val = 'h';
$i = new stdClass(); $i->val = 'i';
$j = new stdClass(); $j->val = 'j';

// Connect them into an acyclic graph
$graph2 = new Gliph\DirectedAdjacencyGraph();
$graph2->addVertex($a);
$graph2->addVertex($b);
$graph2->addDirectedEdge($c, $f);
$graph2->addDirectedEdge($d, $g);
$graph2->addDirectedEdge($c, $a);
$graph2->addDirectedEdge($e, $b);
$graph2->addDirectedEdge($f, $e);
$graph2->addDirectedEdge($g, $e);
$graph2->addDirectedEdge($h, $j);
$graph2->addDirectedEdge($i, $b);
$graph2->addDirectedEdge($j, $b);

// Create an incidence graph representing the optimal groupings
$ggraph = new \Gliph\IncidenceGraph();
$group1 = new stdClass();
$group1->vertices = array($a, $b, $c, $d);
$group2 = new stdClass();
$group2->vertices = array($e, $f, $g);
$group3 = new stdClass();
$group3->vertices = array($h, $i, $j);
$group1->inDegrees = $group2->inDegrees = $group3->inDegrees = array();
$groups = array($group1, $group2, $group3);

foreach ($groups as $group) {
    $vertices = array();
    foreach ($group->vertices as $vertex) {
        $vertices = !empty($vertices) ? $vertices : $group->vertices;
        $vertices = array_splice($vertices, array_search($vertex, $vertices), 1);
        foreach ($vertices as $adjacent) {
            $ggraph->addEdge($vertex, $adjacent);
        }
    }
}

// traverse, then dump the results
$tsl = grouped_depth_first_search($graph2->transpose(), $ggraph, $b);
$vertices = array();
foreach ($tsl as $vertex) {
    $vertices[] = $vertex->val;
}
print "\nOutput:\n";
print implode(', ', $vertices);


function grouped_depth_first_search(\Gliph\DirectedAdjacencyGraph $depgraph, \Gliph\IncidenceGraph $groupgraph, $start = NULL) {
    // Create an initial set of vertices to enqueue.
    $queue = new SplDoublyLinkedList();
    if ($start === NULL) {
        // No start vertex provided - find all appropriate ones.
        $incomings = new SplObjectStorage();
        $depgraph->eachEdge(function ($edge) use (&$incomings) {
            if (!isset($incomings[$edge[1]])) {
                $incomings[$edge[1]] = new \SplObjectStorage();
            }
            $incomings[$edge[1]]->attach($edge[0]);
        });

        // Prime the queue with vertices that have no incoming edges.
        $depgraph->eachVertex(function($vertex) use (&$queue, &$incomings, &$that) {
            if (!$incomings->contains($vertex)) {
                $queue->push($vertex);
            }
        });
    }
    else {
        $queue->push($start);
    }

    $visiting = new SplObjectStorage();
    $visited = new SplObjectStorage();
    $tsl = new SplQueue();

    // The DFS recursive search algorithm, in a closure
    $visit = function($vertex) use ($depgraph, $groupgraph, &$visit, $visiting, $visited, $tsl) {
        if (!$visiting->contains($vertex) && !$visited->contains($vertex)) {
            $visiting->attach($vertex);

            // First, visit directed vertices expressed in the depgraph (standard DFS)
            $depgraph->eachAdjacent($vertex, $visit);
            // Then, visit undirected adjacent vertices from the group graph (special twist!)
            $groupgraph->eachAdjacent($vertex, $visit);

            $visiting->detach($vertex);
            $visited->attach($vertex);
            $tsl->push($vertex);
        }
    };

    while (!$queue->isEmpty()) {
        $vertex = $queue->shift();
        $visit($vertex);
    }

    return $tsl;
}

IncidenceGraph.php

<?php

namespace Gliph;

class IncidenceGraph {

    protected $vertices;

    public function __construct() {
        $this->vertices = new \SplObjectStorage();
    }

    public function addVertex($vertex) {
        if (!$this->hasVertex($vertex)) {
            $this->vertices[$vertex] = new \SplObjectStorage();
        }
    }

    public function addEdge($from, $to) {
        $this->addVertex($from);
        $this->addVertex($to);
        $this->vertices[$from]->attach($to);
        $this->vertices[$to]->attach($from);
    }

    public function removeVertex($vertex) {
        foreach ($this->vertices[$vertex] as $adjacent) {
            $this->vertices[$adjacent]->detach($vertex);
        }
        unset($this->vertices[$vertex]);
    }

    public function removeEdge($from, $to) {
        $this->vertices[$from]->detach($to);
        $this->vertices[$to]->detach($from);
    }

    public function eachAdjacent($vertex, $callback) {
        foreach ($this->vertices[$vertex] as $adjacent) {
            call_user_func($callback, $adjacent);
        }
    }

    public function eachVertex($callback) {
        $this->fev(function ($v, $adjacent) use ($callback) {
            call_user_func($callback, $v, $adjacent);
        });
    }

    public function eachEdge($callback) {
        $edges = array();
        $complete = new \SplObjectStorage();
        $this->fev(function ($a, $adjacent) use (&$edges, &$complete) {
            foreach ($adjacent as $b) {
                if (!$complete->contains($b)) {
                    $edges[] = array($a, $b);
                }
            }
            $complete->attach($a);
        });

        foreach ($edges as $edge) {
            call_user_func($callback, $edge);
        }
    }

    public function hasVertex($vertex) {
        return $this->vertices->contains($vertex);
    }

    protected function fev($callback) {
        foreach ($this->vertices as $vertex) {
            $adjacent = $this->vertices->getInfo();
            $callback($vertex, $adjacent);
        }
    }
}