Opened 5 months ago

Closed 10 days ago

#2736 closed feature request (done)

Implement Graph Coloring Problem

Reported by: abeham Owned by: abeham
Priority: medium Milestone: HeuristicLab 3.3.15
Component: Problems Version: 3.3.14
Keywords: Cc:

Description

The problem has been implemented in the MemPR branch together with benchmark instances and needs to be integrated into the trunk.

Change History (7)

comment:1 Changed 4 weeks ago by abeham

  • Status changed from new to accepted

comment:2 Changed 4 weeks ago by abeham

  • Owner changed from abeham to jkarder
  • Status changed from accepted to reviewing

r15050:

  • Integrated graph coloring (GCP) into trunk
  • Additional Changes to branch version:
    • Added parameter BestKnownColors in addition to BestKnownQuality
    • Added a best colors for the default instance
    • Adapted Analyze() to output best found solution and fixed tracking of "Best Solution Colors" and "Best Solution Conflicts"

comment:3 Changed 2 weeks ago by jkarder

  • Owner changed from jkarder to abeham
  • Status changed from reviewing to assigned

Reviewed r15050:

  • the project GUID within the project reference to HeuristicLab.Encodings.LinearLinkageEncoding-3.4 is wrong; please remove and add the project reference again
  • problem instances / import:
    • some instances cannot be imported; the parser does not handle empty lines
    • rename Parser to GcolParser
    • the parser should already fix the node indices; currently this is done by the GcolInstanceProvider
  • GraphColoringProblem.FitnessFunctionOnValueChanged should not always set the best known quality to null, but instead calculate it (as it is done in Load) if possible

comment:4 Changed 13 days ago by abeham

  • Owner changed from abeham to jkarder
  • Status changed from assigned to reviewing

r15172:

  • Implemented review comments
  • I had to restructure the parser to a greater extent because I found out that some instances defined nodes without edges (which I decided to filter)
  • I added a unit test that loads all instances
  • I also added export of instances

comment:5 Changed 12 days ago by jkarder

  • Owner changed from jkarder to abeham
  • Status changed from reviewing to readytorelease

Looks good, thanks!

r15173: minor formatting

comment:6 Changed 12 days ago by abeham

  • Summary changed from Integrate Graph Coloring Problem into trunk to Implement Graph Coloring Problem

comment:7 Changed 10 days ago by abeham

  • Resolution set to done
  • Status changed from readytorelease to closed

r15217: merged revisions 14412, 14475, 14476, 14659, 14660, 14663, 14779, 14780, 14912, 15050, 15067, 15069, 15079, 15162, 15166, 15172, 15173 to stable

Note: See TracTickets for help on using tickets.