You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
119 lines
3.6 KiB
PHP
119 lines
3.6 KiB
PHP
<?php
|
|
|
|
namespace Graphp\Algorithms;
|
|
|
|
use Graphp\Algorithms\BaseGraph;
|
|
use Fhaculty\Graph\Edge\Base as Edge;
|
|
use Fhaculty\Graph\Edge\Directed as EdgeDirected;
|
|
use Fhaculty\Graph\Exception\UnexpectedValueException;
|
|
use Fhaculty\Graph\Graph;
|
|
use Fhaculty\Graph\Vertex;
|
|
|
|
/**
|
|
* Basic algorithms for working with flow graphs
|
|
*
|
|
* A flow network (also known as a transportation network) is a directed graph
|
|
* where each edge has a capacity and each edge receives a flow.
|
|
*
|
|
* @link http://en.wikipedia.org/wiki/Flow_network
|
|
* @see Algorithm\Balance
|
|
*/
|
|
class Flow extends BaseDual
|
|
{
|
|
/**
|
|
* check if this graph has any flow set (any edge has a non-NULL flow)
|
|
*
|
|
* @return boolean
|
|
* @uses Edge::getFlow()
|
|
*/
|
|
public function hasFlow()
|
|
{
|
|
foreach ($this->set->getEdges() as $edge) {
|
|
if ($edge->getFlow() !== NULL) {
|
|
return true;
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
/**
|
|
* Calculates the flow for this Vertex: sum(outflow) - sum(inflow)
|
|
*
|
|
* Usually, vertices should have a resulting flow of 0: The sum of flows
|
|
* entering a vertex must equal the sum of flows leaving a vertex. If the
|
|
* resulting flow is < 0, this vertex is considered a sink (i.e. there's
|
|
* more flow into this vertex). If the resulting flow is > 0, this vertex
|
|
* is considered a "source" (i.e. there's more flow leaving this vertex).
|
|
*
|
|
* @param Vertex $vertex
|
|
* @return float
|
|
* @throws UnexpectedValueException if they are undirected edges
|
|
* @see Vertex::getBalance()
|
|
* @uses Vertex::getEdges()
|
|
* @uses Edge::getFlow()
|
|
*/
|
|
public function getFlowVertex(Vertex $vertex)
|
|
{
|
|
$sumOfFlow = 0;
|
|
|
|
foreach ($vertex->getEdges() as $edge) {
|
|
if (!($edge instanceof EdgeDirected)) {
|
|
throw new UnexpectedValueException("TODO: undirected edges not suported yet");
|
|
}
|
|
|
|
// edge is an outgoing edge of this vertex
|
|
if ($edge->hasVertexStart($vertex)) {
|
|
// flowing out (flow is "pointing away")
|
|
$sumOfFlow += $edge->getFlow();
|
|
// this is an ingoing edge
|
|
} else {
|
|
// flowing in
|
|
$sumOfFlow -= $edge->getFlow();
|
|
}
|
|
}
|
|
|
|
return $sumOfFlow;
|
|
}
|
|
|
|
public function getBalance()
|
|
{
|
|
$balance = 0;
|
|
// Sum for all vertices of value
|
|
foreach ($this->set->getVertices() as $vertex) {
|
|
$balance += $vertex->getBalance();
|
|
}
|
|
|
|
return $balance;
|
|
}
|
|
|
|
/**
|
|
* check if the current flow is balanced (aka "balanced flow" or "b-flow")
|
|
*
|
|
* a flow is considered balanced if each edge's current flow does not exceed its
|
|
* maximum capacity (which is always guaranteed due to the implementation
|
|
* of Edge::setFlow()) and each vertices' flow (i.e. outflow-inflow) equals
|
|
* its balance.
|
|
*
|
|
* checking whether the FLOW is balanced is not to be confused with checking
|
|
* whether the GRAPH is balanced (see Graph::isBalanced() instead)
|
|
*
|
|
* @return boolean
|
|
* @see Algorithm\Degree::isBalanced() if you merely want to check indegree=outdegree
|
|
* @uses self::getFlowVertex()
|
|
* @uses Vertex::getBalance()
|
|
*/
|
|
public function isBalancedFlow()
|
|
{
|
|
// no need to check for each edge: flow <= capacity (setters already check that)
|
|
// check for each vertex: outflow-inflow = balance
|
|
foreach ($this->set->getVertices() as $vertex) {
|
|
if ($this->getFlowVertex($vertex) !== $vertex->getBalance()) {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
}
|