Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling

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]
[Corion]: marioroy: Heh, glad that you get enjoyment out of it! It's mainly a valve for me to vent some of the pressure ;-D
[Corion]: Oooh - note is interesting, at least in the sense that I will steal its command line interface for my own note taking app ;-D

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (6)
As of 2017-08-16 14:06 GMT
Find Nodes?
    Voting Booth?
    Who is your favorite scientist and why?

    Results (266 votes). Check out past polls.