def test_all_simple_paths_multigraph():
    G = nx.MultiGraph([(1, 2), (1, 2)])
    paths = nx.all_simple_paths(G, 1, 1)
    assert_equal(paths, [])
    nx.add_path(G, [3, 1, 10, 2])
    paths = nx.all_simple_paths(G, 1, 2)
    assert_equal(set(tuple(p) for p in paths), {(1, 2), (1, 2), (1, 10, 2)})

def vote(src,dest,intent):
    path = []
    confidence = 0

    if(intent == 0): #Good Guy. Non Malicious
        path = netshortestpath(src ,dest)
        confidence = get_weight(path)
        #path,confidence=BestBottleneckPath(src,dest)
        return (path,confidence)

    if(intent == 1):          #Evil Guy. malicious
        for paths in nx.all_simple_paths(graph_extern, src, dest):
            temp= get_weight(paths)
            if (temp>confidence):
                confidence = temp
                path = copy.deepcopy(paths)
        #return shortest path weigth -1

        return (path,(get_weight(netshortestpath(src, dest))-1))

    if(intent == 2):          #Good Guy. mis-configured
        for paths in nx.all_simple_paths(graph_extern, src, dest):
            temp= get_weight(paths)
            if (temp>confidence):
                confidence = temp
                path = copy.deepcopy(paths)
                break
        #return shortest path weigth -1
        return (path,confidence)

def find_sg_multiple(G,inode_list,onode_list):
	#print 'Input node list:',inode_list
	#print 'Output node list:', onode_list
	#start = inode_list[0]
	oldreltypes = ['s','n','si','ni','sn','sni']
	for stop in onode_list:
		reltypes = []
		for start in inode_list:
			#print 'start is:', start, 'stop is:', stop
			roads = nx.all_simple_paths(G,start,stop)
			roads = list(roads)
			path_list = sorted(roads, lambda x,y: 1 if len(x)>len(y) else -1 if len(x)<len(y) else 0)
			if len(path_list)>1:
				if start==stop:
					route = path_list[1]
				else:
					route = path_list[0]
			else:
				continue
			prev_rel = 'sn'
			#print 'Looking at path',route
			for i in range(len(route)-1):
				etype = G[route[i]][route[i+1]]['edge_attr']
				rel = path.add(prev_rel,etype)
				if rel == None:
					#print 'Path cannot be added at',route[i],'to',route[i+1]
					srel = sg_add(prev_rel,etype)
					regs = G.predecessors(route[i+1])
					if len(regs)<=1:
						rel = None
					for regulator in regs:
						if regulator == route[i]:
							continue
						found = False
						for source in inode_list:
							if not nx.has_path(G,source,regulator):
								continue
							for p in nx.all_simple_paths(G,source,regulator):
								ptype = path.path_type(G,p)
								rtype = G[regulator][route[i+1]]['edge_attr']
								if sg_add(ptype,rtype) == srel:
									found = True
									break
							if found:
								break
						if found:
							continue
						else:
							rel = None
					rel = srel
				prev_rel = rel
			reltypes.append(rel)
		#print 'for end point',stop,'stored relationships are:',reltypes
		oldreltypes = list(set(reltypes) & set(oldreltypes))
	return oldreltypes

def test_all_simple_paths_on_non_trivial_graph():
    ''' you may need to draw this graph to make sure it is reasonable '''
    G = nx.path_graph(5, create_using=nx.DiGraph())
    G.add_edges_from([(0, 5), (1, 5), (1, 3), (5, 4), (4, 2), (4, 3)])
    paths = nx.all_simple_paths(G, 1, [2, 3])
    assert_equal(set(tuple(p) for p in paths), {
        (1, 2), (1, 3, 4, 2), (1, 5, 4, 2), (1, 3), (1, 2, 3), (1, 5, 4, 3),
        (1, 5, 4, 2, 3)})
    paths = nx.all_simple_paths(G, 1, [2, 3], cutoff=3)
    assert_equal(set(tuple(p) for p in paths), {
        (1, 2), (1, 3, 4, 2), (1, 5, 4, 2), (1, 3), (1, 2, 3), (1, 5, 4, 3)})
    paths = nx.all_simple_paths(G, 1, [2, 3], cutoff=2)
    assert_equal(set(tuple(p) for p in paths), {(1, 2), (1, 3), (1, 2, 3)})

