Re: grid graph for BGL

From: toddgleason (toddgleason_at_[hidden])
Date: 2002-09-23 13:55:49

I just thought I'd throw out my question one more time before 
completely giving up on BGL.  I've looked at the Knight's Tour and 
LEDA graph adaptors as described in the book (which I rush-ordered 
and read through), but I'm still at a loss to discern whether it is 
possible to do this in VC++ 6.  I still have a poor grasp of partial 
template specialization, and looking through these examples hasn't 
helped me.  I don't want to implement a lot of confusing templated 
code only to find out that it will never compile.  I cannot switch 
compilers, because that would add another program to validate, for 
what is really a one-off problem.

Essentially I want the simplest way to specify, from a vertex 
descriptor, the adjacent vertices (though I guess in BGL this must be 
specified as out_edges as well for shortest paths algorithms).  I 
also need to be able to easily define an iterator over edges.  I 
therefore want a simple structure with knowledge of the grid graph 
and a bit of edge state, that can be wrapped in an iterator.

This seems like it should be such a simple task, and yet, when I look 
in the code I get mired in details.  The BGL code is largely 
uncommented so I don't really know what's going on looking at it.  Am 
I better off just writing this myself?  It seems a shame.

--Todd C. Gleason

--- In Boost-Users_at_y..., "toddgleason" <toddgleason_at_y...> wrote:
> 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