110 lines
3.2 KiB
PHP
110 lines
3.2 KiB
PHP
<?php
|
|
|
|
namespace Graphp\Algorithms;
|
|
|
|
use Graphp\Algorithms\BaseGraph;
|
|
use Fhaculty\Graph\Exception\UnexpectedValueException;
|
|
|
|
use Fhaculty\Graph\Graph;
|
|
use Fhaculty\Graph\Edge\Base as Edge;
|
|
use Fhaculty\Graph\Edge\Directed as EdgeDirected;
|
|
|
|
class ResidualGraph extends BaseGraph
|
|
{
|
|
private $keepNullCapacity = false;
|
|
private $mergeParallelEdges = false;
|
|
|
|
public function setKeepNullCapacity($toggle)
|
|
{
|
|
$this->keepNullCapacity = !!$toggle;
|
|
|
|
return $this;
|
|
}
|
|
|
|
public function setMergeParallelEdges($toggle)
|
|
{
|
|
$this->mergeParallelEdges = !!$toggle;
|
|
|
|
return $this;
|
|
}
|
|
|
|
/**
|
|
* create residual graph
|
|
*
|
|
* @throws UnexpectedValueException if input graph has undirected edges or flow/capacity is not set
|
|
* @return Graph
|
|
* @uses Graph::createGraphCloneEdgeless()
|
|
* @uses Graph::createEdgeClone()
|
|
* @uses Graph::createEdgeCloneInverted()
|
|
*/
|
|
public function createGraph()
|
|
{
|
|
$newgraph = $this->graph->createGraphCloneEdgeless();
|
|
|
|
foreach ($this->graph->getEdges() as $edge) {
|
|
if (!($edge instanceof EdgeDirected)) {
|
|
throw new UnexpectedValueException('Edge is undirected');
|
|
}
|
|
|
|
$flow = $edge->getFlow();
|
|
if ($flow === NULL) {
|
|
throw new UnexpectedValueException('Flow not set');
|
|
}
|
|
|
|
$capacity = $edge->getCapacity();
|
|
if ($capacity === NULL) {
|
|
throw new UnexpectedValueException('Capacity not set');
|
|
}
|
|
|
|
// capacity is still available, clone remaining capacity into new edge
|
|
if ($this->keepNullCapacity || $flow < $capacity) {
|
|
$newEdge = $newgraph->createEdgeClone($edge)->setFlow(0)->setCapacity($capacity - $flow);
|
|
|
|
if ($this->mergeParallelEdges) {
|
|
$this->mergeParallelEdges($newEdge);
|
|
}
|
|
}
|
|
|
|
// flow is set, clone current flow as capacity for back-flow into new inverted edge (opposite direction)
|
|
if ($this->keepNullCapacity || $flow > 0) {
|
|
$newEdge = $newgraph->createEdgeCloneInverted($edge)->setFlow(0)->setCapacity($flow);
|
|
|
|
// if weight is set, use negative weight for back-edges
|
|
if ($newEdge->getWeight() !== NULL) {
|
|
$newEdge->setWeight(-$newEdge->getWeight());
|
|
}
|
|
|
|
if ($this->mergeParallelEdges) {
|
|
$this->mergeParallelEdges($newEdge);
|
|
}
|
|
}
|
|
}
|
|
|
|
return $newgraph;
|
|
}
|
|
|
|
/**
|
|
* Will merge all edges that are parallel to to given edge
|
|
*
|
|
* @param Edge $newEdge
|
|
*/
|
|
private function mergeParallelEdges(Edge $newEdge)
|
|
{
|
|
$parallelEdges = $newEdge->getEdgesParallel();
|
|
if ($parallelEdges) {
|
|
|
|
$mergedCapacity = 0;
|
|
|
|
foreach ($parallelEdges as $parallelEdge) {
|
|
$mergedCapacity += $parallelEdge->getCapacity();
|
|
}
|
|
|
|
$newEdge->setCapacity($newEdge->getCapacity() + $mergedCapacity);
|
|
|
|
foreach ($parallelEdges as $parallelEdge) {
|
|
$parallelEdge->destroy();
|
|
}
|
|
}
|
|
}
|
|
}
|