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.
44 lines
1.1 KiB
PHP
44 lines
1.1 KiB
PHP
<?php
|
|
|
|
namespace Graphp\Algorithms;
|
|
|
|
use Graphp\Algorithms\BaseGraph;
|
|
use Fhaculty\Graph\Graph;
|
|
|
|
/**
|
|
* Basic algorithms for working with complete graphs
|
|
*
|
|
* A complete graph is a graph in which every pair of vertices is connected
|
|
* by an edge.
|
|
*
|
|
* @link http://en.wikipedia.org/wiki/Complete_graph
|
|
* @link http://mathworld.wolfram.com/CompleteGraph.html
|
|
*/
|
|
class Complete extends BaseGraph
|
|
{
|
|
/**
|
|
* checks whether this graph is complete (every vertex has an edge to any other vertex)
|
|
*
|
|
* @return boolean
|
|
* @uses Graph::getVertices()
|
|
* @uses Vertex::hasEdgeTo()
|
|
*/
|
|
public function isComplete()
|
|
{
|
|
// copy of array (separate iterator but same vertices)
|
|
$c = $vertices = $this->graph->getVertices()->getVector();
|
|
// from each vertex
|
|
foreach ($vertices as $vertex) {
|
|
// to each vertex
|
|
foreach ($c as $other) {
|
|
// missing edge => fail
|
|
if ($other !== $vertex && !$vertex->hasEdgeTo($other)) {
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
}
|