Subject: [Boost-users] [BGL] boost::adjacency_matrix of > 12K vertices, add_vertex, remove_vertex
From: Hostile Fork (hostilefork_at_[hidden])
Date: 2009-03-11 19:18:27
Hello boost-users...!
I started looking at the boost graph library to use as a "known good
implementation" to compare against during tests of my own custom
graph. I hadn't thought that what I was doing might be useful for
boost, but I then read that it's feasible to build adapters to use
alternate vertex/edge stores with the BGL algorithms. So maybe my
graph could be applied somewhere??
The code I wrote is for storing dense DAGs in a packed adjacency
format. Not rocket science, but it can handle vertex counts in excess
of 65,536 on an ordinary 32-bit build using gcc 4 (boost::adjacency
matrix seemed to stop working around 12K nodes). Also, the memory is
organized so that the connectivity information for higher-numbered
vertices always follows that for lowered-numbered vertices... and you
can push or pop vertices at the end of the graph, as well as mark
vertex IDs as unused. (Neither add_vertex() nor remove_vertex() are
implemented in 1.38 for adjacency_matrix)
I've released my code under the Boost Software License, and started
documenting it in an article here:
http://hostilefork.com/nocycle/
You can browse the repository on GitHub if you like. It doesn't have
any kind of build system yet... just some source files and a test
program:
http://github.com/hostilefork/nocycle/tree/master
BoostImplementation.hpp was my crack at mirroring the functions of my
graph classes in BGL, based on what I could dig up. So I welcome
feedback or general better advice of any sort on issues that might
catch your attention.
(That includes just plain old ideas about "better C++". Do note that
there's a lot of public inheritance at the moment, which was
intentional to try and keep lines of code down during this early
phase. Also, I tried doing some fancy template tricks in things like
my Nstate class but got foiled with issues like static member
initialization. Template guru insights appreciated!)
Just putting it out there for anyone with present or future interest
in such things...
Regards,
Brian