def test_all_shortest_paths(self):
     G = nx.Graph()
     nx.add_path(G, [0, 1, 2, 3])
     nx.add_path(G, [0, 10, 20, 3])
     assert_equal([[0, 1, 2, 3], [0, 10, 20, 3]],
                  sorted(nx.all_shortest_paths(G, 0, 3)))
     # with weights
     G = nx.Graph()
     nx.add_path(G, [0, 1, 2, 3])
     nx.add_path(G, [0, 10, 20, 3])
     assert_equal([[0, 1, 2, 3], [0, 10, 20, 3]],
                  sorted(nx.all_shortest_paths(G, 0, 3, weight='weight')))
     # weights and method specified
     G = nx.Graph()
     nx.add_path(G, [0, 1, 2, 3])
     nx.add_path(G, [0, 10, 20, 3])
     assert_equal([[0, 1, 2, 3], [0, 10, 20, 3]],
                  sorted(nx.all_shortest_paths(G, 0, 3, weight='weight',
                                               method='dijkstra')))
     G = nx.Graph()
     nx.add_path(G, [0, 1, 2, 3])
     nx.add_path(G, [0, 10, 20, 3])
     assert_equal([[0, 1, 2, 3], [0, 10, 20, 3]],
                  sorted(nx.all_shortest_paths(G, 0, 3, weight='weight',
                                               method='bellman-ford')))

def betweenness_centrality(network,weighted=False):

    betweenness = {}
    nodes = network.nodes()

    shortest_paths = {}
    for pre_lpu in nodes:
        shortest_paths[pre_lpu] = {}
        for post_lpu in nodes:
            if weighted:
                shortest_paths[pre_lpu][post_lpu] = list(nx.all_shortest_paths(network,pre_lpu,post_lpu,weight='weight'))
            else:
                shortest_paths[pre_lpu][post_lpu] = list(nx.all_shortest_paths(network,pre_lpu,post_lpu))

    for n in nodes:
        b = 0
        for pre_lpu in nodes:
            for post_lpu in nodes:
                if pre_lpu != post_lpu and pre_lpu != n and post_lpu !=n:
                    p = 0
                    pi = 0
                    for path in shortest_paths[pre_lpu][post_lpu]:
                        p+=1;
                        pi += n in path

                    ratio = float(pi)/p
                    b = b+ ratio 
        betweenness[n] = b
    return betweenness

