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

From: Tom Matelich (tmatelich_at_[hidden])
Date: 2002-12-23 15:35:41

> From: Tom Matelich [mailto:tmatelich_at_[hidden]]
> Sent: Sunday, December 01, 2002 9:11 PM
> 
> From: David Abrahams [mailto:dave_at_[hidden]]
> > Tom Matelich <tmatelich_at_[hidden]> writes:
> > 
> > > From: David Abrahams [mailto:dave_at_[hidden]]
> > > Sent: Sunday, December 01, 2002 5:58 AM
> > >> Tom Matelich <tmatelich_at_[hidden]> 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.
-----------------------------------------------------------------------