Get all the roots of the graph. Time complexity: O(|V|).
199195
function() {

        var sources = [];
        joint.util.forIn(this._nodes, function(exists, node) {
            if (!this._in[node] || joint.util.isEmpty(this._in[node])) {
                sources.push(this.getCell(node));
            }
        }.bind(this));
        return sources;
    }
1295349
def deepest_node((subj, pred, obj), graph):
    """"""
    # i don't fully accept the premise that this docstring presents
    # i'm not a docstring literalist
    to_return = []

    def _deepest_node((subj, pred, obj), graph):
        children = []
        if isinstance(obj, rt.BNode):
            for s, p, o in graph:
                if str(s) == str(obj):
                    children.append((s, p, o))
            for s, p, o in children:
                s1, p1, o1 = _deepest_node((s, p, o), graph)
                # coupling *smacks hand with ruler*
                if "rNews" in str(o1) and (s1, p1, o1) not in to_return:
                    to_return.append((s1, p1, o1))
            return (s1, p1, o1)
        else:
            return (subj, pred, obj)
    _deepest_node((subj, pred, obj), graph)

    return to_return
982668
function(w, degree, t, depth) {
		var left = [], right = [],
			left_count, right_count,
			left_t = [], right_t = [];

		switch (_getCrossingCount(w, degree)) {
			case 0 : {
				return 0;
			}
			case 1 : {
				if (depth >= maxRecursion) {
					t[0] = (w[0].x + w[degree].x) / 2.0;
					return 1;
				}
				if (_isFlatEnough(w, degree)) {
					t[0] = _computeXIntercept(w, degree);
					return 1;
				}
				break;
			}
		}
		_bezier(w, degree, 0.5, left, right);
		left_count  = _findRoots(left,  degree, left_t, depth+1);
		right_count = _findRoots(right, degree, right_t, depth+1);
		for (var i = 0; i < left_count; i++) t[i] = left_t[i];
		for (var i = 0; i < right_count; i++) t[i+left_count] = right_t[i];
		return (left_count+right_count);
	}
482434
def find_order(graph):
    '''
    
    '''
    while graph:
        # Find all items without a parent
        leftmost = [l for l, s in graph.items() if not s]
        if not leftmost:
            raise ValueError('Dependency cycle detected! %s' % graph)
        # If there is more than one, sort them for predictable order
        leftmost.sort()
        for result in leftmost:
            # Yield and remove them from the graph
            yield result
            graph.pop(result)
            for bset in graph.values():
                bset.discard(result)
1177902
def dfs_edges(G, start, depth_limit=1, get_only=True, get_path=False):
    """"""
    depth_limit = depth_limit - 1

    # creates unsigned int array (2 Byte)
    output_nodes = array('L')
    output_depth = array('I')
    # creates float array (4 Byte)
    output_weights = array('f')
    apath = []

    if G.node.get(start) is None:
        # raise KeyError('Start node not found')
        print('Start node not found')
        return output_nodes, output_weights, output_depth, apath

    visited = set()
    visited.add(start)

    # Save the start node with its data to the stack
    stack = [(start, G.edges_iter(start, data=True), 1.0)]
    visited.add(start)
    while stack:
        if len(output_nodes) > 80100100:
            print("To many nodes for: {}".format(start))
            del output_nodes
            del output_weights
            del output_depth
            output_nodes = array('L')
            output_depth = array('I')
            # creates float array (4 Byte)
            output_weights = array('f')
            gc.collect()
            break
        parent, children, weight = stack[-1]
        try:
            parent_, child, child_keys = next(children)
            # print "child: {}, parent_data: {}".format(child, parent_data)
            if child not in visited:
                weight = child_keys.get('weight', 1.0) * weight
                visited.add(child)

                if len(stack) >= depth_limit or weight <= 0.00001:
                    visited.remove(child)
                else:
                    stack.append((child, G.edges_iter(child, data=True),
                                 weight))

                # if its not and user.
                if get_only and child > 100000000000:
                    # if get_only and G.node[child].get('Type') != get_only:
                    continue

                output_nodes.append(child)
                output_weights.append(weight)
                output_depth.append(len(stack))
                if get_path:
                    apath.append([step[0] for step in stack])
        except StopIteration:
            stack.pop()
            visited.remove(parent)
            # if data.get('Type') == "Node":

    return output_nodes, output_weights, output_depth, apath
362295
def get_input_nodes(G: nx.DiGraph) -> List[str]:
    
    return [n for n, d in G.in_degree() if d == 0]
