RE: [Boost-Users] Re: Extended use of BGL File Dependency Example

From: Tom Matelich [mailto:tmatelich@zetec.com] Sent: Sunday, December 01, 2002 9:11 PM

From: David Abrahams [mailto:dave@boost-consulting.com]

...

Tom Matelich writes:

...

From: David Abrahams [mailto:dave@boost-consulting.com] Sent: Sunday, December 01, 2002 5:58 AM

...

Tom Matelich writes:

...

trying to make my graphviz representation look nicer and I was wondering if there is an algorithm already for simplifying:

-----B\ A--< \ --------C D----------/

to:

A---B---C D------/

This eliminated the A-C edge.

Thanks for considering my problem.

Maybe you want a minimum spanning tree, where the weight of each edge in the tree is determined by the distance between its vertices in some topological sort?

That seems to solve the cases shown above pretty nicely.

I had looked at the minimum spanning tree docs a bit, I thought it looked pretty good. The docs say undirected graph though. I'm

currently using a directed graph. I suppose I could create a separate graph. Oh, I see, create an undirected graph with weights as you said, and use the minimum spanning algorithm to choose the useful edges. I like it, hope it works.

Well, I finally got back to this and it almost worked. Things look a lot nicer, the only problem is some edges were lost that I would want to keep. I'll give a list of edges rather than try to draw ascii graphs. So I start out with edges: [1,0], [2,0], [3,0], [4,0], [3,1], [4,2], [4,3] Ideally I want this reduced to: [1,0], [2,0], [3,1], [4,2], [4,3] What I'm getting is: [1,0], [3,1], [4,2], [4,3] Of course my graph is bigger and I have a lot more dead ends than just at 2. 0 is a place holder I have for a "Valid System", so every thing should hit that eventually. I implemented this in the following manner: [create typedefs for undirected graph to be minimized] [get the order from the topological sort in a vector] [create the undirected graph with all edges from dependency graph, assigning weight to be the distance between source and target in the topological sort] [create a vector of edges called spanning_tree] [call kruskal_minimum_spanning_tree(undirected_graph, std::back_inserter(spanning_tree)); ] [then I recreated the directed graph out of the edges in spanning_tree, so I could have my arrows in graphviz] I'm going to try using prim_minimum_spanning_tree, I assume I should expect the same results, but I'll see. Thanks for any advice, Tom ----------------------------------------------------------------------- DISCLAIMER: Information contained in this message and/or attachment(s) may contain confidential information of Zetec, Inc. If you have received this transmission in error, please notify the sender by return email. -----------------------------------------------------------------------