Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/31/14 17:11:39 (10 years ago)
Author:
bburlacu
Message:

#1772: Ported the rest of the changes to the DirectedGraph and Vertex to the GenealogyGraph and GenealogyGraphNode. Adapted tracking operators, analyzers and views.

Location:
branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4
Files:
1 deleted
5 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r11233 r11253  
    173173  </ItemGroup>
    174174  <ItemGroup>
    175     <Compile Include="Analyzers\SymbolicDataAnalysisInternalDiversityAnalyzer.cs" />
    176175    <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectivePruningAnalyzer.cs" />
    177176    <Compile Include="Analyzers\SymbolicDataAnalysisGenealogyAnalyzer.cs" />
     
    207206    <Compile Include="SlidingWindow\SlidingWindowVisualizer.cs" />
    208207    <Compile Include="SymbolicDataAnalysisExpressionPruningOperator.cs" />
    209     <Compile Include="SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs" />
    210208    <Compile Include="SymbolicDataAnalysisSolutionPruningOptimizer.cs" />
    211209    <Compile Include="Analyzers\SymbolicDataAnalysisVariableFrequencyAnalyzer.cs" />
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionAfterCrossoverOperator.cs

    r11233 r11253  
    3434      var nodes0 = (List<ISymbolicExpressionTreeNode>)arcs[0].Data;
    3535      var nodes1 = (List<ISymbolicExpressionTreeNode>)arcs[1].Data;
    36       var childNodes = childVertex.Content.IterateNodesPrefix().ToList();
     36      var childNodes = childVertex.Data.IterateNodesPrefix().ToList();
    3737      IFragment<ISymbolicExpressionTreeNode> fragment = null;
    3838      for (int i = 0; i < Math.Min(nodes0.Count, childNodes.Count); ++i) {
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionAfterManipulatorOperator.cs

    r11233 r11253  
    2929namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    3030  public class SymbolicDataAnalysisExpressionAfterManipulatorOperator : AfterManipulatorOperator<ISymbolicExpressionTree> {
    31     private readonly SymbolicExpressionTreeNodeSimilarityComparer comparer;
    32 
    33     public SymbolicDataAnalysisExpressionAfterManipulatorOperator() {
    34       comparer = new SymbolicExpressionTreeNodeSimilarityComparer {
    35         MatchVariableNames = true,
    36         MatchVariableWeights = true,
    37         MatchConstantValues = true
    38       };
    39     }
    40 
    4131    public override IOperation Apply() {
    42       var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
    43       var nodesBefore = (List<ISymbolicExpressionTreeNode>)vChild.InArcs.First().Data;
     32      var childVertex = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
     33      var nodesBefore = (List<ISymbolicExpressionTreeNode>)childVertex.InArcs.First().Data;
    4434      var nodesAfter = ChildParameter.ActualValue.IterateNodesPrefix().ToList();
    4535      IFragment<ISymbolicExpressionTreeNode> fragment = null;
    4636
    47       for (int i = 0; i < Math.Min(nodesAfter.Count, nodesBefore.Count); ++i) {
    48         var a = nodesAfter[i];
    49         var b = nodesBefore[i];
     37      // try to find if a subtree was replaced by comparing references
     38      for (int i = 0; i < Math.Min(nodesBefore.Count, nodesAfter.Count); ++i) {
     39        if (nodesAfter[i] != nodesBefore[i]) {
     40          fragment = new Fragment<ISymbolicExpressionTreeNode> {
     41            Root = nodesAfter[i],
     42            Index1 = i,
     43            Index2 = i
     44          };
     45        }
     46      }
     47      // if the fragment could not be identified by reference comparison, we try to identify it by comparing node labels
     48      // the fragment root will be the lowest common ancestor of all the differing nodes
     49      if (fragment == null) {
     50        var list = new List<ISymbolicExpressionTreeNode>();
     51        var root = ChildParameter.ActualValue.Root;
    5052
    51         bool found = false;
    52         if (comparer.Equals(a, b)) {
    53           int m = 0;
    54           for (int j = 0; j < a.SubtreeCount; ++j) {
    55             if (!AreSimilar(a.GetSubtree(j), b.GetSubtree(j), comparer)) { ++m; }
    56             if (m > 1) {
    57               found = true;
    58               break;
    59             }
    60           }
    61           if (m == 0) {
    62             // everything is similar so we skip the whole subtree
    63             i += a.GetLength();
    64           }
    65           if (!found) continue;
     53        for (int i = 0; i < Math.Min(nodesBefore.Count, nodesAfter.Count); ++i) {
     54          var a = nodesAfter[i];
     55          var b = nodesBefore[i];
     56
     57          if (!Equals(a.ToString(), b.ToString())) // label comparison is sufficient
     58            list.Add(a);
    6659        }
     60
     61        var lca = LowestCommonAncestor(root, list);
     62        int index = nodesAfter.IndexOf(lca);
    6763        fragment = new Fragment<ISymbolicExpressionTreeNode> {
    68           Root = a,
    69           Index1 = i,
    70           Index2 = i
     64          Root = lca,
     65          Index1 = index,
     66          Index2 = index
    7167        };
    72         break;
    7368      }
    7469
    75       vChild.InArcs.First().Data = fragment;
     70      if (fragment == null)
     71        throw new ArgumentNullException("Could not identify fragment.");
     72
     73      childVertex.InArcs.First().Data = fragment;
    7674      return base.Apply();
    7775    }
    7876
    79     private bool AreSimilar(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
    80       int length = a.GetLength();
    81       return comparer.Equals(a, b) && length.Equals(b.GetLength()) && SymbolicExpressionTreeMatching.Match(a, b, comp) == length;
     77    private static ISymbolicExpressionTreeNode LowestCommonAncestor(ISymbolicExpressionTreeNode root, List<ISymbolicExpressionTreeNode> nodes) {
     78      if (nodes.Count == 0)
     79        throw new ArgumentException("The nodes list should contain at least one element.");
     80
     81      if (nodes.Count == 1)
     82        return nodes[0];
     83
     84      int lowestLevel = nodes.Min(x => root.GetBranchLevel(x));
     85
     86      // bring the nodes in the nodes to the same level (relative to the root)
     87      for (int i = 0; i < nodes.Count; ++i) {
     88        var node = nodes[i];
     89        var level = root.GetBranchLevel(node);
     90        for (int j = lowestLevel; j < level; ++j)
     91          node = node.Parent;
     92        nodes[i] = node;
     93      }
     94
     95      // while not all the elements in the nodes are equal, go one level up
     96      while (nodes.Any(x => x != nodes[0])) {
     97        for (int i = 0; i < nodes.Count; ++i)
     98          nodes[i] = nodes[i].Parent;
     99      }
     100
     101      return nodes[0];
    82102    }
    83103  }
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs

    r11233 r11253  
    3232      var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
    3333      var vClone = vChild.Parents.Last();
    34       vChild.InArcs.First().Data = vClone.Content.IterateNodesPrefix().ToList();
     34      vChild.InArcs.First().Data = vClone.Data.IterateNodesPrefix().ToList();
    3535
    3636      var fragment = (IFragment<ISymbolicExpressionTreeNode>)vClone.InArcs.Last().Data;
     
    3838        // this step must be performed because the fragment root actually references the original child (not the clone).
    3939        // then, a mutation operation (acting on the original child), could disrupt it
    40         fragment.Root = vClone.Content.IterateNodesPrefix().ElementAt(fragment.Index1);
     40        fragment.Root = vClone.Data.IterateNodesPrefix().ElementAt(fragment.Index1);
    4141      }
    4242
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs

    r11233 r11253  
    2424using System.IO;
    2525using System.Linq;
     26using HeuristicLab.Core;
    2627using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2728using HeuristicLab.EvolutionTracking;
     
    7475        }
    7576        var fragmentLength = fragment.Root.GetLength();
    76         var tree = node.Content;
     77        var tree = node.Data;
    7778        var subtree = tree.NodeAt(index);
    7879        var subtreeLength = subtree.GetLength();
     
    9798              // subtree contained in fragment, index stays the same
    9899            } else {
    99               index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength;
     100              index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
    100101            }
    101102          } else if (subtreeIndex < fragment.Index1) {
     
    131132              // fragment distinct from subtree
    132133              node = parents[0]; // take first parent which contains the subtree
    133               index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
     134              index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
    134135            }
    135136            continue;
     
    150151              yield return fragmentNode;
    151152
    152               if (parents[1].Content.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
     153              if (parents[1].Data.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
    153154                throw new Exception("Fragment lengths should match!");
    154155              }
Note: See TracChangeset for help on using the changeset viewer.