Opened 9 years ago

Closed 9 years ago

#8748 closed enhancement (fixed)

Linear Arboricity, Acyclic edge coloring

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

Description

This patch implements LP formulations of Linear Arboricity and Acyclic edge coloring

Nathann Thank you.I got it.

This ticket is the same as #8405. The latter got spam content and the spammer closed the ticket. It would be more trouble and result in confusion to reopen the ticket. So I have moved the ticket over to this one.

Attachments (1)

trac_8748.2.patch (12.8 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (6)

comment:1 Changed 9 years ago by mvngu

  • Status changed from new to needs_review

For an explanation of the Linear Program used to solve this problem, see the LP chapter from : http://code.google.com/p/graph-theory-algorithms-book/

Nathann

comment:2 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to needs_work

Failures:

sage -t -only-optional=glpk,cbc "devel/sage-main/sage/graphs/graph_coloring.py"
**********************************************************************
File "/Users/rlmill/sage-4.4.4.alpha0-cbc/devel/sage-main/sage/graphs/graph_coloring.py", line 749:
    sage: all([g1.has_edge(e) or g2.has_edge(e) for e in g.edges()])  # optional - GLPK, CBC
Expected:
    True
Got:
    False
**********************************************************************
File "/Users/rlmill/sage-4.4.4.alpha0-cbc/devel/sage-main/sage/graphs/graph_coloring.py", line 922:
    sage: all([ any([gg.has_edge(e) for gg in colors]) for e in g.edges()])     # optional - GLPK, CBC
Expected:
    True
Got:
    False
**********************************************************************

comment:3 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Yet another graph constructor from networkx, with {} instead of None as labels. A g.edges(labels = False) did the trick :-)

Sorry abou that !

Nathann

Changed 9 years ago by ncohen

comment:4 Changed 9 years ago by rlm

  • Status changed from needs_review to positive_review

comment:5 Changed 9 years ago by rlm

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