Free cookie consent management tool by TermsFeed Policy Generator

Changeset 11211 for branches


Ignore:
Timestamp:
07/22/14 01:40:12 (10 years ago)
Author:
bburlacu
Message:

#2215: Added implementation of the BottomUpTreeDistanceCalculator in branches/HeuristicLab.BottomUpTreeDistance.

Location:
branches/HeuristicLab.BottomUpTreeDistance
Files:
6 added
2 deleted
8 edited
8 copied

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisPopulationDiversityAnalyzer.cs

    r11210 r11211  
    8080      get { return (ILookupParameter<DoubleValue>)Parameters[SimilarityValuesParmeterName]; }
    8181    }
    82     public IValueParameter<IDistanceCalculator> DistanceCalculatorParameter {
    83       get { return (IValueParameter<IDistanceCalculator>)Parameters[DistanceCalculatorParameterName]; }
     82    public IValueParameter<ISymbolicExpressionTreeDistanceCalculator> DistanceCalculatorParameter {
     83      get { return (IValueParameter<ISymbolicExpressionTreeDistanceCalculator>)Parameters[DistanceCalculatorParameterName]; }
    8484    }
    8585    #endregion
    … …  
    118118      Parameters.Add(new LookupParameter<DoubleValue>(SimilarityValuesParmeterName, ""));
    119119      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
    120       Parameters.Add(new ValueParameter<IDistanceCalculator>(DistanceCalculatorParameterName, "The distance calculator between trees.", new BottomUpDistanceCalculator()));
     120      Parameters.Add(new ValueParameter<ISymbolicExpressionTreeDistanceCalculator>(DistanceCalculatorParameterName, "The distance calculator between trees.", new BottomUpTreeDistanceCalculator()));
    121121      UpdateCounterParameter.Hidden = true;
    122122      UpdateIntervalParameter.Hidden = true;

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/Arc.cs

    r10897 r11211  
    2424using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2525
    26 namespace HeuristicLab.EvolutionTracking {
     26namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    2727  /// <summary>
    2828  /// An arc that can have a weight, a label, and can old additional information in the Data object

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/DirectedGraph.cs

    r11021 r11211  
    2929using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3030
    31 namespace HeuristicLab.EvolutionTracking {
     31namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    3232  [Item("DirectedGraph", "Generic class representing a directed graph with custom vertices and content")]
    3333  [StorableClass]

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/Interfaces/IArc.cs

    r10888 r11211  
    2121
    2222
    23 namespace HeuristicLab.EvolutionTracking {
     23namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    2424  public interface IArc {
    2525    IVertex Source { get; set; }

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/Interfaces/IDirectedGraph.cs

    r10903 r11211  
    2424using HeuristicLab.Core;
    2525
    26 namespace HeuristicLab.EvolutionTracking {
     26namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    2727  public interface IDirectedGraph : IItem {
    2828    bool Contains(IVertex vertex);

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/Interfaces/IVertex.cs

    r10897 r11211  
    2424using HeuristicLab.Core;
    2525
    26 namespace HeuristicLab.EvolutionTracking {
     26namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    2727  public interface IVertex : IItem {
    2828    event EventHandler PreContentChanged;

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/DirectedGraph/Vertex.cs

    r10903 r11211  
    2727using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2828
    29 namespace HeuristicLab.EvolutionTracking {
     29namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    3030  [StorableClass]
    3131  public class Vertex : Item, IVertex {

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r11156 r11211  
    4141    <DebugType>full</DebugType>
    4242    <Optimize>false</Optimize>
    43     <OutputPath>$(SolutionDir)\bin\</OutputPath>
     43    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    4444    <DefineConstants>DEBUG;TRACE</DefineConstants>
    4545    <ErrorReport>prompt</ErrorReport>
    … …  
    5050    <DebugType>pdbonly</DebugType>
    5151    <Optimize>true</Optimize>
    52     <OutputPath>$(SolutionDir)\bin\</OutputPath>
     52    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    5353    <DefineConstants>TRACE</DefineConstants>
    5454    <ErrorReport>prompt</ErrorReport>
    … …  
    9797      <Private>False</Private>
    9898    </Reference>
     99    <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     100      <SpecificVersion>False</SpecificVersion>
     101      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Analysis-3.3.dll</HintPath>
     102      <Private>False</Private>
     103    </Reference>
     104    <Reference Include="HeuristicLab.Collections-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     105      <SpecificVersion>False</SpecificVersion>
     106      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Collections-3.3.dll</HintPath>
     107      <Private>False</Private>
     108    </Reference>
     109    <Reference Include="HeuristicLab.Common-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     110      <SpecificVersion>False</SpecificVersion>
     111      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
     112      <Private>False</Private>
     113    </Reference>
     114    <Reference Include="HeuristicLab.Common.Resources-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     115      <SpecificVersion>False</SpecificVersion>
     116      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Common.Resources-3.3.dll</HintPath>
     117      <Private>False</Private>
     118    </Reference>
     119    <Reference Include="HeuristicLab.Core-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     120      <SpecificVersion>False</SpecificVersion>
     121      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Core-3.3.dll</HintPath>
     122      <Private>False</Private>
     123    </Reference>
     124    <Reference Include="HeuristicLab.Data-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     125      <SpecificVersion>False</SpecificVersion>
     126      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Data-3.3.dll</HintPath>
     127      <Private>False</Private>
     128    </Reference>
     129    <Reference Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     130      <SpecificVersion>False</SpecificVersion>
     131      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll</HintPath>
     132      <Private>False</Private>
     133    </Reference>
     134    <Reference Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     135      <SpecificVersion>False</SpecificVersion>
     136      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views-3.4.dll</HintPath>
     137      <Private>False</Private>
     138    </Reference>
     139    <Reference Include="HeuristicLab.Operators-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     140      <SpecificVersion>False</SpecificVersion>
     141      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Operators-3.3.dll</HintPath>
     142      <Private>False</Private>
     143    </Reference>
     144    <Reference Include="HeuristicLab.Optimization-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     145      <SpecificVersion>False</SpecificVersion>
     146      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Optimization-3.3.dll</HintPath>
     147      <Private>False</Private>
     148    </Reference>
     149    <Reference Include="HeuristicLab.Optimization.Operators-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     150      <SpecificVersion>False</SpecificVersion>
     151      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Optimization.Operators-3.3.dll</HintPath>
     152      <Private>False</Private>
     153    </Reference>
     154    <Reference Include="HeuristicLab.Parameters-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     155      <SpecificVersion>False</SpecificVersion>
     156      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Parameters-3.3.dll</HintPath>
     157      <Private>False</Private>
     158    </Reference>
     159    <Reference Include="HeuristicLab.Persistence-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     160      <SpecificVersion>False</SpecificVersion>
     161      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Persistence-3.3.dll</HintPath>
     162      <Private>False</Private>
     163    </Reference>
     164    <Reference Include="HeuristicLab.PluginInfrastructure-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     165      <SpecificVersion>False</SpecificVersion>
     166      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
     167      <Private>False</Private>
     168    </Reference>
     169    <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     170      <SpecificVersion>False</SpecificVersion>
     171      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.DataAnalysis-3.4.dll</HintPath>
     172      <Private>False</Private>
     173    </Reference>
     174    <Reference Include="HeuristicLab.Problems.Instances-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     175      <SpecificVersion>False</SpecificVersion>
     176      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll</HintPath>
     177      <Private>False</Private>
     178    </Reference>
     179    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     180      <SpecificVersion>False</SpecificVersion>
     181      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     182      <Private>False</Private>
     183    </Reference>
    99184    <Reference Include="System" />
    100185    <Reference Include="System.Core">
    … …  
    112197  </ItemGroup>
    113198  <ItemGroup>
     199    <Compile Include="Analyzers\SymbolicDataAnalysisPopulationDiversityAnalyzer.cs" />
    114200    <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectivePruningAnalyzer.cs" />
    115201    <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveValidationParetoBestSolutionAnalyzer.cs" />
    … …  
    126212      <SubType>Code</SubType>
    127213    </Compile>
     214    <Compile Include="DirectedGraph\Arc.cs" />
     215    <Compile Include="DirectedGraph\DirectedGraph.cs" />
     216    <Compile Include="DirectedGraph\Interfaces\IArc.cs" />
     217    <Compile Include="DirectedGraph\Interfaces\IDirectedGraph.cs" />
     218    <Compile Include="DirectedGraph\Interfaces\IVertex.cs" />
     219    <Compile Include="DirectedGraph\Vertex.cs" />
    128220    <Compile Include="Interfaces\IModelBacktransformator.cs" />
     221    <Compile Include="Interfaces\ISymbolicExpressionTreeDistanceCalculator.cs" />
     222    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionCompiledTreeInterpreter.cs" />
     223    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeCachedLinearInterpreter.cs" />
    129224    <Compile Include="Matching\SymbolicExpressionTreeCanonicalSorter.cs" />
    130225    <Compile Include="Matching\SymbolicExpressionTreeEqualityComparer.cs" />
    … …  
    133228    <Compile Include="Matching\SymbolicExpressionTreeNodeComparer.cs" />
    134229    <Compile Include="Matching\SymbolicExpressionTreeNodeSimilarityComparer.cs" />
     230    <Compile Include="SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs" />
    135231    <Compile Include="SymbolicExpressionTreeBacktransformator.cs" />
    136232    <Compile Include="SymbolicDataAnalysisExpressionPruningOperator.cs" />
    … …  
    231327    <Compile Include="Symbols\VariableTreeNode.cs" />
    232328    <Compile Include="TransformationToSymbolicTreeMapper.cs" />
     329    <Compile Include="TreeDistance\BottomUpTreeDistanceCalculator.cs" />
     330    <Compile Include="TreeDistance\IsomorphicTreeDistanceCalculator.cs" />
    233331    <None Include="HeuristicLab.snk" />
    234332    <None Include="Plugin.cs.frame" />
    … …  
    264362    </BootstrapperPackage>
    265363  </ItemGroup>
    266   <ItemGroup>
    267     <ProjectReference Include="..\..\HeuristicLab.Analysis\3.3\HeuristicLab.Analysis-3.3.csproj">
    268       <Project>{887425B4-4348-49ED-A457-B7D2C26DDBF9}</Project>
    269       <Name>HeuristicLab.Analysis-3.3</Name>
    270       <Private>False</Private>
    271     </ProjectReference>
    272     <ProjectReference Include="..\..\HeuristicLab.Collections\3.3\HeuristicLab.Collections-3.3.csproj">
    273       <Project>{958B43BC-CC5C-4FA2-8628-2B3B01D890B6}</Project>
    274       <Name>HeuristicLab.Collections-3.3</Name>
    275       <Private>False</Private>
    276     </ProjectReference>
    277     <ProjectReference Include="..\..\HeuristicLab.Common.Resources\3.3\HeuristicLab.Common.Resources-3.3.csproj">
    278       <Project>{0E27A536-1C4A-4624-A65E-DC4F4F23E3E1}</Project>
    279       <Name>HeuristicLab.Common.Resources-3.3</Name>
    280       <Private>False</Private>
    281     </ProjectReference>
    282     <ProjectReference Include="..\..\HeuristicLab.Common\3.3\HeuristicLab.Common-3.3.csproj">
    283       <Project>{A9AD58B9-3EF9-4CC1-97E5-8D909039FF5C}</Project>
    284       <Name>HeuristicLab.Common-3.3</Name>
    285       <Private>False</Private>
    286     </ProjectReference>
    287     <ProjectReference Include="..\..\HeuristicLab.Core\3.3\HeuristicLab.Core-3.3.csproj">
    288       <Project>{C36BD924-A541-4A00-AFA8-41701378DDC5}</Project>
    289       <Name>HeuristicLab.Core-3.3</Name>
    290       <Private>False</Private>
    291     </ProjectReference>
    292     <ProjectReference Include="..\..\HeuristicLab.Data\3.3\HeuristicLab.Data-3.3.csproj">
    293       <Project>{BBAB9DF5-5EF3-4BA8-ADE9-B36E82114937}</Project>
    294       <Name>HeuristicLab.Data-3.3</Name>
    295       <Private>False</Private>
    296     </ProjectReference>
    297     <ProjectReference Include="..\..\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding\3.4\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj">
    298       <Project>{06D4A186-9319-48A0-BADE-A2058D462EEA}</Project>
    299       <Name>HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4</Name>
    300       <Private>False</Private>
    301     </ProjectReference>
    302     <ProjectReference Include="..\..\HeuristicLab.Operators\3.3\HeuristicLab.Operators-3.3.csproj">
    303       <Project>{23DA7FF4-D5B8-41B6-AA96-F0561D24F3EE}</Project>
    304       <Name>HeuristicLab.Operators-3.3</Name>
    305       <Private>False</Private>
    306     </ProjectReference>
    307     <ProjectReference Include="..\..\HeuristicLab.Optimization.Operators\3.3\HeuristicLab.Optimization.Operators-3.3.csproj">
    308       <Project>{25087811-F74C-4128-BC86-8324271DA13E}</Project>
    309       <Name>HeuristicLab.Optimization.Operators-3.3</Name>
    310       <Private>False</Private>
    311     </ProjectReference>
    312     <ProjectReference Include="..\..\HeuristicLab.Optimization\3.3\HeuristicLab.Optimization-3.3.csproj">
    313       <Project>{14AB8D24-25BC-400C-A846-4627AA945192}</Project>
    314       <Name>HeuristicLab.Optimization-3.3</Name>
    315     </ProjectReference>
    316     <ProjectReference Include="..\..\HeuristicLab.Parameters\3.3\HeuristicLab.Parameters-3.3.csproj">
    317       <Project>{56F9106A-079F-4C61-92F6-86A84C2D84B7}</Project>
    318       <Name>HeuristicLab.Parameters-3.3</Name>
    319       <Private>False</Private>
    320     </ProjectReference>
    321     <ProjectReference Include="..\..\HeuristicLab.Persistence\3.3\HeuristicLab.Persistence-3.3.csproj">
    322       <Project>{102BC7D3-0EF9-439C-8F6D-96FF0FDB8E1B}</Project>
    323       <Name>HeuristicLab.Persistence-3.3</Name>
    324       <Private>False</Private>
    325     </ProjectReference>
    326     <ProjectReference Include="..\..\HeuristicLab.PluginInfrastructure\3.3\HeuristicLab.PluginInfrastructure-3.3.csproj">
    327       <Project>{94186A6A-5176-4402-AE83-886557B53CCA}</Project>
    328       <Name>HeuristicLab.PluginInfrastructure-3.3</Name>
    329       <Private>False</Private>
    330     </ProjectReference>
    331     <ProjectReference Include="..\..\HeuristicLab.Problems.DataAnalysis\3.4\HeuristicLab.Problems.DataAnalysis-3.4.csproj">
    332       <Project>{DF87C13E-A889-46FF-8153-66DCAA8C5674}</Project>
    333       <Name>HeuristicLab.Problems.DataAnalysis-3.4</Name>
    334       <Private>False</Private>
    335     </ProjectReference>
    336     <ProjectReference Include="..\..\HeuristicLab.Problems.Instances\3.3\HeuristicLab.Problems.Instances-3.3.csproj">
    337       <Project>{3540E29E-4793-49E7-8EE2-FEA7F61C3994}</Project>
    338       <Name>HeuristicLab.Problems.Instances-3.3</Name>
    339       <Private>False</Private>
    340     </ProjectReference>
    341     <ProjectReference Include="..\..\HeuristicLab.Random\3.3\HeuristicLab.Random-3.3.csproj">
    342       <Project>{F4539FB6-4708-40C9-BE64-0A1390AEA197}</Project>
    343       <Name>HeuristicLab.Random-3.3</Name>
    344       <Private>False</Private>
    345     </ProjectReference>
    346   </ItemGroup>
    347364  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
    348365  <!-- To modify your build process, add your task inside one of the targets below and uncomment it.

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interfaces/ISymbolicExpressionTreeDistanceCalculator.cs

    r11210 r11211  
    33
    44namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    5   public interface IDistanceCalculator : IItem {
     5  public interface ISymbolicExpressionTreeDistanceCalculator : IItem {
    66    double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2);
    77  }

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeLinearInterpreter.cs

    r11171 r11211  
    352352    }
    353353
    354     private static void PrepareInstructions(LinearInstruction[] code, Dataset dataset) {
     354    public static void PrepareInstructions(LinearInstruction[] code, Dataset dataset) {
    355355      for (int i = 0; i != code.Length; ++i) {
    356356        var instr = code[i];

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs

    r11210 r11211  
    3939    private const string MatchConstantValuesParameterName = "MatchConstantValues";
    4040
    41     private IDistanceCalculator distanceCalculator;
     41    private ISymbolicExpressionTreeDistanceCalculator distanceCalculator;
    4242
    4343    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
    … …  
    7575    }
    7676
    77     public SymbolicDataAnalysisExpressionTreeSimilarityCalculator(IDistanceCalculator distanceCalculator)
     77    public SymbolicDataAnalysisExpressionTreeSimilarityCalculator(ISymbolicExpressionTreeDistanceCalculator distanceCalculator)
    7878      : base() {
    7979      this.distanceCalculator = distanceCalculator;

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpTreeDistanceCalculator.cs

    r11210 r11211  
    2222using System;
    2323using System.Collections.Generic;
     24using System.Drawing;
    2425using System.Globalization;
    2526using System.Linq;
    … …  
    3031using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    3132using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
    32 using HeuristicLab.EvolutionTracking;
    3333using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3434
    … …  
    4040  [StorableClass]
    4141  [Item("Bottom-up distance calculator", "An operator that calculates the bottom-up distance between two symbolic expression trees.")]
    42   public class BottomUpDistanceCalculator : Item, IDistanceCalculator {
    43     public BottomUpDistanceCalculator() { }
    44 
    45     protected BottomUpDistanceCalculator(BottomUpDistanceCalculator original, Cloner cloner)
     42  public class BottomUpTreeDistanceCalculator : Item, ISymbolicExpressionTreeDistanceCalculator {
     43    public BottomUpTreeDistanceCalculator() { }
     44
     45    protected BottomUpTreeDistanceCalculator(BottomUpTreeDistanceCalculator original, Cloner cloner)
    4646      : base(original, cloner) {
    4747    }
    4848
    4949    public override IDeepCloneable Clone(Cloner cloner) {
    50       return new BottomUpDistanceCalculator(this, cloner);
    51     }
    52 
    53     private static IArc AddArc(IVertex source, IVertex target) {
    54       var arc = new Arc(source, target);
    55       source.AddForwardArc(arc);
    56       target.AddReverseArc(arc);
    57       return arc;
     50      return new BottomUpTreeDistanceCalculator(this, cloner);
     51    }
     52
     53    // return a normalized distance measure in the interval (0,1)
     54    public double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
     55      return BottomUpDistance(t1, t2) / (t1.Length + t2.Length);
     56    }
     57
     58    public static double BottomUpDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
     59      var compactedGraph = Compact(t1, t2);
     60
     61      var forwardMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
     62      var reverseMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
     63
     64      foreach (var v in t1.IterateNodesBreadth()) {
     65        if (forwardMap.ContainsKey(v)) continue;
     66        var kv = compactedGraph[v];
     67        var w = t2.IterateNodesBreadth().FirstOrDefault(x => !reverseMap.ContainsKey(x) && compactedGraph[x] == kv); // not sure of iteration order here (pre/post order or breadth), this seems to work
     68        if (w == null) continue;
     69
     70        // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly (as in the paper) because the trees are unordered (subtree order might differ)
     71        // the solution is to sort subtrees by label using IterateBreadthOrdered (this will work because the subtrees are isomorphic!) and simultaneously iterate over the two subtrees
     72        var eV = IterateBreadthOrdered(v).GetEnumerator();
     73        var eW = IterateBreadthOrdered(w).GetEnumerator();
     74
     75        while (eV.MoveNext() && eW.MoveNext()) {
     76          var s = eV.Current;
     77          var t = eW.Current;
     78          forwardMap[s] = t;
     79          reverseMap[t] = s;
     80        }
     81      }
     82
     83      int c = forwardMap.Count(x => !Label(x.Key).Equals(Label(x.Value)));
     84      double distance = c + t1.Length + t2.Length - 2 * forwardMap.Count;
     85      return distance;
    5886    }
    5987
    … …  
    6593    /// <returns>The compacted DAG representing the two trees</returns>
    6694    private static Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
    67       var K = new Dictionary<ISymbolicExpressionTreeNode, IVertex>();
    68       var F = new DisjointUnion(t1, t2);
    69       var L = new Dictionary<string, IVertex>();
    70       var Children = new Dictionary<ISymbolicExpressionTreeNode, int>();
    71       var G = new List<IVertex>();
    72 
    73       var nodes = F.Nodes.ToList();
     95      var nodesToVertices = new Dictionary<ISymbolicExpressionTreeNode, IVertex>(); // K
     96      var disjointUnion = new DisjointUnion(t1, t2); // F
     97      var labelsToVertices = new Dictionary<string, IVertex>(); // L
     98      var childrenCount = new Dictionary<ISymbolicExpressionTreeNode, int>(); // Children
     99      var vertices = new List<IVertex>(); // G
     100
     101      var nodes = disjointUnion.Nodes.ToList();
    74102
    75103      // for all leaf labels l in F
    … …  
    77105        var label = Label(l);
    78106        var z = new Vertex { Content = l, Label = label };
    79         L[z.Label] = z;
    80         G.Add(z);
    81       }
    82 
    83       var Q = new Queue<ISymbolicExpressionTreeNode>();
    84 
    85       // for all nodes
     107        labelsToVertices[z.Label] = z;
     108        vertices.Add(z);
     109      }
     110
     111      var treeNodes = new Queue<ISymbolicExpressionTreeNode>();
     112
    86113      foreach (var v in nodes) {
    87         Children[v] = v.SubtreeCount;
     114        childrenCount[v] = v.SubtreeCount;
    88115        if (v.SubtreeCount == 0) {
    89           Q.Enqueue(v);
    90         }
    91       }
    92 
    93       while (Q.Any()) {
    94         var v = Q.Dequeue();
     116          treeNodes.Enqueue(v);
     117        }
     118      }
     119
     120      while (treeNodes.Any()) {
     121        var v = treeNodes.Dequeue();
    95122        var label = Label(v);
    96123        if (v.SubtreeCount == 0) {
    97           K[v] = L[label]; // 18
     124          nodesToVertices[v] = labelsToVertices[label]; // 18
    98125        } else {
    99126          bool found = false;
    100127          // for all nodes w in G in reverse order
    101           for (int i = G.Count - 1; i >= 0; --i) {
    102             var w = G[i];
    103             if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || label != w.Label)
    104               break;
     128          for (int i = vertices.Count - 1; i >= 0; --i) {
     129            var w = vertices[i];
     130            // removed requirement for heights to be equal since a compacted dag should not care about heights
     131            // this ensures correct behavior when isomorphic subtrees are placed at different depths.
     132            // furthermore, if the nodes have the same labels and the same subtrees then that should be sufficient,
     133            // since in the bottom-up approach we are guaranteed that no differences would occur on the lower levels
     134            if (v.SubtreeCount != w.OutDegree || label != w.Label)
     135              continue;
    105136
    106137            // sort V and W because we are dealing with unordered trees
    107             var V = v.Subtrees.Select(s => K[s]).OrderBy(x => x.Label);
    108             var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
    109             if (V.SequenceEqual(W)) {
    110               K[v] = w;
     138            var vSubtrees = v.Subtrees.Select(s => nodesToVertices[s]).OrderBy(x => x.Label);
     139            var wSubtrees = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
     140            if (vSubtrees.SequenceEqual(wSubtrees)) {
     141              nodesToVertices[v] = w;
    111142              found = true;
    112143              break;
    … …  
    116147          if (!found) {
    117148            var w = new Vertex { Content = v, Label = label };
    118             G.Add(w);
    119             K[v] = w;
     149            vertices.Add(w);
     150            nodesToVertices[v] = w;
    120151
    121152            foreach (var u in v.Subtrees) {
    122               AddArc(w, K[u]);
     153              AddArc(w, nodesToVertices[u]);
    123154            } // 40: end for
    124155          } // 41: end if
    … …  
    127158        if (v.Parent != null) {
    128159          var p = v.Parent;
    129           Children[p]--;
    130           if (Children[p] == 0)
    131             Q.Enqueue(p);
     160          childrenCount[p]--;
     161          if (childrenCount[p] == 0)
     162            treeNodes.Enqueue(p);
    132163        }
    133164      };
    134165
    135       return K;
    136     }
    137 
    138     private static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> Mapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, IVertex> K) {
    139       var M = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
    140       var M_ = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
    141 
    142       var nodes2 = t2.IterateNodesPrefix().Where(x => !M_.ContainsKey(x)).ToList();
    143       foreach (var v in t1.IterateNodesBreadth().Where(x => !M.ContainsKey(x))) {
    144         var kv = K[v];
    145         var w = nodes2.LastOrDefault(x => K[x] == kv);
    146         if (w == null) continue;
    147 
    148         // simultaneous preorder traversal of the two subtrees
    149         var eV = v.IterateNodesPrefix().GetEnumerator();
    150         var eW = w.IterateNodesPrefix().GetEnumerator();
    151 
    152         while (eV.MoveNext() && eW.MoveNext()) {
    153           var s = eV.Current;
    154           var t = eW.Current;
    155           M[s] = t;
    156           M_[t] = s;
    157         }
    158       }
    159       return M;
    160     }
    161 
    162     // return a normalized distance measure in the interval (0,1)
    163     public double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
    164       return BottomUpDistance(t1, t2) / (t1.Length + t2.Length);
    165     }
    166 
    167     public static double BottomUpDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, double p = 1, double q = 1, double r = 1) {
    168       var K = Compact(t1, t2);
    169       var M = Mapping(t1, t2, K);
    170 
    171       var keys = M.Keys.ToList();
    172       for (int j = 0; j < keys.Count; ++j) {
    173         var key = keys[j];
    174         var value = M[key];
    175         if (key.Parent != null && value.Parent != null && !M.ContainsKey(key.Parent) && Label(key.Parent).Equals(Label(value.Parent))) {
    176           M.Add(key.Parent, value.Parent);
    177           keys.Add(key.Parent);
    178         }
    179       }
    180 
    181       int d = t1.Length - M.Count;
    182       int s = M.Count(x => !Label(x.Key).Equals(Label(x.Value)));
    183       int i = t2.Length - M.Count;
    184 
    185       double distance = s * p + i * q + d * r;
    186       return distance;
    187     }
     166      return nodesToVertices;
     167    }
     168
     169    private static IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node) {
     170      var list = new List<ISymbolicExpressionTreeNode> { node };
     171      int i = 0;
     172      while (i < list.Count) {
     173        var n = list[i];
     174        if (n.SubtreeCount > 0)
     175          list.AddRange(n.Subtrees.OrderBy(Label));
     176        i++;
     177      }
     178      return list;
     179    }
     180
     181    private static IArc AddArc(IVertex source, IVertex target) {
     182      var arc = new Arc(source, target);
     183      source.AddForwardArc(arc);
     184      target.AddReverseArc(arc);
     185      return arc;
     186    }
     187
    188188
    189189    private static string Label(ISymbolicExpressionTreeNode n) {
    … …  
    208208
    209209      public IEnumerable<ISymbolicExpressionTreeNode> Nodes {
    210         get {
    211           var r1 = Item1.Root;
    212           var r2 = Item2.Root;
    213 
    214           var nodes = r1.IterateNodesPostfix().Select(x => new { Node = x, Height = r1.GetBranchLevel(x) })
    215             .Concat(r2.IterateNodesPostfix().Select(x => new { Node = x, Height = r2.GetBranchLevel(x) }));
    216 
    217           return nodes.OrderByDescending(x => x.Height).Select(x => x.Node);
    218         }
     210        get { return Item1.Root.IterateNodesPostfix().Concat(Item2.Root.IterateNodesPostfix()); }
    219211      }
    220212    }
    … …  
    227219    // draw the mapping between t1 and t2 as a tikz picture
    228220    private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
    229       var formatter = new SymbolicExpressionTreeLatexFormatter();
     221      var symbolNameMap = new Dictionary<string, string>
     222    {
     223      {"ProgramRootSymbol", "Prog"},
     224      {"StartSymbol","RPB"},
     225      {"Multiplication", "$\\times$"},
     226      {"Division", "$\\div$"},
     227      {"Addition", "$+$"},
     228      {"Subtraction", "$-$"},
     229      {"Exponential", "$\\exp$"},
     230      {"Logarithm", "$\\log$"}
     231    };
     232
    230233      var sb = new StringBuilder();
    231 
    232       string s1, s2;
    233       var m1 = formatter.Format(t1, out s1);
    234       var m2 = formatter.Format(t2, out s2, 20);
    235 
    236       // skip first 6 lines of s2
    237       s2 = RemoveFirstLines(s2, 6);
    238 
    239       sb.Append(s1);
    240       sb.Append(s2);
     234      var nodeIds = new Dictionary<ISymbolicExpressionTreeNode, string>();
     235      int offset = 0;
     236      var layoutEngine = new ReingoldTilfordLayoutEngine<ISymbolicExpressionTreeNode>(x => x.Subtrees);
     237      var nodeCoordinates = layoutEngine.CalculateLayout(t1.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
     238
     239      double ws = 0.5;
     240      double hs = 0.5;
     241
     242      var nl = Environment.NewLine;
     243      sb.Append("\\documentclass[class=minimal,border=0pt]{standalone}" + nl +
     244                 "\\usepackage{tikz}" + nl +
     245                 "\\begin{document}" + nl +
     246                 "\\begin{tikzpicture}" + nl +
     247                 "\\def\\ws{1}" + nl +
     248                 "\\def\\hs{0.7}" + nl +
     249                 "\\def\\offs{" + offset + "}" + nl);
     250
     251      foreach (var node in t1.IterateNodesBreadth()) {
     252        var id = Guid.NewGuid().ToString();
     253        nodeIds[node] = id;
     254        var coord = nodeCoordinates[node];
     255        var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
     256        sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1} + \\offs,\\hs*{2}) {{{3}}};", nodeIds[node], ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
     257      }
     258
     259      foreach (ISymbolicExpressionTreeNode t in t1.IterateNodesBreadth()) {
     260        var n = t;
     261        foreach (var s in t.Subtrees) {
     262          sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
     263        }
     264      }
     265
     266      nodeCoordinates = layoutEngine.CalculateLayout(t2.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
     267
     268      offset = 20;
     269      sb.Append("\\def\\offs{" + offset + "}" + nl);
     270      foreach (var node in t2.IterateNodesBreadth()) {
     271        var id = Guid.NewGuid().ToString();
     272        nodeIds[node] = id;
     273        var coord = nodeCoordinates[node];
     274        var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
     275        sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1} + \\offs,\\hs*{2}) {{{3}}};", nodeIds[node], ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
     276      }
     277
     278      foreach (ISymbolicExpressionTreeNode t in t2.IterateNodesBreadth()) {
     279        var n = t;
     280        foreach (var s in t.Subtrees) {
     281          sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
     282        }
     283      }
    241284
    242285      foreach (var p in map) {
    243         var id1 = m1[p.Key];
    244         var id2 = m2[p.Value];
    245 
    246         sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->] ({0}) edge[bend left,dashed] ({1});" + Environment.NewLine, id1, id2));
    247       }
    248 
     286        var id1 = nodeIds[p.Key];
     287        var id2 = nodeIds[p.Value];
     288
     289        sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->,color=gray] ({0}) edge[bend left,dashed] ({1});" + Environment.NewLine, id1, id2));
     290      }
     291      sb.Append("\\end{tikzpicture}" + nl +
     292                "\\end{document}" + nl);
    249293      return sb.ToString();
    250294    }
    251295
     296    private static string EscapeLatexString(string s) {
     297      return s.Replace("\\", "\\\\").Replace("{", "\\{").Replace("}", "\\}").Replace("_", "\\_");
     298    }
    252299  }
    253300}

  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/IsomorphicTreeDistanceCalculator.cs

    r11210 r11211  
    1 using HeuristicLab.Common;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2014 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 HeuristicLab.Common;
    223using HeuristicLab.Core;
    324using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    526
    6 namespace HeuristicLab.Problems.DataAnalysis.Symbolic.TreeDistance {
     27namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    728  [StorableClass]
    829  [Item("Isomorphic tree distance calculator", "An operator that computes the distance between two symbolic expression trees based on the size of their largest common subtree.")]
    9   public class IsomorphicTreeDistanceCalculator : Item, IDistanceCalculator {
     30  public class IsomorphicTreeDistanceCalculator : Item, ISymbolicExpressionTreeDistanceCalculator {
    1031    private readonly SymbolicExpressionTreeNodeSimilarityComparer comparer;
    1132
Note: See TracChangeset for help on using the changeset viewer.