Edges are doubled when creating Graphs with multiedges=True

[iandrus]

sage: Graph([[3,3]],multiedges=False)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)

/Users/gvol/<ipython console> in <module>()

/Users/gvol/vcs/cur-sage/local/lib/python2.6/site-packages/sage/graphs/graph.py in __init__(self, data, pos, loops, format, boundary, weighted, implementation, sparse, vertex_labels, **kwds)
   1137                     if multiedges is False:
   1138                         # from sage.misc.prandom import choice

-> 1139                         raise ValueError("Non-multigraph input dict has multiple edges (%s,%s)"%(u, choice([v for v in data[u] if data[u].count(v) > 1])))
   1140                     if multiedges is None: multiedges = True
   1141             if multiedges is None: multiedges = False

ValueError: Non-multigraph input dict has multiple edges (3,3)

[iandrus]

The edge is being added twice which clearly causes a problem. It gets taken care of in the case that multiedges=False, or if the edges are labelled, though I'm still not sure why the edges are added twice there as well.

[ncohen]

What about just testing "v == u" immediately before "data[v].append(u)" ?

The problem with multiedges is that the problem is not well defined. What should be done when the input is :

• (1, 2), (2, 1)
• (1, 2), (1, 2)
• (1, 2, None), (1, 2, None)
• (1, 2, 'a'), (2, 1, 'a')
• (1, 2, 'a'), (2, 1, 'b')

And the same with dictionaries...

• { 1 : [2], 2 : [1] }
• { 1 : [2,2]}
• ...

Nathann

[iandrus]

Replying to ncohen:

What about just testing "v == u" immediately before "data[v].append(u)" ?

That would solve the loop case, but then there is no way to specify only one edge in a multiedge graph. Right now if you add (1,2) as an edge there will be two edges between 1 and 2. If you add (1,2),(2,1) there will be four and so on. Try the examples from the doctest in the patch and you'll see what I mean.

The problem with multiedges is that the problem is not well defined. What should be done when the input is :

• (1, 2), (2, 1)
• (1, 2), (1, 2)
• (1, 2, None), (1, 2, None)
• (1, 2, 'a'), (2, 1, 'a')
• (1, 2, 'a'), (2, 1, 'b')

I think these should all add two edges with the possible exceptions of those which have the same label i.e. (1, 2, None), (1, 2, None) and (1, 2, 'a'), (2, 1, 'a').

And the same with dictionaries...

• { 1 : [2], 2 : [1] }
• { 1 : [2,2]}
• ...

This is a little more tricky, but the second should definitely add 2 edges, and I suppose the first should add 2 as well, though it's fuzzier to me.

I agree some of this is perhaps non-intuitive and I'm open to be convinced, but I think adding twice as many edges is not good. :-)

[ncohen]

Well, I agree that this patch should be merged, but I really think that these parameters are a mess. If I were to use it myself I think I would use add_edge instead of using the constructor as it looks mostly unreliable (surprising behaviour on some inputs) :-/

The patch is good to go, though ! :-)

Nathann