Overwrote methods concerning subdivision of edge(s) in a matching covered graph #40090

janmenjayap · 2025-05-12T07:46:45Z

The objective of this issue is to overwrite the methods pertaining to subdivision of edges in a matching covered graph.

More specifically, this PR aims to overwrite the following methods:

subdivide_edge() | Subdivide an edge k times.
subdivide_edges() | Subdivide k times edges from an iterable container.

This PR shall address the methods related to subdivision of edge(s) in matching covered graphs.

Fixes #38216.
Note that this issue fixes a small part of the mentioned issue.

This issue is the fresh restart of the issue #39650.

📝 Checklist

The title is concise and informative.
The description explains in detail what this PR is about.
I have linked a relevant issue or discussion.
I have created tests covering the changes.
I have updated the documentation and checked the documentation preview.

⌛ Dependencies

Nothing as of now.

cc: @dcoudert.

src/sage/graphs/matching_covered_graph.py

janmenjayap · 2025-05-15T08:55:22Z

By the way,
While running ./sage -t src/sage/graphs/matching_covered_graph.py in my local, I have been getting this error

  File "/home/janmenjaya/open-source/sage/src/bin/sage-runtests", line 9, in <module>
    sys.exit(main())
             ^^^^^^
  File "/home/janmenjaya/open-source/sage/src/sage/doctest/__main__.py", line 192, in main
    err = DC.run()
          ^^^^^^^^
  File "/home/janmenjaya/open-source/sage/src/sage/doctest/control.py", line 1613, in run
    self.run_doctests()
  File "/home/janmenjaya/open-source/sage/src/sage/doctest/control.py", line 1197, in run_doctests
    self.dispatcher = DocTestDispatcher(self)
                      ^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/janmenjaya/open-source/sage/src/sage/doctest/forker.py", line 1745, in __init__
    init_sage(controller)
  File "/home/janmenjaya/open-source/sage/src/sage/doctest/forker.py", line 218, in init_sage
    controller.load_environment()
  File "/home/janmenjaya/open-source/sage/src/sage/doctest/control.py", line 699, in load_environment
    return import_module(self.options.environment)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/janmenjaya/open-source/sage/local/var/lib/sage/venv-python3.12.5/lib/python3.12/importlib/__init__.py", line 90, in import_module
    return _bootstrap._gcd_import(name[level:], package, level)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "<frozen importlib._bootstrap>", line 1387, in _gcd_import
  File "<frozen importlib._bootstrap>", line 1360, in _find_and_load
  File "<frozen importlib._bootstrap>", line 1331, in _find_and_load_unlocked
  File "<frozen importlib._bootstrap>", line 935, in _load_unlocked
  File "<frozen importlib._bootstrap_external>", line 995, in exec_module
  File "<frozen importlib._bootstrap>", line 488, in _call_with_frames_removed
  File "/home/janmenjaya/open-source/sage/src/sage/repl/ipython_kernel/all_jupyter.py", line 6, in <module>
    from sage.all_cmdline import *
  File "/home/janmenjaya/open-source/sage/src/sage/all_cmdline.py", line 17, in <module>
    from sage.all import *
  File "/home/janmenjaya/open-source/sage/src/sage/all.py", line 97, in <module>
    from sage.graphs.all import *
  File "/home/janmenjaya/open-source/sage/src/sage/graphs/all.py", line 9, in <module>
    from sage.graphs.graph import Graph
  File "/home/janmenjaya/open-source/sage/src/sage/graphs/graph.py", line 436, in <module>
    class Graph(GenericGraph):
  File "/home/janmenjaya/open-source/sage/src/sage/graphs/graph.py", line 9551, in Graph
    from sage.graphs.connectivity import minimal_separators
ImportError: cannot import name 'minimal_separators' from 'sage.graphs.connectivity' (/home/janmenjaya/open-source/sage/src/sage/graphs/connectivity.cpython-312-x86_64-linux-gnu.so)

So, I essentially, just comment the line,

from sage.graphs.connectivity import minimal_separators

and the line

"minimal_separators"        : "Connectivity, orientations, trees",

in graph.py and run the doctests (which passes the tests). Any comments on this?

dcoudert · 2025-05-15T09:26:52Z

The problem should be elsewhere in your configuration. I don't have this issue on my local installation (macOS and fedora).

janmenjayap · 2025-05-19T13:04:39Z

Hi @dcoudert,
Please do let me know, if anything else is required to be done.

dcoudert

at least one failing dpctest https://github.com/sagemath/sage/actions/runs/15113755224/job/42479110370?pr=40090#step:14:3733

github-actions · 2025-06-22T16:23:08Z

