Re: [sage-devel] Re: Attributes onto edges in sage graphs
Il 20/06/2010 23:52, Michele Comignano ha scritto:
The check_edge_label is where sage checks for equals labels in
http://hg.sagemath.org/sage-main/file/2cffe66bd642/sage/graphs/base/sparse_graph.pyx#l1
1318 <#l1318> if edge_labels[l_int] == l:
My opinion about that: I would remove rows 1408 and 1409. Or, may be
better replace row 1318 with:
if id(edge_labels[l_int]) == id(l):
I applyed that patch to my sage installation and my previous sample got
working fine:
{'a': 10, 'b': 20}
label dictionary id: 0xafd4c64
{'a': 10, 'b': 25}
label dictionary id: 0xafd48ac
{'a': 10, 'b': 20}
label dictionary id: 0xafd4934
{'a': 10, 'b': 20, 'sometimes_duplicate': 0}
label dictionary id: 0xafd4c64
{'a': 10, 'b': 25, 'sometimes_duplicate': 1}
label dictionary id: 0xafd48ac
{'a': 10, 'b': 20, 'sometimes_duplicate': 2}
label dictionary id: 0xafd4934
{'a': 10, 'b': 20, 'sometimes_duplicate': 0}
{'a': 10, 'b': 25, 'sometimes_duplicate': 1}
{'a': 10, 'b': 20, 'sometimes_duplicate': 2}
Someone should take a look to dense graphs backend to see if behaves as
the sparse one before my patch.
Attached is the patch produced through mercurial.
I have no time di add to the trac now.
Bye :)
--
Michele Comignano
Computer Science student
University of Pisa, Italy
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
# HG changeset patch
# User Michele Comignano
# Date 1277112801 -7200
# Node ID 6594a8f8148ae4deb94a3e68491a9f0e582d31e1
# Parent 2cffe66bd64266c6a64d31ca37ad81d8d5390af8
Modified check_edge_label to consider equals the same objects and not objects with the same contents.
diff -r 2cffe66bd642 -r 6594a8f8148a sage/graphs/base/sparse_graph.pyx
--- a/sage/graphs/base/sparse_graph.pyx Fri Jun 04 12:50:55 2010 -0700
+++ b/sage/graphs/base/sparse_graph.pyx Mon Jun 21 11:33:21 2010 +0200
@@ -1315,7 +1315,7 @@
"""
cdef int l_int, max = 0
for l_int in edge_labels:
-if edge_labels[l_int] == l:
+if id(edge_labels[l_int]) == id(l):
return l_int
if max < l_int:
max = l_int
Re: [sage-devel] Re: Attributes onto edges in sage graphs
Il 21/06/2010 09:14, Nathann Cohen ha scritto: It is ! O_O And I have to admit it would have required some time before I began to suspect such a thing may have come from the graph backends... Good work !!! :) I am adding Robert Miller in Cc as he will know better than anyone else which parts of the library would need to be updated to fix this. I think a small fix (mantaining different objects event if they are equals in contents) is a rapid solution, but a refactoring (mantaining two nx attributes, one for labels and one for sage attributes dicts with different archiving policyes) may be a better one. -- Michele Comignano Computer Science student University of Pisa, Italy -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: Attributes onto edges in sage graphs
Hello !!! > Hope that's useful :) It is ! O_O And I have to admit it would have required some time before I began to suspect such a thing may have come from the graph backends... Good work !!! I am adding Robert Miller in Cc as he will know better than anyone else which parts of the library would need to be updated to fix this. By the way, Michele, have you ever sent code to Sage ? I'd be glad to see new graph theoreticians in the team ! :-) Nathann -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: Attributes onto edges in sage graphs
Il 20/06/2010 23:25, Michele Comignano ha scritto: But since python implementation doesn't reveal an error, it must be in a backend implementation in some of the backends in http://hg.sagemath.org/sage-main/file/2cffe66bd642/sage/graphs/base that are extensions written in cython and it's too late for me to analyze. Ok, i've yelded and examined http://hg.sagemath.org/sage-main/file/2cffe66bd642/sage/graphs/base/sparse_graph.pyx#l1 1408 <#l1408> cdef int l_int = check_edge_label(l, self.edge_labels) 1409 <#l1409> if l_int not in self.edge_labels: 1410 <#l1410> self.edge_labels[l_int] = l That looks like an optimization to avoid representing in memory more than one time the same label. That should be good for strings since each string is a new string, but when (as in my example) one try to modify a component of the object (list, dict, ...) referred by the label that's not good and gives the 'strange behavior'. The check_edge_label is where sage checks for equals labels in http://hg.sagemath.org/sage-main/file/2cffe66bd642/sage/graphs/base/sparse_graph.pyx#l1 1318 <#l1318> if edge_labels[l_int] == l: My opinion about that: I would remove rows 1408 and 1409. Or, may be better replace row 1318 with: if id(edge_labels[l_int]) == id(l): so that the backends avoided to refer two times the same (really the same) object. I think is better avoid a loop onto the whole labels dictionary each time we add an edge to the graph. The gain from having no duplicated objects in memory I think is less than problems caused by cases such as in my initial example. I haven't looked at sparse graphs backend. Anyway I think that separating labels (naturally used for identification and representation) and attributes (naturally used for edge qualitative and quantitative attributes) might be a good way. Hope that's useful :) -- Michele Comignano Computer Science student University of Pisa, Italy -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: Attributes onto edges in sage graphs
Il 20/06/2010 22:26, Nathann Cohen ha scritto:
Could you please give us an example of such a "strange behavior" when
using dictionaries as labels in Sage ?
Try the attached file. It creates a graph, then adds nodes and edges.
After, assigns a new element (a growing integer) to the label dictionary
of each edge.
Edges with the same initial attributes values have same integer
attribute value in the final print. That is the strange behavior.
I noticed (see the output) that labels with same initial values have the
same object id after adding the edges (but not before). That explains
why I get duplicate values. But: why labels with same values have same id?
My output (sage 4.4.3 self compiled on debian squeeze) is:
{'a': 10, 'b': 20}
label dictionary id: 0xb875c64
{'a': 10, 'b': 25}
label dictionary id: 0xb8758ac
{'a': 10, 'b': 20}
label dictionary id: 0xb875934
{'a': 10, 'b': 20, 'sometimes_duplicate': 0}
label dictionary id: 0xb875c64
{'a': 10, 'b': 25, 'sometimes_duplicate': 1}
label dictionary id: 0xb8758ac
{'a': 10, 'b': 20, 'sometimes_duplicate': 2}
label dictionary id: 0xb875c64
{'a': 10, 'b': 20, 'sometimes_duplicate': 2}
{'a': 10, 'b': 25, 'sometimes_duplicate': 1}
{'a': 10, 'b': 20, 'sometimes_duplicate': 2}
http://hg.sagemath.org/sage-main/file/2cffe66bd642/sage/graphs/generic_graph.py
for what i've understood has the implementation of add_edge (row 5026),
but that doesn't reveal anything.
But since python implementation doesn't reveal an error, it must be in a
backend implementation in some of the backends in
http://hg.sagemath.org/sage-main/file/2cffe66bd642/sage/graphs/base that
are extensions written in cython and it's too late for me to analyze.
Hope my example is useful.
--
Michele Comignano
Computer Science student
University of Pisa, Italy
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
vertices = ['A', 'B', 'C']
edges = [
('A', 'B', {'a': 10, 'b': 20}),
('B', 'C', {'a': 10, 'b': 25}),
('C', 'A', {'a': 10, 'b': 20}),
]
# Creating the graph
G = DiGraph()
G.add_vertices(vertices)
G.add_edges(edges)
for o, d, a in edges:
print a
print 'label dictionary id: ' + hex(id(a))
print '\n\n'
i =0
for o, d, a in G.edges():
a['sometimes_duplicate']= i
i+=1
print a
print 'label dictionary id: ' + hex(id(a))
print '\n\n'
for o, d, a in G.edges():
print a
[sage-devel] Re: Attributes onto edges in sage graphs
Hello !! Could you please give us an example of such a "strange behavior" when using dictionaries as labels in Sage ? Thanks ! Nathann -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
