CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in 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 (922 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 (921 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 (918 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) Powered by Gossamer Forum v.1.2.0

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