def get_followers_dist(g, dg, follow):

    if follow == -1: return -1

    if len(dg) == 0:
        dg = nx.read_edgelist(sys.argv[2], create_using=dg)

    no_of_paths = 0
    for u in dg.nodes():

        if not g.has_node(u):
            print "no_source"
            continue

        for v in dg.successors(u):
            if u == v: continue

            if g.has_node(v):
                try:
                    print nx.shortest_path_length(g, source=u, target=v)
                    no_of_paths += 1
                except nx.exception.NetworkXError as err:
                    print "no_path"
            else:
                print "no_target"

    print >> sys.stderr, "no of paths", no_of_paths
    return no_of_paths

    def calc_2_lines_point_shortest_path(self, start_line, end_line):
        p11, p12 = self.line_dict[start_line]
        p21, p22 = self.line_dict[end_line]

        d1 = nx.shortest_path_length(self.G, source=p11, target=p21)
        d2 = nx.shortest_path_length(self.G, source=p11, target=p22)
        d3 = nx.shortest_path_length(self.G, source=p12, target=p21)
        d4 = nx.shortest_path_length(self.G, source=p12, target=p22)

        min_d = min([d1, d2, d3, d4])
        if d1 == min_d:
            return p11, p21
            pass

        if d2 == min_d:
            return p11, p22
            pass

        if d3 == min_d:
            return p12, p21
            pass

        if d4 == min_d:
            return p12, p22
            pass
        pass

    def verify_path_len(self):
        """
        Make sure that the finger links are optimal in length.
        (That they are the shortest paths possible)
        """

        # Iterate over all nodes:
        for nd in self.nodes:
            for f in self.dht_succ_fingers:
                best_succ_f = nd.get_best_succ_finger(f)
                # Calculate shortest path on graph:
                spath_len = nx.shortest_path_length(self.graph,\
                        self.vec_to_graph[nd.ind],\
                        self.vec_to_graph[best_succ_f.lindex])

                # Check if the path we have to best_succ_f equals exactly
                # spath_len:
                if best_succ_f.path_len != spath_len:
                    return False

            for f in self.dht_pred_fingers:
                best_pred_f = nd.get_best_pred_finger(f)
                # Calculate shortest path on graph:
                spath_len = nx.shortest_path_length(self.graph,\
                        self.vec_to_graph[nd.ind],\
                        self.vec_to_graph[best_pred_f.lindex])

                # Check if the path we have to best_pred_f equals exactly
                # spath_len:
                if best_pred_f.path_len != spath_len:
                    return False

        return True

def route_signal(sat_and_ids, route_from, route_to):
    G = networkx.Graph()

    for x, y in itertools.permutations(sat_and_ids, r=2):
        sat_x, sid_x = x
        sat_y, sid_y = y

        in_sight = is_in_sight(sat_x, sat_y)

        if in_sight is not None:
            G.add_edge(sid_x, sid_y, weight=in_sight)

    for sat, sid in sat_and_ids:
        in_sight = can_transmit(route_from, sat)

        if in_sight is not None:
            G.add_edge('SRC', sid, weight=in_sight)

    for sat, sid, in sat_and_ids:
        in_sight = can_transmit(route_to, sat)

        if in_sight is not None:
            G.add_edge('DST', sid, weight=in_sight)

    print networkx.shortest_path_length(G, 'SRC', 'DST', weight='weight')
    return networkx.shortest_path(G, 'SRC', 'DST', weight='weight')

def edge_update(graph, edge, cc, dd):
	u = edge[0]
	v = edge[1]
	change = 0
	if u not in dict:
		dict[u] = {}
		dict[u][v] = 1
		dict[u][u] = 0
	if v not in dict:
		dict[v] = {}
		dict[v][u] = 1
		dict[v][v] = 0
	for s in graph.nodes():
		if u not in dict[s]:
			try:
				dict[s][u] = nx.shortest_path_length(graph, s ,u)
				dict[u][s] = dict[s][u]
		if v not in dict[s]:
			try:
				dict[s][v] = nx.shortest_path_length(graph, s ,v)
				dict[v][s] = dict[s][v]
		if u in dict[s] and v in dict[s]:
			if math.fabs(dict[s][u] - dict[s][v]) > 1:
				dict[s] = {}
				dict[s] = nx.shortest_path_length(graph, s)
				change = change - cc[s]
				cc[s] = 0
				for n in dict[s]:
					cc[s] = cc[s] + 1.0 / dict[s][n]
				change = change + cc[s]
	return cc, dict

def get_followers_dist(g, dg, follow):

    if follow == -1: return -1

    no_of_paths = 0
    for u in dg.nodes():

        if not g.has_node(u):
            print "no_source"
            continue

        for v in dg.neighbors(u):
            if u == v: continue

            if g.has_node(v):
                try:
                    print nx.shortest_path_length(g, source=u, target=v)
                    no_of_paths += 1
                except nx.exception.NetworkXNoPath as err:
                    print "no_path"
            else:
                print "no_target"

    print >> sys.stderr, "no of paths", no_of_paths
    return no_of_paths

 def heuristic(n):
     t = (graph.degree(n), min([nx.shortest_path_length(graph, n, s) for s in self.stations]))
     # geometric mean of these two
     # closest to orders
     return (
         -sum([nx.shortest_path_length(graph, n, order_node) for order_node in order_nodes]),
         (t[0] * t[1]) ** (1 / 2),
     )

def get_chokes(instance, choke_candidates):
    #prevent writing over base space.
    used_set = set()
    start, finish = instance.level.botSpawnAreas[instance.game.enemyTeam.name]
    for i, j in itertools.product(range(int(start.x), int(finish.x)), range(int(start.y), int(finish.y))):
        node_index = regressions2.get_node_index(instance, Vector2(i,j))
        used_set.add(node_index)
            
    choke_dict = {}
    master_chokes = set()
    flag_node = regressions2.get_node_index(instance, instance.game.team.flag.position)
    spawn_node = regressions2.get_node_index(instance, get_enemy_base(instance))

    shortest_length = nx.shortest_path_length(instance.graph, source=spawn_node, target=flag_node, weight="choke_covered")
    choke_count = 0
    while shortest_length == 0.0:
        if len(choke_candidates) == 0.0:
            print "RAN OUT OF CANDIDATES!"
            break
        
        choke_count += 1
        
        one_choke = set()
        choke_center = choke_candidates.pop()
        choke_vector = regressions2.get_node_vector(instance, choke_center)
        
        #Ignore potential chokes too far from their spawn.
        while (choke_vector.distance((get_enemy_base(instance))) > 5.0 or choke_center in used_set) and len(choke_candidates) > 0:
            choke_vector = regressions2.get_node_vector(instance, choke_center)
            choke_center = choke_candidates.pop()
        if len(choke_candidates) == 0:
            print "RAN OUT OF CANDIDATES!"
            return choke_dict, master_chokes
        if choke_vector.distance((get_enemy_base(instance))) > 5.0:
            print "RAN OUT OF CANDIDATES, LAST CANDIDATE DIDN'T WORK!"
            return choke_dict, master_chokes
    
        one_choke.add(choke_center)
        for x in range(4):
            neighbors = set()
            for node in one_choke:
                neighbors2 = instance.graph.neighbors(node)
                if neighbors2 is not None:
                    for neighbor2 in neighbors2:
                        if neighbor2 not in used_set:
                            neighbors.add(neighbor2)
            one_choke = one_choke.union(neighbors)
            used_set = used_set.union(one_choke)
        for node in one_choke:
            instance.graph.node[node]["choke_covered"] = 1.0
            neighbors = instance.graph.neighbors(node)
            for neighbor in neighbors:
                instance.graph.edge[node][neighbor]["choke_covered"] = 1.0
        choke_dict[choke_center] = { "nodes": one_choke, "redundancy": 0}
        master_chokes = master_chokes.union(one_choke)
        shortest_length = nx.shortest_path_length(instance.graph, source=spawn_node, target=flag_node, weight="choke_covered")
        
    return choke_dict, master_chokes