def trunkroute(G,nodelist): 
    nodes = len(nodelist)
    for i in range(0,(nodes-1)):
        startname = nodelist[i]
        endname = nodelist[i+1]
 
        try:
            #pathshort = nx.dijkstra_path(G,startname,endname,'weight')#下面的函数返回对象，这函数返回list，我还不会把对象变成list。
            pathshort = nx.all_shortest_paths(G,startname,endname,'weight') #加weight是按距离选择，选出一条最短路由。
            #psl=nx.dijkstra_path_length(G,startname,endname) #返回最短路径的长度距离。与用all_shortest_paths()函数取出的路径不太一样，是个疑问。
            pathshortseq = []
            pathshortseq = pathsequence(pathshort) #不用排序，但是排序函数可以脱去对象，生成list的Array。
            pathshortlong = []
            pathshortlong=pathadddistance(pathshortseq,G)#在节点之间加上最短距离数据。
            #displayformatpath(pathshort,psl)
            displayformatpath(pathshortlong,'Short') #将路由节点和距离显示在终端上。
            #trunkselectdisplay(pathshortseq)#加入光缆选择信息。最短长度。
        except nx.NetworkXNoPath:
            print '**********Short Route Attention! %s to %s have no route in this G.**********'%(startname.encode('GB2312'),endname.encode('GB2312'))
        try:
            pathall = nx.all_shortest_paths(G,startname,endname) #不加weight按照节点最少为最短，加weight是按距离选择。
            pathallseq = []
            pathallseq = pathsequence(pathall) #从路由组对象转换成arrar，并排序，返回arrar。
            #allnodedist = nx.all_pairs_dijkstra_path_length(G) #返回所有节点间的直连距离字典。转移到全局变量里。
            #pathallseqlong = pathadddistance(allnodedist,pathallseq) #给路由组分别加上距离int。返回带距离的路由array。
            pathallseqlong = []
            pathallseqlong = pathadddistance(pathallseq,G) #给路由组分别加上距离int。返回带距离的路由array。
            displayformatpath(pathallseqlong) #将节点名字传入函数，方便输出错误信息。
            #trunkselectdisplay(pathallseq)#加入光缆选择信息。最少节点。
        except nx.NetworkXNoPath:
            print '**********Route Attention! %s to %s have no route in this G.**********'%(startname.encode('GB2312'),endname.encode('GB2312'))
        #print pathshortseq
        #print pathshortlong
        if len(pathshortseq) != 0 and len(pathallseq) != 0 :
            trunkselectdisplay(pathshortseq,pathallseq)#加入光缆选择函数。

    def concrete_path_exists(self, o1, o2):
        try:
            m1 = o1.leaf_model_name
            m2 = o2.leaf_model_name
        except AttributeError:
            # One of the nodes is not in the dependency graph
            # No dependency
            return False

        # FIXME: Dynamic dependency check
        G = self.model_dependency_graph[False]
        paths = all_shortest_paths(G, m1, m2)

        try:
            any(paths)
            paths = all_shortest_paths(G, m1, m2)
        except NetworkXNoPath:
            # Easy. The two models are unrelated.
            return False

        for p in paths:
            path_verdict = True
            src_object = o1
            da = None

            for i in range(len(p) - 1):
                src = p[i]
                dst = p[i + 1]
                edge_label = G[src][dst]
                sa = edge_label['src_accessor']
                da = edge_label['dst_accessor']
                try:
                    dst_object = getattr(src_object, sa)
                    if dst_object and dst_object.leaf_model_name != dst and i != len(
                            p) - 2:
                        raise AttributeError
                except AttributeError as e:
                    self.log.debug(
                        'Could not check object dependencies, making conservative choice', src_object = src_object, sa = sa, o1 = o1, o2 = o2)
                    return True
                src_object = dst_object

            if src_object and ((not da and src_object == o2) or (
                    da and src_object == getattr(o2, da))):
                return True

            # Otherwise try other paths

        return False

    def onDone(self, node, onDone):
        nodeidx = self.nodes.index(node)
        
        for (start, goal, execData) in node.getConnectedStartGoalPairs():
            self.connectivityGraph.add_node((nodeidx, start))
            self.connectivityGraph.add_node((nodeidx+1, goal))
            self.connectivityGraph.add_edge((nodeidx, start), 
                                            (nodeidx+1, goal), execData=execData)
            #print 'ADD', node, hash(start), hash(goal)
            if node == self.nodes[0]:
                #print 'N0', node
                self.connectivityGraph.add_edge('start', (nodeidx, start))
            if node == self.nodes[-1]:
                #print 'N1', node
                self.connectivityGraph.add_edge((nodeidx+1, goal), 'end')
        if nx.has_path(self.connectivityGraph, 'start', 'end'):
            for path in nx.all_shortest_paths(self.connectivityGraph, 'start', 'end'):
                #import IPython; IPython.embed()
                self.addConnectedStartGoalPair((path[1][1], path[-2][1], None))

        self.connectIdx(nodeidx)
        self.connectIdx(nodeidx+1)
        if self.isPaused() or self.isRunOnce():
            onDone()
            return
        if len(self.getConnectedStartGoalPairs()) == 0:
            self.components.subnode.chooseAndRun(onDone)
        else:
            onDone()
            return

def compute_distance_on_graph(G, s_id, t_id):
    """ Computes the sum of the length in the shortest path between <tt>s</tt> and <tt>t</tt>.
    If the shortest path are more than one the shorter in edge lengths is considered
    <tt>return</tt> a double value of the length of the shortestpath between <tt>s</tt> and <tt>t</tt>
    """
    all_sp = list(nx.all_shortest_paths(G, source=s_id, target=t_id))

    min_sp = float("inf")

    for sp in all_sp:
        curr_length = 0
        for s_index in range(0, len(sp)-1):
            t_index = s_index+1

            s_id = sp[s_index]
            t_id = sp[t_index]

            s = G.node[s_id]
            t = G.node[t_id]

            curr_length += compute_euclidean_distance(s, t)

        min_sp = min(min_sp, curr_length)

    return min_sp

    def all_shortest_paths(self, source, target):
        """
        Generator which yields all shortest paths between the source
        and target types.

        Parameters:
        source   The source type.
        target   The target type.

        Yield: generator(steps)

        steps Yield: tuple(source, target, rules)

        source   The source type for this step of the information flow.
        target   The target type for this step of the information flow.
        rules    The list of rules creating this information flow step.
        """
        if self.rebuildgraph:
            self._build_graph()

        if source in self.G and target in self.G:
            try:
                paths = nx.all_shortest_paths(self.G, source, target)
            except nx.exception.NetworkXNoPath:
                pass
            else:
                for p in paths:
                    yield self.__get_steps(p)

 def get_minimal_pathway(self, g, source, target, steps_cut_off):
     vector_shortest = [s_path for s_path in nx.all_shortest_paths(g, source, target) if len(s_path) == steps_cut_off]
     random.shuffle(vector_shortest)
     try:
         return vector_shortest[0][1]
     except:
         return []

    def findshortestpath(self, startrotmat4, goalrotmat4, base):
        self.__addstartgoal(startrotmat4, goalrotmat4, base)

        # startgrip = random.select(self.startnodeids)
        # goalgrip = random.select(self.goalnodeids)
        startgrip = self.startnodeids[0]
        goalgrip = self.goalnodeids[0]
        self.shortestpaths = nx.all_shortest_paths(self.regg, source = startgrip, target = goalgrip)
        self.directshortestpaths = []
        # directshortestpaths removed the repeated start and goal transit
        try:
            for path in self.shortestpaths:
                print path
                for i, pathnode in enumerate(path):
                    if pathnode.startswith('start') and i < len(path)-1:
                        continue
                    else:
                        self.directshortestpaths.append(path[i-1:])
                        break
                for i, pathnode in enumerate(self.directshortestpaths[-1]):
                    if i > 0 and pathnode.startswith('goal'):
                        self.directshortestpaths[-1]=self.directshortestpaths[-1][:i+1]
                        break
        except:
            print "No path found!"
            pass

