Converting a few python lines in pseudocde

Question

Goal: Trying to convert some of the lines of an algorithm written in python to pseudocode.

Goal of the given algorithm: Find all cycles in a directed graph with cycles.

Where I stand: I well understand the theory behind the algorithm, I have also coded different versions on my own, however I cannot write an algorithm that small, efficient and correct on my own.

Source: stackoverflow

What I have done so far: I cannot describe enough how many weeks spent on it, have coded Tarjan, various versions DFS, Flloyd etc in php but unfortunately they are partial solutions only and one have to extend them more.

In addition: I have run this algorithm online and it worked, I need it for a school project that I am stack and cannot proceed further.

This is the algorithm:

def paths_rec(path,edges):
    if len(path) > 0 and path[0][0] == path[-1][1]:
        print "cycle", path
        return #cut processing when find a cycle

    if len(edges) == 0:
        return

    if len(path) == 0:
        #path is empty so all edges are candidates for next step
        next_edges = edges
    else:
        #only edges starting where the last one finishes are candidates
        next_edges = filter(lambda x: path[-1][1] == x[0], edges)

    for edge in next_edges:
        edges_recursive = list(edges)
        edges_recursive.remove(edge)
        #recursive call to keep on permuting possible path combinations
        paths_rec(list(path) + [edge], edges_recursive)


def all_paths(edges):
    paths_rec(list(),edges)

if __name__ == "__main__":
    #edges are represented as (node,node) 
    # so (1,2) represents 1->2 the edge from node 1 to node 2. 
    edges = [(1,2),(2,3),(3,4),(4,2),(2,1)]
    all_paths(edges)

This is what I have managed to write in pseudocode from it, I have marked with #? the lines I do not understand. Once I have them in pseudocode I can code them in php with which I am a lot familiar.

procedure paths_rec (path, edges)

if size(path) > 0 and path[0][0] equals path[-1][1] 
    print "cycle"
    for each element in path
        print element
    end of for
    return
end of if


if size(edges) equals 0
    return
end of if

if size(path) equals 0
    next_edges equals edges
else
    next edges equals filter(lambda x: path[-1][1] == x[0], edges) #?
end of else  

for each edge in next_edges
edges_recursive = list(edges) #?
edges_recursive.remove(edge)#?
#recursive call to keep on permuting possible path combinations
paths_rec(list(path) + [edge], edges_recursive)#?

Not a surprise at all, at least you could refer the reason for downvoting so I can do something about it, I really wonder sometimes if there is any point on bothering with getting invloved anymore! — Melsi, Mar 05 '12 at 02:00

score 1 · Accepted Answer · answered Mar 05 '12 at 02:04

The line next_edges = filter(lambda x: path[-1][1] == x[0], edges) creates a new list containing those edges in edges whose first point is the same as the second point of the last element of the current path, and is equivalent to

next_edges = []
for x in edges:
    if path[len(path) - 1][1] == x[0]
        next_edges.append[x]

The lines create a new copy of the list of edges edges, so that when edge is removed from this copy, it doesn't change the list edges

edges_recursive = list(edges)
edges_recursive.remove(edge)

paths_rec(list(path) + [edge], edges_recursive) is just the recursive call with the path with edge added to the end and the new list of edges that has edge removed from it.

Converting a few python lines in pseudocde

1 Answers1