Geek Answers Handbook

Find path using all given python edges

I have a list of ribs. I need to decode a path from a node source in order to sink a node from them. There may be loops on my paths, but I should use only one of the edges once. On my list, I could also have the same edge more than once, which means that in my way I have to pass it more than once.

Let's say my ribs are listed as follows:

[(1, 16), (9, 3), (8, 9), (15, 8), (5, 1), (8, 15), (3, 5)]

so my way:

8->15->8->9->3->5->1->16 equivalent to [8,15,8,9,3,5,1,16]

I know the shell of node and the source of node. (In the above example, I knew that 8 is the source and 16 is the receiver), here is another example with more than one using the same edge:

[(1,2),(2,1),(2,3),(1,2)]

way:

1->2->1->2->3 equivalent to [1,2,1,2,3]

This is mainly a type of topological sorting, but we do not have loops in topological sorting. I have the following code, but it does not use nodes in loops!

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
return paths
+4
1

, , .

:

  • . ,
  • in_degree= out_degree , 2 . in_degree - out_degree= 1, in_degree - out_degree= -1.

, , . , . (, , "" [(1,2),(2,1),(1,3),(3,1),(1,4),(4,1),(1,5),(5,1)], .)

, , node , . , , , . . .

. . , "" !

"""
This is a basic implementatin of Hierholzer algorithm as applied to the case of a 
directed graph with perhaps multiple identical edges.
"""

import collections

def node_dict(edge_list):
    s_dict = collections.defaultdict(list)
    for edge in edge_list:
        s_dict[edge[0]].append(edge)
    return s_dict

def get_a_path(n_dict,start):
    """
    INPUT:  A dictionary whose keys are nodes 'a' and whose values are lists of 
    allowed directed edges (a,b) from 'a' to 'b', along with a start WHICH IS 
    ASSUMED TO BE IN THE DICTIONARY.

    OUTPUT:  An ordered list of initial nodes and an ordered list of edges 
    representing a path starting at start and ending when there are no other 
    allowed edges that can be traversed from the final node in the last edge.

    NOTE:  This function modifies the dictionary n_dict!
    """

    cur_edge = n_dict[start][0]
    n_dict[start].remove(cur_edge)

    trail = [cur_edge[0]]
    path = [cur_edge]
    cur_node = cur_edge[1]

    while len(n_dict[cur_node]) > 0:
        cur_edge = n_dict[cur_node][0]
        n_dict[cur_node].remove(cur_edge)
        trail.append(cur_edge[0])
        path.append(cur_edge)
        cur_node = cur_edge[1]

    return trail, path


def find_a_path_with_all_edges(edge_list,start):
    """
    INPUT:  A list of edges given by ordered pairs (a,b) and a starting node.

    OUTPUT:  A list of nodes and an associated list of edges representing a path 
    where each edge is represented once and if the input had a valid Eulerian 
    trail starting from start, then the lists give a valid path through all of 
    the edges.

    EXAMPLES:

        In [2]: find_a_path_with_all_edges([(1,2),(2,1),(2,3),(1,2)],1)
        Out[2]: ([1, 2, 1, 2, 3], [(1, 2), (2, 1), (1, 2), (2, 3)])

        In [3]: find_a_path_with_all_edges([(1, 16), (9, 3), (8, 9), (15, 8), (5, 1), (8, 15), (3, 5)],8)
        Out[3]: 
        ([8, 15, 8, 9, 3, 5, 1, 16],
         [(8, 15), (15, 8), (8, 9), (9, 3), (3, 5), (5, 1), (1, 16)])
    """

    s_dict = node_dict(edge_list)
    trail, path_check = get_a_path(s_dict,start)

    #Now add in edges that were missed in the first pass...
    while max([len(s_dict[x]) for x in s_dict]) > 0:
        #Note:  there may be a node in a loop we don't have on trail yet
        add_nodes = [x for x in trail if len(s_dict[x])>0]
        if len(add_nodes) > 0:
            skey = add_nodes[0]
        else:
            print "INVALID EDGE LIST!!!"
            break

        temp,ptemp = get_a_path(s_dict,skey)
        i = trail.index(skey)
        if i == 0:
            trail = temp + trail
            path_check = ptemp + path_check
        else:
            trail = trail[:i] + temp + trail[i:]
            path_check = path_check[:i] + ptemp + path_check[i:]

    #Add the final node to trail.
    trail.append(path_check[-1][1])
    return trail, path_check
0

More articles:


All Articles