storage of graph embeddings buggy #33759

videlec · 2022-04-25T20:43:14Z

This ticket fixes the following issue

sage: G = Graph([(1,4), (2, 3)])
sage: G.is_planar(set_embedding=True, set_pos=True)
sage: G.delete_vertices([3])
sage: G.is_planar()
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Input In [27], in <cell line: 4>()
      2 G.is_planar(set_embedding=True)
      3 G.delete_vertices([Integer(3)])
----> 4 G.is_planar()

File /usr/lib/python3.10/site-packages/sage/graphs/generic_graph.py:4995, in GenericGraph.is_planar(self, on_embedding, kuratowski, set_embedding, set_pos)
   4993 if hasattr(G, '_immutable'):
   4994     G = copy(G)
-> 4995 planar = is_planar(G,kuratowski=kuratowski, set_pos=set_pos, set_embedding=set_embedding)
   4996 if kuratowski:
   4997     bool_result = planar[0]

File /usr/lib/python3.10/site-packages/sage/graphs/planarity.pyx:114, in sage.graphs.planarity.is_planar (build/cythonized/sage/graphs/planarity.c:2071)()
    112 cdef dict ffrom = {vvv: i + 1 for i, vvv in enumerate(listto)}
    113 cdef dict to = {i + 1: vvv for i, vvv in enumerate(listto)}
--> 114 g.relabel(ffrom)
    115 
    116 cdef graphP theGraph

File /usr/lib/python3.10/site-packages/sage/graphs/generic_graph.py:21878, in GenericGraph.relabel(self, perm, inplace, return_map, check_input, complete_partial_function, immutable)
  21876                 new_attr[perm[v]] = value
  21877             else:
> 21878                 new_attr[perm[v]] = [perm[w] for w in value]
  21880         setattr(self, attr, new_attr)
  21882 if return_map:

File /usr/lib/python3.10/site-packages/sage/graphs/generic_graph.py:21878, in <listcomp>(.0)
  21876                 new_attr[perm[v]] = value
  21877             else:
> 21878                 new_attr[perm[v]] = [perm[w] for w in value]
  21880         setattr(self, attr, new_attr)
  21882 if return_map:

KeyError: 3

It also deprecates parameter circular in method is_planar.

Follow up: #33760, #33769

CC: @dcoudert

Component: graph theory

Author: Vincent Delecroix

Branch/Commit: f2b86c7

Reviewer: David Coudert

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

The text was updated successfully, but these errors were encountered:

videlec · 2022-04-25T20:57:01Z

Branch: u/vdelecroix/33759

videlec · 2022-04-25T20:57:01Z

Author: Vincent Delecroix

videlec · 2022-04-25T20:57:01Z

New commits:

`5cbb17b`	`33759: correctly clean embedding`

videlec · 2022-04-25T20:57:01Z

Commit: 5cbb17b

dcoudert · 2022-04-26T09:32:38Z

comment:3

Several doctests errors due to

-                for vertex in vertices:
-                    attr_dict.pop(vertex, None)
+                for v in vertices:
+                    del attr_dict[v]

sagetrac-git · 2022-04-26T18:36:50Z

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

`35b8028`	`33759: use d.pop(v) instead of del d[v]`

sagetrac-git · 2022-04-26T18:36:50Z

Changed commit from 5cbb17b to 35b8028

sagetrac-git · 2022-04-27T10:29:17Z

Changed commit from 35b8028 to 0e1b3f5

sagetrac-git · 2022-04-27T10:29:17Z

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

`0e1b3f5`	`33759: also fix delete_vertex`

dcoudert · 2022-04-28T10:43:19Z

comment:6

I have several errors

