Opened 8 years ago
Closed 2 years ago
#14708 closed defect (fixed)
Graph constructor forgets vertex labels
Reported by:  vbraun  Owned by:  jason, ncohen, rlm 

Priority:  major  Milestone:  sage8.8 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  Rithesh K  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  e494dc5 (Commits, GitHub, GitLab)  Commit:  e494dc55503e4d12af7d4bc4e60ac52b25840be9 
Dependencies:  Stopgaps: 
Description
sage: g = Graph() sage: g.add_vertex(0) sage: g.set_vertex(0, 'foo') sage: g.get_vertices() {0: 'foo'} sage: Graph(g).get_vertices() {0: None}
Edge labels are remembered, though:
sage: g.add_vertex(1) sage: g.add_edge(0,1, 'bar') sage: g.edges() [(0, 1, 'bar')] sage: Graph(g).edges() [(0, 1, 'bar')]
Change History (27)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
Somewhat related:
sage: g = Graph() sage: g.set_vertex('foo', 'bar') sage: g.get_vertices() {}
Ok, I would have expected a ValueError when calling set_vertex()
. But fine, lets continue...
sage: g.add_vertex('foo') sage: g.get_vertices() {'foo': 'bar'}
wat?
comment:3 Changed 8 years ago by
I think that these "vertex labels" are meant to associate nonhashable values to a vertex (whose name must be hashable).
I never used it, I also think that it is useless (just use an external dictionary..) and that we would be better without it.
Nathann
comment:4 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:5 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:6 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:7 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:8 Changed 5 years ago by
 Stopgaps set to wrongAnswerMarker
comment:9 Changed 3 years ago by
I would like to address the issue raised in the comments section.
This is the source code for the set_vertex() function for generic graphs
def set_vertex(self, vertex, object): if hasattr(self, '_assoc') is False: self._assoc = {} self._assoc[vertex] = object
Since _assoc is a dictionary, even if the vertex isn't added beforehand (as in the example demonstrated in the comments section), the dictionary adds an entry into it. For example,
>>> vert = {} >>> vert['foo'] = 'bar' >>> vert {'foo': 'bar'}
But we are adding a new vertex only on the call of the method _backend.add_vertex() in the graph. Hence, on calling the method get_vertices(), 'foo' was not displayed.
But remember that _alloc already has the dictionary entry {foo: bar}. So once the method add_vertex('foo') is called, the entry foo is added to the list of vertices in the graph, and so on calling get_vertices, the entry {foo: bar} is displayed.
comment:10 Changed 3 years ago by
The issue in the comments is addressed in https://trac.sagemath.org/ticket/27399
comment:11 Changed 3 years ago by
Are you also planning to work on the other issue: copy of vertex labels when calling Graph(g)
or DiGraph(g)
?
If so, there is a minor improvement to do in get_vertices
: no need to build the list of vertices. So
 if verts is None:  verts = list(self) + if verts is None: + verts = self
