Iteratively assign the breadth (x-position) for each node. Nodes are assigned the maximum breadth of incoming neighbors plus one; nodes with no incoming links are assigned breadth zero, while nodes with no outgoing links are assigned the maximum breadth.
515320
function computeNodeBreadths() {
    var remainingNodes = nodes,
        nextNodes,
        x = 0;

    while (remainingNodes.length) {
      nextNodes = [];
      remainingNodes.forEach(function(node) {
        node.x = x;
        node.dx = nodeWidth;
        node.sourceLinks.forEach(function(link) {
          if (!link.causesCycle) {
            nextNodes.push(link.target);
          }
        });
      });
      remainingNodes = nextNodes;
      ++x;
    }

    //
    moveSinksRight(x);
    scaleNodeBreadths((size[0] - nodeWidth) / (x - 1));
  }
972962
function computeNodeValues(nodes) {
    zrUtil.each(nodes, function (node) {
        var value1 = sum(node.outEdges, getEdgeValue);
        var value2 = sum(node.inEdges, getEdgeValue);
        var value = Math.max(value1, value2);
        node.setLayout({value: value}, true);
    });
}
741168
public <E extends Edge> double[] compute(Graph<E> g) {
        // Perform a quick test for whether the vertices of g are a contiguous
        // sequence starting at 0, which makes the vertex mapping trivial
        if (!hasContiguousVertices(g))
            throw new IllegalArgumentException(
                "Vertices must be in continugous order");
        
        double[] centralities = new double[g.order()];
        IntIterator vertexIter = g.vertices().iterator();
        while (vertexIter.hasNext()) {
            int s = vertexIter.nextInt();
            Deque<Integer> S = new ArrayDeque<Integer>();

            // Initialize P to an empty list for each vertex
            List<List<Integer>> P = new ArrayList<List<Integer>>(g.order());
            for (int i = 0; i < g.order(); ++i)
                P.add(new ArrayList<Integer>());

            double[] sigma = new double[g.order()];
            sigma[s] = 1;

            double[] d = new double[g.order()];
            Arrays.fill(d, -1);
            d[s] = 0;
            
            Queue<Integer> Q = new ArrayDeque<Integer>();
            Q.add(s);
            while (!Q.isEmpty()) {
                int v = Q.poll();
                S.offer(v);
                IntIterator neighborIter = g.getNeighbors(v).iterator();
                while (neighborIter.hasNext()) { 
                    int w = neighborIter.nextInt();
                    // Check whether this is the first time we've seen vertex w
                    if (d[w] < 0) {
                        Q.offer(w);
                        d[w] = d[v] + 1;
                    }
                    // Check whether the shortest path to w is through v
                    if (d[w] == d[v] + 1) {
                        sigma[w] += sigma[v];
                        P.get(w).add(v);
                    }
                }
            }
            double[] delta = new double[g.order()];
            // S as a stack returns vertices in order of their non-increasing
            // distance from vertex s
            while (!S.isEmpty()) {
                int w = S.pollLast(); // get the top of the stack
                for (int v : P.get(w)) {
                    delta[v] += (sigma[v] / sigma[w]) * (1 + delta[w]);
                }
                if (w != s) {
                    centralities[w] += delta[w];
                }            
            }
        }
        return centralities;
    }
1106294
static boolean isOpenEdge( SquareNode node , int index ) {
		if( node.edges[index] == null )
			return false;
		int marker = node.edges[index].destination(node).graph;
		return marker == SquareNode.RESET_GRAPH;
	}
21094
def ind_nodes(self, graph=None):
        
        if graph is None:
            graph = self.graph

        dependent_nodes = set(
            node for dependents in six.itervalues(graph) for node in dependents
        )
        return [node for node in graph.keys() if node not in dependent_nodes]
1305696
public static Weighted<Arborescence<Node>> getMaxArborescence(WeightedGraph graph) {
        final PartialSolution partialSolution =
                PartialSolution.initialize(graph.filterEdges(not(DirectedEdge.isAutoCycle())));
        // In the beginning, subgraph has no edges, so no SCC has in-edges.
        final Deque<Node> componentsWithNoInEdges = new ArrayDeque<>(partialSolution.getNodes());

        // Work our way through all componentsWithNoInEdges, in no particular order
        while (!componentsWithNoInEdges.isEmpty()) {
            final Node component = componentsWithNoInEdges.poll();
            // find maximum edge entering 'component' from outside 'component'.
            final Optional<ExclusiveEdge> oMaxInEdge = partialSolution.popBestEdge(component);
            if (!oMaxInEdge.isPresent()) continue; // No in-edges left to consider for this component. Done with it!
            final ExclusiveEdge maxInEdge = oMaxInEdge.get();
            // add the new edge to subgraph, merging SCCs if necessary
            final Optional<Node> newComponent = partialSolution.addEdge(maxInEdge);
            if (newComponent.isPresent()) {
                // addEdge created a cycle/component, which means the new component doesn't have any incoming edges
                componentsWithNoInEdges.add(newComponent.get());
            }
        }
        // Once no component has incoming edges left to consider, it's time to recover the optimal branching.
        return partialSolution.recoverBestArborescence();
    }
