getGraph() !== $this->graph) { throw new InvalidArgumentException('This graph does not contain the given vertex'); } return $this->graph->createGraphCloneVertices($this->createSearch($vertex)->getVertices()); } /** * * @param Vertex $vertex * @return SearchBreadthFirst */ private function createSearch(Vertex $vertex) { $alg = new SearchBreadthFirst($vertex); // follow into both directions (loosely connected) return $alg->setDirection(SearchBreadthFirst::DIRECTION_BOTH); } /** * check whether this graph consists of only a single component * * If a Graph consists of only a single component, it is said to be a * connected Graph, otherwise it's called a disconnected Graph. * * This method returns exactly the same result as checking *

($this->getNumberOfComponents() === 1)

. However, using this * method is faster than calling getNumberOfComponents(), as it only has to * count all vertices in one component to see if the graph consists of only * a single component. * * As such, a null Graph (a Graph with no vertices) is not considered * connected here. * * @return boolean * @see self::getNumberOfComponents() */ public function isSingle() { try { $vertex = $this->graph->getVertices()->getVertexFirst(); } catch (UnderflowException $e) { // no first vertex => empty graph => has zero components return false; } $alg = $this->createSearch($vertex); return (count($this->graph->getVertices()) === count($alg->getVertices())); } /** * count number of connected components * * A null Graph (a Graph with no vertices) will return 0 components. * * @return int number of components * @uses Graph::getVertices() * @uses AlgorithmSearchBreadthFirst::getVertices() */ public function getNumberOfComponents() { $visitedVertices = array(); $components = 0; // for each vertices foreach ($this->graph->getVertices()->getMap() as $vid => $vertex) { // did I visit this vertex before? if (!isset($visitedVertices[$vid])) { // get all vertices of this component $newVertices = $this->createSearch($vertex)->getVertices()->getIds(); ++$components; // mark the vertices of this component as visited foreach ($newVertices as $vid) { $visitedVertices[$vid] = true; } } } // return number of components return $components; } /** * separate input graph into separate independant and unconnected graphs * * @return Graph[] * @uses Graph::getVertices() * @uses AlgorithmSearchBreadthFirst::getVertices() */ public function createGraphsComponents() { $visitedVertices = array(); $graphs = array(); // for each vertices foreach ($this->graph->getVertices()->getMap() as $vid => $vertex) { // did I visit this vertex before? if (!isset($visitedVertices[$vid])) { $alg = $this->createSearch($vertex); // get all vertices of this component $newVertices = $alg->getVertices(); // mark the vertices of this component as visited foreach ($newVertices->getIds() as $vid) { $visitedVertices[$vid] = true; } $graphs []= $this->graph->createGraphCloneVertices($newVertices); } } return $graphs; } }