Searches all vertices for the first negative cycle

@return Walk
@throws UnderflowException if there's no negative cycle
@uses AlgorithmSpMooreBellmanFord::getVertices()
10857
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');
    }
539953
public function getDegree()
    {

        if (!is_a($this->nodeGraph, Graph::class)):
            throw new \Exception("Unkown node parent graph. Cannot calculate InDegree of NODE:" . $this->getId(), PLATFORM_ERROR); //Unkonwn graph type;
        endif;

        $incidence = 0;
        $graph = $this->getGraph();
        $edges = $graph->getEdgeSet();

        //If this graph is undirected, then we can't calculate the  indegree to this node;
        if (empty($edges))
            return $incidence;

        //search for all arcs with this node as tail
        foreach ($edges as $edge):
            if ($edge->getTail()->getId() == $this->getId()) {
                $incidence++;
                //if head is the same as self, as is the case in cycled edges then we have one more indegree,
                //looped vertices have an indegree of two;
                if ($edge->getHead()->getId() == $this->getId())
                    $incidence++;
            } elseif ($edge->getHead()->getId() == $this->getId()) {
                //Cover for cycles
                if ($edge->getHead()->getId() == $this->getId())
                    $incidence++;
            }
        endforeach;

        return $incidence;
    }
741758
@Override
	public  Point3d[] getVertices() {
		double x = getSideLengthFromCircumscribedRadius(circumscribedRadius)/2;
		double z = x/Math.sqrt(2);
		Point3d[] tetrahedron = new Point3d[4];
		tetrahedron[0] = new Point3d(-x,  0, -z);
		tetrahedron[1] = new Point3d( x,  0, -z);
		tetrahedron[2] = new Point3d( 0, -x,  z);
		tetrahedron[3] = new Point3d( 0,  x,  z);
		Point3d centroid = CalcPoint.centroid(tetrahedron);

		// rotate tetrahedron to align one vertex with the +z axis
		Matrix3d m = new Matrix3d();
		m.rotX(0.5 * TETRAHEDRAL_ANGLE);
		for (Point3d p: tetrahedron) {
			p.sub(centroid);
			m.transform(p);
		}
		return tetrahedron;
	}
1288974
function(){
            var isPositive = false,
                num = this.vertices.length,
                prev,
                next,
                d0,
                d1,
                newIsP;

            for( var i = 0; i < num; i++ ){
                prev = (i===0) ? num -1 : i - 1;
                next = (i===num-1) ? 0 : i + 1;
                d0 = this.vertices[i].sub(this.vertices[prev]);
                d1 = this.vertices[next].sub(this.vertices[i]);
                newIsP = (d0.cross(d1) > 0);
                if( i === 0 ) {
                    isPositive = true;
                } else if( isPositive != newIsP ) {
                    return false;
                }
            }
            return true;
        }
876217
protected VertexType getNextSearchTreeRoot() {
        // FIXME: slow linear search, should improve
        for (Iterator<VertexType> i = graph.vertexIterator(); i.hasNext();) {
            VertexType vertex = i.next();
            if (visitMe(vertex)) {
                return vertex;
            }
        }
        return null;
    }
246917
def find_cycle(graph):
    
    n = len(graph)
    prec = [None] * n  # ancestor marks for visited vertices
    for u in range(n):
        if prec[u] is None:  # unvisited vertex
            S = [u]  # start new DFS
            prec[u] = u  # mark root (not necessary for this algorithm)
            while S:
                u = S.pop()
                for v in graph[u]:  # for all neighbors
                    if v != prec[u]:  # except arcs to father in DFS tree
                        if prec[v] is not None:
                            cycle = [v, u]  # cycle found, (u,v) back edge
                            while u != prec[v] and u != prec[u]:  # directed
                                u = prec[u]  # climb up the tree
                                cycle.append(u)
                            return cycle
                        else:
                            prec[v] = u  # v is new vertex in tree
                            S.append(v)
    return None
468481
private function findNodesWithoutParents()
    {
        // get nodes that have no parent but depth > 0
        $qb = $this->accountRepository->createQueryBuilder('c2')
            ->select('count(c2.id)')
            ->leftJoin('c2.parent', 'c1')
            ->where('c2.depth <> 0 AND c2.parent IS NULL');

        return $qb->getQuery()->getSingleScalarResult();
    }
1090020
private function getStepsSortedDescByPriority()
    {
        $steps = $this->steps;
        // Use illogically large and small priorities
        $steps[-255][] = new Step\ArrayCheckStep;
        foreach ($this->writers as $writer) {
            $steps[-256][] = new Step\WriterStep($writer);
        }

        krsort($steps);

        $sortedStep = [];
        /** @var Step[] $stepsAtSamePriority */
        foreach ($steps as $stepsAtSamePriority) {
            foreach ($stepsAtSamePriority as $step) {
                $sortedStep[] = $step;
            }
        }

        return array_reverse($sortedStep);
    }