sage -t --warn-long 293.2 --random-seed=30092742952270998397219008776926923749 src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 5239, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    g439.is_circular_planar(kuratowski=True, boundary=[1, 2, 3])
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.?[4]>", line 1, in <module>
        g439.is_circular_planar(kuratowski=True, boundary=[Integer(1), Integer(2), Integer(3)])
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/graphs/generic_graph.py", line 5328, in is_circular_planar
        graph._embedding[w].pop(graph._embedding[w].index(extra))
    ValueError: 0 is not in list
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 5241, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    g439.get_embedding()
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.?[5]>", line 1, in <module>
        g439.get_embedding()
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/graphs/generic_graph.py", line 2684, in get_embedding
        raise ValueError('%s has been modified and the embedding is no longer valid'%self)
    ValueError: Graph on 7 vertices has been modified and the embedding is no longer valid
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 5253, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    K23.is_circular_planar(boundary=[0, 1, 2, 3])
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.?[7]>", line 1, in <module>
        K23.is_circular_planar(boundary=[Integer(0), Integer(1), Integer(2), Integer(3)])
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/graphs/generic_graph.py", line 5328, in is_circular_planar
        graph._embedding[w].pop(graph._embedding[w].index(extra))
    ValueError: 5 is not in list
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 5260, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    K23.is_circular_planar(set_embedding=True, boundary=[0, 2, 1, 3])
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.?[9]>", line 1, in <module>
        K23.is_circular_planar(set_embedding=True, boundary=[Integer(0), Integer(2), Integer(1), Integer(3)])
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/graphs/generic_graph.py", line 5328, in is_circular_planar
        graph._embedding[w].pop(graph._embedding[w].index(extra))
    ValueError: 5 is not in list
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 5269, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    Graph(1).is_circular_planar()
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.?[11]>", line 1, in <module>
        Graph(Integer(1)).is_circular_planar()
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/graphs/generic_graph.py", line 5328, in is_circular_planar
        graph._embedding[w].pop(graph._embedding[w].index(extra))
    ValueError: 1 is not in list
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 5740, in sage.graphs.generic_graph.GenericGraph.genus
Failed example:
    cube.is_circular_planar()
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.genus[12]>", line 1, in <module>
        cube.is_circular_planar()
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/graphs/generic_graph.py", line 5328, in is_circular_planar
        graph._embedding[w].pop(graph._embedding[w].index(extra))
    ValueError: 0 is not in list
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 10268, in sage.graphs.generic_graph.GenericGraph.delete_vertex
Failed example:
    G.delete_vertex([3])
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.delete_vertex[17]>", line 1, in <module>
        G.delete_vertex([Integer(3)])
      File "/Users/dcoudert/sage/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/graphs/generic_graph.py", line 10276, in delete_vertex
        raise ValueError("vertex (%s) not in the graph"%str(vertex))
    ValueError: vertex ([3]) not in the graph

in the doctest of delete_vertex, change [3] -> 3
instead of neighbors.difference_update([vertex]), you can do neighbors.discard(vertex)

videlec · 2022-04-28T13:01:20Z

comment:7

Will fix that.

What about also fixing _embedding when calling delete_edge, delete_edges, contract_edge, contract_edges in this ticket?

sagetrac-git · 2022-04-28T15:30:04Z

Changed commit from 0e1b3f5 to f2b86c7

sagetrac-git · 2022-04-28T15:30:04Z

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

`f2b86c7`	`33759: more embedding fixes`

dcoudert · 2022-04-29T09:16:25Z

comment:10

Can you list the changes you have done and the introduced deprecation in the ticket description.

I agree that we can also fix contract_edge and contract_edges in this ticket.

dcoudert · 2022-04-29T09:16:54Z

comment:11

The good news is that all tests pass with the last commit ;)

videlec · 2022-04-29T09:59:57Z

comment:12

Simply some cleaning in sage.graphs.planarity.is_planar: the argument circular was ignored unless set_pos=True. The corresponding operation (ie setting positions) is more logically done in Graph.is_circular_planar.

videlec · 2022-04-29T10:03:31Z

comment:13

