Gist of the Day: Find All Paths for an Undirected Graph

I’ve been doing a lot of stuff lately with data structures and algorithms. This is one that seemed remarkably complicated to me – and still kinda does – when I started. It’s not as trivial as a binary tree mainly because there are far fewer rules. There’s a whole lot of stuff you can do with graphs, and this is by no means an advanced or complicated usage of them. This is as simple a task you can do with a graph.
The task at hand is to find all possible paths between two vertices.

The Graph

So, I’m not even going to try to be clever with the image of the graph here. Instead I’m going to give you a fancy hand-drawn one in my best handwriting (yes, this is my best handwriting):

So here you can see that I have a lovely graph, and this is what I will construct in my test.

The Code

Please note that I have abandoned a lot of the usual OO-Perl boilerplate here since I was still trying to really understand this problem when I wrote this. I still think that the extra OO boilerplate is a bit much for this test. I’m using a recursive function to traverse the tree, and since this is the first time I’ve ever attempted this structure or this algorithm I am virtually certain that there are better ways to do both.
This is pretty basic, if you want to read something to get a better understanding about this problem check out the chapter on graphs in Mastering Algorithms in Perl, it’s a great read and it has helped me tremendously.
Here’s the code:

You’ll notice at the bottom where I have the tests section that I am creating edges between all vertices in both directions, and this is because I want this graph to be undirected, while I believe the algorithm I have implemented works with both directed and undirected (I haven’t tested it with directed graphs though).
If you run the program you get this output:

1..4
Path: F, B, A, C
Path: F, B, E, C
Path: F, D, A, B, E, C
Path: F, D, A, C
ok 1 – Verify we have four paths between F and C…
Path: A, B
Path: A, C, E, B
Path: A, D, F, B
ok 2 – Verify we have four paths between A and B…
Path: A
ok 3 – Verify we have only the one path for A to A…
Path: B, A, C, G
Path: B, E, C, G
Path: B, F, D, A, C, G
ok 4 – Verify we have only the three paths between B and G…

So you can see that I have four tests defined, to get from F to C, to get from A to B, to test a cycle from A to A, and to test from B to G.

The Conclusion

Graphs appear to me to be one of the more complicated data structures, mainly because there are so many different ways you can use them and many different things you can do with them. I think I need to dig a little deeper into this topic, but I think that I did pretty well to perform this particular task. Be kind if you have criticism or corrections, and again, remember Wheaton’s law.
I did not develop this Gist using koding.com, but I do most of the time. I had bandwidth issues while I was writing the code, so I couldn’t get to koding.com.
If you think you’d like to use koding.com (and I think you would), check it out. If you click here and sign up, it gives me more disk space to write code with, which enables me to do more of this. I apologize in advance, but there is no way to stop me.