Graph traversal--shortest path?

porkpilot has asked for the wisdom of the Perl Monks concerning the following question:

Venerable Monks,

Please hear me for I am in much need of your wisdom...

Nearing the anniversary of this (Golf) post, I find myself faced with a similar, "bacon number" type problem.

I have a MySQL database of collected factoids (nodes), each identified by a unique integer. Intersecting factoids (vertices) are identified in graph coordinate fashion. So, if fact1id='1' and fact2id='2', the intersection between them is identified as (1,2).

After hours of searching the web, a good deal of thought and much fiddling with code, I am left wondering about a few things... (Please read more for questions.)

Firstly, since the data is not recorded in the database in similar form to the Bacon/Golf post mentioned above, I am wondering if the form

    %t =(22 =>[7, 40, 19, 24, 21, 33],
         ...
         40 =>[18, 33, 23, 37, 22, 48, 26, 45],
         ...
         23 =>[25, 46, 27, 40],
         ...
         27 =>[46, 2, 28, 16, 23, 47]
         ...
    );
[download]

is the best structure for the data. In other words, is there a better choice of data structures? This is the way I have been ordering the data culled from the database, but only because of the example.

Secondly, though I am quite sure the Perl golf examples are well done, I have a hard time following them let alone coaxing out the results I would hope to get. Does anyone have or know where I can find a more fleshed out example of a shortest path/breadth first search (with "bacon number" tracking, perferably) in Perl? The samples I have been looking at are in C or Java--I don't know Java and it's been years and years since I looked at C.

Lastly, and this is the tie-in for all of the above, how would an experienced Perl programmer approach the problem?

Thanks very much in advance for any help!

porkpilot

Edit by tye, adjust links

Comment on Graph traversal--shortest path? Download Code

Replies are listed 'Best First'.
Re: Graph traversal--shortest path? by djantzen (Priest) on May 04, 2003 at 23:49 UTC
You might also try an adjacency matrix for your datastructure, which is basically a two dimensional array of node identifiers, and where there's an intersection (or arc, or edge in graph lingo) you place a marker. Graph::Base uses a variant of this as its underlying implementation, so the implementation in Graph::Traversal would be useful if you pursue this route. "The dead do not recognize context" -- Kai, Lexx	[reply]
Re: Graph traversal--shortest path? by Abigail-II (Bishop) on May 04, 2003 at 23:17 UTC
Did you look at the `Graph::BFS` module on CPAN? Abigail	[reply]
Re: Graph traversal--shortest path? by ferrency (Deacon) on May 05, 2003 at 14:48 UTC
Mastering Algorithms with Perl by Jon Orwant, Jarkko Hietaniemi and John Macdonald, published by O'Reilly has a chapter on graphs and graph traversal algorithms. As the title suggests, the book covers much of the standard "algorithms" repertoire with an emphasis on implementation in Perl. Personally, I'd ask how Any experienced programmer would approach the problem, and then figure out how to do it in Perl. When learning new algorithms and concepts, it can sometimes be easier to learn things in your native human lanugage first, and in a programming language only after you understand the basic flow of the algorithm. Alan	[reply]
Re: Graph traversal--shortest path? by jkahn (Friar) on May 05, 2003 at 19:41 UTC
A very similar conversation came up in the chatterbox a few weeks ago. Someone asked about Graph::BFS and linked to Six Degrees via Shortest Path ?. I did some research on this problem, and was able to solve a variant of the problem porkpilot describes by using simple accesses to Graph::Base methods. In the process of exploring Graph::BFS I found that its biggest problem was its poor documentation -- I couldn't figure out how it worked without reading all the code, and I didn't have the energy.	[reply]
Re: Re: Graph traversal--shortest path? by Anonymous Monk on May 06, 2003 at 04:31 UTC
Thanks very much to all for your replies! I appreciate you taking the time. Initially, I searched CPAN for "breadth first" and came up with Graph::BFS (it's at the top of the results ;) ), but until djantzen's suggestions about Graph::Traversal and adjaceny matrices, I could not see how to make it go... While I certainly agree with jkhan about the Graph modules' documentation, the dots are now connected and I have learned a great deal. Now, to go get a copy of Mastering Algorithms with Perl!	[reply]
Re: Re: Re: Graph traversal--shortest path? by porkpilot (Deacon) on May 06, 2003 at 11:59 UTC
Sorry--forgot to check I was logged in for that last post. Anyway, my script is now 100% working and I am adding bells and whistles. ++ to you all and thanks again.	[reply]