public function getOutput(Graph $graph)
 {
     $output = '';
     // build an array to map vertex IDs (which may contain complex strings) to temporary numeric IDs for output
     $tid = 1;
     $tids = array();
     foreach ($graph->getVertices()->getMap() as $vid => $vertex) {
         $output .= $tid . ' ' . $this->getVertexLabel($vertex) . self::EOL;
         $tids[$vid] = $tid++;
     }
     // end of vertex list, start of edge list
     $output .= '#' . self::EOL;
     foreach ($graph->getEdges() as $edge) {
         /* @var $edge Edge */
         $ids = $edge->getVertices()->getIds();
         $a = $tids[$ids[0]];
         $b = $tids[$ids[1]];
         $label = $this->getEdgeLabel($edge);
         if ($label !== '') {
             $label = ' ' . $label;
         }
         $output .= $a . ' ' . $b . $label . self::EOL;
         // this is not a directed edge => also add back-edge with same label
         if (!$edge instanceof Directed) {
             $output .= $b . ' ' . $a . $label . self::EOL;
         }
     }
     return $output;
 }

 public function testMixedParallelEdgesMultiple()
 {
     // 1 -> 2
     // 1 -> 2
     // 1 -- 2
     // 1 -- 2
     // 2 -> 1
     // 2 -> 1
     $graph = new Graph();
     $v1 = $graph->createVertex(1);
     $v2 = $graph->createVertex(2);
     $e1 = $v1->createEdgeTo($v2);
     $e2 = $v1->createEdgeTo($v2);
     $e3 = $v1->createEdge($v2);
     $e4 = $v1->createEdge($v2);
     $e5 = $v2->createEdgeTo($v1);
     $e6 = $v2->createEdgeTo($v1);
     $alg = new AlgorithmParallel($graph);
     $this->assertTrue($alg->hasEdgeParallel());
     $this->assertEquals(array($e2, $e3, $e4), $alg->getEdgesParallelEdge($e1)->getVector());
     $this->assertEquals(array($e1, $e3, $e4), $alg->getEdgesParallelEdge($e2)->getVector());
     $this->assertEquals(array($e1, $e2, $e4, $e5, $e6), $alg->getEdgesParallelEdge($e3)->getVector());
     $this->assertEquals(array($e1, $e2, $e3, $e5, $e6), $alg->getEdgesParallelEdge($e4)->getVector());
     $this->assertEquals(array($e3, $e4, $e6), $alg->getEdgesParallelEdge($e5)->getVector());
     $this->assertEquals(array($e3, $e4, $e5), $alg->getEdgesParallelEdge($e6)->getVector());
 }

 /**
  *
  * @param  string                $dir
  * @return \Fhaculty\Graph\Graph
  */
 public function createGraph($vendorName = null, $excludeDevDependency = true)
 {
     $graph = new Graph();
     foreach ($this->dependencyGraph->getPackages() as $package) {
         $name = $package->getName();
         if (null !== $vendorName && false === strpos($name, $vendorName)) {
             continue;
         }
         $start = $graph->createVertex($name, true);
         $label = $name;
         if ($package->getVersion() !== null) {
             $label .= ': ' . $package->getVersion();
         }
         $start->setLayout(array('label' => $label) + $this->getLayoutVertex($name));
         foreach ($package->getOutEdges() as $requires) {
             $targetName = $requires->getDestPackage()->getName();
             if (null !== $vendorName && false === strpos($targetName, $vendorName)) {
                 continue;
             }
             if ($excludeDevDependency && $requires->isDevDependency()) {
                 continue;
             }
             $target = $graph->createVertex($targetName, true);
             $label = $requires->getVersionConstraint();
             $start->createEdgeTo($target)->setLayout(array('label' => $label) + $this->layoutEdge);
         }
     }
     return $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);
 }

 /**
  *
  * @param string $dir
  * @return \Fhaculty\Graph\Graph
  */
 public function createGraph()
 {
     $graph = new Graph();
     foreach ($this->dependencyGraph->getPackages() as $package) {
         $name = $package->getName();
         $start = $graph->createVertex($name, true);
         $label = $name;
         if ($package->getVersion() !== null) {
             $label .= ': ' . $package->getVersion();
         }
         $this->setLayout($start, array('label' => $label) + $this->layoutVertex);
         foreach ($package->getOutEdges() as $requires) {
             $targetName = $requires->getDestPackage()->getName();
             $target = $graph->createVertex($targetName, true);
             $label = $requires->getVersionConstraint();
             $edge = $start->createEdgeTo($target);
             $this->setLayout($edge, array('label' => $label) + $this->layoutEdge);
             if ($requires->isDevDependency()) {
                 $this->setLayout($edge, $this->layoutEdgeDev);
             }
         }
     }
     $root = $graph->getVertex($this->dependencyGraph->getRootPackage()->getName());
     $this->setLayout($root, $this->layoutVertexRoot);
     return $graph;
 }

 /**
  * expect exception for non-bipartit graphs
  * @expectedException UnexpectedValueException
  */
 public function testInvalidBipartit()
 {
     $graph = new Graph();
     $graph->createVertex(0)->setGroup(1)->createEdge($graph->createVertex(1)->setGroup(1));
     $alg = new Flow($graph);
     $alg->getNumberOfMatches();
 }

 /**
  *
  */
 public function createGraph()
 {
     $graph = new Graph();
     $file = $this->getLines();
     $graph->createVertices($this->readInt($file[0]));
     unset($file[0]);
     // set the value of the vertices
     $zeile = 1;
     foreach ($graph->getVertices() as $vertex) {
         $vertex->setBalance($this->readFloat($file[$zeile]));
         unset($file[$zeile]);
         ++$zeile;
     }
     foreach ($file as $zeile) {
         $parts = $this->readLine($zeile, array('vertex', 'vertex', 'float', 'float'), $graph);
         if ($this->directedEdges) {
             $edge = $parts[0]->createEdgeTo($parts[1]);
         } else {
             $edge = $parts[0]->createEdge($parts[1]);
         }
         $edge->setWeight($parts[2]);
         $edge->setCapacity($parts[3]);
     }
     return $graph;
 }

 public function createGraph()
 {
     $graph = new Graph();
     $file = $this->getLines();
     $countOfAllVertices = $this->readInt($file[0]);
     $countOfVerticesInA = $this->readInt($file[1]);
     if ($countOfVerticesInA > $countOfAllVertices || $countOfVerticesInA < 0) {
         throw new UnexpectedValueException('Invalid value for number of vertices in group 0');
     }
     $graph->createVertices($countOfAllVertices);
     for ($i = 0; $i < $countOfVerticesInA; ++$i) {
         $graph->getVertex($i)->setGroup(0);
     }
     for ($k = $countOfVerticesInA; $k < $countOfAllVertices; ++$k) {
         $graph->getVertex($k)->setGroup(1);
     }
     unset($file[0]);
     unset($file[1]);
     foreach ($file as $zeile) {
         $parts = $this->readLine($zeile, array('vertex', 'vertex'), $graph);
         if ($this->directedEdges) {
             $edge = $parts[0]->createEdgeTo($parts[1]);
         } else {
             $edge = $parts[0]->createEdge($parts[1]);
         }
     }
     $alg = new AlgorithmGroups($graph);
     if (!$alg->isBipartit()) {
         throw new UnexpectedValueException('Graph read from file does not form a valid bipartit graph');
     }
     return $graph;
 }

 /**
  * @expectedException InvalidArgumentException
  */
 public function testInvalidVertexPassedToAlgorithm()
 {
     $graph = new Graph();
     $graph2 = new Graph();
     $v2 = $graph2->createVertex(12);
     $alg = new AlgorithmConnected($graph);
     $alg->createGraphComponentVertex($v2);
 }

 /**
  * @expectedException UnexpectedValueException
  */
 public function testFailCycle()
 {
     $graph = new Graph();
     $graph->createVertex(1)->createEdgeTo($graph->createVertex(2));
     $graph->getVertex(2)->createEdgeTo($graph->getVertex(1));
     $alg = new TopologicalSort($graph);
     $alg->getVertices();
 }

 /**
  * @expectedException UnexpectedValueException
  */
 public function testVertexWithUndirectedEdgeHasInvalidFlow()
 {
     // 1 -- 2
     $graph = new Graph();
     $graph->createVertex(1)->createEdge($graph->createVertex(2))->setFlow(10);
     $alg = new AlgorithmFlow($graph);
     $alg->getFlowVertex($graph->getVertex(1));
 }

 public function provideNamespacable()
 {
     $graph = new Graph();
     $vertex = $graph->createVertex();
     $bag = $vertex->getAttributeBag();
     $subNamespace = new AttributeBagNamespaced($bag, 'prefix');
     return array(array($graph), array($vertex), array($bag), array($subNamespace));
 }

 public function setUp()
 {
     $graph = new Graph();
     $graph->createVertex(1);
     $graph->createVertex(2);
     // 1 -> 2
     $this->edge = $graph->getVertex(1)->createEdge($graph->getVertex(2));
 }

 public function testGraphSingleUndirectedIsSymmetricr()
 {
     // 1 -- 2
     $graph = new Graph();
     $graph->createVertex(1)->createEdge($graph->createVertex(2));
     $alg = new AlgorithmSymmetric($graph);
     $this->assertTrue($alg->isSymmetric());
 }

 public function testOne()
 {
     $loader = new CompleteGraph(1);
     $graph = $loader->createGraph();
     $expected = new Graph();
     $expected->createVertex();
     $this->assertGraphEquals($expected, $graph);
 }

 /**
  *
  * @param Graph $graph
  * @depends testGraphSimple
  */
 public function testGraphWithUnweightedEdges(Graph $graph)
 {
     $graph->createVertex(5)->createEdgeTo($graph->createVertex(6))->setFlow(7);
     $alg = new AlgorithmWeight($graph);
     $this->assertEquals(3, $alg->getWeight());
     $this->assertEquals(12, $alg->getWeightFlow());
     $this->assertEquals(3, $alg->getWeightMin());
     $this->assertTrue($alg->isWeighted());
 }

 /**
  * @param Graph $graph
  */
 private function bindGroupAttributesBy(Graph $graph)
 {
     if ($groups = $graph->getAttribute('graphviz.groups')) {
         $this->getGraphViz()->setGroups($groups);
     }
     if ($groupLayout = $graph->getAttribute('graphviz.groupLayout')) {
         $this->getGraphViz()->setGroupLayout($groupLayout);
     }
 }

 public function testSingleVertexIsTrivial()
 {
     $graph = new Graph();
     $graph->createVertex(1);
     $alg = new GraphProperty($graph);
     $this->assertFalse($alg->isNull());
     $this->assertTrue($alg->isEdgeless());
     $this->assertTrue($alg->isTrivial());
 }

 public function testGraphDirectedLoop()
 {
     // 1 -> 1
     $graph = new Graph();
     $graph->createVertex(1)->createEdgeTo($v1 = $graph->getVertex(1));
     $alg = new AlgorithmLoop($graph);
     $this->assertTrue($alg->hasLoop());
     $this->assertTrue($alg->hasLoopVertex($v1));
 }

 public function testGraphMixed()
 {
     // 1 -- 2 -> 3
     $graph = new Graph();
     $graph->createVertex(1)->createEdge($graph->createVertex(2));
     $graph->getVertex(2)->createEdgeTo($graph->createVertex(3));
     $alg = new AlgorithmDirected($graph);
     $this->assertTrue($alg->hasDirected());
     $this->assertTrue($alg->hasUndirected());
     $this->assertTrue($alg->isMixed());
 }