Re: [boost] Re: BGL: implementing internal properties - howto ?

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> 
artwis> Exactly.
artwis> 
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> 
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> 
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> 
artwis>    property_map<MyGraphType, vertex_bits_t>::type bits
artwis>       = get(vertex_bits, g);
artwis> 
artwis> instead of
artwis> 
artwis>    property_map<MyGraphType::Base, vertex_bits_t>::type bits
artwis>       = get(vertex_bits, g);
artwis> 
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.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------