DFS traversal to detect cycles in augmented job graph.
775568
def _checkJobGraphAcylicDFS(self, stack, visited, extraEdges):
        
        if self not in visited:
            visited.add(self)
            stack.append(self)
            for successor in self._children + self._followOns + extraEdges[self]:
                successor._checkJobGraphAcylicDFS(stack, visited, extraEdges)
            assert stack.pop() == self
        if self in stack:
            stack.append(self)
            raise JobGraphDeadlockException("A cycle of job dependencies has been detected '%s'" % stack)
1249008
def get_workflow_graph(promise):
    """"""
    workflow = get_workflow(promise)

    dot = Digraph()
    for i, n in workflow.nodes.items():
        dot.node(str(i), label="{0} \n {1}".format(
            n.foo.__name__,
            _format_arg_list(n.bound_args.args)))

    for i in workflow.links:
        for j in workflow.links[i]:
            dot.edge(str(i), str(j[0]), label=str(j[1].name))

    return dot
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
332301
def key_cycles():
    
    graph = garbage()
    sccs = graph.strongly_connected_components()
    return [scc for scc in sccs if _is_orphan(scc, graph)]
1078076
def connected_components(graph):
    
    recursionlimit = getrecursionlimit()
    setrecursionlimit(max(len(graph.nodes())*2,recursionlimit))
    
    visited = {}
    count = 1

    # For 'each' node not found to belong to a connected component, find its connected
    # component.
    for each in graph:
        if (each not in visited):
            _dfs(graph, visited, count, each)
            count = count + 1
    
    setrecursionlimit(recursionlimit)
    return visited
26688
def _serialiseJobGraph(self, jobGraph, jobStore, returnValues, firstJob):
        
        #Check if the job graph has created
        #any cycles of dependencies or has multiple roots
        self.checkJobGraphForDeadlocks()

        #Create the jobGraphs for followOns/children
        with jobStore.batch():
            jobsToJobGraphs = self._makeJobGraphs(jobGraph, jobStore)
        #Get an ordering on the jobs which we use for pickling the jobs in the
        #correct order to ensure the promises are properly established
        ordering = self.getTopologicalOrderingOfJobs()
        assert len(ordering) == len(jobsToJobGraphs)

        with jobStore.batch():
            # Temporarily set the jobStore locators for the promise call back functions
            for job in ordering:
                job.prepareForPromiseRegistration(jobStore)
                def setForServices(serviceJob):
                    serviceJob.prepareForPromiseRegistration(jobStore)
                    for childServiceJob in serviceJob.service._childServices:
                        setForServices(childServiceJob)
                for serviceJob in job._services:
                    setForServices(serviceJob)

            ordering.reverse()
            assert self == ordering[-1]
            if firstJob:
                #If the first job we serialise all the jobs, including the root job
                for job in ordering:
                    # Pickle the services for the job
                    job._serialiseServices(jobStore, jobsToJobGraphs[job], jobGraph)
                    # Now pickle the job
                    job._serialiseJob(jobStore, jobsToJobGraphs, jobGraph)
            else:
                #We store the return values at this point, because if a return value
                #is a promise from another job, we need to register the promise
                #before we serialise the other jobs
                self._fulfillPromises(returnValues, jobStore)
                #Pickle the non-root jobs
                for job in ordering[:-1]:
                    # Pickle the services for the job
                    job._serialiseServices(jobStore, jobsToJobGraphs[job], jobGraph)
                    # Pickle the job itself
                    job._serialiseJob(jobStore, jobsToJobGraphs, jobGraph)
                # Pickle any services for the job
                self._serialiseServices(jobStore, jobGraph, jobGraph)
320937
public int dfs(int root, boolean isRootT1, boolean[] marked1, boolean[] marked2, BipVisitor<T1,T2> visitor) {
        IntStack sNode = new IntStack();
        ByteStack sIsT1 = new ByteStack(); // TODO: This should be a boolean stack.
        sNode.push(root);
        sIsT1.push((byte)(isRootT1 ? 1 : 0)); 
        
        // The number of times we check if any node is marked. 
        // For acyclic graphs this should be two times the number of nodes.
        int numMarkedChecks = 0;
        
        while (sNode.size() != 0) {
            int node = sNode.pop();
            boolean isT1 = (sIsT1.pop() == 1);            
            if (isT1) {
                // Visit node only if not marked.
                int t1 = node;
                if (!marked1[t1]) {
                    marked1[t1] = true;
                    if (visitor != null) { visitor.visit(t1, true, this); }
                    for (int nb = numNbsT1(t1)-1; nb >= 0; nb--) {
                        int t2 = childT1(t1, nb);
                        if (!marked2[t2]) {
                            sNode.push(t2);
                            sIsT1.push((byte)0);
                        }
                        numMarkedChecks++;
                    }
                }
                numMarkedChecks++;
            } else {
                // Visit node only if not marked.
                int t2 = node;
                if (!marked2[t2]) {
                    marked2[t2] = true;
                    if (visitor != null) { visitor.visit(t2, false, this); }
                    for (int nb = numNbsT2(t2)-1; nb >= 0; nb--) {
                        int t1 = childT2(t2, nb);
                        if (!marked1[t1]) {
                            sNode.push(t1);
                            sIsT1.push((byte)1);
                        }
                        numMarkedChecks++;
                    }
                }
                numMarkedChecks++;
            }
        }
        return numMarkedChecks;
    }
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);
    }
193546
public boolean findAndReportCycles(DependencyGraph graph) {
    this.graph = graph;
    cycleDetected = false;
    visitedEdge = new LinkedHashMap<Key<?>, Dependency>(graph.size());
    
    for (Key<?> key : graph.getAllKeys()) {
      visit(key, null);
    }

    return cycleDetected;
  }
