CGI/Perl Guide | Learning Center | Forums | Advertise | Login Site Search: in Perl Guide PerlGuru Forums Learning Ctr
 MAIN INDEX SEARCHPOSTS WHO'S ONLINE LOG IN

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

zing
Novice

Oct 3, 2012, 9:13 AM

Post #1 of 3 (2809 views)
 Finding subgraphs induced by a set of given vertices. Can't Post
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

Post #2 of 3 (2808 views)
 Re: [zing] Finding subgraphs induced by a set of given vertices. [In reply to] Can't Post
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

Post #3 of 3 (2805 views)
 Re: [Laurent_R] Finding subgraphs induced by a set of given vertices. [In reply to] Can't Post
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`

 Announcements     PerlGuru Announcements Perl Programming Help     Frequently Asked Questions     Beginner     Intermediate     Advanced     Regular Expressions     mod_perl     DBI     Win32 Programming Help Fun With Perl     Perl Quizzes - Learn Perl the Fun Way     Perl Golf     Perl Poetry Need a Custom or Prewritten Perl Program?     I need a program that...     I Need a Programmer for Freelance Work     Throw Down The Gauntlet General Discussions     General Questions     Feedback     Tutorial/Article Suggestions for The Learning Cent     Internet Security Other Programming Languages     Javascript     PHP

 Search this forum this category all forums for All words Any words Whole Phrase (options) Powered by Gossamer Forum v.1.2.0