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

Subject: Re: [boost] [gsoc] Boost graph library - Hypergraphs
From: Oliver Kullmann (O.Kullmann_at_[hidden])
Date: 2009-03-27 09:58:53

Hello,

it is (obviously) correct that hypergraphs are "undirected", since
those structures mentioned below are "directed hypergraphs".

More substantially, I would strongly warn against considering "directed
hypergraphs", if the people involved are not actually doing research
in this direction (for some time, that is).
There are only a few people considering directed hypergraphs, and it is
a research topic (already that the document is from 1992 says something;
I'm actually working on the topic, on the connections between hypergraphs
and SAT (as in that paper), and thus I would be glad to see something in
this direction, but my impression is that the people involved here are not really
specialists, but just want to implement something "standard").

Hypergraphs themselves are already such complicated beasts, that I would predict
that no useful library can come out of a concept combining "directed hypergraphs"
with hypergraphs.

Oliver

On Thu, Mar 26, 2009 at 06:00:17PM -0400, Andrew Sutton wrote:
> > IIRC, hypergraphs are only "undirected". An edge is represented as a set of
> > vertices, that is, as an element of the powerset of vertices.
> >
> 
> This is incorrect.
> 
> http://www.cis.upenn.edu/~lhuang3/wpe2/papers/gallo92directed.pdf
> 
> Andrew Sutton
> andrew.n.sutton_at_[hidden]
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

-- 
Dr. Oliver Kullmann
Computer Science Department
Swansea University
Faraday Building, Singleton Park
Swansea SA2 8PP, UK
http://cs.swan.ac.uk/~csoliver/