public function getCycleNegative()
    {
        // remember vertices already visited, as they can not lead to a new cycle
        $verticesVisited = array();
        // check for all vertices
        foreach ($this->graph->getVertices()->getMap() as $vid => $vertex) {
            // skip vertices already visited
            if (!isset($verticesVisited[$vid])) {
                // start MBF algorithm on current vertex
                $alg = new SpMooreBellmanFord($vertex);

                try {
                    // try to get all connected vertices (or throw new cycle)
                    foreach ($alg->getVertices()->getIds() as $vid) {
                        // getting connected vertices succeeded, so skip over all of them
                        $verticesVisited[$vid] = true;
                    // no cycle found, check next vertex...
                    }
                // yey, negative cycle encountered => return
                } catch (NegativeCycleException $e) {
                    return $e->getCycle();
                }
            }
        // no more vertices to check => abort
        }
        throw new UnderflowException('No negative cycle found');
    }