comment:12 Changed 3 years ago by
This solution did not work. The problem still persist
sage: g.set_vertex(0, 'foo') sage: g.get_vertices() {0: 'foo', 1: None, 2: None, 3: None, 4: None} sage: Graph(g).get_vertices() {0: None, 1: None, 2: None, 3: None, 4: None}
I think the problem is in not communicating the labels of vertices in g
to Graph(g)
.
If we look at the .set_vertex
method, we have
self._assoc[vertex] = object
which, I believe, is not being transferred to Graph(g). On the other hand, in the .set_edge_label
method, we have
self._backend.set_edge_label(u, v, l, self._directed)
I am not yet sure how these two different implementations affect Graph(g), but edge labels are retained in Graph(g) but not vertex labels
comment:13 Changed 3 years ago by
And this is one more thing I've found: if g
has multiple edges and loops, then Graph(g)
allows loops but not multiple edges. But Graph(g.edges())
allows both (with a warning to set multiedges
flag to True
).
sage: g = digraphs.DeBruijn(2,2) sage: g1 = Graph(g) sage: g1.edges() [('00', '00', '0'), ('00', '01', '1'), ('00', '10', '0'), ('01', '10', '0'), ('01', '11', '1'), ('10', '11', '0'), ('11', '11', '1')] sage: g2 = Graph(g.edges()) sage: g2.edges() [('00', '00', '0'), ('00', '01', '1'), ('00', '10', '0'), ('01', '10', '0'), ('01', '10', '1'), ('01', '11', '1'), ('10', '11', '0'), ('11', '11', '1')]
comment:14 Changed 3 years ago by
When calling Graph(g)
, the constructor gives the same settings for loops and multiple edges to the resulting graph than g
, and here, the digraph g
has loops but no multiple edges. Hence the returned graph has no multiple edges.
When a list of edges is given as input, we get a deprecation warning and the constructor sets parameter for multiple edges to True if necessary, but this behavior will soon be changed to False unless the user specifies multiedges=True
.
comment:15 followup: ↓ 16 Changed 3 years ago by
Oh ok Sir. Anything suggestions on comment 13?
comment:16 in reply to: ↑ 15 Changed 3 years ago by
Replying to ghRithesh17:
Oh ok Sir. Anything suggestions on comment 13?
The current behavior is the right one. So nothing to do for #comment:13.
There is however something to do for #comment:11
comment:17 Changed 3 years ago by
Sorry Sir. I meant any suggestion on comment 12.
comment:18 Changed 3 years ago by
Check the Graph
and DiGraph
constructors.
comment:19 Changed 3 years ago by
I went through the __init__
constructa of both Graph
and DiGraph
classes and found this line in both of them:
self.add_vertices(data.vertex_iterator()) self.add_edges(data.edge_iterator())
Now in the vertex_iterator
there is no field for the labels
sage: g = digraphs.DeBruijn(2,2) sage: for v in g.vertex_iterator(): ....: print(v) ....: 11 10 00 01
But the labels are displayed in the case of edge_iterator
sage: for v in g.edge_iterator(): ....: print(v) ....: ('11', '10', '0') ('11', '11', '1') ('10', '00', '0') ('10', '01', '1') ('00', '00', '0') ('00', '01', '1') ('01', '10', '0') ('01', '11', '1')
If we need to modify into the vertex_iterator
method. we must change the backend code.
def vertex_iterator(self, vertices=None): return self._backend.iterator_verts(vertices)
I'll have to look into the Pyrex file basic/c_graph.pyx
to modify _backend.iterator_verts(vertices)
, but can I do it? I generally would not like to touch the backend files because there could be many more methods using it
comment:20 Changed 3 years ago by
Please don't change the backend.
What you must do is simply add self.set_vertices(data.get_vertices())
at the right place in the __init__
methods.
comment:21 Changed 3 years ago by
Yeah. That's a simpler solution.
I had to also modify to_undirected
method in DiGraphs? and to_directed
method in Graphs to support vertex labels. And now it is working.
sage: g = Graph() sage: g.add_vertex(0) sage: g.set_vertex(0, 'foo') sage: g.get_vertices() {0: 'foo'} sage: Graph(g).get_vertices() {0: 'foo'}
Do I need to add a doctest for this?
comment:22 Changed 3 years ago by
Yes, you need to add a doctest with a pointer to this ticket, i.e., :trac:`14708`
comment:23 Changed 3 years ago by
 Branch set to u/ghRithesh17/vertexlabelsingraphdigraph
 Commit set to 5f40353c94f2710ef7bbeee631daf8fb79a5693f
 Status changed from new to needs_review
New commits:
5f40353  error in vertex labelling in Graph() and DiGraph() modified

comment:24 Changed 3 years ago by
 Reviewers set to David Coudert
Can you change the first example in digraph.py to only DiGraph
, so
 sage: g = Graph() + sage: g = DiGraph()
Also, add (:trac:`14708`)
to each of the added doctests.
comment:25 Changed 3 years ago by
 Commit changed from 5f40353c94f2710ef7bbeee631daf8fb79a5693f to e494dc55503e4d12af7d4bc4e60ac52b25840be9
Branch pushed to git repo; I updated commit sha1. New commits:
e494dc5  error in vertex labelling in Graph() and DiGraph() modified

comment:26 Changed 2 years ago by
 Milestone changed from sage6.4 to sage8.8
 Status changed from needs_review to positive_review
 Stopgaps wrongAnswerMarker deleted
Just tested it over 8.8.beta3. LGTM.
comment:27 Changed 2 years ago by
 Branch changed from u/ghRithesh17/vertexlabelsingraphdigraph to e494dc55503e4d12af7d4bc4e60ac52b25840be9
 Resolution set to fixed
 Status changed from positive_review to closed
I'm also totally confused about what
set_vertex()
is supposed to achieve. Vertices are already some object. Then you can associate another object to the vertex object. How is that different to just using a pair(object1, object2)
as vertex?