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

Anyone here have any strong experience with Graph and its methods? I've read the docs and they are sparse. The distribution is amazing, but as is obvious from some of my recent posts, I haven't been making very strong use of it.

Are there any good tutorials or pages or mailing lists or anything I can go to in order to better understand how to use this lifesaver. Whether it's using the module or using graph theory in general or whatever.

------
We are the carpenters and bricklayers of the Information Age.

Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

Replies are listed 'Best First'.
Re: Knowledge of the Graph distribution
by kappa (Chaplain) on Apr 02, 2004 at 13:23 UTC
    Graph is cool. I've made use of it almost instantly, no learning curve or something. We had Graph Theory course in the university, though. So I recommend reading some basics graph theory tutorials and off you go :)
[reply]
Re: Knowledge of the Graph distribution
by Joost (Canon) on Apr 02, 2004 at 13:37 UTC
[reply]
Re: Knowledge of the Graph distribution
by kvale (Monsignor) on Apr 02, 2004 at 17:30 UTC
    I would also recommend the Wolf book for the Graph module. With respect to your question Reducing HoH to AoA yesterday, here is a program to compute strongly connected components: 
    use Graph::Directed;

my $g = Graph::Directed->new();

# Each pair is a pair of vertices qw|a b| indicating 
# a directed edge from a to b
# graph: lineitem <-> invioce <-> claim <-> insurer
$g->add_edges( qw| lineitem invoice  invoice lineitem
                   invoice claim  insurer claim
                   claim invoice  claim insurer|);

print "Strongly connected components: ", $g->strongly_connected_graph,
+ "\n";

    [download]
    Now when I run this, I get 
    Strongly connected components:

    [download]
    Which doesn't seem right; the graph above clearly has one strongly connected component. If I take out the invoice->claim edge, I get 
    Strongly connected components: insurer+claim-lineitem+invoice

    [download]
    which makes sense to me. Adding edges cannot reduce the connectivity of a graph, so Graph looks buggy to me.

    Do others concur?

    -Mark

[reply]
[d/l]
[select]
      I'm also running into an infinite loop when I have a graph where not all the vertices are connected and I try to use SSSP_Dijkstra() on a vertex without edges.

      ------
      We are the carpenters and bricklayers of the Information Age.

      Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

[reply]
      It looks to me like the Graph module has a bug in it. Since all the vertices in your example graph are strongly connected, a graph with a single vertex and no edges should be returned. However, it looks like the graph computed by strongly_connected_graph() is created by adding edges. There needs to be some logic added to copy the single vertex if there are no edges.

      The strongly_connected_components() method does return all four vertices.

      I have sent Jarkko a suggestion for how to fix this, msg me if you need a copy.

      Update:
      Keep asking, and you will receive.
      Jarkko has just released Graph-0.20102, a bug-fix release, which includes the fix mentioned above and others.

      Update #2:
      Jarkko notes that he does not claim that the module is bug-free as of now.

      It should work perfectly the first time! - toma
[reply]

Back to Seekers of Perl Wisdom