def get_routes(origin, destin, mode, days, hours, weights=WEIGHTS):

    key = (origin, destin, mode, days, hours)
    if key in ROUTES:
        routes = ROUTES[key]
    else:
        start = time()
        graph = get_graph(mode, hours)
        ncity = NUMCITIES[days, hours]
        print('INFO: Graph was built in {0:.3f}s'
              .format(time() - start))

        start = time()

        routes = list(nx.all_simple_paths(graph, source=origin, target=destin,
                                          cutoff=ncity))
        if not routes:
            while not routes and ncity < days:
                print hours
                if hours == 4:
                    hours = 7
                    graph = get_graph(mode, hours)
                    ncity = NUMCITIES[days, hours]
                elif hours == 7:
                    hours = 10
                    graph = get_graph(mode, hours)
                    ncity = NUMCITIES[days, hours]
                else:
                    ncity += 1
                routes = list(nx.all_simple_paths(graph, source=origin, target=destin,
                                                  cutoff=ncity))
        else:
            roundway = origin == destin
            # print 'MAX: ', days, hours, '->', max((len(r) - roundway for r in routes))
            if hours > 4:
                routes.extend(get_routes(origin, destin, mode, days, 4, weights)[0])
                # print 'MAX: ', days, hours, '->', max((len(r) - roundway for r in routes))
            elif hours > 7:
                routes.extend(get_routes(origin, destin, mode, days, 7, weights)[0])
                # print 'MAX: ', days, hours, '->', max((len(r) - roundway for r in routes))
        print('INFO: {} routes were calculated in {:.3f}'
              .format(len(routes), time() - start))

        start = time()
        routes = filter_routes(routes)
        print('INFO: {} routes were selected in {:.3f}'
              .format(len(routes), time() - start))
        ROUTES[key] = routes


    return routes, hours

def find_directed_paths(request, project_id=None):
    """ Given a set of two or more skeleton IDs, find directed paths of connected neurons between them, for a maximum inner path length as given (i.e. origin and destination not counted). A directed path means that all edges are of the same kind, e.g. presynaptic_to. """

    sources = set(int(v) for k,v in request.POST.iteritems() if k.startswith('skeleton_ids['))
    if len(sources) < 2:
        raise Exception('Need at least 2 skeleton IDs to find directed paths!')

    path_length = int(request.POST.get('n_circles', 1))
    cursor = connection.cursor()
    mins, relations = _clean_mins(request, cursor, int(project_id))
    presynaptic_to = relations['presynaptic_to']
    graph = nx.DiGraph()
    next_sources = sources
    all_sources = sources
    length = path_length

    def rev_args(fn):
        def f(arg1, arg2):
            fn(arg2, arg1)
        return f

    # Create a graph by growing the sources
    while length > 0 and next_sources:
        length -= 1
        next_circles = _next_circle(next_sources, cursor)
        next_sources = set()
        for skid1, c in next_circles.iteritems():
            for relationID, targets in c.iteritems():
                threshold = mins[relationID]
                add_edge = graph.add_edge if relationID == presynaptic_to else rev_args(graph.add_edge)
                for skid2, count in targets.iteritems():
                    if count < threshold:
                        continue
                    add_edge(skid1, skid2)
                    next_sources.add(skid2)
        next_sources = next_sources - all_sources
        all_sources = all_sources.union(next_sources)

    # Find all directed paths between all pairs of inputs
    unique = set()
    for start, end in combinations(sources, 2):
        for paths in [nx.all_simple_paths(graph, start, end, path_length + 1),
                      nx.all_simple_paths(graph, end, start, path_length + 1)]:
            for path in paths:
                for node in path:
                    unique.add(node)

    skeleton_ids = tuple(unique - sources)
    return HttpResponse(json.dumps([skeleton_ids, _neuronnames(skeleton_ids, project_id)]))

def _prune_states(K, graph, source, sink):
    """
    Removes cycles and redundant nodes (that are not reachable from source)
    from the subgraph of graph defined by the nodes in K.
    
    """
    
    # Create a subgraph with the nodes now in K
    # Find and remove cycles by deleting the edge between 
    # the second to last node and the last node of the cycle,
    # thus keeping nodes that may be important 
    # to the trust calculation.
    subgraph = graph.subgraph(K)
    cycles = nx.simple_cycles(subgraph)
    if cycles:
        for cycle in cycles:
            subgraph.remove_edges_from([(cycle[-2], cycle[-1])])
            
    # Get all paths from source to sink without cycles and redundant nodes
    simple_paths = list(nx.all_simple_paths(G=graph, source=source, target=sink))
    relevant_nodes = set(chain.from_iterable(simple_paths))
            
    # Remove nodes no longer used (not in simple_paths)
    for n in K:
        if n not in relevant_nodes:
            subgraph.remove_node(n)
            
    return subgraph