Maybe it is enough for a first step. I opened #33769 for dealing with edge deletion/contraction.

dcoudert · 2022-04-29T11:12:31Z

Reviewer: David Coudert

dcoudert · 2022-04-29T11:12:31Z

comment:15

I have updated the ticket description.

vbraun · 2022-05-12T21:42:32Z

Changed branch from u/vdelecroix/33759 to f2b86c7

…s_planar` Remove deprecated parameter `circular` from method `is_planar`. The deprecation was introduced in sagemath#33759. ### 📝 Checklist - [x] The title is concise, informative, and self-explanatory. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [x] I have updated the documentation accordingly. ### ⌛ Dependencies   URL: sagemath#36076 Reported by: David Coudert Reviewer(s): Frédéric Chapoton

videlec added this to the sage-9.6 milestone Apr 25, 2022

videlec added c: graph theory labels Apr 25, 2022

videlec added the s: needs review label Apr 25, 2022

This comment has been minimized.

Sign in to view

dcoudert added s: needs work and removed s: needs review labels Apr 28, 2022

videlec added s: needs review and removed s: needs work labels Apr 28, 2022

This comment has been minimized.

Sign in to view

dcoudert added s: positive review and removed s: needs review labels Apr 29, 2022

mkoeppe added p: blocker / 1 and removed p: major / 3 labels May 7, 2022

vbraun removed the s: positive review label May 12, 2022

vbraun closed this as completed in 7020df1 May 12, 2022

videlec mentioned this issue Jan 29, 2023

storage of graph embeddings buggy II : deleting/contracting edges #33769

Open

dcoudert mentioned this issue Aug 11, 2023

Remove deprecated parameter circular from method is_planar #36076

Merged

5 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

storage of graph embeddings buggy #33759

storage of graph embeddings buggy #33759

videlec commented Apr 25, 2022

videlec commented Apr 25, 2022

videlec commented Apr 25, 2022

videlec commented Apr 25, 2022

videlec commented Apr 25, 2022

This comment has been minimized.

dcoudert commented Apr 26, 2022

sagetrac-git mannequin commented Apr 26, 2022

sagetrac-git mannequin commented Apr 26, 2022

sagetrac-git mannequin commented Apr 27, 2022

sagetrac-git mannequin commented Apr 27, 2022

dcoudert commented Apr 28, 2022

videlec commented Apr 28, 2022

sagetrac-git mannequin commented Apr 28, 2022

sagetrac-git mannequin commented Apr 28, 2022

dcoudert commented Apr 29, 2022

dcoudert commented Apr 29, 2022

videlec commented Apr 29, 2022

videlec commented Apr 29, 2022

This comment has been minimized.

This comment has been minimized.

dcoudert commented Apr 29, 2022

dcoudert commented Apr 29, 2022

vbraun commented May 12, 2022

storage of graph embeddings buggy #33759

storage of graph embeddings buggy #33759

Comments

videlec commented Apr 25, 2022

videlec commented Apr 25, 2022

videlec commented Apr 25, 2022

videlec commented Apr 25, 2022

videlec commented Apr 25, 2022

This comment has been minimized.

dcoudert commented Apr 26, 2022

sagetrac-git mannequin commented Apr 26, 2022

sagetrac-git mannequin commented Apr 26, 2022

sagetrac-git mannequin commented Apr 27, 2022

sagetrac-git mannequin commented Apr 27, 2022

dcoudert commented Apr 28, 2022

videlec commented Apr 28, 2022

sagetrac-git mannequin commented Apr 28, 2022

sagetrac-git mannequin commented Apr 28, 2022

dcoudert commented Apr 29, 2022

dcoudert commented Apr 29, 2022

videlec commented Apr 29, 2022

videlec commented Apr 29, 2022

This comment has been minimized.

This comment has been minimized.

dcoudert commented Apr 29, 2022

dcoudert commented Apr 29, 2022

vbraun commented May 12, 2022