289714
public static <N, E, D> boolean traverse(TraversalOrder order,
                                             IndefiniteGraph<N, E> graph,
                                             int limit,
                                             N initialNode,
                                             GraphTraversalVisitor<N, E, D> vis) {
        return traverse(order, graph, limit, Collections.singleton(initialNode), vis);
    }
868274
public function isTriangle()
    {
        // exactly 3 (implicitly distinct) edges
        return (count($this->walk->getEdges()) === 3 &&
                // exactly three distinct vertices
                count($this->walk->getVertices()->getVerticesDistinct()) === 3 &&
                // this is actually a cycle
                $this->isCycle());
    }
254821
protected function searchComponent($start)
    {
        if (!isset($this->component)) {
            $this->component = $start;
        }

        if (isset($this->graph[$start]['paths'])) {
            return null;
        }

        $this->graph[$start]['paths'] = array();
        $this->graph[$start]['component'] = $this->component;
        $this->state['components'][$this->component][] = $start;

        if (isset($this->graph[$start]['edges'])) {
            foreach ($this->graph[$start]['edges'] as $end => $v) {
                $this->graph[$start]['paths'][$end] = $v;
                if (isset($this->graph[$end]['component']) && $this->component != $this->graph[$end]['component']) {
                    $new_component = $this->graph[$end]['component'];
                    foreach ($this->state['components'][$this->component] as $vertex) {
                        $this->graph[$vertex]['component'] = $new_component;
                        $this->state['components'][$new_component][] = $vertex;
                    }
                    unset($this->state['components'][$this->component]);
                    $this->component = $new_component;
                }

                if (isset($this->graph[$end])) {
                    $this->searchComponent($end);
                    $this->graph[$start]['paths'] += $this->graph[$end]['paths'];
                }
            }
        }

        foreach ($this->graph[$start]['paths'] as $end => $v) {
            if (isset($this->graph[$end])) {
                $this->graph[$end]['reverse_paths'][$start] = $v;
            }
        }

        $this->state['last_visit_order'][] = $start;
        return null;
    }
928242
public int numVertices() {
	if(CACHING && (cachedNumVertices != -1)) {
	    return cachedNumVertices;
	}	
	int numVertices = vertices().size();       
	if(CACHING) {
	    cachedNumVertices = numVertices;
	}
	return numVertices;
    }
401685
@SuppressWarnings("unchecked")
    private Set<Integer> getPredecessors(Graph g, Integer vertex) {
        // The DirectedGraph cast seems to change the return type of the set
        // from Set<Integer> to just Set
        if (g instanceof DirectedGraph) {
            DirectedGraph<?> dg = (DirectedGraph)g;
            return dg.predecessors(vertex);
        }
        else {
            return g.getNeighbors(vertex);
        }
    }
1280701
public static <V> Set<V> getIncomingVertices(DirectedGraph<V, DefaultEdge> graph, V target) {
        Set<DefaultEdge> edges = graph.incomingEdgesOf(target);
        Set<V> sources = new LinkedHashSet<V>();
        for (DefaultEdge edge : edges) {
            sources.add(graph.getEdgeSource(edge));
        }
        return sources;
    }
1202269
public Set<GraphObject> run()
	{
		// result set of neighborhood query
		Set<GraphObject> queryResult = new HashSet<GraphObject>();

		// if upstream is selected
		if (direction == Direction.UPSTREAM || direction == Direction.BOTHSTREAM)
		{
			// run BFS in upstream direction
			BFS bfsBackward = new BFS(sourceNodes, null, Direction.UPSTREAM, this.limit);

			/*
	  Maps to hold forward and backward BFS results
	 */
			Map<GraphObject, Integer> mapBackward = bfsBackward.run();

			// add result of BFS to result Set
			queryResult.addAll(mapBackward.keySet());
		}

		// if downstream is selected
		if (direction == Direction.DOWNSTREAM || direction == Direction.BOTHSTREAM)
		{
			// run BFS in downstream direction
			BFS bfsForward = new BFS(sourceNodes, null, Direction.DOWNSTREAM, this.limit);

			Map<GraphObject, Integer> mapForward = bfsForward.run();

			// add result of BFS to result Set
			queryResult.addAll(mapForward.keySet());
		}
		
		// return the result of query
		return queryResult;
	}
436363
function step() {
        // Back to the first iterator.
        if (index === count - 1) {
            index = -1;
        }

        // Go to the next iterator.
        index++;

        // Ignore empty iterators.
        while(empties.has(index)) {
            if (index === count - 1) {
                index = -1;
            }

            index++;
        }

        return iterators[index];
    }
583831
protected function findNextStep() {
		// otherwise get next step in chain
		$currentStep = $this->CurrentStep();
		return $this
			->Steps()
			->filter("Status", "Queued")
			->filter("Order:GreaterThanOrEqual", $currentStep->Order)
			->exclude("ID", $currentStep->ID)
			->sort("Order ASC")
			->first();
	}