1284515
def BFS_Tree(G, start):
    
    if start not in G.vertices:
        raise GraphInsertError("Vertex %s doesn't exist." % (start,))
    pred = BFS(G, start)
    T = digraph.DiGraph()
    queue = Queue()
    queue.put(start)
    while queue.qsize() > 0:
        current = queue.get()
        for element in pred:
            if pred[element] == current:
                T.add_edge(current, element)
                queue.put(element)
    return T
1125947
def one_to_one(graph, nodes):
    
    edges = itertools.chain.from_iterable(graph.values())
    return len(graph) == len(nodes) and len(set(edges)) == len(nodes)
1265479
def initial_edges(self) -> iter:
        """"""
        nodes_in = lambda n: ([n] if self.is_node(n) else self.nodes_in(n))
        for node, succs in self.edges.items():
            twos = tuple(two for succ in succs for two in nodes_in(succ))
            for one in nodes_in(node):
                for two in twos:
                    yield one, two
396496
def neighbors_of( p )
      Set.new.tap do |neighbors|
        i = index_mapping[p]
        (0..index_mapping.size-1).each do |j|
          neighbors.add(points[j]) if adjacency_matrix.lookup(i,j) <= eps
        end
      end
    end
1040156
def neighborhood(self, node, degree=4):
    """"""
    assert self.by_name[node.name] == node
    already_visited = frontier = set([node.name])
    for _ in range(degree):
      neighbor_names = set()
      for node_name in frontier:
        outgoing = set(n.name for n in self.by_input[node_name])
        incoming = set(self.by_name[node_name].input)
        neighbor_names |= incoming | outgoing
      frontier = neighbor_names - already_visited
      already_visited |= neighbor_names
    return [self.by_name[name] for name in already_visited]
887929
public IntArrayList bfs(int root, boolean isRootT1, boolean[] marked1, boolean[] marked2) {
        IntArrayList ccorder = new IntArrayList();
        Queue<Integer> qNode = new ArrayDeque<>();
        Queue<Boolean> qIsT1 = new ArrayDeque<>();
        qNode.add(root);
        qIsT1.add(isRootT1);

        while (!qNode.isEmpty()) {
            // Process the next node in the queue.
            int parent = qNode.remove();
            boolean isT1 = qIsT1.remove();

            if (isT1) {
                // Visit node only if not marked.
                if (!marked1[parent]) {
                    log.trace("Visiting node {} of type T1", parent);
                    // For each neighbor...
                    for (int nb = 0; nb < this.numNbsT1(parent); nb++) {
                        int e = this.edgeT1(parent, nb);
                        int child = this.childE(e);
                        if (!marked2[child]) {
                            // If the neighbor is not marked, queue the node and add the edge to
                            // the order.
                            qNode.add(child);
                            qIsT1.add(false);
                            ccorder.add(e);
                        }
                    }
                    // Mark the node as visited.
                    marked1[parent] = true;
                }
            } else {
                // Visit node only if not marked.
                if (!marked2[parent]) {
                    log.trace("Visiting node {} of type T2", parent);
                    // For each neighbor...
                    for (int nb = 0; nb < this.numNbsT2(parent); nb++) {
                        int e = this.edgeT2(parent, nb);
                        int child = this.childE(e);
                        if (!marked1[child]) {
                            // If the neighbor is not marked, queue the node and add the edge to
                            // the order.
                            qNode.add(child);
                            qIsT1.add(true);
                            ccorder.add(e);
                        }
                    }
                    // Mark the node as visited.
                    marked2[parent] = true;
                }
            }
        }
        return ccorder;
    }
1052112
def bfs(graph, start=0):
    
    to_visit = deque()
    dist = [float('inf')] * len(graph)
    prec = [None] * len(graph)
    dist[start] = 0
    to_visit.appendleft(start)
    while to_visit:              # an empty queue is considered False
        node = to_visit.pop()
        for neighbor in graph[node]:
            if dist[neighbor] == float('inf'):
                dist[neighbor] = dist[node] + 1
                prec[neighbor] = node
                to_visit.appendleft(neighbor)
    return dist, prec
311506
def find_path_BFS(Graph,n,m):
    
    if m not in Graph:
        return None
    if n == m:
        return [m]
    path = [[n]]
    searched = []
    while True:
        j = len(path)
        #k = len(Graph[n])
        for i in range(j):
            node = path[i][-1]
            for neighbor in Graph[node]:
                if neighbor not in searched:                    
                    path.append(path[i]+[neighbor])  
                    searched.append(neighbor)
                    if neighbor==m:
                        return path[-1]
        for i in range(j):
            path.pop(0)
    return path
1098849
def number_of_links(neighbors, datapoints, x, y)
      (0..datapoints.size-1).map do |i|
        neighbors.lookup(x,i) * neighbors.lookup(i,y)
      end.inject(0) {|m,v| m+v}
    end