def get_ontology_paths(basic_ontology, from_type, to_obj):
    """
    type-to-type ontology path

    :param ontology:
    :param from_type:
    :param to_obj:
    :return:
    """
    assert from_type.name in basic_ontology.types
    assert to_obj.type.name in basic_ontology.types


    graph = basic_ontology.ontology_graph.copy()
    assert isinstance(graph, nx.DiGraph)

    for function in basic_ontology.functions.values():
        if function.valence > 1:
            graph.remove_node(function.id)

    """
    if from_type is to_obj:
        paths = [cycle for cycle in nx.simple_cycles(basic_ontology.ontology_graph) if from_type.id in cycle]
    """
    if not nx.has_path(graph, from_type.id, to_obj.type.id):
        paths = []
    elif from_type == to_obj.type:
        paths = [[from_type.id]]

    else:
        paths = list(nx.all_simple_paths(graph, from_type.id, to_obj.type.id))

    path_dict = {key: OntologyPath(basic_ontology, [basic_ontology.get_by_id(id_) for id_ in path] + [to_obj], key)
                 for key, path in enumerate(paths)}
    return path_dict

def pathOD_incidence(graph, haspath=False):
    """
    get path-OD incidence matrix

    Parameters
    ----------
    graph: graph object
    haspath: if True, simple has already been set before

    Return value
    ------------
    C: matrix of incidence path-OD
    """
    nnode, nlink = graph.numnodes, graph.numlinks
    npair = len(graph.ODs.keys())

    G = nx.DiGraph()
    G.add_nodes_from(graph.nodes.keys())
    G.add_edges_from([(key[0],key[1]) for key in graph.links.keys()])
    if not haspath:
        for OD in graph.ODs.itervalues():
            for nodes_on_path in nx.all_simple_paths(G, OD.o, OD.d):
                graph.add_path_from_nodes(nodes_on_path)
    npath = len(graph.paths)
    entries, I, J = [], [], []
    for OD in graph.ODs.itervalues():
        u = OD.o; v=OD.d
        indcol = graph.indods[(u,v)]
        for path in graph.paths.iterkeys():
            if (u == path[0]) and (v == path[-1]):
                indrow = graph.indpaths[path]
                entries.append(1.0); I.append(indrow), J.append(indcol)
    C = spmatrix(entries, I, J, (npath, npair))
    return C

def write_sat_dcbusprop2(G,buslist, genlist):
    H = copy.deepcopy(G)
    for i in buslist:
        f.write('(assert (=> (not (or ')
        for j in genlist:
            gen_temp = copy.deepcopy(gens)
            gen_temp.remove(j)
            H.remove_nodes_from(gen_temp)
            for path in nx.all_simple_paths(H,i,j):
                f.write(' (and')
                for k in range(1,len(path)):
                    if path[k] in gens:
                        f.write(' (= g'+str(path[k])+' true)')
                    elif path[k] in busac:
                        f.write(' (= b'+str(path[k])+' true)')
                    elif path[k] in null:
                        f.write(' (= b'+str(path[k])+' true)')
                    elif path[k] in rus:
                        f.write(' (= r'+str(path[k])+' true)')
                for m in range(0,len(path)-1):
                    if path[m] in busdc and path[m+1] in rus:
                        pass
                    elif path[m] in rus and path[m+1] in busdc:
                        pass
                    elif path[m] < path[m+1]:
                        f.write(' (= c'+str(path[m])+str(path[m+1])+' true)')
                    elif path[m+1] < path[m]:
                        f.write(' (= c'+str(path[m+1])+str(path[m])+' true)')
                f.write(')')
            H = copy.deepcopy(G)
        f.write(')) (= b'+str(i)+' false)))\n')

def dcbusspec(G,busno,gen):
    """Creates specifications for when DC bus gets powered
    
    Parameters
    ----------
    G : networkX graph

    busno : node
       dc bus
       
    gen : node
       generator

    """
    paths = []
    C = []
    temp = []
    edges = []
    D = copy.deepcopy(G)
    gens2 = copy.deepcopy(gens)
    gens2.remove(gen)
    D.remove_nodes_from(gens2)
    for path in nx.all_simple_paths(D,busno,gen,cutoff=None):
        paths.append(path)
    for j in range(0,len(paths)):
        f.write('guarantees += '"'"'&\\n\\t[]((B'+str(busno)+str(gen)+str(j)+') -> (b'+str(busno)+'=1))'"'"'\n')