def main(json_file, output_prefix, source, target):
    
    with open(json_file) as data_file:    
        data = json.load(data_file)

    G = json_graph.node_link_graph(data, directed=False)

    print "Finished Reading in Graph: {0}".format(datetime.datetime.now())

    id_seq = networkx.get_node_attributes(G, "sequence")

    seq_id = { seq : node_id for node_id, seq in id_seq.items()}

    print "Created inverse lookup table: {0}".format(datetime.datetime.now())

    if ',' in target:
        targets = target.split(',')

    for target in targets:
        paths = networkx.all_shortest_paths(G, seq_id[source], seq_id[target])

        with open("{0}_paths_{1}_{2}.txt".format(output_prefix, source, target), 'w') as o:
            for path in paths:
                o.write(",".join( [id_seq[node_id] for node_id in path ] ))
	        o.write("\n")

    print "Output paths: {0}".format(datetime.datetime.now())

def baconise(g, actorA, actorB):
	actorA = actorA.replace("_", " ")
	actorB = actorB.replace("_", " ")

	if not(actorA in g.nodes()):
		actorA = findClosest(g, actorA)

	if not(actorB in g.nodes()):
		actorB = findClosest(g, actorB)

	lists = nx.all_shortest_paths(g, actorA, actorB)
	lista = lists.next()
	i = 1
	actors = []
	while not(lista is None):
		try:
			printPath(g, lista)
			lista = lists.next()
			actors = actors +lista
			i = i+1
		except StopIteration:
			break

	print "found " + str(i) + " paths of length " + str(len(lista))
	return list(set(actors))

 def shortest_paths(self, v1, v2):
     try:
         l = nx.shortest_path_length(self.graph, v1, v2)
         paths = nx.all_shortest_paths(self.graph, v1, v2)
     except:
         paths = []
     return paths

    def _calculate_shortest_paths(self, env, action_size):
        s_next_s_action = {}
        G = nx.DiGraph()

        for s in range(env.n_locations):
          for a in range(action_size):
            next_s = env.transition_graph[s, a]
            if next_s >= 0:
              s_next_s_action[(s, next_s)] = a
              G.add_edge(s, next_s)

        best_action = np.zeros((env.n_locations, action_size), dtype=np.float)
        for i in range(env.n_locations):
          if i == env.terminal_state_id:
            continue
          if env.shortest_path_distances[i, env.terminal_state_id] == -1:
            continue
          for path in nx.all_shortest_paths(G, source=i, target=env.terminal_state_id):
            action = s_next_s_action[(i, path[1])]
            best_action[i, action] += 1

        action_sum = best_action.sum(axis=1, keepdims=True)
        action_sum[action_sum == 0] = 1  # prevent divide-by-zero
        shortest_path_actions = best_action / action_sum

        return shortest_path_actions

    def all_shortest_paths(self, source, target):
        """
        Generator which yields all shortest paths between the source
        and target types.

        Parameters:
        source   The source type.
        target   The target type.

        Yield: generator(steps)

        steps Yield: tuple(source, target, rules)

        source   The source type for this step of the information flow.
        target   The target type for this step of the information flow.
        rules    The list of rules creating this information flow step.
        """
        s = self.policy.lookup_type(source)
        t = self.policy.lookup_type(target)

        if self.rebuildsubgraph:
            self._build_subgraph()

        self.log.info("Generating all shortest information flow paths from {0} to {1}...".
                      format(s, t))

        with suppress(NetworkXNoPath, NodeNotFound):
            # NodeNotFound: the type is valid but not in graph, e.g.
            # excluded or disconnected due to min weight
            # NetworkXNoPath: no paths or the target type is
            # not in the graph
            for path in nx.all_shortest_paths(self.subG, s, t):
                yield self.__generate_steps(path)

