search

wting / python-graph

Automatically exported from code.google.com/p/python-graph
Other
5 stars 3 forks source link

Hypergraphs #4

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
I was just about to roll out my own code for handling graphs when I came
upon this.

Any chance of getting hypergraph support? At least for representation? Thanks

Original issue reported on code.google.com by christian.muise on 31 Jul 2008 at 3:18

GoogleCodeExporter commented 9 years ago 
I'm sorry, but I don't think this library will ever support hypergraphs. I don't
really know much about them. How do conventional graph algorithms behave in 
hypergraphs?

I guess you could extend the graph class to represent them, depending of your 
needs.
Maybe using a combination of regular nodes and edges to represent a hyperedge?

Original comment by pmatiello on 31 Jul 2008 at 5:24

GoogleCodeExporter commented 9 years ago

Original comment by pmatiello on 31 Jul 2008 at 5:30

GoogleCodeExporter commented 9 years ago 
Basically an edge represents a set of nodes. Simple graphs are just hypergraphs 
with
every edge only containing 2 elements.

Connectivity generalizes nicely, so a number of concepts do as well (path, 
width,
components, etc). Technically they could be abstracted by introducing a new 
node to
replace each hyper edge, and have those new nodes connect to what the hyperedge
covered. This would result in a bipartite graph with the partitions being the 
nodes
in the original graph, and nodes representing hyperedges in the original graph.

Still, an implementation from the ground up would be useful when working on
algorithms. I'd be willing to pitch in if you want some help with it.

Original comment by christian.muise on 31 Jul 2008 at 6:08

GoogleCodeExporter commented 9 years ago 
Hum, I guess we can do it if you are interested to join in. Please, drop me a 
mail at
pmatiello [at] gmail [dot] com.

I'll surely need help with it as I have no experience with hypergraphs.

Work on it can start soon. I just need a couple of days to get everything right 
to
the 1.0 release.

Original comment by pmatiello on 31 Jul 2008 at 7:10

GoogleCodeExporter commented 9 years ago

Original comment by pmatiello on 1 Aug 2008 at 3:58

GoogleCodeExporter commented 9 years ago

Original comment by pmatiello on 1 Aug 2008 at 4:04

GoogleCodeExporter commented 9 years ago 
Added in svn.

Original comment by pmatiello on 18 Aug 2008 at 1:09