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.
71 lines
1.6 KiB
PHP
71 lines
1.6 KiB
PHP
<?php
|
|
|
|
namespace Graphp\Algorithms\TravelingSalesmanProblem;
|
|
|
|
use Fhaculty\Graph\Walk;
|
|
use Fhaculty\Graph\Vertex;
|
|
use Fhaculty\Graph\Edge\Base as Edge;
|
|
use Fhaculty\Graph\Set\Edges;
|
|
use Graphp\Algorithms\Base as AlgorithmBase;
|
|
|
|
abstract class Base extends AlgorithmBase
|
|
{
|
|
/**
|
|
* get resulting graph with the (first) best circle of edges connecting all vertices
|
|
*
|
|
* @throws Exception on error
|
|
* @return Graph
|
|
* @uses Tsp::getGraph()
|
|
* @uses AlgorithmTsp::getEdges()
|
|
* @uses Graph::createGraphCloneEdges()
|
|
*/
|
|
public function createGraph()
|
|
{
|
|
return $this->getGraph()->createGraphCloneEdges($this->getEdges());
|
|
}
|
|
|
|
/**
|
|
* get graph this algorithm operates on
|
|
*
|
|
* @return Graph
|
|
*/
|
|
abstract protected function getGraph();
|
|
|
|
/**
|
|
* get start vertex this algorithm starts on
|
|
*
|
|
* @return Vertex
|
|
*/
|
|
abstract protected function getVertexStart();
|
|
|
|
/**
|
|
* get (first) best circle connecting all vertices
|
|
*
|
|
* @return Walk
|
|
* @uses AlgorithmTsp::getEdges()
|
|
* @uses AlgorithmTsp::getVertexStart()
|
|
* @uses Walk::factoryCycleFromEdges()
|
|
*/
|
|
public function getCycle()
|
|
{
|
|
return Walk::factoryCycleFromEdges($this->getEdges(), $this->getVertexStart());
|
|
}
|
|
|
|
public function getWeight()
|
|
{
|
|
$weight = 0;
|
|
foreach ($this->getEdges() as $edge) {
|
|
$weight += $edge->getWeight();
|
|
}
|
|
|
|
return $weight;
|
|
}
|
|
|
|
/**
|
|
* get array of edges connecting all vertices in a circle
|
|
*
|
|
* @return Edges
|
|
*/
|
|
abstract public function getEdges();
|
|
}
|