Finding reachable vertices of a vertex in a graph

Question

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 vertex 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 i.e. 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 reachability for each vertex i.e. for each vertex calculate the vertices that it can reach. For example 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 isn't a school based assignment.....

Answer 1

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.