Opened 4 years ago

Last modified 3 months ago

#24989 needs_work defect

G.edges_incident returns edges with vertices swapped

Reported by: mantepse Owned by:
Priority: major Milestone: sage-9.5
Component: graph theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/gh-vipul79321/ticket24989 (Commits, GitHub, GitLab) Commit: 89b9695c2238950cedeb01ed034a3002f8fab970
Dependencies: Stopgaps:

Status badges

Description

sage: G = (graphs.PathGraph(4)).relabel(immutable=True, inplace=False)
sage: G.edges(labels=False)
[(0, 1), (1, 2), (2, 3)]
sage: G.edges_incident([1,2], labels=False)
[(1, 0), (1, 2), (2, 3)]

I would expect that G.edges_incident returns a subset of G.edges

Change History (14)

comment:1 Changed 4 years ago by dcoudert

This is due to method iterator_edges of the static_sparse_graph backend.

sage: G = (graphs.PathGraph(4)).relabel(immutable=True, inplace=False)
sage: G._backend
<sage.graphs.base.static_sparse_backend.StaticSparseBackend object at 0x2198ceea8>
sage: G.edges_incident([1,2], labels=False)
[(1, 0), (1, 2), (2, 3)]
sage: list(G.edge_iterator([1,2], labels=False))
[(1, 0), (1, 2), (2, 3)]
sage:
sage: G = (graphs.PathGraph(4)).relabel(immutable=False, inplace=False)
sage: G._backend
<sage.graphs.base.sparse_graph.SparseGraphBackend object at 0x218d369d0>
sage: G.edges_incident([1,2], labels=False)
[(0, 1), (1, 2), (2, 3)]
sage: list(G.edge_iterator([1,2], labels=False))
[(0, 1), (1, 2), (2, 3)]

comment:2 Changed 22 months ago by gh-vipul79321

  • Branch set to u/vipul_gupta/ticket24989
  • Status changed from new to needs_review

comment:3 Changed 22 months ago by gh-vipul79321

  • Branch u/vipul_gupta/ticket24989 deleted

comment:4 Changed 22 months ago by gh-vipul79321

  • Status changed from needs_review to needs_work

comment:5 Changed 22 months ago by gh-vipul79321

  • Branch set to u/gh-vipul79321/ticket24989

comment:6 Changed 22 months ago by git

  • Commit set to 89b9695c2238950cedeb01ed034a3002f8fab970

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

cef6f9eEdges_incident modified
89b9695Edges_incident modified

comment:7 Changed 22 months ago by gh-vipul79321

  • Status changed from needs_work to needs_review

comment:8 follow-up: Changed 22 months ago by dcoudert

  • Milestone changed from sage-8.2 to sage-9.1
  • Status changed from needs_review to needs_work

No, this is not an acceptable solution. We do our best to provide as fast as possible solutions and making a copy of the graph is a too expensive operation for this purpose. Furthermore, it is not algorithmically sounded as it relies only on the way the copy is done.

The problem must be fixed in the backend.

comment:9 in reply to: ↑ 8 Changed 22 months ago by gh-vipul79321

Replying to dcoudert:

No, this is not an acceptable solution. We do our best to provide as fast as possible solutions and making a copy of the graph is a too expensive operation for this purpose. Furthermore, it is not algorithmically sounded as it relies only on the way the copy is done.

Yeah, I agree that it is not fast. We can also try to pass another argument 'bool is_immutable'. So that our function will make copy of the graph only when it is immutable.

The problem must be fixed in the backend.

I dont think it is worth it to make changes in backend for this purpose.

comment:10 Changed 22 months ago by dcoudert

This problem must be fixed without copy of the graph, and FYI, we can check if a graph is immutable or not using G.is_immutable().

comment:11 Changed 20 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

comment:12 Changed 15 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:13 Changed 10 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:14 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5
Note: See TracTickets for help on using tickets.