Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask

Re^2: Finding subgraphs induced by a set of given vertices.

by remiah (Hermit)
on Oct 04, 2012 at 07:52 UTC ( #997199=note: print w/replies, xml ) Need Help??

in reply to Re: Finding subgraphs induced by a set of given vertices.
in thread Finding subgraphs induced by a set of given vertices.

I just wanted to use Graph module.

#!/usr/bin/perl use strict; use warnings; use Graph; my @path_sets = ( [ "b", "c", "a" ], [ "a", "c", "d" ], [ "d", "e", "b +" ] ); my @vertex_sets = ( [qw[ a b c d ]], [qw[ b e d ]] ); #convert [b,c,d] to "[b-c,c-d]" sub to_pathstr { my @path_set =@_; my $pre='';my @ret=(); for (@path_set) { for( @{$_} ){ push @ret, "$pre-$_" if ($pre); $pre=$_; } } return @ret; } #if edges of path[b,c,d] shares 2 edges of complete graph[a,b,c,d] #this path go through 3 vertices of graph, maybe. for my $vertex_set (@vertex_sets){ my($g, $c); $g=new Graph(directed=>1); $g->add_vertices( @$vertex_set ); $c=$g->complete; #ex. [a,b,c,d] =>a-b,a-c,a-d,b-a,b-c,b-d,c-a,c-b, +c-d,d-a,d-b,d-c print "target vertex=$g\n"; #convert array [b,c,d] to "b-c,c-d", Graph module's edge represent +ation for my $pathstr( map{ [ to_pathstr($_)] } @path_sets ){ my $regex=join('|', map{"\Q$_\E"} @{$pathstr}); my (@matched)= "$c" =~ /($regex)/g; #check how may egdes match if( @matched >= 2 ){ print "matched path=".join(',',@$pathstr)."\n"; } } print "\n"; }
Your one with hash operation is nicer than mine.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://997199]
[erix]: choroba I believe you ;)
[1nickt]: Corion I assume you are talking about Retry? Attempt doesn;t offer callbacks and has a much simpler interface. (Also written by someone I trust...)
[perldigious]: I train for long portaging/rowing trips by carrying my kayak to the river about a half mile from my house 2-3 times a week depending on weather... but due to a lingering winter, I haven't had long to train this year.

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (10)
As of 2017-05-24 12:58 GMT
Find Nodes?
    Voting Booth?