def _min_cycle(G, orth, weight=None):
    """
    Computes the minimum weight cycle in G, orthogonal to the vector orth
    as per [p. 338, 1]
    """
    T = nx.Graph()

    nodes_idx = {node: idx for idx, node in enumerate(G.nodes())}
    idx_nodes = {idx: node for node, idx in nodes_idx.items()}

    nnodes = len(nodes_idx)

    # Add 2 copies of each edge in G to T. If edge is in orth, add cross edge;
    # otherwise in-plane edge
    if weight is not None:
        for u, v in G.edges():
            uidx, vidx = nodes_idx[u], nodes_idx[v]
            edge_w = G[u][v][weight]
            if frozenset((u, v)) in orth:
                T.add_edges_from(
                    [(uidx, nnodes + vidx), (nnodes + uidx, vidx)], weight=edge_w)

            else:
                T.add_edges_from(
                    [(uidx, vidx), (nnodes + uidx, nnodes + vidx)], weight=edge_w)

        all_shortest_pathlens = nx.shortest_path_length(T, weight='weight')

    else:
        for u, v in G.edges():
            uidx, vidx = nodes_idx[u], nodes_idx[v]
            if frozenset((u, v)) in orth:
                T.add_edges_from(
                    [(uidx, nnodes + vidx), (nnodes + uidx, vidx)])

            else:
                T.add_edges_from(
                    [(uidx, vidx), (nnodes + uidx, nnodes + vidx)])

        all_shortest_pathlens = nx.shortest_path_length(T)

    cross_paths_w_lens = {
        n: all_shortest_pathlens[n][nnodes + n] for n in range(nnodes)}

    # Now compute shortest paths in T, which translates to cyles in G
    min_path_startpoint = min(cross_paths_w_lens, key=cross_paths_w_lens.get)
    min_path = nx.shortest_path(
        T, source=min_path_startpoint, target=nnodes + min_path_startpoint, weight='weight')

    # Now we obtain the actual path, re-map nodes in T to those in G
    min_path_nodes = [
        node if node < nnodes else node - nnodes for node in min_path]
    # Now remove the edges that occur two times
    mcycle_pruned = _path_to_cycle(min_path_nodes)

    return {frozenset((idx_nodes[u], idx_nodes[v])) for u, v in mcycle_pruned}

def closeness_vitality(grafo,vertice, aresta=False):
    """Calcula closeness vitality do vértice no grafo

    Retorna a closeness vitality para o vértice ou aresta especificado
    no grafo especificado.

    Parâmetros
    ----------
    grafo: grafo networkx
        Grafo no qual se quer calcular closeness vitality.
    vertice: identificador
        Identificador do vértice para o qual se quer a medida.
    aresta: tupla
        Identificador dos vértices que formam a aresta para o qual se quer a medida de centralidade.
    """

    g_foo=nx.copy.deepcopy(grafo)
    dists=nx.shortest_path_length(g_foo, weighted=True)
    vertices=g_foo.nodes()
    pares=[]
    soma_dists1=0
    for v1 in vertices:
        for v2 in vertices:
            if set((v1,v2)) not in pares:
                soma_dists1+=dists[v1][v2]
                pares.append(set((v1,v2)))
    Iwg=soma_dists1

    if aresta:
        g_foo.remove_edge(aresta[0],aresta[1])
        dists=nx.shortest_path_length(g_foo, weighted=True)
        vertices=g_foo.nodes()
        pares=[]
        soma_dists2=0
        for v1 in vertices:
            for v2 in vertices:
                if set((v1,v2)) not in pares:
                    soma_dists2+=dists[v1][v2]
                    pares.append(set((v1,v2)))
        Iwg2=soma_dists2
        return Iwg-Iwg2

    g_foo.remove_node(vertice)

    dists=nx.shortest_path_length(g_foo, weighted=True)
    vertices=g_foo.nodes()
    pares=[]
    soma_dists2=0
    for v1 in vertices:
        for v2 in vertices:
            if set((v1,v2)) not in pares:
                soma_dists2+=dists[v1][v2]
                pares.append(set((v1,v2)))
    Iwg2=soma_dists2

    return Iwg-Iwg2

def AssociatedExternal(node, Dual, External):
    associate = External.iterkeys().next()
    min_dist = nx.shortest_path_length(Dual, node, External[associate]['measure']) + 1

    for candidate in External:
        distance = nx.shortest_path_length(Dual, node, External[candidate]['measure']) + 1
        if distance < min_dist:
            min_dist = distance
            associate = candidate
    return associate

def extract_shortestpath_subgraph(g, nodes):
    newg = nx.DiGraph()
    for beg in nodes:
        for end in nodes:
            if beg != end:
                newg.add_edge(beg,
                              end,
                              duration=nx.shortest_path_length(g,source=beg,target=end,weight='duration'),
                              min_duration=nx.shortest_path_length(g,source=beg,target=end,weight='min_duration'),
                              max_duration=nx.shortest_path_length(g,source=beg,target=end,weight='max_duration'))
    return newg

def get_sigma(G, s, v, predecessors):
  if s == v:
    return 1

  l = nx.shortest_path_length(G,s,v)
  sigma_v = 0
  for u in G.neighbors(v):
    if nx.shortest_path_length(G,s,u) < l:
      predecessors.add(u)
      sigma_v += get_sigma(G, s, u, predecessors)
  return sigma_v

def main():
    for i in range(size):
        for j in range(size):
            G.add_edge((i,j), (i+1,j), weight=mat[i,j])
            G.add_edge((i,j), (i,j+1), weight=mat[i,j])


    for i in range(size):
        G.remove_node((i,size))
        G.remove_node((size,i))
    
    print nx.shortest_path_length(G, (0,0), (size-1,size-1), weight='weight')

def normalize_step_weight(graph):
    "Changes the edge weights in the graph proportional to the longest path."
    longest_path_len = max(nx.shortest_path_length(graph, "ROOT").values())
    # add normalized path length as weight to edges.
    for category in "ABCEDFGHJKLMNPQRSTUVWXZ":
        # for each category, find out how long the longest path is.
        cat_longest_path_len = max(nx.shortest_path_length(graph, category).values()) + 1
        # normalize the stepsize
        stepsize = float(longest_path_len) / cat_longest_path_len
        # traverse tree for this category and assign stepsize to edges as weight attribute
        for a, b in nx.dfs_edges(graph, category):
            graph[a][b]["weight"] = stepsize

 def test_single_source_shortest_path_length(self):
     l=nx.shortest_path_length(self.cycle,0)
     assert_equal(l,{0:0,1:1,2:2,3:3,4:3,5:2,6:1})
     assert_equal(l,nx.single_source_shortest_path_length(self.cycle,0))
     l=nx.shortest_path_length(self.grid,1)
     assert_equal(l[16],6)
     # now with weights
     l=nx.shortest_path_length(self.cycle,0,weighted=True)
     assert_equal(l,{0:0,1:1,2:2,3:3,4:3,5:2,6:1})
     assert_equal(l,nx.single_source_dijkstra_path_length(self.cycle,0))
     l=nx.shortest_path_length(self.grid,1,weighted=True)
     assert_equal(l[16],6)

 def test_all_pairs_shortest_path_length(self):
     l=nx.shortest_path_length(self.cycle)
     assert_equal(l[0],{0:0,1:1,2:2,3:3,4:3,5:2,6:1})
     assert_equal(l,nx.all_pairs_shortest_path_length(self.cycle))
     l=nx.shortest_path_length(self.grid)
     assert_equal(l[1][16],6)
     # now with weights
     l=nx.shortest_path_length(self.cycle,weighted=True)
     assert_equal(l[0],{0:0,1:1,2:2,3:3,4:3,5:2,6:1})
     assert_equal(l,nx.all_pairs_dijkstra_path_length(self.cycle))
     l=nx.shortest_path_length(self.grid,weighted=True)
     assert_equal(l[1][16],6)

def nxShortestPath(nxGraph, nxPos, startPt, endPt, Dijk=0):
    if Dijk == 0:
        nxList = nx.shortest_path(nxGraph, source=startPt, target=endPt)
        score = nx.shortest_path_length(nxGraph, source=startPt, target=endPt)
        dist = nx.shortest_path_length(nxGraph, source=startPt, target=endPt, weight="distance")
    elif Dijk == 1:
        nxList = nx.dijkstra_path(nxGraph, source=startPt, target=endPt, weight="weight")
        score = nx.dijkstra_path_length(nxGraph, source=startPt, target=endPt, weight="weight")
        dist = nx.dijkstra_path_length(nxGraph, source=startPt, target=endPt, weight="distance")

    nxH = nx.subgraph(nxGraph, nxList)
    return nxList, nxH, score, dist

def random_pairs_dist(data1, data, el):
    """
    Chooses random pairs of branches in the skeleton and computes the distances
    between them.
    
    Parameters
    ------------
    data1 : list of pathes for the break-ups dictionaries. Used here for the 
            estimation of the necessary number of pairs.
    data : list of pathes for the graphs
    el : list of length scales
    
    Return
    -------
    d_ran : list of distances along the skeleton between random branches.
    """
    d_ran = list()
    u=0
    for b, g in zip(data1, data):
        br = np.load(b).item().keys()
        gr = nx.read_gpickle(g)
        edg = list(nx.edges(gr))
        number = nx.get_edge_attributes(gr, 'number')
        num_dict = {}
        for k in number:
            for v in number[k]:
                num_dict.setdefault(v, []).append(k)
        a = len(list(br))
        if a > 1500: #We cannot use here infinitly many pairs because of the computing time.
            a = 1500
        for j in range(a):
            e1 = random.choice(edg)
            e2 = random.choice(edg)
            if (e1==e2):
                continue
            n1 = e1[0]
            n2 = e1[1]
            m1 = e2[0]
            m2 = e2[1]
            try: 
                p_min = p_max = nx.shortest_path_length(gr, n1, m1, 'length')
            except nx.NetworkXNoPath:
                continue    
            for i in itertools.product((n1,n2), (m1,m2)):
                p = nx.shortest_path_length(gr, i[0], i[1], 'length')
                if p < p_min:
                    p_min = p
                if p > p_max:
                    p_max = p
            d = (p_min+p_max)/(2. * el[u])
            d_ran.append(d)
        u+=1
    return d_ran

 def distance(self, type, node1, node2):
     if node1 in self.Dual[type].nodes() and node2 in self.Dual[type].nodes():
         return nx.shortest_path_length(self.Dual[type], node1, node2)
     elif node1 in self.Dual[type].nodes() and node2 not in self.Dual[type].nodes():
         node2 = self.External[type][node2]['measure']
         return nx.shortest_path_length(self.Dual[type], node1, node2) + 1
     elif node1 not in self.Dual[type].nodes() and node2 in self.Dual[type].nodes():
         node1 = self.External[type][node1]['measure']
         return nx.shortest_path_length(self.Dual[type], node1, node2) + 1
     else:
         node1 = self.External[type][node1]['measure']
         node2 = self.External[type][node2]['measure']
         return nx.shortest_path_length(self.Dual[type], node1, node2) + 2