def getAllPaths():
    #import matplotlib.pyplot as plt
    
    g = nx.read_weighted_edgelist("hb.txt")   
    
    #print g["ASPA0085"]["HOHA0402"]
    
    
         
    fp = open("allpaths.txt", 'w')
    
    try:
        counter = 1
        for eachPath in nx.all_shortest_paths(g, u"ASPA0085", u"GLUA0194"):
            if not isValidPath(eachPath):
                continue
            fp.write("path%d" % counter)
            for eachResidue in eachPath:
                fp.write('%10s' % eachResidue)
            fp.write('\n')
            counter += 1
    except nx.exception.NetworkXNoPath:
        fp.write("No connected pathway\n")
    finally:
        fp.close()

    def get_degree_of_separation_visualisation(self, author1, author2):
        
        if author1 == '' or author2 == '':
            return Graph()
        
        if author1 == author2:
            return Graph()
        
        # Compute all the shortest paths from author1 to author2
        try:
            list_of_paths = all_shortest_paths(self.authors_graph, self.author_idx[author1], self.author_idx[author2])
        except NetworkXError as e:
            return "Not found"

        g = Graph()
        # Add the shortest paths to the graph
        try:
            for path in list_of_paths:
                g.add_path(path)
        except NetworkXNoPath as e:
            return Graph()

        # Add attributes to nodes
        for i in g.nodes():
            g.node[i]['name']=self.authors[i].name
        print g.nodes(data=True)
        return g

def shortestInOutPaths(model, input, output):
    shortestPaths = []
    inputnodes = []
    outputnodes = []
    colCount = 0

    for i in input.T:
        if i.any() == 1 and not colCount in inputnodes:
            inputnodes.append(colCount)
        colCount = colCount + 1

    colCount = 0
    for i in output.T:
        if i.any() == 1 and not colCount in outputnodes:
            outputnodes.append(colCount)
        colCount = colCount + 1


    for i in inputnodes:
        for o in outputnodes:
            #if i != o: NOT SURE?!?!?!!?!??!?!?!?
                #from perturbed to the inputs
            shortestPaths.append(networkx.all_shortest_paths(model.myGraph, i, o))

    return shortestPaths

def sorted_paths(graph, station, order_node):
    """Return a list of all paths from station to order_node, but sorted"""
    shortest_length = len(nx.shortest_path(graph, station, order_node))
    all_paths = list(filter(lambda s: len(s) < shortest_length + 5,
            nx.all_shortest_paths(graph, station, order_node)))
    all_paths.sort(key=len)
    return (path for path in all_paths)

 def run(self):
     while True:
         flow = yield self.src.store.get()
         #print flow
         if flow.des == self.src.id:
             flow.end_time = self.env.now
             self.out.store.put(flow)
             #print flow,
             #print " -> arriving time %.8f" % self.env.now
             continue
         # compute the next hop
         
         paths = nx.all_shortest_paths(self.topo,self.src.id,flow.des)
         next_hops = []
         for path in paths:
             if len(path)>1:
                 next_hops.append(path[1])
         next_hop = random.choice(next_hops)
         #print next_hop,
         # forwarding to next_hop
         target = self.src.id
         for sw in self.god.all_nodes:
             if sw.id == next_hop:
                 target = sw
                 break
         #print target
         if target:
             flow.src = target.id
             yield self.env.timeout(flow.size*1.0/self.rate)
             target.store.put(flow)

	def do_path(self, args):
		"Display the shortest path between two nodes"

		arglist = args.split(" ")

		if arglist[0] and arglist[1]:
			#Grab the args
			node1=arglist[0].upper()
			node2=arglist[1].upper()
		else:
			print "[-] Error: Args Needed"

		#ensure they exist
		if G.has_node(node1) and G.has_node(node2):
			if (nx.has_path(G,node1,node2)):
				print "[*] Shortest Paths from %s to %s" %(node1,node2)
				#Get the shortest paths
				paths = nx.all_shortest_paths(G, node1, node2)

				#Print all paths in pretty format
				for p in paths:
					outputpath = "[*] "
					for n in p:
						outputpath+=n+" -> "
					print outputpath[:-4]
			else:
				print "[-] No path exist :("
		else:
			print "[-] Node %s or %s does not exist :(" % (node1, node2)