def GetLocalBridge(g, topic, windowsize, date):
    '''
    通过遍历边，对是否为捷径进行判断，将跨度最大的前10名存放在数据库中
    '''
    localbridge = []
    edges_list = g.edges()
    for (a,b) in edges_list:
        a_n = set(g.neighbors(a))
        b_n = set(g.neighbors(b))
        l_a_n = len(a_n)
        l_b_n = len(b_n)
        l_ab_n = len(a_n & b_n)
        if (l_a_n!=1)&(l_b_n!=1)&(l_ab_n==0):
            paths_list = nx.all_simple_paths(g, source=a, target=b)
            span_ab = 0
            len_path = 0
            for path in paths_list:
                len_path += 1
                if len(path) > span_ab:
                    span_ab = len(path)
            if len_path == 1:
                span_ab = 10000 # 当去除了仅有的那条边之后没有其他路径能够连接ab，则使跨度为10000
            
            localbridge.append((a, b, span_ab, l_a_n, l_b_n))
            
    SaveLocalBridge(topic, date, windowsize, localbridge) # 存放localbridge数组

    def slice_graph(graph, node, frontier, include_frontier=False):
        """
        Generate a slice of the graph from the head node to the given frontier.

        :param networkx.DiGraph graph: The graph to work on.
        :param node: The starting node in the graph.
        :param frontier: A list of frontier nodes.
        :param bool include_frontier: Whether the frontier nodes are included in the slice or not.
        :return: A subgraph.
        :rtype: networkx.DiGraph
        """

        subgraph = networkx.DiGraph()

        for frontier_node in frontier:
            for simple_path in networkx.all_simple_paths(graph, node, frontier_node):
                for src, dst in zip(simple_path, simple_path[1:]):
                    if include_frontier or (src not in frontier and dst not in frontier):
                        subgraph.add_edge(src, dst)
        if not list(subgraph.nodes):
            # HACK: FIXME: for infinite loop nodes, this would return an empty set, so we include the loop body itself
            # Make sure this makes sense (EDG thinks it does)
            if (node, node) in graph.edges:
                subgraph.add_edge(node, node)
        return subgraph

    def get_all_simple_path(self, source, dest):
        """Get all simple path from a point to an other.

        Return
        ------
        Return a networkX list of path
        """
        source_node = None
        dest_node = None

        if source:
            for i in self.subnet_list:
                if Ip.ListContains([i], source):
                    source_node = i
                    break

        if dest:
            for i in self.subnet_list:
                if Ip.ListContains([i], dest):
                    dest_node = i
                    break

        if not source or not dest:
            for node in self.graph.nodes(data=True):
                if node[1]['object'].marker_type == 'from':
                    source_node = node[0]
                if node[1]['object'].marker_type == 'to':
                    dest_node = node[0]

        if not source_node or not self.multidigraph.has_node(source_node)\
                or not dest_node or not self.multidigraph.has_node(dest_node):
            raise

        return nx.all_simple_paths(self.multidigraph, source_node, dest_node)

def least_overlapping_backup_path(G):
    for n, nattr in G.nodes(data=True):
        pp = nattr['primary_paths']
        bp = nattr['backup_paths']
        bnh = nattr['backup_next_hop']
        print "\nCalculating Node = %d" % n
        for m, mattr in G.nodes(data=True):
            if m == n:
                pp.append([])
                bp.append([])
                bnh[m] = None
            else:
                ppx = nx.shortest_path(G, source=n, target=m)
                pp.append(ppx)
                pm = nx.all_simple_paths(G, source=n, target=m)
                # random.shuffle(pm)
                bp.append(get_single_backup(ppx, pm))
                bnh[m] = (bp[m][1])
                sys.stdout.write('.')
                # print "Path Matrix of %d to %d = %s" % (n, m, pm)
            # print "Primary_path of %d to %d = %s" % (n, m, pp[m])
            # print "Backup_path of %d to %d = %s" % (n, m, bp[m])
            # print "Backup_next_hop of %d to %d = %.0f" % (n, m, bnh[m])

        nattr['primary_paths'] = pp
        nattr['backup_paths'] = bp
        nattr['backup_next_hop'] = bnh

