Boost logo

Boost :

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
> Perhaps this graph type of yours would make a nice addition to the
> 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.


> --------------------------------------------------------------------

>  Jeremy Siek                        www:
>  Ph.D. Candidate                  email: jsiek_at_l...
>  Univ. of Notre Dame         work phone: (219) 631-3906
> --------------------------------------------------------------------

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