Opened 4 years ago

Closed 4 years ago

#24573 closed defect (fixed)

bug in creating graphic matroid with explicit groundset labels

Reported by: dimpase Owned by:
Priority: major Milestone: sage-8.2
Component: matroid theory Keywords:
Cc: Stefan, Rudi, zgershkoff Merged in:
Authors: Dima Pasechnik Reviewers: Zach Gershkoff
Report Upstream: N/A Work issues:
Branch: ef524ec (Commits, GitHub, GitLab) Commit: ef524ec55973d68ac1a735cb348d5b4f67dad152
Dependencies: Stopgaps:

Status badges

Description

with the branch in #24512, which changes the implementation of WheelGraph, one has

sage: M = Matroid(range(8),graphs.WheelGraph(5))
sage: M.graphic_coextension(0,X=[1,2])
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-38-f3164ab7cc54> in <module>()
----> 1 M.graphic_coextension(Integer(0),X=[Integer(1),Integer(2)])

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/matroids/graphic_matroid.pyc in graphic_coextension(self, u, v, X, element)
   1593         edgelist = self.groundset_to_edges(X)
   1594 
-> 1595         split_vertex(G, u, v, edgelist)
   1596         G.add_edge(u, v, element)
   1597 

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/matroids/utilities.pyc in split_vertex(G, u, v, edges)
    773                 G.delete_edge(e)
    774             else:
--> 775                 raise ValueError("the edges are not all incident with u")
    776 
    777         elif e[0] == u:

ValueError: the edges are not all incident with u

which indicates an inconsistency in creation of M. Indeed, the following works:

sage: M = Matroid(graphs.WheelGraph(5))
sage: M.graphic_coextension(0,X=[(0,2),(0,3)])
Graphic matroid of rank 5 on 9 elements

Change History (10)

comment:1 follow-up: Changed 4 years ago by dimpase

isn't there a documentation bug: Currently one only sees

   A coextension in a graphic matroid is the opposite of contracting
   an edge; that is, vertices are merged, and a new edge is added
   between them. This method will split a vertex, and move the edges
   indicated by "X" to the new vertex.

This vertices are merged, and a new edge is added makes no sense to me. It seems that one started talking about what an edge contraction means, as merging happens in edge contraction, stopped half-way, and switched to describing coextension.


And while I am at it, isn't edges of "u" in description of X too informal? Should it be edges incident to "u" ?

comment:2 in reply to: ↑ 1 Changed 4 years ago by zgershkoff

Given the discussion in #24512, I'm not sure what needs to be changed in the code, if anything. The doctest was fixed already so future changes to WheelGraph() won't upset it.

Replying to dimpase:

isn't there a documentation bug: Currently one only sees

   A coextension in a graphic matroid is the opposite of contracting
   an edge; that is, vertices are merged, and a new edge is added
   between them. This method will split a vertex, and move the edges
   indicated by "X" to the new vertex.

This vertices are merged, and a new edge is added makes no sense to me. It seems that one started talking about what an edge contraction means, as merging happens in edge contraction, stopped half-way, and switched to describing coextension.

Yes, that's an error. How about this:

   A coextension in a graphic matroid is the opposite of contracting
   an edge; that is, a vertex is split, and a new edge is added
   between the resulting vertices. This method will create a new vertex
   adjacent to "u", and move the edges indicated by "X" from "u"
   to the new vertex.

And while I am at it, isn't edges of "u" in description of X too informal? Should it be edges incident to "u" ?

I suppose it's not standard, but I think the meaning is unambiguous. The phrase "edges of" only makes sense followed by a set of edges or an object that implies a set of edges (such as a graph), and I think there's only one set of edges that a vertex implies. But sure, we can change it since we're changing things.

comment:3 Changed 4 years ago by dimpase

  • Authors set to Dima Pasechnik
  • Branch set to u/dimpase/matpat
  • Commit set to 7def5ffdc91844fae9f416c376dd6224c5770db2
  • Status changed from new to needs_review

OK, so here is the reworded doc. Please review.


New commits:

7def5ffmeaningful documentation for coextension, cf. #24573

comment:4 Changed 4 years ago by zgershkoff

Looks fine. Patchbot doesn't like it but I think that's unrelated.

You're not going to fix edges of "u" as well?

comment:5 Changed 4 years ago by git

  • Commit changed from 7def5ffdc91844fae9f416c376dd6224c5770db2 to ef524ec55973d68ac1a735cb348d5b4f67dad152

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d0ffd5dmeaningful documentation for coextension, cf. #24573
ef524ec"of" -> "incident to" rewording

comment:6 Changed 4 years ago by dimpase

  • Dependencies #24512 deleted

OK, right, fixed this too.

comment:7 Changed 4 years ago by zgershkoff

  • Status changed from needs_review to positive_review

LGTM

comment:8 Changed 4 years ago by zgershkoff

  • Reviewers set to Zachary Gershkoff

comment:9 Changed 4 years ago by zgershkoff

  • Reviewers changed from Zachary Gershkoff to Zach Gershkoff

comment:10 Changed 4 years ago by vbraun

  • Branch changed from u/dimpase/matpat to ef524ec55973d68ac1a735cb348d5b4f67dad152
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.