DFS on a graph using a python generator

Question

I am using a generator to do a full search on a graph, the real data set is fairly large, here is a portion of the code i wrote on a small data set:



class dfs:
    def __init__(self):
        self.start_nodes = [1,2]  # not used, see below explanation
        self.end_nodes = [5,7] # not used, see below explanation
    _graph={
        1 : [4,5,6,2],
        2 : [1,3,5],
        4 : [1,5],
        3 : [5,2],
        5 : [3,1,4,6,2,7],
        6 : [1,5],
        7 : [5],
    }

    def __iter__(self):
        return self.find_path(self._graph, 2, 7)

    def find_path(self, graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            yield path
        if not graph.has_key(start):
            return
        for node in graph[start]:
            if node not in path:
                for new_path in self.find_path(graph, node, end, path):
                    if new_path:
                        yield new_path


d = dfs()
print list(d)

when run this outputs all the paths from '2' to '7' as expected:

[[2, 1, 4, 5, 7], [2, 1, 5, 7], [2, 1, 6, 5, 7], [2, 3, 5, 7], [2, 5, 7]]

What I would like to do is modify this generator so that it does the same thing except i get the paths back for a set number of start and end points, ie self.start_nodes and self.end_nodes.

Since my generator is a recursive function it makes it difficult to loop on the different start and end points, been scratching my head over this any ideas?

Be careful using a list as a default argument! See stackoverflow.com/questions/1534407/… and stackoverflow.com/questions/1011431/common-pitfalls-in-python — blinsay
– blinsay, Commented Jul 21, 2011 at 7:02

Community · Accepted Answer · 2017-05-23 09:58:49Z

1

Perhaps I'm misunderstanding your question, but it seems to me that you want to replace your __iter__ function with something like this:

def __iter__(self):
    for start in self.start_nodes:
        for end in self.end_nodes:
            for path in self.find_path(self._graph, start, end):
                yield path

You can find more information about generators in this question.

edited May 23, 2017 at 9:58

CommunityBot

11 silver badge

answered Apr 18, 2011 at 1:50

srgerg

19.4k4 gold badges59 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

john Over a year ago

that worked, sorry it seems obvious now i guess i need some more practice with generators (just learned about them)

Collectives™ on Stack Overflow

DFS on a graph using a python generator

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related