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.
39 lines
933 B
PHP
39 lines
933 B
PHP
<?php
|
|
|
|
namespace Graphp\Algorithms;
|
|
|
|
use Graphp\Algorithms\BaseGraph;
|
|
use Fhaculty\Graph\Graph;
|
|
use Graphp\Algorithms\Degree;
|
|
|
|
class Eulerian extends BaseGraph
|
|
{
|
|
/**
|
|
* check whether this graph has an eulerian cycle
|
|
*
|
|
* @return boolean
|
|
* @uses ConnectedComponents::isSingle()
|
|
* @uses Degree::getDegreeVertex()
|
|
* @todo isolated vertices should be ignored
|
|
* @todo definition is only valid for undirected graphs
|
|
*/
|
|
public function hasCycle()
|
|
{
|
|
$components = new ConnectedComponents($this->graph);
|
|
if ($components->isSingle()) {
|
|
$alg = new Degree($this->graph);
|
|
|
|
foreach ($this->graph->getVertices() as $vertex) {
|
|
// uneven degree => fail
|
|
if ($alg->getDegreeVertex($vertex) & 1) {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
}
|