Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

Re: Building Networks of Matches

by simonm (Vicar)
on Dec 23, 2004 at 17:36 UTC ( [id://417165]=note: print w/replies, xml ) Need Help??


in reply to Building Networks of Matches

I've been looking at the Graph code lately and it occurred to me that this was easily expressed in that form, but I fear that this will not be fast enough for your purposes:
#!/usr/bin/perl -w use strict; use Graph::Undirected; my $graph = Graph::Undirected->new(); my @data = map { [ grep defined, split /\s+/ ] } <DATA>; foreach my $line ( 1 .. scalar @data ) { $graph->add_edges( map { $line => $_ } @{ $data[ $line - 1 ] } ) } my @sets = $graph->strongly_connected_components; for (@sets) { printf "{ %s }\n", join ' ', sort { $a cmp $b } @$_; } __END__ a b c d e f b g h i j k l m f

Replies are listed 'Best First'.
Re^2: Building Networks of Matches
by osunderdog (Deacon) on Dec 23, 2004 at 17:50 UTC

    I hate meetings.

    Slight variation that I was working on before having to attend a meeting. Use add_path rather than add_edges

    use strict; use Graph; use Graph::Undirected; my $ud = Graph::Undirected->new(); while(<DATA>) { my @items = split(' '); if(@items <= 1) { $ud->add_vertex(@items); } else { $ud->add_path(@items); } } foreach my $connectedSet ($ud->strongly_connected_components) { print "Connected Nodes: " . join(',', @$connectedSet) . "\n"; } __DATA__ a b c d e f b g h i j k l m f z

    Update: Modified code based on feedback. Have to handle the case where there is only one letter on a line. UNFORTUNATELY this cause it to lock on strongly_connected_components call.


    "Look, Shiny Things!" is not a better business strategy than compatibility and reuse.


    OSUnderdog
      This doesn't work. :(

      First, you cannot use strongly_connected_components in an undirected graph. However, simply substituting connected_components takes care of that, so that's not a big deal.

      However, it only works when there is more than one element on a line. If my data looked like this:

      __DATA__ a b c d e f b g h i j k l m f z
      it would not deal with the line with just the "z" on it - it would ignore that line and give me the same results as the data-set without the "z" instead of telling me there's a set of 1-ement containing z that is unique to the list.

      I will go read more about Graph and see if there's a solution to this problem. Thank you anyway

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://417165]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others avoiding work at the Monastery: (6)
As of 2024-03-29 05:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found