Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL] creating a single vertex for the loop in a graph
From: Jens Müller (blog_at_[hidden])
Date: 2012-01-12 13:46:43

Am 12.01.2012 16:09, schrieb srinivas boppu:
> Hello All,
> I am looking for the following in boost graph.
> I have a graph in which I am able to find out the loops.

Cycles. "loop" is easily misunderstood as self-loop, i.e., an edge (v,v).

> Now, I wanted to replace the whole loop with a single vertex in the
> same Graph.
> Is that possible ? if it is, can you suggest me how do it.

What happens with your edges? They get collapsed?

So {v1,...,vn} becomes v, each (u,vi) becomes (u,v) and each (vi,u)
becomes (v,u)?

Easy enough, I'd say. Add v, iterate over all vi and their edges, add
the respective (u,v) or (v,u) edges.

Note that deleting vertices is difficult with an adjacency list storing
vertices in a vector (vecS), because deleting a vertex invalidates _all_
vertex and edge descriptors/iterators of the graph. With listS or setS,
however, it's easy: Just iterate over your list of vertices in the cycle
and delete them.

> Alternate way could be, I copy the loop

To what?

> and make another graph

Looking how?

> and add
> this whole graph
> as a "vertex" in initial graph.

"Initial" graph?

> Can I add a "graph" as a vertex to existing graph?

That's known as hierarchical graphs. I don't think there is a dedicated
type in the BGL.

But I wonder whether this (one graph per vertex) is really the proper
way to represent a hierarchical graph.

 -- Jens

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at