Changeset 10886


Ignore:
Timestamp:
05/22/14 13:49:35 (8 years ago)
Author:
bburlacu
Message:

#1772: Simplified GenealogyGraph (and related components) API in an effort to improve speed and memory consumption (eg., by sharing the same arc when walking the graph in both directions: parent-child and child-parent).

Location:
branches/HeuristicLab.EvolutionTracking
Files:
14 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking.Views/3.4/HeuristicLab.EvolutionTracking.Views-3.4.csproj

    r10884 r10886  
    9797      <DependentUpon>FrequentFragmentsDialog.cs</DependentUpon>
    9898    </Compile>
    99     <Compile Include="GenealogyGraphChart.cs" />
     99    <Compile Include="GenealogyGraphChart.cs">
     100      <SubType>UserControl</SubType>
     101    </Compile>
    100102    <Compile Include="GenealogyGraphChart.Designer.cs">
    101103      <DependentUpon>GenealogyGraphChart.cs</DependentUpon>
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Analyzers/GenealogyAnalyzer.cs

    r10884 r10886  
    5454    private const string EnableSolutionCreatorTrackingParameterName = "EnableSolutionCreatorTracking"; // should always be enabled. maybe superfluous
    5555
    56     public string CrossoverParentsParameterName { get; set; }
    57     public string CrossoverChildParameterName { get; set; }
    58     public string ManipulatorChildParameterName { get; set; }
    59 
     56    #region parameter properties
    6057    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
    6158      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[QualityParameterName]; }
    6259    }
    63 
    6460    public IScopeTreeLookupParameter<T> PopulationParameter {
    6561      get { return (IScopeTreeLookupParameter<T>)Parameters[PopulationParameterName]; }
    6662    }
    67 
    6863    public IValueParameter<ICrossoverOperator<T>> BeforeCrossoverOperatorParameter {
    6964      get { return (IValueParameter<ICrossoverOperator<T>>)Parameters[BeforeCrossoverOperatorParameterName]; }
     
    7873      get { return (IValueParameter<IManipulatorOperator<T>>)Parameters[AfterManipulatorOperatorParameterName]; }
    7974    }
    80 
    81     #region parameter properties
    8275    public ILookupParameter<ResultCollection> ResultsParameter {
    8376      get { return (ILookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
     
    265258        }
    266259      } else {
     260        // TODO: eliminate from the graph extra vertices added by the recombination operators when filling the pool of offspring with offspring selection
     261
    267262        var elite = population.FirstOrDefault(x => GenealogyGraph.Contains(x));
    268263        if (elite != null) {
     
    282277          GenealogyGraph[vertex.Content] = vertex;
    283278          GenealogyGraph[previousVertex.Content] = previousVertex;
    284           // connect current elite with previous elite
    285           previousVertex.AddForwardArc(vertex);
    286           vertex.AddReverseArc(previousVertex);
     279          GenealogyGraph.AddArc(previousVertex, vertex); // connect current elite with previous elite
    287280          vertex.Id = previousVertex.Id; // another way would be to introduce the vertex.Id into the scope of the elite
    288281          vertex.Quality = previousVertex.Quality;
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/DirectedGraph/Interfaces/IVertex.cs

    r10677 r10886  
    3636    double Weight { get; set; }
    3737
    38     void AddForwardArc(IVertex target, double weight = 0.0, object content = null);
    3938    void AddForwardArc(IArc arc);
    40     void AddReverseArc(IVertex target, double weight = 0.0, object content = null);
    4139    void AddReverseArc(IArc arc);
    4240
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/DirectedGraph/Vertex.cs

    r10834 r10886  
    8787    // (they do not appear in the nodes Dictionary). It is the programmers responsibility to
    8888    // enforce the correct and desired behavior.
    89     public void AddForwardArc(IVertex target, double w = 0.0, object data = null) {
    90       var arc = new Arc { Source = this, Target = target, Data = data, Weight = w };
    91       if (outArcs == null) outArcs = new List<IArc> { arc };
    92       else outArcs.Add(arc);
    93     }
    9489    public void AddForwardArc(IArc arc) {
    95       if (arc.Source == null) { arc.Source = this; }
    9690      if (arc.Source != this) { throw new Exception("AddForwardArc: Source should be equal to this."); }
    97       if (outArcs == null) { outArcs = new List<IArc> { arc }; } else { outArcs.Add(arc); }
    98     }
    99     public void AddReverseArc(IVertex source, double w = 0.0, object data = null) {
    100       var arc = new Arc { Source = source, Target = this, Data = data, Weight = w };
    101       if (inArcs == null) inArcs = new List<IArc> { arc };
    102       else inArcs.Add(arc);
     91      if (outArcs == null)
     92        outArcs = new List<IArc>();
     93      outArcs.Add(arc);
    10394    }
    10495    public void AddReverseArc(IArc arc) {
    105       if (arc.Target == null) { arc.Target = this; }
    10696      if (arc.Target != this) { throw new Exception("AddReverseArc: Target should be equal to this."); };
    107       if (inArcs == null) { inArcs = new List<IArc> { arc }; } else { inArcs.Add(arc); }
     97      if (inArcs == null)
     98        inArcs = new List<IArc>();
     99      inArcs.Add(arc);
    108100    }
    109 
    110101    public int InDegree { get { return InArcs.Count(); } }
    111102    public int OutDegree { get { return OutArcs.Count(); } }
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/GenealogyGraph/GenealogyGraph.cs

    r10833 r10886  
    4040      get { return from n in base.Nodes select (IGenealogyGraphNode)n; }
    4141    }
     42
     43    public IGenealogyGraphArc AddArc(IGenealogyGraphNode source, IGenealogyGraphNode target) {
     44      var arc = new GenealogyGraphArc(source, target);
     45      source.AddForwardArc(arc);
     46      target.AddReverseArc(arc);
     47      return arc;
     48    }
     49
    4250    protected GenealogyGraph(GenealogyGraph original, Cloner cloner)
    4351      : base(original, cloner) {
     
    98106      get { return from n in base.Nodes select (IGenealogyGraphNode<T>)n; }
    99107    }
     108
     109    public IGenealogyGraphArc AddArc(IGenealogyGraphNode source, IGenealogyGraphNode target) {
     110      var arc = new GenealogyGraphArc(source, target);
     111      source.AddForwardArc(arc);
     112      target.AddReverseArc(arc);
     113      return arc;
     114    }
     115
    100116    // contructors
    101117    protected GenealogyGraph(GenealogyGraph<T> original, Cloner cloner)
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/GenealogyGraph/GenealogyGraphArc.cs

    r10293 r10886  
    3232    protected GenealogyGraphArc(GenealogyGraphArc original, Cloner cloner)
    3333      : base(original, cloner) {
     34      this.Target = original.Target;
     35      this.Source = original.Source;
     36      this.Label = original.Label;
     37      this.Weight = original.Weight;
     38      this.Data = original.Data;
    3439    }
    3540
    36     public GenealogyGraphArc() { }
     41    protected GenealogyGraphArc() { }
     42
     43    public GenealogyGraphArc(IGenealogyGraphNode source, IGenealogyGraphNode target, object data = null) {
     44      Source = source;
     45      Target = target;
     46      Data = data;
     47    }
    3748
    3849    public override IDeepCloneable Clone(Cloner cloner) {
     
    6071      Data = (T)original.Data.Clone();
    6172    }
    62     public GenealogyGraphArc() { }
    6373
    6474    public override IDeepCloneable Clone(Cloner cloner) {
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/GenealogyGraph/GenealogyGraphNode.cs

    r10685 r10886  
    107107      return Quality.CompareTo(other.Quality);
    108108    }
    109     public new void AddForwardArc(IVertex target, double w = 0.0, object data = null) {
    110       var arc = new GenealogyGraphArc { Source = this, Target = (IGenealogyGraphNode)target, Data = data, Weight = w };
    111       base.AddForwardArc(arc);
    112     }
    113     public new void AddReverseArc(IVertex source, double w = 0.0, object data = null) {
    114       var arc = new GenealogyGraphArc { Source = (IGenealogyGraphNode)source, Target = this, Data = data, Weight = w };
    115       base.AddReverseArc(arc);
    116     }
    117109    public IEnumerable<IGenealogyGraphNode> Parents {
    118110      get { return InArcs.Select(a => a.Source); }
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/GenealogyGraph/Interfaces/IGenealogyGraph.cs

    r10830 r10886  
    2727    Dictionary<double, List<IGenealogyGraphNode>> Ranks { get; }
    2828    new IEnumerable<IGenealogyGraphNode> Nodes { get; }
     29    IGenealogyGraphArc AddArc(IGenealogyGraphNode source, IGenealogyGraphNode target);
    2930  }
    3031
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Operators/BeforeCrossoverOperator.cs

    r10884 r10886  
    7878      };
    7979      GenealogyGraph.AddVertex(childVertex);
    80       foreach (var v in parentVertices) {
    81         childVertex.AddReverseArc(v);
    82         v.AddForwardArc(childVertex);
     80      foreach (var parentVertex in parentVertices) {
     81        GenealogyGraph.AddArc(parentVertex, childVertex);
    8382      }
    8483      ExecutionContext.Scope.Variables.Add(new Variable("Id", new StringValue(childVertex.Id)));
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Operators/BeforeManipulatorOperator.cs

    r10837 r10886  
    6060        var parents = vChild.Parents; // parents of child become parents of clone
    6161        foreach (var p in parents) {
    62           foreach (var a in p.OutArcs.Where(a => a.Target == vChild)) {
    63             a.Target = vClone;
    64           }
    65           vClone.AddReverseArc(p);
     62          var arc = p.OutArcs.First(a => a.Target == vChild);
     63          arc.Target = vClone;
     64          vClone.AddReverseArc(arc);
    6665        }
    6766
    6867        vClone.InArcs.Last().Data = vChild.InArcs.Last().Data; // fragment of child becomes fragment of clone
    6968        vChild.InArcs = new List<IGenealogyGraphArc>(); // child will be connected to clone
    70         vChild.AddReverseArc(vClone);
    71         vClone.AddForwardArc(vChild);
     69        GenealogyGraph.AddArc(vClone, vChild);
    7270
    7371        // the following step in necessary because some mutation operators change values while the reference stays the same
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolGraph/FPGraph.cs

    r10347 r10886  
    5656      return node;
    5757    }
    58 
    59     void AddArc(SymbolNode source, SymbolNode target, double weight, object data = null) {
    60       source.AddForwardArc(target, weight, data);
    61     }
    6258  }
    6359}
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolGraph/SymbolGraph.cs

    r10347 r10886  
    4949      return node;
    5050    }
    51 
    52     void AddArc(SymbolNode source, SymbolNode target, double weight, object data = null) {
    53       source.AddForwardArc(target, weight, data);
    54     }
    5551  }
    5652
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs

    r10884 r10886  
    5858          };
    5959          if (parent != null) {
    60             var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
     60            var arc = new GenealogyGraphArc(parent, fragmentNode);
    6161            parent.AddForwardArc(arc);
    62             fragmentNode.AddReverseArc(parent);
     62            fragmentNode.AddReverseArc(arc);
    6363          }
    6464          yield return fragmentNode; // no tracing if there are no parents
     
    9191          };
    9292          if (parent != null) {
    93             var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
     93            var arc = new GenealogyGraphArc(parent, fragmentNode);
    9494            parent.AddForwardArc(arc);
    95             fragmentNode.AddReverseArc(parent);
     95            fragmentNode.AddReverseArc(arc);
    9696          }
    9797          yield return fragmentNode;
     
    134134              };
    135135              if (parent != null) {
    136                 var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
     136                var arc = new GenealogyGraphArc(parent, fragmentNode);
    137137                parent.AddForwardArc(arc);
    138                 fragmentNode.AddReverseArc(parent);
     138                fragmentNode.AddReverseArc(arc);
    139139              }
    140140              //              fragmentNode.Content.Index1 = fragment.Index1 - index;
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs

    r10830 r10886  
    388388        if (TSPCrossover != null) {
    389389          TSPGenealogyAnalyzer.BeforeCrossoverOperatorParameter.ActualValue = new BeforeCrossoverOperator<Permutation>();
     390          TSPGenealogyAnalyzer.BeforeCrossoverOperator.ParentsParameter.ActualName = TSPCrossover.ParentsParameter.Name;
     391          TSPGenealogyAnalyzer.BeforeCrossoverOperator.ChildParameter.ActualName = TSPCrossover.ChildParameter.Name;
    390392          TSPGenealogyAnalyzer.AfterCrossoverOperatorParameter.ActualValue = new AfterCrossoverOperator<Permutation>();
    391           TSPGenealogyAnalyzer.CrossoverParentsParameterName = TSPCrossover.ParentsParameter.Name;
    392           TSPGenealogyAnalyzer.CrossoverChildParameterName = TSPCrossover.ChildParameter.Name;
     393          TSPGenealogyAnalyzer.AfterCrossoverOperator.ParentsParameter.ActualName = TSPCrossover.ParentsParameter.Name;
     394          TSPGenealogyAnalyzer.AfterCrossoverOperator.ChildParameter.ActualName = TSPCrossover.ChildParameter.Name;
    393395        }
    394396        if (TSPManipulator != null) {
    395397          TSPGenealogyAnalyzer.BeforeManipulatorOperatorParameter.ActualValue = new BeforeManipulatorOperator<Permutation>();
     398          TSPGenealogyAnalyzer.BeforeManipulatorOperator.ChildParameter.ActualName = TSPManipulator.PermutationParameter.Name;
    396399          TSPGenealogyAnalyzer.AfterManipulatorOperatorParameter.ActualValue = new AfterManipulatorOperator<Permutation>();
    397           TSPGenealogyAnalyzer.ManipulatorChildParameterName = TSPManipulator.PermutationParameter.Name;
     400          TSPGenealogyAnalyzer.AfterManipulatorOperator.ChildParameter.ActualName = TSPManipulator.PermutationParameter.Name;
    398401        }
    399402        TSPGenealogyAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
Note: See TracChangeset for help on using the changeset viewer.