1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022013 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("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  }

