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

CGI/Perl Guide | Learning Center | Forums | Advertise | Login

Site Search: in


	MAIN INDEX	SEARCH POSTS	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 (888 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 (887 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 (884 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

Search for (options)

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives