Graph constructor forgets vertex labels

[vbraun]

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')]

Component: graph theory

Author: Rithesh K

Branch/Commit: e494dc5

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/14708

[vbraun]

comment:1

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?

[vbraun]

comment:2

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?

[nathanncohen]

comment:3

I think that these "vertex labels" are meant to associate non-hashable 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

[sagetrac-jakobkroeker]

Stopgaps: wrongAnswerMarker

[Rithesh17]

comment:9

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.

[Rithesh17]

comment:10

The issue in the comments is addressed in #27399

[dcoudert]

comment:11

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

[Rithesh17]

comment:12

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

[Rithesh17]

comment:13

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')]

[dcoudert]

comment:14

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.

[Rithesh17]

comment:15

Oh ok Sir. Anything suggestions on comment 13?

[dcoudert]

comment:16

Replying to @Rithesh17:

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

[Rithesh17]

comment:17

Sorry Sir. I meant any suggestion on comment 12.

[dcoudert]

comment:18

Check the Graph and DiGraph constructors.

[Rithesh17]

comment:19

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 back-end 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

[dcoudert]

comment:20

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.

[Rithesh17]

comment:21

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?

[dcoudert]

comment:22

Yes, you need to add a doctest with a pointer to this ticket, i.e., :trac:`14708`

[Rithesh17]

Author: Rithesh K

[Rithesh17]

Branch: u/gh-Rithesh17/vertex-labels-in-graph-digraph

[Rithesh17]

New commits:

5f40353

error in vertex labelling in Graph() and DiGraph() modified

[Rithesh17]

Commit: 5f40353

[dcoudert]

comment:24

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.

[dcoudert]

Reviewer: David Coudert

[sagetrac-git]

Changed commit from 5f40353 to e494dc5

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e494dc5

error in vertex labelling in Graph() and DiGraph() modified

[dcoudert]

comment:26

Just tested it over 8.8.beta3. LGTM.

[dcoudert]

Changed stopgaps from wrongAnswerMarker to none

[vbraun]

Changed branch from u/gh-Rithesh17/vertex-labels-in-graph-digraph to e494dc5