breadth first search / depth first search or Directed graph?

Question

I have been struggling with this for a while now. given a set of nodes:

nodes = { ('A','B'),
          ('B','C'),
          ('C','D'),
          ('C','E'),
          ('B','E'),
          ('C','F') }

what is the best way to achieve the following:

                          A
                          |
                          B
                 _________|_________
                 |                  |
                 C                  E
            _____|_____             |
            |    |     |            C
            D    E     F        ____|____
                                |        |
                                D        F

where I can see that:

the routes from A -> B:
A -> B
the routes from A -> C: 
A -> B -> C
A -> B -> E -> C
the routes from A -> D:
A -> B -> C -> D
A -> B -> E -> C -> D

etc...

My reason for doing this, is purely because I want to understand how to.

I know that bfs finds the quickest route, (I think I might be using something similar in the get children function)

but I do not know the best way to loop / recursively run over the graph. Should I use a dictionary and work with key/vals or a list. Or sets...

def make_graph(nodes):
    d = dict()
    for (x,y,*z) in nodes:
        if x not in d: d[x] = set()
        if y not in d: d[y] = set()
        d[x].add(y)
        d[y].add(x)
    return d

I am using *z here as the tuples will actually include a float, but at the moment I am trying to keep things simple.

def display_graph(nodes):
    for (key,val) in make_graph(nodes).items():
        print(key, val)

# A {'B'}
# C {'B', 'E', 'D', 'F'}
# B {'A', 'C', 'E'}
# E {'C', 'B'}
# D {'C'}
# F {'C'}

the getchildren function finds all possible end points for the node root:

def getchildren(noderoot,graph):
    previousnodes, nextnodes = set(), set()
    currentnode = noderoot
    while True:
        previousnodes.add(currentnode)
        nextnodes.update(graph[currentnode] - previousnodes)
        try:
            currentnode = nextnodes.pop()
        except KeyError: break
    return (noderoot, previousnodes - set(noderoot))

In this case A:

print(getchildren('A', make_graph(nodes)))

# ('A', {'C', 'B', 'E', 'D', 'F'})

Answer 1

Before coding with a program language, you need to abstract the problem properly.

First you need to think about the properties of your graph, such as cyclic/acyclic, directed/undirected, etc..

Then you need to choose a way to solve your problem accordingly. e.g. if it's a acyclic, undirected and connected graph, then you can represent the graph as a tree and use either BFS or DFS to traverse it.

Finally, after you think through all of these, you can put it into code much more easier. Like what you've already been doing, you can give each node a list storing all the neighbors and use the BFS to traverse the tree.

Answer 2

Thank you everyone, Problem solved. The function I needed to write was the following.

def trace_graph(k, graph):
    """ takes a graph and returns a list of lists showing all possible routes from k """
    paths = [[k,v] for v in graph[k]]
    for path in paths:
        xs = path[:-1]
        x  = path[-1]
        for v in graph[x]:
            if v not in xs and path + [v] not in paths:
                paths.append(path + [v])
    paths.sort()
    return paths


for path in trace_graph('A', make_graph(nodes)):
    print(path)


['A', 'B']
['A', 'B', 'C']
['A', 'B', 'C', 'D']
['A', 'B', 'C', 'E']
['A', 'B', 'C', 'F']
['A', 'B', 'E']
['A', 'B', 'E', 'C']
['A', 'B', 'E', 'C', 'D']
['A', 'B', 'E', 'C', 'F']

Answer 3

I don't think an ordinary tree structure makes sense for representing your data, given that it's sequential but not necessarily ordered/sorted. It would probably be more appropriate to make use of either tries (either prefix or radix trees) or (probably better) directed graphs.

Answer 4

I think you may be making things more complicated than they need to be. Think about the type of data you are representing as xvatar has said.

For a basic directed graph a dictionary makes sense. Simply store parent: list of children.

nodes = [ ('A','B'),
          ('B','C'),
          ('C','D'),
          ('C','E'),
          ('B','E'),
          ('C','F') ]

from collections import defaultdict
d = defaultdict(list)
for node in nodes:
    d[node[0]].append(node[1])

Finding all reachable children from any root node is simple:

def getchildren(root, graph, path=[]):
    path = path + [root]
    for child in graph[root]:
        if child not in path:  #accounts for cycles
            path=getchildren(child, graph, path)
    return path

When calling:

>>> print getchildren('A',d)
['A', 'B', 'C', 'D', 'E', 'F']
>>> print getchildren('C',d)
['C', 'D', 'E', 'F']