Implemented from the algorithm in the paper "On Variants of Shortest-Path Betweenness Centrality and their Generic Computation" by Ulrik Brandes
548364
function betweennessCentrality(options) {
    var _defaults = defaults$3(options),
        directed = _defaults.directed,
        weight = _defaults.weight;

    var weighted = weight != null;
    var cy = this.cy(); // starting

    var V = this.nodes();
    var A = {};
    var _C = {};
    var max = 0;
    var C = {
      set: function set(key, val) {
        _C[key] = val;

        if (val > max) {
          max = val;
        }
      },
      get: function get(key) {
        return _C[key];
      }
    }; // A contains the neighborhoods of every node

    for (var i = 0; i < V.length; i++) {
      var v = V[i];
      var vid = v.id();

      if (directed) {
        A[vid] = v.outgoers().nodes(); // get outgoers of every node
      } else {
        A[vid] = v.openNeighborhood().nodes(); // get neighbors of every node
      }

      C.set(vid, 0);
    }

    var _loop = function _loop(s) {
      var sid = V[s].id();
      var S = []; // stack

      var P = {};
      var g = {};
      var d = {};
      var Q = new Heap(function (a, b) {
        return d[a] - d[b];
      }); // queue
      // init dictionaries

      for (var _i = 0; _i < V.length; _i++) {
        var _vid = V[_i].id();

        P[_vid] = [];
        g[_vid] = 0;
        d[_vid] = Infinity;
      }

      g[sid] = 1; // sigma

      d[sid] = 0; // distance to s

      Q.push(sid);

      while (!Q.empty()) {
        var _v = Q.pop();

        S.push(_v);

        if (weighted) {
          for (var j = 0; j < A[_v].length; j++) {
            var w = A[_v][j];
            var vEle = cy.getElementById(_v);
            var edge = void 0;

            if (vEle.edgesTo(w).length > 0) {
              edge = vEle.edgesTo(w)[0];
            } else {
              edge = w.edgesTo(vEle)[0];
            }

            var edgeWeight = weight(edge);
            w = w.id();

            if (d[w] > d[_v] + edgeWeight) {
              d[w] = d[_v] + edgeWeight;

              if (Q.nodes.indexOf(w) < 0) {
                //if w is not in Q
                Q.push(w);
              } else {
                // update position if w is in Q
                Q.updateItem(w);
              }

              g[w] = 0;
              P[w] = [];
            }

            if (d[w] == d[_v] + edgeWeight) {
              g[w] = g[w] + g[_v];
              P[w].push(_v);
            }
          }
        } else {
          for (var _j = 0; _j < A[_v].length; _j++) {
            var _w = A[_v][_j].id();

            if (d[_w] == Infinity) {
              Q.push(_w);
              d[_w] = d[_v] + 1;
            }

            if (d[_w] == d[_v] + 1) {
              g[_w] = g[_w] + g[_v];

              P[_w].push(_v);
            }
          }
        }
      }

      var e = {};

      for (var _i2 = 0; _i2 < V.length; _i2++) {
        e[V[_i2].id()] = 0;
      }

      while (S.length > 0) {
        var _w2 = S.pop();

        for (var _j2 = 0; _j2 < P[_w2].length; _j2++) {
          var _v2 = P[_w2][_j2];
          e[_v2] = e[_v2] + g[_v2] / g[_w2] * (1 + e[_w2]);

          if (_w2 != V[s].id()) {
            C.set(_w2, C.get(_w2) + e[_w2]);
          }
        }
      }
    };

    for (var s = 0; s < V.length; s++) {
      _loop(s);
    }

    var ret = {
      betweenness: function betweenness(node) {
        var id = cy.collection(node).id();
        return C.get(id);
      },
      betweennessNormalized: function betweennessNormalized(node) {
        if (max == 0) {
          return 0;
        }

        var id = cy.collection(node).id();
        return C.get(id) / max;
      }
    }; // alias

    ret.betweennessNormalised = ret.betweennessNormalized;
    return ret;
  }
97235
def find_biconnected_components(graph):
    

    list_of_components = []

    # Run the algorithm on each of the connected components of the graph
    components = get_connected_components_as_subgraphs(graph)
    for component in components:
        # --Call the internal biconnnected components function to find
        # --the edge lists for this particular connected component
        edge_list = _internal_get_biconnected_components_edge_lists(component)
        list_of_components.extend(edge_list)

    return list_of_components
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);
                }
            }
        }
    }
41626
private void computeMatrixTopoGraphHalfEdges_(int geometry_a, int geometry_b) {
		boolean bRelationKnown = false;

		int id_a = m_topo_graph.getGeometryID(geometry_a);
		int id_b = m_topo_graph.getGeometryID(geometry_b);

		m_visited_index = m_topo_graph.createUserIndexForHalfEdges();

		for (int cluster = m_topo_graph.getFirstCluster(); cluster != -1; cluster = m_topo_graph
				.getNextCluster(cluster)) {
			int first_half_edge = m_topo_graph.getClusterHalfEdge(cluster);
            if (first_half_edge == -1)
            {
                if (m_predicates_cluster != -1)
                {
                    // Treat cluster as an interior point
                    switch (m_predicates_cluster)
                    {
                        case Predicates.AreaPointPredicates:
                            bRelationKnown = areaPointPredicates_(cluster, id_a, id_b);
                            break;
                        case Predicates.LinePointPredicates:
                            bRelationKnown = linePointPredicates_(cluster, id_a, id_b);
                            break;
                        default:
                            throw GeometryException.GeometryInternalError();
                    }
                }

                continue;
            }

			int next_half_edge = first_half_edge;

			do {
				int half_edge = next_half_edge;
				int visited = m_topo_graph.getHalfEdgeUserIndex(half_edge,
						m_visited_index);

				if (visited != 1) {
					do {
						// Invoke relational predicates
						switch (m_predicates_half_edge) {
						case Predicates.AreaAreaPredicates:
							bRelationKnown = areaAreaPredicates_(half_edge,
									id_a, id_b);
							break;
						case Predicates.AreaLinePredicates:
							bRelationKnown = areaLinePredicates_(half_edge,
									id_a, id_b);
							break;
						case Predicates.LineLinePredicates:
							bRelationKnown = lineLinePredicates_(half_edge,
									id_a, id_b);
							break;
						default:
							throw GeometryException.GeometryInternalError();
						}

						if (bRelationKnown)
							break;

						m_topo_graph.setHalfEdgeUserIndex(half_edge,
								m_visited_index, 1);
						half_edge = m_topo_graph.getHalfEdgeNext(half_edge);
					} while (half_edge != next_half_edge && !bRelationKnown);
				}

				if (bRelationKnown)
					break;

				next_half_edge = m_topo_graph.getHalfEdgeNext(m_topo_graph
						.getHalfEdgeTwin(half_edge));
			} while (next_half_edge != first_half_edge);

			if (bRelationKnown)
				break;
		}

		if (!bRelationKnown)
			setRemainingPredicatesToFalse_();

		m_topo_graph.deleteUserIndexForHalfEdges(m_visited_index);
	}
501731
def edges(self, sites, permutation=None, input='sites'):
        
        if input == 'sites':
            coords = [site.coords for site in sites]
        elif input == 'coords':
            coords = sites
        # if permutation is None:
        #     coords = [site.coords for site in sites]
        # else:
        #     coords = [sites[ii].coords for ii in permutation]
        if permutation is not None:
            coords = [coords[ii] for ii in permutation]
        return [[coords[ii] for ii in e] for e in self._edges]
386219
private Matrix getEdgeSimMatrix(List<Edge> edgeList, SparseMatrix sm,
                                    boolean keepSimilarityMatrixInMemory) {
        return (keepSimilarityMatrixInMemory) 
            ? calculateEdgeSimMatrix(edgeList, sm)
            : new LazySimilarityMatrix(edgeList, sm);            
    }
955690
def reachable_nodes(self, p_id, p_recursive=True, p_reverse=False):
        
        stack = [p_id]
        visited = set()
        result = set()

        while len(stack):
            current = stack.pop()

            if current in visited or current not in self._edges:
                continue

            visited.add(current)

            if p_reverse:
                parents = [node for node, neighbors in self._edges.items()
                           if current in neighbors]

                stack = stack + parents
                result = result.union(parents)
            else:
                stack = stack + list(self._edges[current])
                result = result.union(self._edges[current])

            if not p_recursive:
                break

        return result
1247705
function findMinSlackEdge(t, g) {
  return _.minBy(g.edges(), function(e) {
    if (t.hasNode(e.v) !== t.hasNode(e.w)) {
      return slack(g, e);
    }
  });
}
184116
def node_centroid_hill_climbing(G, relax=1, num_centerings=20, verbose=False):
  ''''''
  # Initialize order with BFS from a random start node.
  order = _breadth_first_order(G)
  for it in range(num_centerings):
    B = permute_graph(G, order).bandwidth()
    nc_order = _node_center(G, order, relax=relax)
    nc_B = permute_graph(G, nc_order).bandwidth()
    if nc_B < B:
      if verbose:  # pragma: no cover
        print('post-center', B, nc_B)
      order = nc_order
    order = _hill_climbing(G, order, verbose=verbose)
  return permute_graph(G, order)
1002643
def tsp(edges, constraint_generation=False):
    
    edges = populate_edge_weights(edges)
    incoming, outgoing, nodes = node_to_edge(edges)

    nedges, nnodes = len(edges), len(nodes)
    L = LPInstance()

    L.add_objective(edges, objective=MINIMIZE)
    balance = []
    # For each node, select exactly 1 incoming and 1 outgoing edge
    for v in nodes:
        incoming_edges = incoming[v]
        outgoing_edges = outgoing[v]
        icc = summation(incoming_edges)
        occ = summation(outgoing_edges)
        balance.append("{0} = 1".format(icc))
        balance.append("{0} = 1".format(occ))

    # Subtour elimination - Miller-Tucker-Zemlin (MTZ) formulation
    # <http://en.wikipedia.org/wiki/Travelling_salesman_problem>
    # Desrochers and laporte, 1991 (DFJ) has a stronger constraint
    # See also:
    # G. Laporte / The traveling salesman problem: Overview of algorithms
    start_step = nedges + 1
    u0 = nodes[0]
    nodes_to_steps = dict((n, start_step + i) for i, n in enumerate(nodes[1:]))
    edge_store = dict((e[:2], i) for i, e in enumerate(edges))
    mtz = []
    for i, e in enumerate(edges):
        a, b = e[:2]
        if u0 in (a, b):
            continue
        na, nb = nodes_to_steps[a], nodes_to_steps[b]
        con_ab = " x{0} - x{1} + {2}x{3}".format(na, nb, nnodes - 1, i + 1)
        if (b, a) in edge_store:  # This extra term is the stronger DFJ formulation
            j = edge_store[(b, a)]
            con_ab += " + {0}x{1}".format(nnodes - 3, j + 1)
        con_ab += " <= {0}".format(nnodes - 2)
        mtz.append(con_ab)

    # Step variables u_i bound between 1 and n, as additional variables
    bounds = []
    for i in xrange(start_step, nedges + nnodes):
        bounds.append(" 1 <= x{0} <= {1}".format(i, nnodes - 1))

    L.add_vars(nedges)

    """
    Constraint generation seek to find 'cuts' in the LP problem, by solving the
    relaxed form. The subtours were then incrementally added to the constraints.
    """
    if constraint_generation:
        L.constraints = balance
        subtours = []
        while True:
            selected, obj_val = L.lpsolve()
            results = sorted(x for i, x in enumerate(edges) if i in selected) \
                if selected else None
            if not results:
                break
            G = edges_to_graph(results)
            cycles = list(nx.simple_cycles(G))
            if len(cycles) == 1:
                break
            for c in cycles:
                incident = [edge_store[a, b] for a, b in pairwise(c + [c[0]])]
                icc = summation(incident)
                subtours.append("{0} <= {1}".format(icc, len(incident) - 1))
            L.constraints = balance + subtours
    else:
        L.constraints = balance + mtz
        L.add_vars(nnodes - 1, offset=start_step, binary=False)
        L.bounds = bounds
        selected, obj_val = L.lpsolve()
        results = sorted(x for i, x in enumerate(edges) if i in selected) \
            if selected else None

    return results
729125
private void dfs(int v, int[] cc, int id) {
        cc[v] = id;
        for (Edge edge : graph[v]) {
            int t = edge.v2;
            if (!digraph && t == v) {
                t = edge.v1;
            }

            if (cc[t] == -1) {
                dfs(t, cc, id);
            }
        }
    }
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));
  }
968416
def build_downstream_edge_predicate(nodes: Iterable[BaseEntity]) -> EdgePredicate:
    """"""
    nodes = set(nodes)

    def downstream_filter(graph: BELGraph, u: BaseEntity, v: BaseEntity, k: str) -> bool:
        """Pass for relations for which one of the given nodes is the subject."""
        return u in nodes and graph[u][v][k][RELATION] in CAUSAL_RELATIONS

    return downstream_filter
571382
private void bfs(int v, int[] cc, int id) {
        cc[v] = id;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        while (!queue.isEmpty()) {
            int t = queue.poll();
            for (Edge edge : graph[t]) {
                int i = edge.v2;
                if (!digraph && i == t) {
                    i = edge.v1;
                }

                if (cc[i] == -1) {
                    queue.offer(i);
                    cc[i] = id;
                }
            }
        }
    }
12424
def _sparse_neighbor_graph(X, k, binary=False, metric='l2'):
  ''''''
  knn = NearestNeighbors(n_neighbors=k, metric=metric).fit(X)
  mode = 'connectivity' if binary else 'distance'
  try:
    adj = knn.kneighbors_graph(None, mode=mode)
  except IndexError:
    # XXX: we must be running an old (<0.16) version of sklearn
    #  We have to hack around an old bug:
    if binary:
      adj = knn.kneighbors_graph(X, k+1, mode=mode)
      adj.setdiag(0)
    else:
      adj = knn.kneighbors_graph(X, k, mode=mode)
  return Graph.from_adj_matrix(adj)
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 )
      }
    }
936074
private Set<SNode> getMatchedNodes(SDocumentGraph graph) {

    Set<SNode> matchedNodes = new HashSet<>();

    for (SNode node: graph.getNodes()) {
       if (node.getFeature(AnnisConstants.ANNIS_NS, AnnisConstants.FEAT_MATCHEDNODE) != null)
         matchedNodes.add(node);
    }

    return matchedNodes;
  }