Re: Graph Theory problem

Jeff,

> I think you're probably right. I was thrown off by the definition of
> "topological order" which requires a directed acyclic graph whereas, if
> I now understand correctly, "topological sort" does not. Have I got
> that right?

I'm not sure of the difference myself... :-) I think, though, that any graph can be topologically sorted if you disregard any
vertex already visited. That removes cycles and if the undirected graph is implemented (as I think the Graph module is) as a directed graph with 2 directed
edges for each undirected edge, we have a directed graph with a way to avoid cycles
in the sort.

>
> > my $G = new Graph::Undirected;
> >...
> > adding the
> > base tables and pairs to the graph, then only taking the pairs as
result,
> > seems to give the results you desire
>
> Yes, very clever. I think I accomplished the same thing by using a
> directed graph instead of an undirected one and creating bi-directional
> links between the tables in a pair:
>

Since the Graph module uses directed graphs to implement undirected graphs, our methods are almost identical in that respect. Also, As far as I can tell, since every "pair" vertex (a:b) in my attempt was a "terminal" vertex
(no edges leaving it except those entering it), removing them shouldn't affect the
result, so, in many ways, your model is much clearer than mine :-)

In any case, I can see no substantial difference between our methods.

> sub order_joins {
> my $joins = shift;
> my $G = new Graph::Directed;
> foreach $pair (_at_$joins) {
> my ($first,$second) = _at_$pair;
> $G->add_path( $first, $second );
> $G->add_path( $second, $first );
> }
> my(undef,$unconnected) = $G->strongly_connected_components();
> return undef if $unconnected;
> my %isa;
> return [ grep !$isa{$_}++, $G->toposort ];
> }
>
> My way seems like it is closer to what is actually being modeled, but
> should it produce the same result? (in my test cases, it seems to)
>
> Thanks much Tom!
>

Glad to help...

-Tom Received on Mon Oct 29 2001 - 18:52:20 CET