Computes the betweenness centrality of a graph.
    kind : string, either 'vertex' (default) or 'edge'
    directed : bool, defaults to self.is_directed()
    weighted : bool, defaults to self.is_weighted()
16361
def betweenness(self, kind='vertex', directed=None, weighted=None):
    '''
    '''
    assert kind in ('vertex', 'edge'), 'Invalid kind argument: ' + kind
    weighted = weighted is not False and self.is_weighted()
    directed = directed if directed is not None else self.is_directed()
    adj = self.matrix('csr')
    btw = betweenness(adj, weighted, kind=='vertex')
    # normalize if undirected
    if not directed:
      btw /= 2.
    return btw
823854
def get_in_degrees(self):
        '''
        
        '''
        degree = {}
        if self.attr['type'] is not DIRECTED_GRAPH:
            print('This function only works for directed graphs')
            return
        for n in self.get_node_list():
            degree[n] = len(self.get_in_neighbors(n))
        return degree
99222
def from_edges(edges):
        
        dag = DirectedGraph()
        for _u, _v in edges:
            dag.add_edge(_u, _v)
        return dag
737360
def dijkstra_single_path_length(G, start, end):
    
    if start not in G.vertices:
        raise GraphInsertError("Vertex %s doesn't exist." % (start,))
    if end not in G.vertices:
        raise GraphInsertError("Vertex %s doesn't exist." % (end,))
    dijkstra_data = dijkstra(G, start)
    length = dijkstra_data[0][end]
    path = [end]
    current = end
    while current is not start:
        for vertex in dijkstra_data[1]:
            if vertex is current:
                path.append(dijkstra_data[1][vertex])
                current = dijkstra_data[1][vertex]
                break
    return length, path
554768
def edge_by_node(self, head, tail):
        
        for edge in self.out_edges(head):
            if self.tail(edge) == tail:
                return edge
        return None
13891
def mutual_accessibility(graph):
    
    recursionlimit = getrecursionlimit()
    setrecursionlimit(max(len(graph.nodes())*2,recursionlimit))
    
    mutual_access = {}
    stack = []
    low = {}
        
    def visit(node):
        if node in low:
            return

        num = len(low)
        low[node] = num
        stack_pos = len(stack)
        stack.append(node)
        
        for successor in graph.neighbors(node):
            visit(successor)
            low[node] = min(low[node], low[successor])
        
        if num == low[node]:
            component = stack[stack_pos:]
            del stack[stack_pos:]
            component.sort()
            for each in component:
                mutual_access[each] = component

            for item in component:
                low[item] = len(graph)
    
    for node in graph:
        visit(node)
    
    setrecursionlimit(recursionlimit)
    return mutual_access
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
1359298
def graph(self):
        

        if self._local_transition_graph is not None:
            return self._local_transition_graph

        g = networkx.DiGraph()
        if self.startpoint is not None:
            g.add_node(self.startpoint)
        for block in self._local_blocks.values():
            g.add_node(block)
        for src, dst, data in self.transition_graph.edges(data=True):
            if 'type' in data:
                if data['type']  == 'transition' and ('outside' not in data or data['outside'] is False):
                    g.add_edge(src, dst, **data)
                elif data['type'] == 'fake_return' and 'confirmed' in data and \
                        ('outside' not in data or data['outside'] is False):
                    g.add_edge(src, dst, **data)

        self._local_transition_graph = g

        return g
868341
def is_causal_sink(graph: BELGraph, node: BaseEntity) -> bool:
    
    return has_causal_in_edges(graph, node) and not has_causal_out_edges(graph, node)
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
157351
def Dirichlet(concentration: vertex_constructor_param_types, label: Optional[str]=None) -> Vertex:
    
    return Double(context.jvm_view().DirichletVertex, label, cast_to_double_vertex(concentration))
377999
def eulerian_tour_directed(graph):
    
    P = []
    Q = [0]
    R = []
    succ = [0] * len(graph)
    while Q:
        node = Q.pop()
        P.append(node)
        while succ[node] < len(graph[node]):
            neighbor = graph[node][succ[node]]
            succ[node] += 1
            R.append(neighbor)
            node = neighbor
        while R:
            Q.append(R.pop())
    return P
1142710
def _get_connected_components_adjacency(self, graph, counts):
        ''' '''

        found = set()
        components = list()

        for node in sorted(graph, key=lambda x: counts[x], reverse=True):
            if node not in found:
                # component = self.search(node, graph)
                component = breadth_first_search(node, graph)
                found.update(component)
                components.append(component)
        return components
219616
def identify_vertex_neighbours(self, vertex):
        
        vertex = self._permutation[vertex]

        lpl = self.lend[vertex-1]
        lp = lpl

        neighbours = []

        while True:
            lp = self.lptr[lp-1]
            neighbours.append(self.lst[lp-1]-1)
            if (lp == lpl):
                break

        return self._deshuffle_simplices(neighbours)
416358
def is_causal_source(graph: BELGraph, node: BaseEntity) -> bool:
    
    # TODO reimplement to be faster
    return not has_causal_in_edges(graph, node) and has_causal_out_edges(graph, node)
410974
function eccentricity(graph, oriented) {
  var Q = [];
  // distance from source
  var dist = Object.create(null);

  var currentNode;
  var centrality = Object.create(null);

  graph.forEachNode(setCentralityToZero);
  graph.forEachNode(calculateCentrality);

  return centrality;

  function setCentralityToZero(node) {
    centrality[node.id] = 0;
  }

  function calculateCentrality(node) {
    currentNode = node.id;
    singleSourceShortestPath(currentNode);
    accumulate();
  }

  function accumulate() {
    var maxDist = 0;
    Object.keys(dist).forEach(function (key) {
      var val = dist[key];
      if (maxDist < val) maxDist = val;
    });

    centrality[currentNode] = maxDist;
  }

  function singleSourceShortestPath(source) {
    graph.forEachNode(initNode);
    dist[source] = 0;
    Q.push(source);

    while (Q.length) {
      var v = Q.shift();
      graph.forEachLinkedNode(v, processNode, oriented);
    }

    function initNode(node) {
      var nodeId = node.id;
      dist[nodeId] = -1;
    }

    function processNode(otherNode) {
      var w = otherNode.id
      if (dist[w] === -1) {
        // Node w is found for the first time
        dist[w] = dist[v] + 1;
        Q.push(w);
      }
    }
  }
}
17136
def graph_from_adjacency_matrix(matrix, node_prefix='', directed=False):
    

    node_orig = 1

    if directed:
        graph = Dot(graph_type='digraph')
    else:
        graph = Dot(graph_type='graph')

    for row in matrix:
        if not directed:
            skip = matrix.index(row)
            r = row[skip:]
        else:
            skip = 0
            r = row
        node_dest = skip + 1

        for e in r:
            if e:
                graph.add_edge(
                    Edge(
                        node_prefix + node_orig,
                        node_prefix + node_dest))
            node_dest += 1
        node_orig += 1

    return graph