Re: Graph Theory problem

Jeff,

I think what you are wanting is a topological sort. This places your verticies in a partial order based on which is connected to which other. I saw your post in comp.lang.perl.misc, but didn't reply because I wasn't sure my code was correct. Here is the message I was composing as a reply. Hope it helps.

If it doesn't work correctly, but you figure it out, please drop me a note to let me know where I went wrong ;-)

Thanks!

-Tom

---Cut---

Jeff,

What you are describing sounds like a topological sort. RDBMS theory is rife with applications of graph theory, so try the following and see if it does what you want. It stores each pair as an edge in a graph and the topological sort puts the verticies (Tables in this case) in a partial order based on which verticies must come before others. In this case, adding the base tables and pairs to the graph, then only taking the pairs as result, seems to give the results you desire. Also, as you can see from the last line of the test program, if there is more than one list returned by the strongly_conneced_components(), then not all vertices are reachable from each other and that can be the "undef" condition you mentioned. Also, you can use the graph module to add weighted edges to the graph to represent the weights of joining two tables (vertices) and then compute $G->MST_Kruskal() minimum spanning tree to find the lowest weighted graph which joins all the vertices.

use Graph::Undirected;
use Data::Dump;

my $G = new Graph::Undirected;

my _at_pairs = qw ( c:d b:a a:d c:e c:c f:g );

foreach $pair (_at_pairs) {
  my ($first,$second) = split(/:/,$pair);

  $G->add_path($first,$pair);
  $G->add_path($second,$pair);
  $G->add_path($first,$second);

_at_toposort = $G->toposort();

my _at_results = grep /:/, @toposort;

print Data::Dump::dump(_at_toposort) . "\n";

print Data::Dump::dump(_at_results) . "\n";

print Data::Dump::dump($G->strongly_connected_components()) ."\n";

Hope this is useful...

-Tom

"Jeff Zucker" <jeff_at_vpservices.com> wrote in message news:3BDA0844.FFE3EF11_at_vpservices.com...
> I want to be able to evaluate the table relations implied by equijoins
> in a WHERE clause, for example, given somthing like:
>
> WHERE a.foo = b.foo
> AND c.bar = d.bar
> AND d.baz = a.baz
>
> I want to be able to place the tables in order for joining (at a low
> implementation level, not in an rdbms) such that each table is joined
> with one it has an equijoin to. In the example, if I start with table
> a, I can't immediately join table c to it, but must first join table d
> to table a and then join table c to those two.
>
> From my (very) limited knowledge of graph theory, this can be stated as:
>
> Given a graph containing an arbitrary number of paths each
> of which contains exactly two vertices, return the vertices
> in an order such that each vertex (except the first) shares
> an edge with at least one vertex prior to it but not
> necessarily adjacent to it or fail if that is not possible.
>
> Is that a correct statement of the problem? Is there a name for that in
> graph theory? I know it shares some features with topological sort and
> transitive closure. Any suggestions on algorithims or resources that
> might help me out?
>
> --
> Jeff
>
Received on Sun Oct 28 2001 - 19:50:25 CET