75 lines
2.2 KiB
PHP
75 lines
2.2 KiB
PHP
|
<?php
|
||
|
|
|
||
|
|
namespace Graphp\Algorithms\TravelingSalesmanProblem;
|
||
|
|
|
||
|
|
use Fhaculty\Graph\Graph;
|
||
|
|
use Fhaculty\Graph\Edge\Base as Edge;
|
||
|
|
use Fhaculty\Graph\Set\Edges;
|
||
|
|
use Graphp\Algorithms\MinimumSpanningTree\Kruskal as MstKruskal;
|
||
|
|
use Graphp\Algorithms\Search\BreadthFirst as SearchDepthFirst;
|
||
|
|
|
||
|
|
class MinimumSpanningTree extends Base4
|
||
|
|
{
|
||
|
|
/**
|
||
|
|
*
|
||
|
|
* @var Graph
|
||
|
|
*/
|
||
|
|
private $graph;
|
||
|
|
|
||
|
|
public function __construct(Graph $inputGraph)
|
||
|
|
{
|
||
|
|
$this->graph = $inputGraph;
|
||
|
|
}
|
||
|
|
|
||
|
|
protected function getVertexStart()
|
||
|
|
{
|
||
|
|
return $this->graph->getVertices()->getVertexFirst();
|
||
|
|
}
|
||
|
|
|
||
|
|
protected function getGraph()
|
||
|
|
{
|
||
|
|
return $this->graph;
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
*
|
||
|
|
* @return Edges
|
||
|
|
*/
|
||
|
|
public function getEdges()
|
||
|
|
{
|
||
|
|
$returnEdges = array();
|
||
|
|
|
||
|
|
// Create minimum spanning tree
|
||
|
|
$minimumSpanningTreeAlgorithm = new MstKruskal($this->graph);
|
||
|
|
$minimumSpanningTree = $minimumSpanningTreeAlgorithm->createGraph();
|
||
|
|
|
||
|
|
$alg = new SearchDepthFirst($minimumSpanningTree->getVertices()->getVertexFirst());
|
||
|
|
// Depth first search in minmum spanning tree (for the eulerian path)
|
||
|
|
|
||
|
|
$startVertex = NULL;
|
||
|
|
$oldVertex = NULL;
|
||
|
|
|
||
|
|
// connect vertices in order of the depth first search
|
||
|
|
foreach ($alg->getVertices() as $vertex) {
|
||
|
|
|
||
|
|
// get vertex from the original graph (not from the depth first search)
|
||
|
|
$vertex = $this->graph->getVertex($vertex->getId());
|
||
|
|
// need to clone the edge from the original graph, therefore i need the original edge
|
||
|
|
if ($startVertex === NULL) {
|
||
|
|
$startVertex = $vertex;
|
||
|
|
} else {
|
||
|
|
// get edge(s) to clone, multiple edges are possible (returns an array if undirected edge)
|
||
|
|
$returnEdges []= $oldVertex->getEdgesTo($vertex)->getEdgeFirst();
|
||
|
|
}
|
||
|
|
|
||
|
|
$oldVertex = $vertex;
|
||
|
|
}
|
||
|
|
|
||
|
|
// connect last vertex with start vertex
|
||
|
|
// multiple edges are possible (returns an array if undirected edge)
|
||
|
|
$returnEdges []= $oldVertex->getEdgesTo($startVertex)->getEdgeFirst();
|
||
|
|
|
||
|
|
return new Edges($returnEdges);
|
||
|
|
}
|
||
|
|
}
|