Changeset 16767


Ignore:
Timestamp:
04/05/19 09:37:39 (2 weeks ago)
Author:
abeham
Message:

#2521: Adapted graph coloring problem

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/2521_ProblemRefactoring/HeuristicLab.Problems.GraphColoring/3.3/GraphColoringProblem.cs

    r16723 r16767  
    2222using System;
    2323using System.Linq;
     24using HEAL.Attic;
    2425using HeuristicLab.Analysis;
    2526using HeuristicLab.Common;
     
    3031using HeuristicLab.Optimization.Operators;
    3132using HeuristicLab.Parameters;
    32 using HEAL.Attic;
    3333using HeuristicLab.Problems.Instances;
    3434
     
    3838  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 135)]
    3939  [StorableType("007BD5F0-196C-4045-AC5D-BF287927C3DC")]
    40   public sealed class GraphColoringProblem : SingleObjectiveBasicProblem<LinearLinkageEncoding>, IProblemInstanceConsumer<GCPData>, IProblemInstanceExporter<GCPData> {
     40  public sealed class GraphColoringProblem : SingleObjectiveProblem<LinearLinkageEncoding, LinearLinkage>,
     41    IProblemInstanceConsumer<GCPData>, IProblemInstanceExporter<GCPData> {
    4142
    4243    public override bool Maximization {
     
    7475    }
    7576    public GraphColoringProblem() {
    76       Encoding = new LinearLinkageEncoding("lle");
    7777      Parameters.Add(adjacencyListParameter = new ValueParameter<IntMatrix>("Adjacency List", "The adjacency list that describes the (symmetric) edges in the graph with nodes from 0 to N-1."));
    7878      Parameters.Add(fitnessFunctionParameter = new ValueParameter<EnumValue<FitnessFunction>>("Fitness Function", "The function to use for evaluating the quality of a solution.", new EnumValue<FitnessFunction>(FitnessFunction.Penalized)));
     
    130130    }
    131131
    132     public override double Evaluate(Individual individual, IRandom random) {
     132    public override double Evaluate(LinearLinkage lle, IRandom random) {
    133133      var adjList = adjacencyListParameter.Value;
    134       var llee = individual.LinearLinkage(Encoding.Name).ToEndLinks(); // LLE-e encoding uses the highest indexed member as group number
     134      var llee = lle.ToEndLinks(); // LLE-e encoding uses the highest indexed member as group number
    135135
    136136      switch (FitnessFunction) {
     
    169169    }
    170170
    171     public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
    172       var orderedIndividuals = individuals.Zip(qualities, (i, q) => new { Individual = i, Quality = q }).OrderBy(z => z.Quality);
    173       var best = Maximization ? orderedIndividuals.Last().Individual.LinearLinkage(Encoding.Name) : orderedIndividuals.First().Individual.LinearLinkage(Encoding.Name);
     171    public override void Analyze(LinearLinkage[] lles, double[] qualities, ResultCollection results, IRandom random) {
     172      var orderedIndividuals = lles.Zip(qualities, (i, q) => new { LLE = i, Quality = q }).OrderBy(z => z.Quality);
     173      var best = Maximization ? orderedIndividuals.Last().LLE : orderedIndividuals.First().LLE;
    174174       
    175       var lle = best.ToEndLinks();
    176       var colors = lle.Distinct().Count();
    177       var conflicts = CalculateConflicts(lle);
     175      var llee = best.ToEndLinks();
     176      var colors = llee.Distinct().Count();
     177      var conflicts = CalculateConflicts(llee);
    178178     
    179179      IResult res;
     
    199199          ((IntValue)res.Value).Value = bestColors = colors;
    200200      }
    201       if (!results.TryGetValue("Best Solution", out res)) {
    202         res = new Result("Best Solution", (LinearLinkage)best.Clone());
    203         results.Add(res);
     201      if (!results.ContainsKey("Best Encoded Solution") || improvement)
     202        results.AddOrUpdateResult("Best Encoded Solution", (LinearLinkage)best.Clone());
     203
     204      if (!results.TryGetValue("Best Solution", out res) || !(res.Value is IntMatrix)) {
     205        var matrix = new IntMatrix(llee.Length, 2) { ColumnNames = new[] { "Node", "Color" } };
     206        UpdateMatrix(llee, matrix);
     207        res = new Result("Best Solution", matrix);
     208        results.AddOrUpdateResult("Best Solution", matrix);
    204209      } else {
    205         if (improvement)
    206           res.Value = (LinearLinkage)best.Clone();
     210        if (improvement) {
     211          UpdateMatrix(llee, (IntMatrix)res.Value);
     212        }
    207213      }
    208214
     
    210216        if (BestKnownColorsParameter.Value == null || BestKnownColorsParameter.Value.Value > colors)
    211217          BestKnownColorsParameter.Value = new IntValue(colors);
     218      }
     219    }
     220
     221    private static void UpdateMatrix(int[] llee, IntMatrix matrix) {
     222      var assign = llee.Select((v, i) => new { Node = i, Color = v }).OrderBy(x => x.Color);
     223      var color = 0;
     224      var prev = -1;
     225      foreach (var a in assign) {
     226        if (prev >= 0 && prev != a.Color)
     227          color++;
     228        matrix[a.Node, 0] = a.Node;
     229        matrix[a.Node, 1] = color;
     230        prev = a.Color;
    212231      }
    213232    }
Note: See TracChangeset for help on using the changeset viewer.