
Boost : 
From: artwisz_at_[hidden]
Date: 20010324 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 outedges, 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 readonly, all I do is take all outedges 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: (219) 6313906 >  
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk