Re: [boost] Graphs: need to merge vertices

From: David Abrahams (abrahams_at_[hidden])
Date: 2001-05-14 19:13:20

Art,

I am currently trying to work out how to express a minimum degree (minimum
fill) ordering algorithm for sparse matrix factorization, in case your
problem is similar and you are interested in collaborating.

Regards,
Dave

----- Original Message -----
From: "Artur Wisz" <gagatech_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Saturday, May 05, 2001 3:56 AM
Subject: Re: [boost] Graphs: need to merge vertices

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