Opened 9 years ago

Closed 9 years ago

#8894 closed enhancement (fixed)

topological minor

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.6.2
Component: graph theory Keywords:
Cc: Merged in: sage-4.6.2.alpha1
Authors: Nathann Cohen Reviewers: Leonardo Sampaio
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

Graph.topological_minor !

I hope it will be useful, though the performances of GLPK are veeeery bad on this kind of problem... CPLEX can solve immediately problems GLPK can not handle (find there is no topological K5 minor in a Petersen Graph for example, or the same in a Grid2d graph).

I mentionned it in the docstring.

Nathann

Attachments (1)

trac_8894.patch (8.6 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_work

comment:2 Changed 9 years ago by ncohen

  • Authors set to Nathann Cohen
  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:3 Changed 9 years ago by ncohen

  • Description modified (diff)
  • Type changed from defect to enhancement

comment:4 Changed 9 years ago by lsampaio

  • Reviewers set to Leonardo Sampaio
  • Status changed from needs_review to positive_review

The patch seens to be correct and I believe it is ready to be merged to sage.

comment:5 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-4.6.1 to sage-4.6.2

comment:6 Changed 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Even though the patch applies (with fuzz and large offset), you should rebase it to sage-4.6.2.alpha0:

patching file sage/graphs/graph.py
Hunk #1 succeeded at 2960 with fuzz 2 (offset 461 lines).

Changed 9 years ago by ncohen

comment:7 Changed 9 years ago by ncohen

  • Status changed from needs_work to positive_review

Done !

Nathann

comment:8 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.