477179
def find_cycles(self):
        """"""

        # Apply the Tarjan's algorithm successively until all functions are visited
        stack = []
        data = {}
        order = 0
        for function in compat_itervalues(self.functions):
            order = self._tarjan(function, order, stack, data)
        cycles = []
        for function in compat_itervalues(self.functions):
            if function.cycle is not None and function.cycle not in cycles:
                cycles.append(function.cycle)
        self.cycles = cycles
        if 0:
            for cycle in cycles:
                sys.stderr.write("Cycle:\n")
                for member in cycle.functions:
                    sys.stderr.write("\tFunction %s\n" % member.name)
990581
def dfs(initial)
      nodes, seen = Set.new, Set.new
      stack = Array(initial).reverse

      while node = stack.pop
        if seen.include?(node)
          nodes.add(node)
        else
          seen.add(node)
          stack.push(node)
          stack.concat(Array(yield node).reverse)
        end
      end

      nodes
    end
435820
function tightTree(t, g) {
  function dfs(v) {
    _.forEach(g.nodeEdges(v), function(e) {
      var edgeV = e.v,
        w = (v === edgeV) ? e.w : edgeV;
      if (!t.hasNode(w) && !slack(g, e)) {
        t.setNode(w, {});
        t.setEdge(v, w, {});
        dfs(w);
      }
    });
  }

  _.forEach(t.nodes(), dfs);
  return t.nodeCount();
}
773514
private void dfs(Visitor visitor, int v, int[] cc, int id) {
        visitor.visit(v);
        cc[v] = id;
        for (int t = 0; t < n; t++) {
            if (graph[v][t] != 0.0) {
                if (cc[t] == -1) {
                    dfs(visitor, t, cc, id);
                }
            }
        }
    }
235014
def __setup_dfs_data(graph, adj):
    """"""
    dfs_data = __get_dfs_data(graph, adj)

    dfs_data['graph'] = graph
    dfs_data['adj'] = adj

    L1, L2 = __low_point_dfs(dfs_data)
    dfs_data['lowpoint_1_lookup'] = L1
    dfs_data['lowpoint_2_lookup'] = L2

    edge_weights = __calculate_edge_weights(dfs_data)
    dfs_data['edge_weights'] = edge_weights

    return dfs_data
1355618
def depth_first_search_with_parent_data(graph, root_node = None, adjacency_lists = None):
    """"""
    ordering = []
    parent_lookup = {}
    children_lookup = defaultdict(lambda: [])

    all_nodes = graph.get_all_node_ids()
    if not all_nodes:
        return ordering, parent_lookup, children_lookup

    stack = deque()
    discovered = defaultdict(lambda: False)
    unvisited_nodes = set(all_nodes)

    if root_node is None:
        root_node = all_nodes[0]

    if adjacency_lists is None:
        adj = lambda v: graph.neighbors(v)
    else:
        adj = lambda v: adjacency_lists[v]

    # --Initialize the stack, simulating the DFS call on the root node
    stack.appendleft(root_node)
    parent_lookup[root_node] = root_node

    # We're using a non-recursive implementation of DFS, since Python isn't great for deep recursion
    while True:
        # Main DFS Loop
        while len(stack) > 0:
            u = stack.popleft()

            if not discovered[u]:
                discovered[u] = True
                if u in unvisited_nodes:
                    unvisited_nodes.remove(u)
                ordering.append(u)
                neighbors = adj(u)
                # When adding the new nodes to the stack, we want to add them in reverse order so that
                # the order the nodes are visited is the same as with a recursive DFS implementation
                for n in neighbors[::-1]:
                    if discovered[n]:
                        # If the node already exists in the discovered nodes list
                        # we don't want to re-add it to the stack
                        continue
                    stack.appendleft(n)
                    parent_lookup[n] = u
                    children_lookup[u].append(n)

        # While there are still nodes that need visiting, repopulate the stack
        if len(unvisited_nodes) > 0:
            u = unvisited_nodes.pop()
            stack.appendleft(u)
        else:
            break

    return ordering, parent_lookup, children_lookup
755027
def computeNodeLinks(cls, element, graph):
        
        index = element.nodes.kdims[-1]
        node_map = {}
        if element.nodes.vdims:
            values = zip(*(element.nodes.dimension_values(d)
                           for d in element.nodes.vdims))
        else:
            values = cycle([tuple()])
        for index, vals in zip(element.nodes.dimension_values(index), values):
            node = {'index': index, 'sourceLinks': [], 'targetLinks': [], 'values': vals}
            graph['nodes'].append(node)
            node_map[index] = node

        links = [element.dimension_values(d) for d in element.dimensions()[:3]]
        for i, (src, tgt, value) in enumerate(zip(*links)):
            source, target = node_map[src], node_map[tgt]
            link = dict(index=i, source=source, target=target, value=value)
            graph['links'].append(link)
            source['sourceLinks'].append(link)
            target['targetLinks'].append(link)
1178732
def _detect_loops(self, loop_callback=None):
        

        loop_finder = self.project.analyses.LoopFinder(kb=self.kb, normalize=False, fail_fast=self._fail_fast)

        if loop_callback is not None:
            graph_copy = networkx.DiGraph(self._graph)

            for loop in loop_finder.loops:  # type: angr.analyses.loopfinder.Loop
                loop_callback(graph_copy, loop)

            self.model.graph = graph_copy

        # Update loop backedges and graph
        self._loop_back_edges = list(itertools.chain.from_iterable(loop.continue_edges for loop in loop_finder.loops))