[Boost-users] [BGL] boost::adjacency_matrix of > 12K vertices, add_vertex, remove_vertex

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