#15278: Hash and equality for graphs
-------------------------------------+-------------------------------------
Reporter: SimonKing | Owner:
Type: defect | Status: needs_work
Priority: major | Milestone: sage-6.1
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: Simon King | Reviewers: Nathann Cohen
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/SimonKing/ticket/15278 | fcf9e3018d5e87f49e1f3f3d68ad4cc49382c0b9
Dependencies: #12601, #15491 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by SimonKing):
Meanwhile I see at what point the copy is taken: It is
{{{
#!python
def transitive_reduction(self):
r"""
Returns a transitive reduction of a graph. The original graph is
not modified.
A transitive reduction H of G has a path from x to y if and only
if
there was a path from x to y in G. Deleting any edge of H destroys
this property. A transitive reduction is not unique in general. A
transitive reduction has the same transitive closure as the
original graph.
A transitive reduction of a complete graph is a tree. A transitive
reduction of a tree is itself.
EXAMPLES::
sage: g=graphs.PathGraph(4)
sage: g.transitive_reduction()==g
True
sage: g=graphs.CompleteGraph(5)
sage: edges = g.transitive_reduction().edges(); len(edges)
4
sage: g=DiGraph({0:[1,2], 1:[2,3,4,5], 2:[4,5]})
sage: g.transitive_reduction().size()
5
"""
from copy import copy
from sage.rings.infinity import Infinity
G = copy(self)
for e in self.edge_iterator():
# Try deleting the edge, see if we still have a path
# between the vertices.
G.delete_edge(e)
if G.distance(e[0],e[1])==Infinity:
# oops, we shouldn't have deleted it
G.add_edge(e)
return G
}}}
Hence, it seems that we indeed want a mutable copy here. And perhaps it
isn't ''their'' mess after all, as this method is broken for all truely
immutable graphs.
--
Ticket URL: <http://trac.sagemath.org/ticket/15278#comment:75>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
