Re: grid graph for BGL

From: Chris Russell (cdr_at_[hidden])
Date: 2002-09-23 14:20:37

VC6 has limitations. Lots of uncharacterized weirdness dealing with complex
templated code and no support for partial template specialization. I haven't
messed around with the knight's tour example specifically but have been
actively building on top of BGL for a solid month now. But not with the
Microsoft compiler. I understand your concern about switching compilers. For
what's it's worth, I was in a similar position several weeks ago, and
decided that it was less risk to try the Intel 6.0 compiler on evaluation
than to try to duplicate the work and testing that has already gone into the
BGL. I'm glad I tried it. You might consider just *trying* the Intel
compiler before writing your own graph library! It took me 15 minutes to get
the Intel compiler installed and get code that was crash the MS compiler up
and running. I would think long and hard about writing your own graph
library... I tried, it got out of hand, and then I discovered the BGL...

----- Original Message -----
From: "toddgleason" <toddgleason_at_[hidden]>
Newsgroups: gmane.comp.lib.boost.user
Sent: Monday, September 23, 2002 2:55 PM
Subject: Re: grid graph for BGL

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