source: stable/HeuristicLab.Problems.LinearAssignment/3.3/HungarianAlgorithm.cs @ 10032

Last change on this file since 10032 was 9456, checked in by swagner, 9 years ago

Updated copyright year and added some missing license headers (#1889)

File size: 5.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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("Hungarian Algorithm", "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, IStorableContent {
40    public string Filename { get; set; }
41
42    #region Problem Properties
43    public override Type ProblemType {
44      get { return typeof(LinearAssignmentProblem); }
45    }
46    public new LinearAssignmentProblem Problem {
47      get { return (LinearAssignmentProblem)base.Problem; }
48      set { base.Problem = value; }
49    }
50    #endregion
51
52    #region Parameter Properties
53    private ValueParameter<MultiAnalyzer> AnalyzerParameter {
54      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
55    }
56    #endregion
57
58    #region Properties
59    public MultiAnalyzer Analyzer {
60      get { return AnalyzerParameter.Value; }
61      set { AnalyzerParameter.Value = value; }
62    }
63    private LinearAssignmentProblemSolver Solver {
64      get { return (LinearAssignmentProblemSolver)OperatorGraph.InitialOperator; }
65    }
66    #endregion
67
68    [StorableConstructor]
69    private HungarianAlgorithm(bool deserializing) : base(deserializing) { }
70    private HungarianAlgorithm(HungarianAlgorithm original, Cloner cloner)
71      : base(original, cloner) {
72      RegisterEventHandlers();
73    }
74    public HungarianAlgorithm()
75      : base() {
76      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the result.", new MultiAnalyzer()));
77
78      var solver = new LinearAssignmentProblemSolver();
79      OperatorGraph.InitialOperator = solver;
80
81      var placeholder = new Placeholder();
82      placeholder.Name = "(Analyzer)";
83      placeholder.OperatorParameter.ActualName = AnalyzerParameter.Name;
84      solver.Successor = placeholder;
85
86      UpdateAnalyzers();
87      RegisterEventHandlers();
88
89      Problem = new LinearAssignmentProblem();
90    }
91
92    public override IDeepCloneable Clone(Cloner cloner) {
93      return new HungarianAlgorithm(this, cloner);
94    }
95
96    public override void Prepare() {
97      if (Problem != null) base.Prepare();
98    }
99
100    #region Events
101    protected override void OnProblemChanged() {
102      Problem.SolutionCreatorChanged += new EventHandler(Problem_SolutionCreatorChanged);
103      Problem.EvaluatorChanged += new EventHandler(Problem_EvaluatorChanged);
104      UpdateAnalyzers();
105      Parameterize();
106      base.OnProblemChanged();
107    }
108
109    private void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
110      Parameterize();
111    }
112
113    private void Problem_EvaluatorChanged(object sender, EventArgs e) {
114      Parameterize();
115    }
116
117    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
118      UpdateAnalyzers();
119      base.Problem_OperatorsChanged(sender, e);
120    }
121    #endregion
122
123    #region Helpers
124    [StorableHook(HookType.AfterDeserialization)]
125    private void AfterDeserialization() {
126      RegisterEventHandlers();
127    }
128
129    private void RegisterEventHandlers() {
130      if (Problem != null) {
131        Problem.SolutionCreatorChanged += new EventHandler(Problem_SolutionCreatorChanged);
132        Problem.EvaluatorChanged += new EventHandler(Problem_EvaluatorChanged);
133      }
134    }
135    private void UpdateAnalyzers() {
136      Analyzer.Operators.Clear();
137      if (Problem != null) {
138        foreach (var analyzer in Problem.OperatorsParameter.Value.OfType<IAnalyzer>()) {
139          foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
140            param.Depth = 0;
141          Analyzer.Operators.Add(analyzer);
142        }
143      }
144    }
145    private void Parameterize() {
146      if (Problem != null) {
147        Solver.AssignmentParameter.ActualName = Problem.SolutionCreator.PermutationParameter.ActualName;
148        Solver.CostsParameter.ActualName = Problem.CostsParameter.Name;
149        Solver.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
150      }
151    }
152    #endregion
153  }
154}
Note: See TracBrowser for help on using the repository browser.