breadth_first_searchable graph, without invalidable vertex descriptors

From: cristipp_at_[hidden]
Date: 2001-11-20 21:03:00

Hello,

I am trying to use the BCG as backbone for a ControlFlowGraph in a 
compiler project. It seems that I cannot use BCG for this task 
because of the follow contradicting (from BCG point of view) 
requirements:

1. I want to be able to breadth_first_search through my graph.
2. I want to be able to keep descriptors to vertices 'for ever' so I 
can refer a specific vertex at any given time (for removal or 
whatever other reasons).

To implement requirement 1 my adjacency_list should have its 
VertexList of type vecS.
To implement requirement 2 my adjacency_list should have its 
VertexList of type listS.

Unfortunately those are mutualy exclusive and it seems that BCG is 
unsuited for the job. But I can't really think of a decent generic 
graph library unable to support those requirements. After all, it's 
all about being able to use basic graph traversals on randomly 
mutating graphs. STL has the list which has those nice properties, 
why a graph library should be different?!

Perhaps I am missing something and I am asking for help: how should I 
declare my graph and how can I do a bfs on it?

Thanks in advance,
Cristi