grid graph for BGL

From: toddgleason (toddgleason_at_[hidden])
Date: 2002-09-18 20:31:43

Hi, I'm new to using the BGL, and have been working on a problem that 
uses a directed acyclic grid graph and subgraphs, and computes 
shortest paths.

In my problem, the subgraphs are determined by paths from one end to 
the other.  It is possible to determine in constant time whether a 
grid point or edge is within the graph, by looking at the paths 
bounding the subgraph.

I started out using adjacency_list and filtered_graph to limit the 
graph, but this is not optimal because adjacency_list iterates over 
all vertices in the original graph to filter them.  Ideally I'd like 
to use the indices from the master graph but be able to dynamically 
iterate over them according to the computations the code performs to 
limit the scope of the graphs.  However, I'm not sure if anyone has 
done anything like this, and I'm a little frightened of trying to 
write my own graph class into the BGL structure.  (I've never dealt 
with such heavily templated code before, and am even more confused 
than when looking at the STL!)

Are there any pointers anyone can give me that would make it easier 
to construct such a class?

Another option I'll throw out:  Might it be simpler to hack one of 
the shortest paths algorithms to do a better job of restricting 
itself based on the dynamic subgraph filtering?  I considered this 
(the code looks shorter and simpler), but it'd be cleaner to have a 
new graph class.

Thanks to any who can help me.  Also, I'm using VC++ 6 so all the 
problems with partial template specialization (which I don't even 
understand) apply to me.

--Todd C. Gleason