Re: [Boost-users] [BGL] creating a single vertex for the loop in a graph

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