def find_same_level_regions(region):
    # Load graph
    graph = load_graph()
    if not graph:
        logger.error("Can't trace multiple regions: Region call graph not available.\n\
                      Run cere profile.\n\
                      Tracing region {0}".format(region))
        return

    # Find region node id
    region_node = get_region_id(region, graph)

    #Find roots
    roots = [n for n,d in graph.in_degree().items() if d==0]

    #Compute for every nodes, the max distance from himself to each root
    max_path_len = {}
    for root in roots:
        for n, d in graph.nodes(data=True):
            if n not in max_path_len: max_path_len[n]=0
            #Get every paths from the current root to the node
            paths = list(nx.all_simple_paths(graph, root, n))
            #Keep the max length path
            for path in paths:
                if len(path)-1 > max_path_len[n]:
                    max_path_len[n] = len(path)-1

    #Keep region which have the same depth than the requested region
    for n, p in max_path_len.iteritems():
        if p == max_path_len[region_node]:
            yield graph.node[n]['_name']

    def get_maximal_path_length(self):
        """
        Get the maximal path length from all simple paths that traverses the projection graph from
        one leave node to another.

        .. note::
           This measure is sensitive to the resolution of a projection
           the same way the length of a coastline is sensitive to the resoltuion.

        .. warning::
            Whether this code will stay in the library or not depends
            on future evaluation of the usefulness of this and similar descriptors.

        """
        import networkx as nx
        maxl = 0
        for i, node1 in enumerate(self.proj_graph.nodes()):
            for j, node2 in enumerate(self.proj_graph.nodes()):
                if j <= i:
                    continue
                all_paths = nx.all_simple_paths(self.proj_graph, node1, node2)
                for path in all_paths:
                    l = self._get_path_length(path)
                    if l > maxl:
                        maxl = l
        return maxl

def get_long_walk_score(node1, node2, graph):
	
	edge_removed = False
	if graph.has_edge(node1, node2):
		edge_removed = True
		edge_data = graph[node1][node2]
		graph.remove_edge(node1, node2)

	all_simple_paths = nx.all_simple_paths(graph, source=node1, target=node2, cutoff=PATH_LENGTH_CUTOFF)
	
	output = 0
	num_paths = 0
	for path in all_simple_paths:
		path_score = 1
		for loc1,loc2 in zip(*(path[i:] for i in [0,1])): # for every connected pair
			dat = graph[loc1][loc2]
			num_lines = dat["first_user_num_lines"]+dat["second_user_num_lines"]
			path_score *= (1 - 1/float(num_lines+1) )
 		output = max(output,path_score)
		num_paths += 1
    
	if edge_removed:                                   
		graph.add_edge(node1, node2, attr_dict=edge_data)

	return output	

    def _generate_path(self, topo, src_mac, dst_mac, src_port,
                       dst_port, src_dpid, dst_dpid):
        """Generate path method."""
        net = nx.DiGraph(data=topo)
        net.add_node(src_mac)
        net.add_node(dst_mac)
        net.add_edge(int(src_dpid), src_mac, {'port': int(src_port)})
        net.add_edge(src_mac, int(src_dpid))
        net.add_edge(int(dst_dpid), dst_mac, {'port': int(dst_port)})
        net.add_edge(dst_mac, int(dst_dpid))

        target_path = None
        try:
            path = nx.shortest_path(net, src_mac, dst_mac)
            path2 = nx.shortest_path(net, src_mac, dst_mac)
            path2.pop()
            path2.pop(0)
            list_load = check_switch_load(path2, data_collection.switch_stat, constant.load_limitation)
            if len(list_load) > 0:
                # print 'lui', list_load
                all_paths = nx.all_simple_paths(net, src_mac, dst_mac)
                path_list = list(all_paths)
                target_path_index, target_path_cost = calculate_least_cost_path(path_list, data_collection.switch_stat, net)
                target_path = path_list[target_path_index]
            else:
                target_path = path
            print 'tarrr', target_path
        except Exception:
            target_path = None
        return target_path

def get_assemblie(G,read_db):
    contigs={}
    if len(G.nodes())>1:
        starting_nodes=[n for n in G.nodes() if G.in_degree(n)==0]
        ending_nodes=[n for n in G.nodes() if G.out_degree(n)==0]

        paths=[]
        for start_node in starting_nodes:
            for end_node in ending_nodes:
                two_nodes_paths=nx.all_simple_paths(G,start_node,end_node)

                for path in two_nodes_paths:
                    print path
                    contig_key='contig_'+':'.join(path)
                    contigs[contig_key]=read_db[path[0]]
                    for idx in range(1,len(path)):
                        prev,current=path[idx-1],path[idx]
                        seq=read_db[current]
                        #pdb.set_trace()
                        overlap=int(G[prev][current]["label"])
                        contigs[contig_key]+=seq[overlap:]
                    #contigs.append(contig)
    else:
        contig_key='contig_'+G.nodes()[0]
        contigs[contig_key]=read_db[G.nodes()[0]]

    return contigs