Re: grid graph for BGL

Hi, I'm new to using the BGL, and have been working on a problem

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

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" 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@y..., "toddgleason" wrote: that 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