following node links

Question

I am having trouble getting my head around how to approach this... I am not asking for an explicit answer, just a heads up about what approach to take. As I have run into problems with every one I have taken so far.

I have a set of nodes:

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

as a dictionary of sets:

nodedict = { 'A': {'B'},
             'C': {'B', 'E', 'D', 'F'},
             'B': {'A', 'C', 'E'},
             'E': {'C', 'B'},
             'D': {'C'},
             'F': {'C'} }

what I want to do is to build a structure like this:

for 'A'

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

so all possible routes from A can be found.

I have been using a list to represent the braches, and then trying to wrap a for loop in a while loop... appending each list with its children if the child is not in the list... but I keep coming unstuck. I sometimes get close, but this is when I am writing explicit for loops and know exactly what I am looking for.

is it best to try to get to one tip first, then backtrack and then to the next tip ...

for x in xs:
   ...
   for a in x:
      ...
      for b in a

but obviously I do not know how deep node 'n' goes... hmmm... any helpful suggestions much appreciated!

yeah, and the thing is I have been learning Haskell... I got it working recursively in Python, but when I returned the list index, and passed it back into the function it did not appreciate what I had intended. It didn't change. — beoliver, Jun 10 '12 at 17:53

score 1 · Accepted Answer · edited May 23 '17 at 11:49

1

I have no experience with python, however you have said you do not want an explicit answer.

You have a tree. This is one of the most well covered structures out there and there are many ways to represent it and traverse it.

At minimum you need to know the node at the root of the tree and be able to retrieve the children of any given node. From those two pieces of information it is possible to traverse the entire tree if you keep track of what you're doing.

Look into Tree traversal.

There is also a question on implementing a tree in python here.

edited May 23 '17 at 11:49

Community

1
1

answered Jun 10 '12 at 18:06

MutterMumble

36
2

it is the keeping track that is causing the problems. :) – beoliver Jun 10 '12 at 18:19
I am not clear what approach you are trying for. Procedural or functional? Recursive or not? It is difficult to give you an approach without being more specific. Breadth first and depth first search are easy to find implemented in any given language. – MutterMumble Jun 10 '12 at 18:31
Ideally It would be functionally, but I have a feeling it will turn into some strange lovechild that only a mother could love. I am also thinking about seeing if I can use python set comparisons to my advantage. – beoliver Jun 10 '12 at 18:33
If you are doing it functionally you will need to have an argument to your function that accumulates as you go. For example you can call something like findPaths(visitedNodes, currentNode, nodesToVisit). When you start currentNode is the root - A. You will have an empty list of visitedNodes and nodesTovisit. (i.e. findPaths([],A,[]). From there you would call findPaths([A],B,[]) which would in turn call findPaths([A,B], C, [E]) and so forth... – MutterMumble Jun 10 '12 at 18:42
this was actually something that I was using, but I was using a list, and the list index that I returned and passed back did reference what I wanted. I am going to try again, but with a dictionary. – beoliver Jun 10 '12 at 18:50

score 0 · Answer 2 · answered Jun 10 '12 at 17:56

0

Have you considered adopting Dijkstra's algorithm?

answered Jun 10 '12 at 17:56

Managu

8,849
2
30
36

following node links

2 Answers2