599036
def iteration(self, node_status=True):
        
        # One iteration changes the opinion of all agents using the following procedure:
        # - first all agents communicate with institutional information I using a deffuant like rule
        # - then random pairs of agents are selected to interact  (N pairs)
        # - interaction depends on state of agents but also internal cognitive structure

        self.clean_initial_status(None)

        actual_status = {node: nstatus for node, nstatus in future.utils.iteritems(self.status)}

        if self.actual_iteration == 0:
            self.actual_iteration += 1
            delta, node_count, status_delta = self.status_delta(self.status)
            if node_status:
                return {"iteration": 0, "status": self.status.copy(),
                        "node_count": node_count.copy(), "status_delta": status_delta.copy()}
            else:
                return {"iteration": 0, "status": {},
                        "node_count": node_count.copy(), "status_delta": status_delta.copy()}

        # first interact with I
        I = self.params['model']['I']
        for node in self.graph.nodes():
            T = self.params['nodes']['cognitive'][node][2]
            R = self.params['nodes']['cognitive'][node][0]
            actual_status[node] = actual_status[node] + T * (I - actual_status[node])
            if R == 1:
                actual_status[node] = 0.5 * (1 + actual_status[node])
            if R == -1:
                actual_status[node] *= 0.5

        # then interact with peers
        for i in range(0, self.graph.number_of_nodes()):
            # select a random node
            n1 = list(self.graph.nodes)[np.random.randint(0, self.graph.number_of_nodes())]

            # select all of the nodes neighbours (no digraph possible)
            neighbours = list(self.graph.neighbors(n1))
            if len(neighbours) == 0:
                continue

            # select second node - a random neighbour
            n2 = neighbours[np.random.randint(0, len(neighbours))]

            # update status of n1 and n2
            p1 = pow(actual_status[n1], 1.0 / self.params['nodes']['cognitive'][n1][1])
            p2 = pow(actual_status[n2], 1.0 / self.params['nodes']['cognitive'][n2][1])

            oldn1 = self.status[n1]
            if np.random.random_sample() < p2:  # if node 2 talks, node 1 gets changed
                T1 = self.params['nodes']['cognitive'][n1][2]
                R1 = self.params['nodes']['cognitive'][n1][0]
                actual_status[n1] += (1 - T1) * (actual_status[n2] - actual_status[n1])
                if R1 == 1:
                    actual_status[n1] = 0.5 * (1 + actual_status[n1])
                if R1 == -1:
                    actual_status[n1] *= 0.5
            if np.random.random_sample() < p1:  # if node 1 talks, node 2 gets changed
                T2 = self.params['nodes']['cognitive'][n2][2]
                R2 = self.params['nodes']['cognitive'][n2][0]
                actual_status[n2] += (1 - T2) * (oldn1 - actual_status[n2])
                if R2 == 1:
                    actual_status[n2] = 0.5 * (1 + actual_status[n2])
                if R2 == -1:
                    actual_status[n2] *= 0.5

        delta, node_count, status_delta = self.status_delta(actual_status)
        self.status = actual_status
        self.actual_iteration += 1

        if node_status:
            return {"iteration": self.actual_iteration - 1, "status": delta.copy(),
                    "node_count": node_count.copy(), "status_delta": status_delta.copy()}
        else:
            return {"iteration": self.actual_iteration - 1, "status": {},
                    "node_count": node_count.copy(), "status_delta": status_delta.copy()}
444547
def iteration(self, node_status=True):
        
        self.clean_initial_status(self.available_statuses.values())

        actual_status = {node: nstatus for node, nstatus in future.utils.iteritems(self.status)}

        if self.actual_iteration == 0:
            self.actual_iteration += 1
            self.params['model']['queue'] = dict()
            return 0, actual_status

        gamma = float(self.params['model']['mu']) * float(self.actual_iteration) / float(self.params['model']['tau'])
        list_node = self.graph.nodes()
        start = min(list_node)
        stop = max(list_node)
        number_node_susceptible = len(self.graph.nodes()) - sum(self.status.values())

        while gamma >= 1 and number_node_susceptible >= 1:
            random_index = random.randrange(start, stop+1, 1)
            if random_index in list_node and actual_status[random_index] == 0:
                actual_status[random_index] = 1
                gamma -= 1
                number_node_susceptible -= 1

        for u in self.graph.nodes():
            if actual_status[u] == 1:
                continue

            neighbors = list(self.graph.neighbors(u))
            if isinstance(self.graph, nx.DiGraph):
                neighbors = list(self.graph.predecessors(u))

            infected = 0
            for v in neighbors:
                infected += self.status[v]

            if len(neighbors) > 0:
                infected_ratio = float(infected)/len(neighbors)
                if infected_ratio >= self.params['nodes']['threshold'][u]:
                    if u not in self.inqueue:
                        self.queue.put((self.actual_iteration, u))
                        self.inqueue[u] = None

        while not self.queue.empty():
            next = self.queue.queue[0]
            if self.actual_iteration - next[0] >= self.params['model']['tau']:
                self.queue.get()
            else:
                break

        delta = self.status_delta(actual_status)
        self.status = actual_status
        self.actual_iteration += 1

        return self.actual_iteration - 1, delta