#region License Information
/* HeuristicLab
* Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
*
* This file is part of HeuristicLab.
*
* HeuristicLab is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* HeuristicLab is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with HeuristicLab. If not, see .
*/
#endregion
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using HeuristicLab.Core;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.EvolutionTracking;
namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
public static class SymbolicDataAnalysisExpressionTracing {
public static FragmentGraph TraceSubtree(IGenealogyGraphNode graphNode, int subtreeIndex) {
var graph = new FragmentGraph();
var vertices = Trace(graphNode, subtreeIndex).ToList();
graph.AddVertices(vertices);
return graph;
}
///
/// Traces a subtree in a genealogy of individuals, tracking down it's genetic components
///
/// The point in the genealogy where to start the tracing from
/// The traced subtree preorder index in the current tree
/// The parent node in the fragment graph if there is any
///
private static IEnumerable Trace(IGenealogyGraphNode graphNode, int subtreeIndex, FragmentNode parentNode = null) {
var node = graphNode; // current node
var index = subtreeIndex; // current index
var parent = parentNode; // current parent
while (true) {
if (!node.Parents.Any()) {
// no tracing if there are no parents, return a fragment node representing the current trace
var fragmentNode = new FragmentNode(node) { SubtreeIndex = index };
if (parent != null) {
var arc = new Arc(parent, fragmentNode);
parent.AddArc(arc);
fragmentNode.AddArc(arc);
}
yield return fragmentNode;
break;
}
var parents = node.Parents.ToList();
var fragment = (IFragment)node.InArcs.Last().Data;
if (fragment == null) {
// fragment == null can only mean that the individual is the previous generation elite
// which got introduced in the next generation. skip elite, go up the graph to original individual
node = parents[0];
continue;
}
var fragmentLength = fragment.Root.GetLength();
var tree = node.Data;
var subtree = tree.NodeAt(index);
var subtreeLength = subtree.GetLength();
#region mutation tracing
if (parents.Count == 1) {
// we are tracing a mutation operation
var fragmentNode = new FragmentNode(node) {
SubtreeIndex = index,
FragmentIndex = fragment.Index1
};
if (parent != null) {
var arc = new Arc(parent, fragmentNode);
parent.AddArc(arc);
fragmentNode.AddArc(arc);
}
node = parents[0];
if (subtreeIndex == fragment.Index1) {
// index stays the same
} else if (fragment.Index1 < subtreeIndex) {
if (subtreeIndex < fragment.Index1 + fragmentLength) {
// subtree contained in fragment, index stays the same
} else {
index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
}
} else if (subtreeIndex < fragment.Index1) {
if (fragment.Index1 < subtreeIndex + subtreeLength) {
// subtree contains fragment
index = fragment.Index1;
} else {
// index stays the same
}
}
yield return fragmentNode;
var up = Trace(node, index, fragmentNode);
foreach (var v in up) { yield return v; }
break;
}
#endregion
#region crossover tracing
if (parents.Count == 2) {
// we are tracing a crossover operation
if (fragment.Index1 == index) {
node = parents[1]; // take second parent which contains the fragment
index = fragment.Index2;
continue;
}
if (fragment.Index1 < index) {
if (fragment.Index1 + fragmentLength > index) {
node = parents[1]; // fragment contains subtree, take second parent
index += fragment.Index2 - fragment.Index1; // the subtree has the same index relative to the fragment
} else {
// fragment distinct from subtree
node = parents[0]; // take first parent which contains the subtree
index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
}
continue;
}
if (fragment.Index1 > index) {
if (fragment.Index1 < index + subtreeLength) {
// subtree contains fragment => branching point in the fragment graph
var fragmentNode = new FragmentNode(node) {
SubtreeIndex = index,
FragmentIndex = fragment.Index1
};
if (parent != null) {
var arc = new Arc(parent, fragmentNode);
parent.AddArc(arc);
fragmentNode.AddArc(arc);
}
yield return fragmentNode;
if (parents[1].Data.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
throw new Exception("Fragment lengths should match!");
}
// the two paths below ("left" and "right") correspond to the subtree and the fragment, respectively
var left = Trace(parents[0], index, fragmentNode); // trace subtree
var right = Trace(parents[1], fragment.Index2, fragmentNode); // trace fragment
foreach (var v in left.Concat(right)) { yield return v; }
break;
} else {
node = parents[0]; // fragment distinct from subtree: update node, index remains unchanged
}
}
}
#endregion
}
}
private static string ViewAsText(this ISymbolicExpressionTreeNode root) {
var writer = new StringWriter();
SymbolicExpressionTreeHierarchicalFormatter.RenderNode(writer, root, string.Empty);
return writer.ToString();
}
#region some helper methods for shortening the tracing code
private static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int position) {
return NodeAt(tree.Root, position);
}
private static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
return root.IterateNodesPrefix().ElementAt(position);
}
#endregion
}
}