Multigraph support

[GoogleCodeExporter]

There has been some interest in a multigraph implementation. Both digraph
and graph classes should have their respective multigraph implementation.
Hypergraphs already support it out of the box.

  More information on multigraphs can be found here:
http://en.wikipedia.org/wiki/Multigraph

Original issue reported on code.google.com by christian.muise on 23 Nov 2009 at 3:22

[GoogleCodeExporter]

Am I imagining it - didn't we have support for Multigraph a long time ago? 

A multigraph should be simple enough to implement - the most basic version is 
just a
digraph with certain validations relaxed. 

As y'all know I'm working on a new implementation of digraph (and eventually 
one of
graph as well) - do you think I should just make this support multi as an 
__init__
argument. 

It might still be worth delivering multi with the old implementation style 
since we
have a user waiting for this feature.

Original comment by salimfadhley@gmail.com on 23 Nov 2009 at 3:31

[GoogleCodeExporter]

You have a good point -- multigraph's are far too close to normal graph to 
warrant an
entirely new implementation. It's probably best that we just have a parameter 
in the
constructor defaulted to false, and only check the duplicate edges if it's not
supposed to be a multigraph.

Original comment by christian.muise on 23 Nov 2009 at 4:00

[GoogleCodeExporter]

It won't work so easily. Which edge should del_edge() delete? Maybe multigraph 
edges
should be (u, v, id) instead of (u, v)? I think new classes might be 
appropriate then.

Original comment by pmatiello on 23 Nov 2009 at 6:29

[GoogleCodeExporter]

I just remembered that over lunch...

  How about I put in the ability to make uniform hypergraphs? A uniform hypergraph
has only edges of a certain size. If you want a multi-graph, you could just 
make a
2-uniform hypergraph. Doesn't solve the multi-digraph requirement, but that can 
come
when I put in directed hypergraphs.

Original comment by christian.muise on 23 Nov 2009 at 6:46

[GoogleCodeExporter]

That sounds a lot cleaner.

Original comment by pmatiello on 23 Nov 2009 at 7:11

[GoogleCodeExporter]

I like the uniform hypergraph idea - however as you say, it's the non-uniform 
case
which poses the greatest challenge. 

At the moment G[(u,v)] gives us an edge in G, however the obvious alternative 
is that
this would return a set of zero or more edges. We could make it so that if 
G.MULTI ==
False then it validates that:

len( G[(u,v)] ) in [ 0, 1] 

and always returns:

len( G[(u,v)] )[0]

if G.MULTI == True then:

len( G[(u,v)] ) >= 0

and it returns all nodes from u to v

Original comment by salimfadhley@gmail.com on 23 Nov 2009 at 9:24

[GoogleCodeExporter]

@christian:Yep the uniform hypergraph idea is a quick hack. But it still has 
the id
prob. mentioned by pedro or so it seems to me..
.. For ex: when a user deletes an edge, all the edges between the 2 nodes will 
be
removed. and what about a weighted graph case?? we still can't assign different
weights to diff. edges btw two nodes right??

I think new classes or an update of the graph and digraph classes is called for 
in
that case.

P.S: excuse me, if i have missed something.. I am still new to the codebase.

Original comment by anand.ib...@gmail.com on 24 Nov 2009 at 8:42

[GoogleCodeExporter]

@salim: The non-uniform isn't any more problem than the uniform case. Just 
means we
don't do checks on edge size.

@anand: It's actually not a problem with hypergraphs. You add an edge as an 
arbitrary
object, and then link nodes to that edge. Mind you, it still needs a function 
to link
multiple nodes at once (so we can enforce uniformity), but that's a minor 
thing. This
does also mean that your edge can't be the object (u,v) -- it would need to be
something else that's distinct. Including the weight in there, or some id, 
would do
the trick.

Original comment by christian.muise on 24 Nov 2009 at 12:50

[GoogleCodeExporter]

@christian: nope...... what i meant to point out was that pedro's objection 
"Which
edge should del_edge() delete? Maybe multigraph edges
should be (u, v, id) instead of (u, v)?" 
is still valid.... but of course, uniform hypergraph is more generic.

Also, i checked out networkx source, they use a dict for the unique id...

Original comment by anand.ib...@gmail.com on 26 Nov 2009 at 3:46

[GoogleCodeExporter]

I think you're missing the generality of the hypergraph implementation. Edges 
are
arbitrary objects -- not necessarily tuples of nodes. You can make multigraphs 
by
just treating your edge objects as distinct things (edge id, or whatever). For
example, if you wanted a graph with two nodes, and two edges between them:

# Create the graph
h = hypergraph()

# Add the node / edge objects
h.add_nodes([1,2])
h.add_edges(['a','b'])

# Link up the edges (ie. create the edge connections)
h.link(1,'a')
h.link(2,'a')

h.link(1,'b')
h.link(2,'b')

# h is now a graph with two nodes (1 and 2) and two edges between them ('a' and 
'b')

# Delete an edge
h.del_edge('a')

Original comment by christian.muise on 26 Nov 2009 at 3:58

[GoogleCodeExporter]

@christian: you are right..... though it still needs a del_edge function.. 
@all:i went ahead and did the changes. am attaching the patch file with this.. 
can
somebody review the changes, while i run tests module?? 
oh and btw i added the ability to link any no. of hyperedges, since it seemed 
like a
easy feature to add...
will update once the tests are done..

Original comment by anand.ib...@gmail.com on 28 Nov 2009 at 12:45

Attachments:

• issue59

[GoogleCodeExporter]

@anand: Odd -- never realized it was missing a del_edge function. A single patch
isn't the best approach however. I'd suggest opening a separate issue for:
- enforcing uniformity in hypergraphs
- adding a del_edge function
- function for multiple linkages

  We can discuss each one separately, but none will hit the code-base til Pedro get's
the next release out the door.

Original comment by christian.muise on 28 Nov 2009 at 2:30

[GoogleCodeExporter]

I think del_edge can get into 1.6.3: I'm late with Issue 44 and it seems
uncontroversial. Is this ok with you, Christian? I'll follow your decision on 
this.

@Anand: Would you please fill a separate issue and patch for del_edge?

@Christian: I'll accept this issue and set you as the owner. We'll build it atop
hypergraphs, so you're the natural choice here. :)

Original comment by pmatiello on 28 Nov 2009 at 3:02

• Changed state: Accepted
• Added labels: Milestone-1.8.0

[GoogleCodeExporter]

@christian: wouldn't the function for multiple linkages a part of enforcing 
uniformity?? 
oh i think since the unlink was there it was not noticed..... i happened to 
notice
only when i printed it, while running your example above.
@pedro: done

Original comment by anand.ib...@gmail.com on 28 Nov 2009 at 1:13

[GoogleCodeExporter]

Original comment by pmatiello on 20 Mar 2010 at 10:22

• Removed labels: Milestone-1.8.0

[GoogleCodeExporter]

Hi, if I understand it correctly,

Does it mean that now multigraph is indirectly implemented by hypergraph?
But what if want to use directed multigraph.

I found that the created hypergraph has already DIRECTED=true. But the result 
of applying topological_sorting to it is not correct.

Can anyone shed some light on this issue?
Thanks in advance!

Original comment by w...@qiu.es on 23 May 2013 at 11:49