Re: BGL: implementing internal properties - howto ?

From: artwisz_at_[hidden]
Date: 2001-03-24 16:14:04

--- In boost_at_y..., Jeremy Siek <jsiek_at_l...> wrote:
> 
> 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?
> 

Possibly yes, mainly for dense graphs, such structure is described in 
a book by Narsingh Deo that I keep around as a good reference. I 
could as well use an adjacency_list for my algorithm, and I did at 
the beginning, but then in the chase for speed I found out a bit 
vector is much faster, especially when the graph has a small number 
of vertices (when < 32 the bit vector reduces to a machine word). 
The graph is really read-only, all I do is take all out-edges of a 
vertex, rule out those that are marked and gather those that remain 
in a vector, it is all as simple as this:

  register unsigned long bits;
  int arcs[32], n_arcs = 0, i = 0;

  for(bits = OutArcs[v] & Marking; bits != 0L; bits >>= 1, ++i)
    if(bits & 0x01)
      arcs[n_arcs++] = i;

after that I have to make all possible combinations of the arcs by 
generating indexes into the arcs vector. 
(Now I am replacing the unsigned long with my hand crafted bit_vector 
class for bit vectors of any length. )
My professor comes from the era of machine code and it is hard to 
beat his goto/loop style, nevertheless I want to templatize my code 
as much as possible to gain some flexibility.

> 
> I'll try to get those docs written soon.
> 

I'm sure other people will benefit from that as well.
Thanks,

Art

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