Re: [boost] Graphs: need to merge vertices

From: Artur Wisz (gagatech_at_[hidden])
Date: 2001-05-05 02:56:46

----- 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.



--