CGAL users discussion list

Bernhard Kornberger wrote:
>  schrieb:
>
> > Bernhard Kornberger wrote:
> >
> > >  schrieb:
> >
> >
> > > > > Is it true that I have to implement the conversion from
> > > > > the power diagram to a graph of the power diagram by myself
> > > > > or is there already a function that I didn't find?
> > > >
> > > >
> > > >
> > > > The graph is dual to the triangulation (up to degeneracies), do you 
> > > > need to convert the triangulation to its dual that you would store 
> > > > in addition ?
> > > >
> > > >     Monique
> > >
> > >
> > >
> > > Right. I need a function like this:
> > >
> > > Regular_triangulation Tr;
> > > Tr.insert(p1);
> > > Tr.insert(p2);
> > > Tr.insert(p3);
> > > Tr.insert(p4);
> > >
> > > UndirectedGraph g=Tr.dual();
> > >
> > > ..such that I can traverse along the edges of $g afterwards.
> >
> >
> > but you can traverse edges of g by just following adjacency relations 
> > between tetrahedra in Tr, without storing g.
> >     Monique
>
>
> I need functions like breath-first search on the edges of the
> power diagram and I need to label edges as already visited or
> not. This is complicated to implement (and horrible to debug)
> if the power-diagram is not explicitly given as a graph.

I agree that you need to store the graph as some graph data structure of 
the BGL if you want to use directly some existing BGL algorithms. This 
is maybe what you mean.

But if you are implementing the traversal yourself, then the graph is 
already _explicitly_ given, since adjacency relations between cells of 
the triangulation are explicitely stored.
And you can mark facets of the triangulation by adding marking into the 
cells of the triangulation (but in fact marks will be duplicated in this 
way).
A traversal of the power graph along its edges is exactly the same as 
the traversal of the cells of the triangulation using these adjacency 
relations.
        Monique