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 vertex labels are 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?

Version 0, edited 8 years ago by vbraun (next)

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.