On 1/9/08, vijay <[EMAIL PROTECTED]> wrote:
> I am using Graph::Directed module but there does not seem to be a way
> to test if one graph is a subgraph of another.
If you don't care about isomorphism it is fairly easy. Let's say we have a
graph
a-b-c-d
|
e-f
|
g
and we want to know if
e-f
|
g
is a subgraph of it, then all you have to do is make sure all of the vertices
in the subgraph are in the graph and all of edges in the subgraph are in the
graph:
#this could be much more efficient
sub is_subgraph {
my ($g, $sg) = @_;
my @v = $g->vertices;
for my $v ($sg->vertices) {
return 0 unless grep { $_ eq $v } @v;
}
my @e = $g->edges;
for my $e ($sg->edges) {
return 0 unless grep { $_ eq $g } @g;
}
return 1;
}
If you care about isomorphism, that is this graph
x-y
|
z
should also be considered a subgraph, it gets a lot harder. It is also more
difficult if you need the subgraph to be able to reach all of the vertices the
corresponding subgraph in the original graph can reach. For instance, the
following graph is considered a subgraph of the first graph
a
b
c
Since there are no edges to compare, the fact that the vertices are in the
first graph is enough to say that this graph is a subset of the first one. A
less efficient method would be to walk the graph comparing all vertices that
can be reached from that vertex with the candidate subgraph. If you find an
exact match you have a subgraph.
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
http://learn.perl.org/
