Re: 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
[download]

Comment on Re: Building Networks of Matches Download Code

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` [download] 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	[reply] [d/l] [select]
Re^3: Building Networks of Matches by bowsie (Initiate) on Jan 11, 2005 at 20:20 UTC
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` [download] 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	[reply] [d/l]

I hate meetings.