Boost logo

Boost :

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-03-24 13:45:33

On Sat, 24 Mar 2001 artwisz_at_[hidden] wrote:
artwis> > Let me guess, is it all the stuff about the property_map traits
artwis> class (and
artwis> > the mess of classes like vertex_property_selector, etc in
artwis> > detail/adjacency_list.hpp) that is confusing you? It sure confuses
artwis> me ;)
artwis> Exactly.
artwis> >
artwis> > The main reason the property_map traits stuff is so complicated is
artwis> that
artwis> > the BGL components use workarounds instead of partial
artwis> specialization. If I
artwis> > had used partial spec. in the implementation of adjacency_list,
artwis> then the
artwis> > property_map traits stuff would have been MUCH simpler. Does your
artwis> > compiler support partial spec?
artwis> I am using MSVC++ for the sake of its cool optimizer, but perhaps
artwis> I'll try the newest gcc release.

Ok, so MSVC++ does not have partial spec., while g++ does.

I'll write up docs for both with and without partial... it may
take a couple days.

artwis> > The second complicated part about the adjacency_list implementation
artwis> > is that it supports attaching multiple arbitrary properties to
artwis> > the graph. Do you want your graph class to also have this capability
artwis> > or do you just need to provide access to a couple specific
artwis> > internal properties?
artwis> I need to have a vertex property that is a template parameter of my
artwis> graph. Lately I plan on adding some edge properties too.
artwis> Actually what I need is an adjacency bit matrix representation, where
artwis> each out-edge corresponds to one bit of a bit vector. I have already
artwis> implemented my algorithm in terms of this representation and I don't
artwis> want to loose efficiency, now I just want to do it "the BGL way". The
artwis> efficiency gain is where I operate on the whole set of out-edges, ex.
artwis> I store vertex colors as bits and excluding colored out-edges boils
artwis> down to bit masking. Because of that I don't want to use iterators
artwis> (maybe later for a more generalized, less efficient case), and I
artwis> thought of keeping the bit vector associated with each vertex as a
artwis> vertex property.

Sounds like a useful kind of graph structure... I've been looking
at bit vector stuff for out_edges for use in an isomorphism algorithm.
Perhaps this graph type of yours would make a nice addition to the BGL?

Other than the excluding color out-edges, what other operations do you do
on your graph?

artwis> One shortcut I thought of was simply to derive my graph class from a
artwis> specialized adjacency_list and overload all operations tunneling most
artwis> of them to the base class, but still I need to partially specialize
artwis> the property_map, so that I can write
artwis> property_map<MyGraphType, vertex_bits_t>::type bits
artwis> = get(vertex_bits, g);
artwis> instead of
artwis> property_map<MyGraphType::Base, vertex_bits_t>::type bits
artwis> = get(vertex_bits, g);
artwis> I guess it would not be difficult with gcc but don't really have a
artwis> clue how to do it in MSVC++.
artwis> Any suggestions would be *very* welcome.

I'll try to get those docs written soon.


 Jeremy Siek www:
 Ph.D. Candidate email: jsiek_at_[hidden]
 Univ. of Notre Dame work phone: (219) 631-3906

Boost list run by bdawes at, gregod at, cpdaniel at, john at