Opened 3 years ago

Closed 3 years ago

#24991 closed defect (fixed)

acyclic_edge_coloring(G, value_only=True) always gives 0.0

Reported by: mantepse Owned by:
Priority: major Milestone: sage-8.2
Component: graph theory Keywords:
Cc: Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 2b9c9f0 (Commits, GitHub, GitLab) Commit: 2b9c9f0f45789ef67dfac3a09e956e2ace0fd607
Dependencies: Stopgaps:

Status badges


sage: from sage.graphs.graph_coloring import acyclic_edge_coloring
sage: [acyclic_edge_coloring(G, value_only=True) for G in graphs(4)]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]

According to the documentation, it should return the acyclic chromatic index of the graph.

Change History (7)

comment:1 Changed 3 years ago by dcoudert

This is easy to fix. Are you already working on a patch ? otherwise I can do it.

comment:2 Changed 3 years ago by mantepse

Please go ahead, I wouldn't have a clue!

comment:3 Changed 3 years ago by dcoudert

  • Authors set to David Coudert
  • Branch set to u/dcoudert/24991_acyclic_edge_coloring
  • Commit set to 4d8b816937edf17c62e34b0200ce09f27e431949
  • Status changed from new to needs_review

The returned value was wrong: instead of returned the number of colors, it was returned the value of the objective function. Since the ILP formulation is a constraints satisfaction problem without objective, it was always returning 0.

I took the opportunity of this patch to polish the method.

New commits:

bd8b805trac #24991: fix issue when value_only is True
4d8b816trac #24991: polishing of the method

comment:4 Changed 3 years ago by git

  • Commit changed from 4d8b816937edf17c62e34b0200ce09f27e431949 to 2b9c9f0f45789ef67dfac3a09e956e2ace0fd607

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

ec77f1ftrac #24991: fix linear_arboricity when value_only is True
3eb4e81trac #24991: polish method linear_arboricity
2b9c9f0trac #24991: move reference to the right place

comment:5 Changed 3 years ago by dcoudert

The linear_arboricity method had the same issue, so I also fixed it.

comment:6 Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review


comment:7 Changed 3 years ago by vbraun

  • Branch changed from u/dcoudert/24991_acyclic_edge_coloring to 2b9c9f0f45789ef67dfac3a09e956e2ace0fd607
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.