The ideal solution to use both because: for some algorithms will be easier to use through the incidence matrix (but as you said, resizing the matrix for every operation is an expensive operation of O(V*E) ). For some other algorithms, it is easier to use the bipartite approach. We should leave to the user who adds an algorithm to BGL to choose whichever suits his needs the most. Defining hypergraph concepts again, can be done using the best of both.
This is the same argument for supporting adjacency lists and matrices in the graph library. Some algorithms work better with matrices. The graph concepts are really derived from observations about the structure and similar use of different implementations. You basically have to ask yourself, "How are the similar? How are they different? How can we make dissimilar structures appear similar?" This may not be worth attempting until late in the summer, and may not even be possible without both implementations. Maybe. As an afterthought, and being frank, I'm not very sure as of now as to how
the exact implementation will be done using the BGL and this is appearing to be a tough (but tremendously exciting) problem! I'm looking at the other proposed project idea on *incidence matrices* and will post on it soon.
That's probably a better place to start. Good luck. Andrew Sutton andrew.n.sutton@gmail.com