Re: [boost] Graphs: need to merge vertices

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-05-15 10:37:40

Rich Lee did a minimum degree algorithm for part of his Master's degree
work, using the older GGCL interface. He's planning on updating the
code at some point, but in the mean time here's the code in its
current state.

Note that the code uses the following function to manipulate
out edge lists:

std::remove_copy_if()
container::erase(first,last)
container::empty()
container::push_back()

where "container" is the out_edge list for a vertex.

Since the BGL interface is not "container-based", the new way to do this
is a bit different:

// remove_copy_if and erase() can be replaced by:
remove_out_edge_if(vertex, predicate, graph)

// empty() can be replaced by
out_degree(vertex, graph) == 0

// push_back() can be replaced by
add_edge(vertex, vertex, graph)

Cheers,
Jeremy

On Mon, 14 May 2001, David Abrahams wrote:

abraha> Art,
abraha> 
abraha> I am currently trying to work out how to express a minimum degree (minimum
abraha> fill) ordering algorithm for sparse matrix factorization, in case your
abraha> problem is similar and you are interested in collaborating.
abraha> 
abraha> Regards,
abraha> Dave
abraha> 
abraha> ----- Original Message -----
abraha> From: "Artur Wisz" <gagatech_at_[hidden]>
abraha> To: <boost_at_[hidden]>
abraha> Sent: Saturday, May 05, 2001 3:56 AM
abraha> Subject: Re: [boost] Graphs: need to merge vertices
abraha> 
abraha> 
abraha> >
abraha> > ----- Original Message -----
abraha> > From: "Lie-Quan Lee" <llee1_at_[hidden]>
abraha> > To: "Artur Wisz" <gagatech_at_[hidden]>
abraha> > Cc: <boost_at_[hidden]>
abraha> > Sent: Thursday, May 03, 2001 5:41 PM
abraha> > Subject: Re: [boost] Graphs: need to merge vertices
abraha> >
abraha> >
abraha> > > At Thu, 3 May 2001 12:36:08 +0200,
abraha> > >
abraha> > > This is a contraction operation (to contract vertex u into vertex
abraha> > > v). You might already know that sometimes the contraction algorithm to
abraha> > > describe the solution to the problem could be implemented quite
abraha> > > differently. For example, people optimize contraction in minimum
abraha> > > degree algorithm in very different way.
abraha> > >
abraha> > > One possible way is to rebuild the out-edges/in-edges, not just modify
abraha> > > them. Namely, copy original edges of v to new ones and mark them. Then
abraha> > > when you deal with edges of u, you know whether an edge is already
abraha> > > existing in edges og v or not. You can use a predicate to copy_if all
abraha> > > edges of u's. Anyway, sorting edges to find common targets/sources
abraha> > > might not be a good idea here.
abraha> > >
abraha> >
abraha> > I am not sure if I understand you well, is this a suggestion that I just
abraha> > copy the u edges to v ? Then the graph is a multigraph, and at some point
abraha> I
abraha> > have to contract the edges anyway, because the core of the problem
abraha> involves
abraha> > tree enumeration algorithms, and the number of edges has to be kept
abraha> minimal
abraha> > because of those algorithms complexity.
abraha> >
abraha> >
abraha> >
abraha> > --
abraha> >
abraha> >
abraha> > To unsubscribe, send email to: <mailto:boost-unsubscribe_at_[hidden]>
abraha> >
abraha> >
abraha> > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
abraha> >
abraha> >
abraha> 
abraha> 
abraha> To unsubscribe, send email to: <mailto:boost-unsubscribe_at_[hidden]>
abraha>  
abraha> 
abraha> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
abraha> 
abraha> 
abraha> 

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------