1095985
function( roots, fn, directed ){
      directed = arguments.length === 1 && !$$.is.fn(fn) ? fn : directed;
      fn = $$.is.fn(fn) ? fn : function(){};
      var cy = this._private.cy;
      var v = $$.is.string(roots) ? this.filter(roots) : roots;
      var S = [];
      var connectedNodes = [];
      var connectedBy = {};
      var id2depth = {};
      var discovered = {};
      var j = 0;
      var found;
      var edges = this.edges();
      var nodes = this.nodes();

      // push v
      for( var i = 0; i < v.length; i++ ){
        if( v[i].isNode() ){
          S.push( v[i] );

          connectedNodes.push( v[i] );
          id2depth[ v[i].id() ] = 0;
        }
      }

      while( S.length !== 0 ){
        var v = S.pop();

        if( !discovered[ v.id() ] ){
          discovered[ v.id() ] = true;

          var depth = id2depth[ v.id() ];

          var ret = fn.call(v, j++, depth);

          if( ret === true ){
            found = v;
            break;
          }

          if( ret === false ){
            break;
          }

          var vwEdges = v.connectedEdges(directed ? '[source = "' + v.id() + '"]' : undefined).intersect( edges );
          
          for( var i = 0; i < vwEdges.length; i++ ){
            var e = vwEdges[i];
            var w = e.connectedNodes('[id != "' + v.id() + '"]').intersect( nodes );

            if( w.length !== 0 && !discovered[ w.id() ] ){
              w = w[0];

              S.push( w );

              id2depth[ w.id() ] = id2depth[ v.id() ] + 1;

              connectedNodes.push( w );
              connectedBy[ w.id() ] = e;
            }
          }
        }
      }

      var connectedEles = [];

      for( var i = 0; i < connectedNodes.length; i++ ){
        var node = connectedNodes[i];
        var edge = connectedBy[ node.id() ];

        if( edge ){
          connectedEles.push( edge );
        }

        connectedEles.push( node );
      }

      return {
        path: new $$.Collection( cy, connectedEles ),
        found: new $$.Collection( cy, found )
      }
    }
829685
def toposort(graph, pick_first='head'):
    
    in_deg = {}
    for node, next_nodes in six.iteritems(graph):
        for next_node in [next_nodes.head_node, next_nodes.update_node]:
            if next_node is None:
                continue
            in_deg[next_node] = in_deg.get(next_node, 0) + 1

    stk = [FIRST]
    ordered = []
    visited = set()
    while stk:
        node = stk.pop()
        visited.add(node)
        if node != FIRST:
            ordered.append(node)
        traversal = _get_traversal(graph.get(node, BeforeNodes()), pick_first)
        for next_node in traversal:
            if next_node is None:
                continue
            if next_node in visited:
                raise ValueError('Graph has a cycle')

            in_deg[next_node] -= 1
            if in_deg[next_node] == 0:
                stk.append(next_node)

    # Nodes may not be walked because they don't reach in degree 0.
    if len(ordered) != len(graph) - 1:
        raise ValueError('Graph has a cycle')
    return ordered
665782
def get_nodes(self):
        
        return self.fold_up(lambda n, fl, fg: [n] + fl + fg, lambda leaf: [leaf])
1204526
def _elimination_trees(theta, decision_variables):
    
    # auxiliary variables are any variables that are not decision
    auxiliary_variables = set(n for n in theta.linear if n not in decision_variables)

    # get the adjacency of the auxiliary subgraph
    adj = {v: {u for u in theta.adj[v] if u in auxiliary_variables}
           for v in theta.adj if v in auxiliary_variables}

    # get the elimination order that minimizes treewidth
    tw, order = dnx.treewidth_branch_and_bound(adj)

    ancestors = {}
    for n in order:
        ancestors[n] = set(adj[n])

        # now make v simplicial by making its neighborhood a clique, then
        # continue
        neighbors = adj[n]
        for u, v in itertools.combinations(neighbors, 2):
            adj[u].add(v)
            adj[v].add(u)
        for v in neighbors:
            adj[v].discard(n)
        del adj[n]

    roots = {}
    nodes = {v: {} for v in ancestors}
    for vidx in range(len(order) - 1, -1, -1):
        v = order[vidx]

        if ancestors[v]:
            for u in order[vidx + 1:]:
                if u in ancestors[v]:
                    # v is a child of u
                    nodes[u][v] = nodes[v]  # nodes[u][v] = children of v
                    break
        else:
            roots[v] = nodes[v]  # roots[v] = children of v

    return roots, ancestors
