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: sage-8.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:

Status badges

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 vbraun

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?

Last edited 8 years ago by vbraun (previous) (diff)

comment:2 Changed 8 years ago by vbraun

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 ncohen

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

comment:4 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 5 years ago by jakobkroeker

  • Stopgaps set to wrongAnswerMarker

comment:9 Changed 3 years ago by gh-Rithesh17

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 gh-Rithesh17

The issue in the comments is addressed in https://trac.sagemath.org/ticket/27399

comment:11 Changed 3 years ago by dcoudert

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 gh-Rithesh17

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

Last edited 3 years ago by gh-Rithesh17 (previous) (diff)

comment:13 Changed 3 years ago by gh-Rithesh17

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 dcoudert

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 follow-up: Changed 3 years ago by gh-Rithesh17

Oh ok Sir. Anything suggestions on comment 13?

comment:16 in reply to: ↑ 15 Changed 3 years ago by dcoudert

Replying to gh-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

comment:17 Changed 3 years ago by gh-Rithesh17

Sorry Sir. I meant any suggestion on comment 12.

comment:18 Changed 3 years ago by dcoudert

Check the Graph and DiGraph constructors.

comment:19 Changed 3 years ago by gh-Rithesh17

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

comment:20 Changed 3 years ago by dcoudert

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 gh-Rithesh17

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 dcoudert

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

comment:23 Changed 3 years ago by gh-Rithesh17

  • Authors set to Rithesh K
  • Branch set to u/gh-Rithesh17/vertex-labels-in-graph-digraph
  • Commit set to 5f40353c94f2710ef7bbeee631daf8fb79a5693f
  • Status changed from new to needs_review

New commits:

5f40353error in vertex labelling in Graph() and DiGraph() modified

comment:24 Changed 3 years ago by dcoudert

  • 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 git

  • Commit changed from 5f40353c94f2710ef7bbeee631daf8fb79a5693f to e494dc55503e4d12af7d4bc4e60ac52b25840be9

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

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

comment:26 Changed 2 years ago by dcoudert

  • Milestone changed from sage-6.4 to sage-8.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 vbraun

  • Branch changed from u/gh-Rithesh17/vertex-labels-in-graph-digraph to e494dc55503e4d12af7d4bc4e60ac52b25840be9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.