1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022012 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 


22  using System;


23  using System.Linq;


24  using HeuristicLab.Analysis;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Operators;


28  using HeuristicLab.Optimization;


29  using HeuristicLab.Parameters;


30  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


31 


32  namespace 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  }

