Compute shortest path length between satrt
    and all other reachable nodes for a weight graph.
    return -> ({vertex: weight form start, }, {vertex: predeseccor, })
190771
def dijkstra(G, start, weight='weight'):
    
    if start not in G.vertices:
        raise GraphInsertError("Vertex %s doesn't exist." % (start,))
    visited = {start: 0}
    path = {}
    vertices = set(G.vertices.keys())
    while vertices:
        min_vertex = None
        for vertex in vertices:
            if vertex in visited:
                if min_vertex is None or visited[vertex] < visited[min_vertex]:
                    min_vertex = vertex
        if min_vertex is None:
            break
        vertices.remove(min_vertex)
        current_weight = visited[min_vertex]
        for edge in G.vertices[min_vertex]:
            edge_weight = current_weight + G.edges[(min_vertex, edge)][weight]
            if edge not in visited or edge_weight < visited[edge]:
                visited[edge] = edge_weight
                path[edge] = min_vertex
    return visited, path
1006550
def pseudotime(starting_node, edges, fitted_vals):
    
    # TODO
    # 1. calculate a distance matrix...
    distances = np.array([[sum((x - y)**2) for x in fitted_vals.T] for y in fitted_vals.T])
    # 2. start from the root node/cell, calculate distance along graph
    distance_dict = graph_distances(starting_node, edges, distances)
    output = []
    for i in range(fitted_vals.shape[1]):
        output.append(distance_dict[i])
    return np.array(output)
318077
def optimize(self, graph):
                
        for center in self.centers:
            shortest_routes = shortest_path(graph, center)[1]
            for node, weight in list(shortest_routes.items()):
                self.nodes.setdefault(node, []).append(weight)
928549
def computeNodeValues(cls, graph):
        
        for node in graph['nodes']:
            source_val = np.sum([l['value'] for l in node['sourceLinks']])
            target_val = np.sum([l['value'] for l in node['targetLinks']])
            node['value'] = max([source_val, target_val])
327136
synchronized Weight getMaximumFinish() {
        if (calcMaxFinish == null) {
            // Find the longest distance from time zero to a finish.
            Weight result = WeightFactory.NEG_INFINITY;
            if (shortestDistancesFromTimeZeroSource == null) {
                shortestDistancesFromTimeZeroSource = BellmanFord.calcShortestDistances(timeZero, directedGraph,
                        BellmanFord.Mode.SOURCE);
                if (shortestDistancesFromTimeZeroSource == null) {
                    throw new IllegalStateException("Negative cycle detected!");
                }
            }
            for (int i = 0, n = intervals.size(); i < n; i++) {
                Object finish = intervals.get(i).getFinish();
                result = Weight.max(result,
                        (Weight) shortestDistancesFromTimeZeroSource.get(finish));
            }
            calcMaxFinish = result;
        }

        return calcMaxFinish;
    }
572298
private List<Trip.Leg> parsePathIntoLegs(List<Label.Transition> path, Graph graph, Weighting weighting, Translation tr) {
        if (path.size() <= 1) {
            return Collections.emptyList();
        }
        if (GtfsStorage.EdgeType.ENTER_PT == path.get(1).edge.edgeType) {
            final GtfsStorage.FeedIdWithTimezone feedIdWithTimezone = gtfsStorage.getTimeZones().get(path.get(2).edge.timeZoneId);
            List<Trip.Leg> result = new ArrayList<>();
            long boardTime = -1;
            List<Label.Transition> partition = null;
            for (int i = 1; i < path.size(); i++) {
                Label.Transition transition = path.get(i);
                Label.EdgeLabel edge = path.get(i).edge;
                if (edge.edgeType == GtfsStorage.EdgeType.BOARD) {
                    boardTime = transition.label.currentTime;
                    partition = new ArrayList<>();
                }
                if (partition != null) {
                    partition.add(path.get(i));
                }
                if (EnumSet.of(GtfsStorage.EdgeType.TRANSFER, GtfsStorage.EdgeType.LEAVE_TIME_EXPANDED_NETWORK).contains(edge.edgeType)) {
                    Geometry lineString = lineStringFromEdges(partition);
                    GtfsRealtime.TripDescriptor tripDescriptor;
                    try {
                        tripDescriptor = GtfsRealtime.TripDescriptor.parseFrom(realtimeFeed.getTripDescriptor(partition.get(0).edge.edgeIteratorState.getEdge()));
                    } catch (InvalidProtocolBufferException e) {
                        throw new RuntimeException(e);
                    }
                    final StopsFromBoardHopDwellEdges stopsFromBoardHopDwellEdges = new StopsFromBoardHopDwellEdges(feedIdWithTimezone.feedId, tripDescriptor);
                    partition.stream()
                            .filter(e -> EnumSet.of(GtfsStorage.EdgeType.HOP, GtfsStorage.EdgeType.BOARD, GtfsStorage.EdgeType.DWELL).contains(e.edge.edgeType))
                            .forEach(stopsFromBoardHopDwellEdges::next);
                    stopsFromBoardHopDwellEdges.finish();
                    List<Trip.Stop> stops = stopsFromBoardHopDwellEdges.stops;

                    result.add(new Trip.PtLeg(
                            feedIdWithTimezone.feedId, partition.get(0).edge.nTransfers == 0,
                            tripDescriptor.getTripId(),
                            tripDescriptor.getRouteId(),
                            edges(partition).map(edgeLabel -> edgeLabel.edgeIteratorState).collect(Collectors.toList()).get(0).getName(),
                            stops,
                            partition.stream().mapToDouble(t -> t.edge.distance).sum(),
                            path.get(i - 1).label.currentTime - boardTime,
                            lineString));
                    partition = null;
                }
            }
            return result;
        } else {
            InstructionList instructions = new InstructionList(tr);
            InstructionsFromEdges instructionsFromEdges = new InstructionsFromEdges(path.get(1).edge.edgeIteratorState.getBaseNode(), graph,
                    weighting, weighting.getFlagEncoder(), weighting.getFlagEncoder().getBooleanEncodedValue(EncodingManager.ROUNDABOUT), graph.getNodeAccess(), tr, instructions);
            int prevEdgeId = -1;
            for (int i = 1; i < path.size(); i++) {
                if (path.get(i).edge.edgeType != GtfsStorage.EdgeType.HIGHWAY) {
                    throw new IllegalStateException("Got a transit edge where I think I must be on a road.");
                }
                EdgeIteratorState edge = path.get(i).edge.edgeIteratorState;
                instructionsFromEdges.next(edge, i, prevEdgeId);
                prevEdgeId = edge.getEdge();
            }
            instructionsFromEdges.finish();
            final Instant departureTime = Instant.ofEpochMilli(path.get(0).label.currentTime);
            final Instant arrivalTime = Instant.ofEpochMilli(path.get(path.size() - 1).label.currentTime);
            return Collections.singletonList(new Trip.WalkLeg(
                    "Walk",
                    Date.from(departureTime),
                    lineStringFromEdges(path),
                    edges(path).mapToDouble(edgeLabel -> edgeLabel.distance).sum(),
                    instructions,
                    Date.from(arrivalTime)));
        }
    }
108447
def neighborhood_subgraph(self, start_idx, radius=1, weighted=True,
                            directed=True, return_mask=False):
    ''''''
    adj = self.matrix('dense', 'csr', 'csc')
    dist = ssc.dijkstra(adj, directed=directed, indices=start_idx,
                        unweighted=(not weighted), limit=radius)
    mask = np.isfinite(dist)
    sub_adj = adj[mask][:,mask]
    g = self.__class__.from_adj_matrix(sub_adj)
    if return_mask:
      return g, mask
    return g
968083
function(node1, node2, previousPathLength) {
    var isEverythingDefined =
      node1 != undefined &&
      node2 != undefined &&
      node1.x != undefined &&
      node1.y != undefined &&
      node2.x != undefined &&
      node2.y != undefined;
    if(!isEverythingDefined) {
      return undefined;
    }

    return (previousPathLength || 0) + Math.sqrt(
      Math.pow((node2.y - node1.y), 2) + Math.pow((node2.x - node1.x), 2)
    );
  }
