Opened 10 years ago
Closed 10 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)
Change History (6)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- 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 10 years ago by
- 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 10 years ago by
comment:4 Changed 10 years ago by
- Status changed from needs_review to positive_review
comment:5 Changed 10 years ago by
- 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.
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