Documentation preview for this PR (built with commit f30722b; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

dcoudert · 2025-06-22T16:58:19Z

Make this test more robust

sage -t --warn-long 5.0 --random-seed=334098958671645686078940818804175858609 src/sage/graphs/matching_covered_graph.py
**********************************************************************
Error: Failed example:: Got: ([(0, 4, None),
  (0, 6, None),
  (1, 5, None),
  (1, 7, None),
  (4, 5, None),
  (6, 7, None)],
 [])
                                                                                                                                                                                                                                                                                                                                                                          
    sorted([f for f in F if f not in E]), sorted([e for e in E if e not in F])
Expected:
    ([(0, 4, None), (0, 6, None), (1, 5, None), (1, 7, None),
      (4, 5, None), (6, 7, None)], [(0, 1, None), (0, 1, None)])
Got:
    ([(0, 4, None),
      (0, 6, None),
      (1, 5, None),
      (1, 7, None),
      (4, 5, None),
      (6, 7, None)],
     [])

dcoudert · 2025-06-26T09:14:29Z

You still have to fix doctests

janmenjayap · 2025-06-26T09:17:37Z

Hi @dcoudert,

Apologies for the delay in this. In my local, it was passing all the doctests. I have been building the sage again after all the recent changes. I will fix this PR soon.

dcoudert

LGTM.

janmenjayap · 2025-07-15T20:15:38Z

Thank you.

@dcoudert

sagemathgh-40090: Overwrote methods concerning subdivision of edge(s) in a matching covered graph  The objective of this issue is to overwrite the methods pertaining to subdivision of edges in a matching covered graph.    More specifically, this PR aims to overwrite the following methods: - [x] `subdivide_edge()` | Subdivide an edge `k` times. - [x] `subdivide_edges()` | Subdivide `k` times edges from an iterable container.  This PR shall address the methods related to subdivision of edge(s) in matching covered graphs.  Fixes sagemath#38216. Note that this issue fixes a small part of the mentioned issue. This issue is the fresh restart of the issue sagemath#39650. ### 📝 Checklist  - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [x] I have created tests covering the changes. - [x] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies Nothing as of now.    cc: @dcoudert. URL: sagemath#40090 Reported by: Janmenjaya Panda Reviewer(s): David Coudert, Janmenjaya Panda

janmenjayap added 3 commits May 12, 2025 12:57

overwrote subdivide_edge()

bd642d8

overwrote subdivide_edges()

3990853

corrected a grammatical error

6c7e92d

github-actions bot added the s: needs review label May 12, 2025

janmenjayap mentioned this pull request May 12, 2025

Overwrote methods concerning subdivision of edges in a matching covered graph #39650

Closed

7 tasks

janmenjayap changed the title ~~Overwrote methods concerning subdivision of edges in a matching covered graph~~ Overwrote methods concerning subdivision of edge(s) in a matching covered graph May 12, 2025

dcoudert reviewed May 12, 2025

View reviewed changes

src/sage/graphs/matching_covered_graph.py Outdated Show resolved Hide resolved

src/sage/graphs/matching_covered_graph.py Outdated Show resolved Hide resolved

src/sage/graphs/matching_covered_graph.py Outdated Show resolved Hide resolved

janmenjayap added 2 commits May 14, 2025 01:43

updated subdivide_edge()

cba3f39

updated subdivide_edges()

3ad285e

dcoudert reviewed May 14, 2025

View reviewed changes

janmenjayap added 2 commits May 15, 2025 08:44

updated subdivide_edge()

c94966c

updated subdivide_edges()

f08e37d

dcoudert reviewed May 15, 2025

View reviewed changes

src/sage/graphs/matching_covered_graph.py Show resolved Hide resolved

updated subdivide_edges()

150fe72

Merge branch 'develop' into subdivision_of_edges

80ca6d0

dcoudert suggested changes May 24, 2025

View reviewed changes

Merge branch 'develop' into subdivision_of_edges

bc77052

Merge branch 'sagemath:develop' into subdivision_of_edges

f30722b

dcoudert added the c: graph theory label Jun 26, 2025

janmenjayap and others added 2 commits July 11, 2025 10:56

Merge branch 'develop' into subdivision_of_edges

f78b3ca

updated doctests

11cfdd9

dcoudert approved these changes Jul 15, 2025

View reviewed changes

dcoudert removed the s: needs review label Jul 15, 2025

dcoudert added s: positive review gsoc: 2025 Tag for GSoC2025 issues/PRs labels Jul 15, 2025

vbraun merged commit adddfb5 into sagemath:develop Jul 25, 2025
21 of 25 checks passed

github-actions bot removed the s: positive review label Jul 25, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Overwrote methods concerning subdivision of edge(s) in a matching covered graph #40090

Overwrote methods concerning subdivision of edge(s) in a matching covered graph #40090

Uh oh!

janmenjayap commented May 12, 2025

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

janmenjayap commented May 15, 2025

Uh oh!

dcoudert commented May 15, 2025

Uh oh!

janmenjayap commented May 19, 2025

Uh oh!

dcoudert left a comment

Uh oh!

github-actions bot commented Jun 22, 2025 •

edited

Loading

Uh oh!

dcoudert commented Jun 22, 2025

Uh oh!

dcoudert commented Jun 26, 2025

Uh oh!

janmenjayap commented Jun 26, 2025

Uh oh!

dcoudert left a comment

Uh oh!

janmenjayap commented Jul 15, 2025

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Overwrote methods concerning subdivision of edge(s) in a matching covered graph #40090

Overwrote methods concerning subdivision of edge(s) in a matching covered graph #40090

Uh oh!

Conversation

janmenjayap commented May 12, 2025

📝 Checklist

⌛ Dependencies

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

janmenjayap commented May 15, 2025

Uh oh!

dcoudert commented May 15, 2025

Uh oh!

janmenjayap commented May 19, 2025

Uh oh!

dcoudert left a comment

Choose a reason for hiding this comment

Uh oh!

github-actions bot commented Jun 22, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dcoudert commented Jun 22, 2025

Uh oh!

dcoudert commented Jun 26, 2025

Uh oh!

janmenjayap commented Jun 26, 2025

Uh oh!

dcoudert left a comment

Choose a reason for hiding this comment

Uh oh!

janmenjayap commented Jul 15, 2025

Uh oh!

Uh oh!

Uh oh!

github-actions bot commented Jun 22, 2025 •

edited

Loading