Home: Perl Programming Help: Beginner:
Finding subgraphs induced by a set of given vertices.

zing
Novice

Oct 3, 2012, 9:13 AM

Views: 2823
 Finding subgraphs induced by a set of given vertices.
Hi guys, I have this code which takes in input in the form of triplets of vertices(see DATA)
 Code
`use strict; use warnings; use Data::Dumper;  my @S; while (<DATA>) {     push @S, [split]; } print "-----TRIPLETS-------\n"; print Dumper \@S;  __DATA__ b c a a c d d e b`

What Im stuck with is this :: Suppose I have these points=(a,b,c,d);

Then I want to find the set of triplets induced by these 4 vertices.
For example for above four points the induced triplets should be:
 Code
`b c a  a c d`

Whereas for vertices=(d,e,a) there isn't any triplet in the data.
Similarly for vertices=(b,e,d) there is a triplet (d e b) in the data(the last one).

Laurent_R
Veteran / Moderator

Oct 3, 2012, 9:33 AM

Views: 2822
 Re: [zing] Finding subgraphs induced by a set of given vertices.
Yes, and what are you trying to do exactly?

Are you looking for all the triplets i your DATA section that are a subset of quadruplet (a, b, c, d)?

Are your triplets commutative, i.e. is, for example, (a b c) the same thing as (c b a), (b a c), etc. If such is the case, you should probably look for some form of "canonical" form. For example, the nodes of a triplet (or any other set) should be presented in alphabetical order. In other words, the triplets in you data section should then be: a b c, a c d and b d e.

This would make your searches far easier, I think.

Then, you should probably take a look at the List::Util module, which is likely to contain most of the subroutines you might be looking for. Other modules of possible interest for you are Scalar::Util and List::MoreUtils.

zing
Novice

Oct 3, 2012, 10:25 AM

Views: 2819
 Re: [Laurent_R] Finding subgraphs induced by a set of given vertices.
Yes they are commutative. The code below does it partially. Is it efficient ??
 Code
`#!/usr/bin/perl use Data::Dumper; use strict; use warnings;   my @S = do {     open my(\$data), '<', \q{b c a a c d d e b};     map { [ split ] } readline \$data; };  print Dumper \@S;  for my \$QT ( [qw[ a b c d ]], [qw[ b e d ]] ){     print Dumper \$QT;     for my \$triplet ( @S ){         my %Pie;         undef @Pie{@\$QT};         delete @Pie{ @\$triplet }; #~         warn scalar keys %Pie ; #~         warn scalar @\$QT;         print "@\$triplet\n" if keys(%Pie) <= ( @\$QT - @\$triplet ) ;     } }`
-------OUTPUT-----------
 Code
`\$VAR1 = [           [             'b',             'c',             'a'           ],           [             'a',             'c',             'd'           ],           [             'd',             'e',             'b'           ]         ]; \$VAR1 = [           'a',           'b',           'c',           'd'         ]; b c a a c d \$VAR1 = [           'b',           'e',           'd'         ]; d e b`