Finding reachable vertices of a vertice in a graph

I am having problem in my code to calculate the reachable vertices in a graph.

I have the following code for the graph

class Vertices():
    number = 0
    def __init__(self):
        Vertices.number += 1
        self.number = Vertices.number
        self.Reachable= []

I create the graph in the following way

a = Vertices()
a.Reachable = [1,2]
b = Vertices()
b.Reachable = [3]
c = Vertices()
c.Reachable= [3]
List = []
List.append(a)
List.append(b)
List.append(c)

Thus vertice 1 that is a has an edge to itself and b . Similarly for b and for c.

We can move around the graph using List ie for vertex a it is reachable to List[trans-1] where trans refers to the Reachable list of a (List[0] and List[1])

Now in this graph I have to calculate the reachabil开发者_如何转开发ity for each vertice ie for each vertice calculate the vertices that it can reach.For eg a can reach a,b and c

I have read that I can use sets to do depth first search in all the list. Can you provide me a solution as to how to proceed.

Can anyone tell me how to use sets as I think that it is quite ideal for this problem seeing that it has union and difference functions associated with it.... PS : This is'nt a school based assignment.....

How about using well-known solution to your problem?

First, you need a data structure for a graph. You can do it as dictionary of lists where each vertex is represented as the key and reachable vertices are the list values.

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

If you represent your graph as shown above, finding the neighbouring vertices of B would be just

neighbours_of_B = graph['B']

and (from the same site) finding all paths without cycles would be:

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

and run it as:

find_all_paths(graph, 'A', 'D')

hope that helps. Read more about it at the above link.

Why don't you use NetworkX or any other graph library?

Your current representation won't work. How is any function supposed to go from the number 2 to the vertice b ? You need to add the actual object, not just their number.

Once you did that you can do something like this:

def reachable( start ):
    # the set of reachable nodes
    reachable = set()

    # recursive function to add all reachable nodes to `reachable`
    def finder(node):
        reachable.add(node.)
        for other in node.Reachable:
            finder(other)

    # add everything we can reach from here
    finder(start)
    return reachable

Well first off it's Vertex, not Vertice. Secondly, you have (approximately) implemented an adjacency list as the data structure for your graph; it would be more standard to use an adjacency matrix.

Do you know what depth-first search is? Roughly, you start at a vertex and pick a neighbour, then pick a neighbour of that, and so on until you run out of neighbours to pick. Then you backtrack and pick the next neighbour, and so on. It is elegantly implemented recursively (have you come across that before?), because the problem can easily be separated into smaller pieces: to search a graph depth-first you simply start from any vertex and then depth-first search from all its neighbours in turn.

Concretely, you need to break the problem into smaller problems: suppose you can find the nodes reachable from b and c. What can you reach from a? Well, b, everything reachable from b, c, and everything reachable from c.