Re: [boost] [gsoc] Boost graph library - Hypergraphs

Subject: Re: [boost] [gsoc] Boost graph library - Hypergraphs
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-03-27 08:40:39

>
> > 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_at_[hidden]