1124095
def collapse(self, weight_attr='weight'):
        

        if self.directed:
            graph = nx.DiGraph()
        else:
            graph = nx.Graph()

        # Transfer all nodes and attributes.
        for n, attrs in self.master_graph.nodes(data=True):
            graph.add_node(n, attrs)

        for s, t, attrs in self.master_graph.edges(data=True):
            if not graph.has_edge(s, t):
                graph.add_edge(s, t)

            if 'weight' not in graph[s][t]:
                graph[s][t]['weight'] = 0.
            if weight_attr in attrs:
                graph[s][t]['weight'] += attrs[weight_attr]
            else:
                graph[s][t]['weight'] += 1.

            gname = attrs['graph']
            for k, v in attrs.iteritems():
                if k in [weight_attr, 'graph']:
                    continue
                if k not in graph[s][t]:
                    graph[s][t][k] = {}
                graph[s][t][k][gname] = v
        return graph
119127
def diameter(self):
        '''
        '''
        d = dict(); best = float('-inf')
        for node in self.traverse_postorder():
            if node.is_leaf():
                d[node] = 0
            else:
                dists = sorted(d[c]+c.edge_length for c in node.children)
                d[node] = dists[-1]; max_pair = dists[-1]+dists[-2]
                if max_pair > best:
                    best = max_pair
        return best
561948
function spfa(graph, s) {
  const distance = {};
  const previous = {};
  const queue = {};
  const isInQue = {};
  const cnt = {};
  let head = 0;
  let tail = 1;
  // initialize
  distance[s] = 0;
  queue[0] = s;
  isInQue[s] = true;
  cnt[s] = 1;
  graph.vertices.forEach(v => {
    if (v !== s) {
      distance[v] = Infinity;
      isInQue[v] = false;
      cnt[v] = 0;
    }
  });

  let currNode;
  while (head !== tail) {
    currNode = queue[head++];
    isInQue[currNode] = false;
    const neighbors = graph.neighbors(currNode);
    for (let i = 0; i < neighbors.length; i++) {
      const v = neighbors[i];
      // relaxation
      const newDistance = distance[currNode] + graph.edge(currNode, v);
      if (newDistance < distance[v]) {
        distance[v] = newDistance;
        previous[v] = currNode;
        if (!isInQue[v]) {
          queue[tail++] = v;
          isInQue[v] = true;
          cnt[v]++;
          if (cnt[v] > graph.vertices.size) {
            // indicates negative-weighted cycle
            return {
              distance: {}
            };
          }
        }
      }
    }
  }

  return {
    distance,
    previous
  };
}
1176835
def _compute_linear_weights_edge(idcs, ndist):
    """"""
    # Get out-of-bounds indices from the norm_distances. Negative
    # means "too low", larger than or equal to 1 means "too high"
    lo = np.where(ndist < 0)
    hi = np.where(ndist > 1)

    # For "too low" nodes, the lower neighbor gets weight zero;
    # "too high" gets 2 - yi (since yi >= 1)
    w_lo = (1 - ndist)
    w_lo[lo] = 0
    w_lo[hi] += 1

    # For "too high" nodes, the upper neighbor gets weight zero;
    # "too low" gets 1 + yi (since yi < 0)
    w_hi = np.copy(ndist)
    w_hi[lo] += 1
    w_hi[hi] = 0

    # For upper/lower out-of-bounds nodes, we need to set the
    # lower/upper neighbors to the last/first grid point
    edge = [idcs, idcs + 1]
    edge[0][hi] = -1
    edge[1][lo] = 0

    return w_lo, w_hi, edge
993911
def path_exists(self, dest, weight=None):
        
        try:
            return bool(self.shortest_path_length(dest, weight))
        except KeyError:
            return False
854852
function getSubjectBarycenter(subject){

	var weighted_number_of_edges = 0;
	var number_of_edges = 0;
	for( var o = 1; o <= object_vector.length; o++ ){
	    if( relation_matrix[object_vector[o -1].id()] &&
		relation_matrix[object_vector[o -1].id()][subject.id()]){
		weighted_number_of_edges += o;
		number_of_edges++;
	    }
	}
	// The '-1' is to offset the indexing.
	return ( weighted_number_of_edges / number_of_edges ) -1;
    }
328049
def complete(self, match, subject_graph):
        """"""
        if not CustomPattern.complete(self, match, subject_graph):
            return False
        if self.strong:
            # If the ring is not strong, return False
            if self.size % 2 == 0:
                # even ring
                for i in range(self.size//2):
                    vertex1_start = match.forward[i]
                    vertex1_stop = match.forward[(i+self.size//2)%self.size]
                    paths = list(subject_graph.iter_shortest_paths(vertex1_start, vertex1_stop))
                    if len(paths) != 2:
                        #print "Even ring must have two paths between opposite vertices"
                        return False
                    for path in paths:
                        if len(path) != self.size//2+1:
                            #print "Paths between opposite vertices must half the size of the ring+1"
                            return False
            else:
                # odd ring
                for i in range(self.size//2+1):
                    vertex1_start = match.forward[i]
                    vertex1_stop = match.forward[(i+self.size//2)%self.size]
                    paths = list(subject_graph.iter_shortest_paths(vertex1_start, vertex1_stop))
                    if len(paths) > 1:
                        return False
                    if len(paths[0]) != self.size//2+1:
                        return False
                    vertex1_stop = match.forward[(i+self.size//2+1)%self.size]
                    paths = list(subject_graph.iter_shortest_paths(vertex1_start, vertex1_stop))
                    if len(paths) > 1:
                        return False
                    if len(paths[0]) != self.size//2+1:
                        return False
        return True
180108
public void findAllCC() {
		if (nodeCC == null) {
			CCFirstNode = new int[n];
			CCNextNode = new int[n];
			nodeCC = new int[n];
			sizeCC = new int[n];
		}
		sizeMinCC = 0;
		sizeMaxCC = 0;
		ISet act = graph.getNodes();
		for (int i : act) {
			p[i] = -1;
		}
		for (int i = 0; i < CCFirstNode.length; i++) {
			CCFirstNode[i] = -1;
			sizeCC[i] = -1;
		}
		int cc = 0;
		for (int i : act) {
			if (p[i] == -1) {
				findCC(i, cc);
				if (sizeMinCC == 0 || sizeMinCC > sizeCC[cc]) {
					sizeMinCC = sizeCC[cc];
				}
				if (sizeMaxCC < sizeCC[cc]) {
					sizeMaxCC = sizeCC[cc];
				}
				cc++;
			}
		}
		nbCC = cc;
	}
881932
def find_tree(sub_network, weight='x_pu'):
    

    branches_bus0 = sub_network.branches()["bus0"]
    branches_i = branches_bus0.index
    buses_i = sub_network.buses_i()

    graph = sub_network.graph(weight=weight, inf_weight=1.)
    sub_network.tree = nx.minimum_spanning_tree(graph)

    #find bus with highest degree to use as slack
    tree_slack_bus, slack_degree = max(degree(sub_network.tree), key=itemgetter(1))
    logger.info("Tree slack bus is %s with degree %d.", tree_slack_bus, slack_degree)

    #determine which buses are supplied in tree through branch from slack

    #matrix to store tree structure
    sub_network.T = dok_matrix((len(branches_i),len(buses_i)))

    for j,bus in enumerate(buses_i):
        path = nx.shortest_path(sub_network.tree,bus,tree_slack_bus)
        for i in range(len(path)-1):
            branch = next(iterkeys(graph[path[i]][path[i+1]]))
            branch_i = branches_i.get_loc(branch)
            sign = +1 if branches_bus0.iat[branch_i] == path[i] else -1
            sub_network.T[branch_i,j] = sign