Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3/HungarianAlgorithm.cs @ 8093

Last change on this file since 8093 was 8093, checked in by abeham, 12 years ago

#1855:

  • Added possibility to name row and column in matrix (to have more interpretable results)
  • Added a "standard" assignment problem
File size: 5.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Linq;
24using HeuristicLab.Analysis;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Operators;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Problems.LinearAssignment {
33  /// <summary>
34  /// A genetic algorithm.
35  /// </summary>
36  [Item("HungarianAlgorithm", "The Hungarian algorithm can be used to solve the linear assignment problem in O(n^3). It is also known as the Kuhn–Munkres algorithm or Munkres assignment algorithm.")]
37  [Creatable("Algorithms")]
38  [StorableClass]
39  public sealed class HungarianAlgorithm : EngineAlgorithm {
40    #region Problem Properties
41    public override Type ProblemType {
42      get { return typeof(LinearAssignmentProblem); }
43    }
44    public new LinearAssignmentProblem Problem {
45      get { return (LinearAssignmentProblem)base.Problem; }
46      set { base.Problem = value; }
47    }
48    #endregion
49
50    #region Parameter Properties
51    private ValueParameter<MultiAnalyzer> AnalyzerParameter {
52      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
53    }
54    #endregion
55
56    #region Properties
57    public MultiAnalyzer Analyzer {
58      get { return AnalyzerParameter.Value; }
59      set { AnalyzerParameter.Value = value; }
60    }
61    private LinearAssignmentProblemSolver Solver {
62      get { return (LinearAssignmentProblemSolver)OperatorGraph.InitialOperator; }
63    }
64    #endregion
65
66    [StorableConstructor]
67    private HungarianAlgorithm(bool deserializing) : base(deserializing) { }
68    private HungarianAlgorithm(HungarianAlgorithm original, Cloner cloner)
69      : base(original, cloner) {
70      AttachEventHandlers();
71    }
72    public HungarianAlgorithm()
73      : base() {
74      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the result.", new MultiAnalyzer()));
75
76      var solver = new LinearAssignmentProblemSolver();
77      OperatorGraph.InitialOperator = solver;
78
79      var placeholder = new Placeholder();
80      placeholder.Name = "(Analyzer)";
81      placeholder.OperatorParameter.ActualName = AnalyzerParameter.Name;
82      solver.Successor = placeholder;
83
84      UpdateAnalyzers();
85      AttachEventHandlers();
86
87      Problem = new LinearAssignmentProblem();
88    }
89
90    public override IDeepCloneable Clone(Cloner cloner) {
91      return new HungarianAlgorithm(this, cloner);
92    }
93
94    public override void Prepare() {
95      if (Problem != null) base.Prepare();
96    }
97
98    #region Events
99    protected override void OnProblemChanged() {
100      Problem.SolutionCreatorChanged += new EventHandler(Problem_SolutionCreatorChanged);
101      Problem.EvaluatorChanged += new EventHandler(Problem_EvaluatorChanged);
102      UpdateAnalyzers();
103      Parameterize();
104      base.OnProblemChanged();
105    }
106
107    private void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
108      Parameterize();
109    }
110
111    private void Problem_EvaluatorChanged(object sender, EventArgs e) {
112      Parameterize();
113    }
114
115    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
116      UpdateAnalyzers();
117      base.Problem_OperatorsChanged(sender, e);
118    }
119    #endregion
120
121    #region Helpers
122    [StorableHook(HookType.AfterDeserialization)]
123    private void AttachEventHandlers() {
124      if (Problem != null) {
125        Problem.SolutionCreatorChanged += new EventHandler(Problem_SolutionCreatorChanged);
126        Problem.EvaluatorChanged += new EventHandler(Problem_EvaluatorChanged);
127      }
128    }
129    private void UpdateAnalyzers() {
130      Analyzer.Operators.Clear();
131      if (Problem != null) {
132        foreach (var analyzer in Problem.OperatorsParameter.Value.OfType<IAnalyzer>()) {
133          foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
134            param.Depth = 0;
135          Analyzer.Operators.Add(analyzer);
136        }
137      }
138    }
139    private void Parameterize() {
140      if (Problem != null) {
141        Solver.AssignmentParameter.ActualName = Problem.SolutionCreator.PermutationParameter.ActualName;
142        Solver.CostsParameter.ActualName = Problem.CostsParameter.Name;
143        Solver.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
144      }
145    }
146    #endregion
147  }
148}
Note: See TracBrowser for help on using the repository browser.