77221
def _internal_get_cut_vertex_list(graph):
    
    list_of_cut_vertices = set()
    if graph.num_nodes() == 0:
        return list(list_of_cut_vertices)

    dfs_count = 0
    root_dfs_count = 1
    dfs_stack = deque()
    visited = defaultdict(lambda: False)
    parent = defaultdict(lambda: None)
    children = defaultdict(lambda: [])
    depth = {}
    low = {}
    preorder_processed = defaultdict(lambda: False)
    postorder_processed = defaultdict(lambda: False)

    # We're simulating a recursive DFS with an explicit stack, since Python has a really small function stack
    unvisited_nodes = set(graph.get_all_node_ids())
    while len(unvisited_nodes) > 0:
        # --Initialize the first stack frame, simulating the DFS call on the root node
        u = unvisited_nodes.pop()
        parent[u] = u
        stack_frame = {
            'u': u,
            'v': None,
            'remaining_children': graph.neighbors(u)
        }
        dfs_stack.appendleft(stack_frame)

        while len(dfs_stack) > 0:
            frame = dfs_stack.popleft()
            u = frame['u']
            v = frame['v']

            if not visited[u]:
                if u in unvisited_nodes:
                    unvisited_nodes.remove(u)
                visited[u] = True
                dfs_count += 1
                depth[u] = dfs_count
                low[u] = depth[u]
                if len(frame['remaining_children']) > 0:
                    v = frame['remaining_children'].pop()
                    frame['v'] = v

            if v is None:
                # --u has no neighbor nodes
                continue

            if not preorder_processed[v]:
                # --This is the preorder processing, done for each neighbor node ''v'' of u
                parent[v] = u
                children[u].append(v)
                preorder_processed[v] = True
                # print 'preorder for {}'.format(v)
                dfs_stack.appendleft(frame)

                # --Simulate the recursion to call the DFS on v
                new_frame = {
                    'u': v,
                    'v': None,
                    'remaining_children': graph.neighbors(v)
                }
                dfs_stack.appendleft(new_frame)
                continue

            elif not postorder_processed[v] and u == parent[v]:
                # --This is the postorder processing, done for each neighbor node ''v'' of u
                if low[v] >= depth[u] and depth[u] > 1:
                    list_of_cut_vertices.add(u)
                low[u] = min(low[u], low[v])
                postorder_processed[v] = True
                # print 'postorder for {}'.format(v)

            elif visited[v] and (parent[u] != v) and (depth[v] < depth[u]):
                # (u,v) is a backedge from u to its ancestor v
                low[u] = min(low[u], depth[v])

            if len(frame['remaining_children']) > 0:
                # --Continue onto the next neighbor node of u
                v = frame['remaining_children'].pop()
                frame['v'] = v
                dfs_stack.appendleft(frame)

    # The root node gets special treatment; it's a cut vertex iff it has multiple children
    if len(children[root_dfs_count]) > 1:
        for node_id, dfs in list(depth.items()):
            if dfs == root_dfs_count:
                list_of_cut_vertices.add(node_id)
                break

    return list(list_of_cut_vertices)
490077
function( roots, fn, directed ){
      directed = arguments.length === 1 && !$$.is.fn(fn) ? fn : directed;
      fn = $$.is.fn(fn) ? fn : function(){};
      var cy = this._private.cy;
      var v = $$.is.string(roots) ? this.filter(roots) : roots;
      var Q = [];
      var connectedEles = [];
      var connectedFrom = {};
      var id2depth = {};
      var V = {};
      var j = 0;
      var found;
      var nodes = this.nodes();
      var edges = this.edges();

      // enqueue v
      for( var i = 0; i < v.length; i++ ){
        if( v[i].isNode() ){
          Q.unshift( v[i] );
          V[ v[i].id() ] = true; 

          connectedEles.push( v[i] );
          id2depth[ v[i].id() ] = 0;
        }
      }

      while( Q.length !== 0 ){
        var v = Q.shift();
        var depth = id2depth[ v.id() ];
        var ret = fn.call(v, j++, depth);

        if( ret === true ){
          found = v;
          break;
        }

        if( ret === false ){
          break;
        }

        var vwEdges = v.connectedEdges(directed ? '[source = "' + v.id() + '"]' : undefined).intersect( edges );
        for( var i = 0; i < vwEdges.length; i++ ){
          var e = vwEdges[i];
          var w = e.connectedNodes('[id != "' + v.id() + '"]').intersect( nodes );

          if( w.length !== 0 && !V[ w.id() ] ){
            w = w[0];

            Q.push( w );
            V[ w.id() ] = true;

            id2depth[ w.id() ] = id2depth[ v.id() ] + 1;

            connectedEles.push( w );
            connectedEles.push( e );
          }
        }
        
      }

      return {
        path: new $$.Collection( cy, connectedEles ),
        found: new $$.Collection( cy, found )
      };
    }
1041
public static <T> DiGraphIterator<T> getInstance(T root, Function<? super T, ? extends Collection<T>> edges)
    {
        return new DiGraphIterator<>(root, (y)->edges.apply(y).stream());
    }
675292
def predecessors(self, node, graph=None):
        
        if graph is None:
            graph = self.graph
        return [key for key in graph if node in graph[key]]
1073938
def _neighbors(self,v):
        
        assert self.layout.dag
        dirv = self.layout.dirv
        grxv = self.layout.grx[v]
        try: #(cache)
            return grxv.nvs[dirv]
        except AttributeError:
            grxv.nvs={-1:v.N(-1),+1:v.N(+1)}
            if grxv.dummy: return grxv.nvs[dirv]
            # v is real, v.N are graph neigbors but we need layers neighbors
            for d in (-1,+1):
                tr=grxv.rank+d
                for i,x in enumerate(v.N(d)):
                    if self.layout.grx[x].rank==tr:continue
                    e=v.e_with(x)
                    dum = self.layout.ctrls[e][tr]
                    grxv.nvs[d][i]=dum
            return grxv.nvs[dirv]
295484
def find_root(self):
        """"""
        self.find_parents()
        index = 0
        while len(self.vertices[index].parents)>0:
            index = self.vertices[index].parents[0]
        return index
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();
}