Thomas Kramer

IT-COW | All posts tagged 'Walker-Algorithmus'

Isolierung der Walker-Engine aus TooCoM

By Administrator at Juli 04, 2012 16:39
Filed Under: Algorithmen

Die Ontologie-Software TooCoM benutzt den optimierten Walker-Algorithmus und steht unter GPL-Lizenz, ihr Quellcode kann u. a. auf koders.com eingesehen werden.

 

Erfahrungen mit TooCoM

 

Ich habe einmal die optimierte Walker-Implementierung von TooCoM isoliert und damit getestet. Ich denke ich habe sie richtig isoliert - demnach wird der interne Walker-Algorithmus mit der layoutTree-Methode aufgerufen:

 

int maxY = Walker.layoutTree(fRootNode, (double)heightBox);

 

Was sie zurückliefert sind die x-Koordinaten des am weitesten rechts liegenden Knoten, welcher über die internen Variablen max_ordonnee und ordonnee (französisch) bestimmt wird. Aber auch wenn man berücksichtigt dass mit

 

y = maxY - node.ordonnee + heightBox + heightUsed;

 

noch Berechnungen mit der x-Koordinate namens node.ordonnee stattfinden, so dürfte die Walker-Implementierung auf keinen Fall identische x-Koordinaten für mehrere Knoten auf der gleichen Ebene zurückliefern, wie sie das in meinen Tests aber reproduzierbar tat. Ich gehe nicht von einem Isolierungsfehler aus weil das Separieren eigentlich nicht so schwer/umfangreich war.

 

Die andere Koordinate wird dort so berechnet:

 

x = ((Integer)widthLongestBox.get(new Integer(node.getLevel()))).intValue();

 

Da stellt sich mir die Frage warum hier x und y vertauscht werden. In einem kartesischen Koordinatensystem werden x für die Spalten und y für die Zeilen verwendet - in diesem Projekt ist es anders herum. Die Klasse TreeNode enthält keine Methode getLevel(), leitet aber von DefaultMutableTreeNode ab und liefert über diese Methode somit eindeutig die y-Koordinate des Knotens zurück.

 

Also das TooCoM da richtig arbeitet, davon bin ich noch nicht überzeugt. Ich will die Leistung der Autoren ausdrücklich nicht schmälern, aber meines Erachtens bekomme ich von dieser Engine eben falsche Ergebnisse - natürlich ist aber auch mein Französisch für die Quellcode-Kommentare nicht so gut. Nachfolgend jedenfalls die Isolierung.

 

Die Main-Klasse ist von mir, die TreeNode-Klasse ist gekürzt damit sie separat funktioniert und die Walker-Klasse ist praktisch unverändert. Die Frage bleibt halt warum identische x-Koordinaten für mehrere Knoten auf der gleichen Ebene zurückgeliefert werden. IMHO ist das falsch und es müssen immer unterschiedliche Werte pro Ebene erzeugt werden.

 

Main-Klasse:

import java.util.ArrayList;

/**
 *
 * Main-Klasse.
 *
 * @author $Author:  Thomas Kramer
 * @version $Revision:  $, $Date:  $ UTC
 */

public class Main
{

   /**
    * Main-Methode.
    *
    * @param args
    */

   public static void main(String[] args)
   {
      TreeNode Wurzel;
      TreeNode Knoten;
      ArrayList<TreeNode> pointerList = new ArrayList<TreeNode>();     
     
      /**
       * Erzeugung des Wurzel-Knotens und der Söhne, fest vorgegebene Hierarchie.
       */

      Wurzel = new TreeNode(15); 
      pointerList.add(Wurzel);      
     
      Knoten = Einfuegen(Wurzel, 87);  
      pointerList.add(Knoten);      
      Knoten = Einfuegen(Knoten, 95);     
      pointerList.add(Knoten);      
     
      Knoten = Einfuegen(Wurzel, 3);
      pointerList.add(Knoten);      
      Knoten = Einfuegen(Knoten, 66);
      pointerList.add(Knoten);      
     
      Knoten = Einfuegen(Wurzel, 55);
      pointerList.add(Knoten);      
      Knoten = Einfuegen(Knoten, 17);
      pointerList.add(Knoten);      

      Knoten = Einfuegen(Wurzel, 77);
      pointerList.add(Knoten);      
     
      Knoten = Einfuegen(Knoten, 90);                
      pointerList.add(Knoten);
     
      int maxY = Walker.layoutTree(Wurzel, 0);

      for (int b=0; b<pointerList.size(); b++)
      {
         System.out.println("Knoten " + pointerList.get(b).content + " auf Ebene " + pointerList.get(b).getLevel());
         /**
          * bei Unterknoten auch den Parent ausgeben.
          */

         if (pointerList.get(b).getParent() !=null)
         {
            System.out.println("Parent: " + ((TreeNode) pointerList.get(b).getParent()).content);
         }
         System.out.println("ordonnee (x-Koordinate) = " + pointerList.get(b).ordonnee);
         System.out.println("");
      }
    
   }
  
   public static TreeNode Einfuegen(TreeNode Vater, int Inhalt)
   { 
       TreeNode Knoten = new TreeNode(Inhalt);  
       (Knoten).content = Inhalt;     
       Vater.add(Knoten);            
       return Knoten;               
   } 
}

 

TreeNode-Klasse, abgeleitet von DefaultMutableTreeNode:

/**
 * This class contains the tree structure to display.
 *
 * @author Stefan Petrik,Matthieu
 *         ... gekürzt auf das wesentliche von Thomas Kramer, aber Originalcode siehe obige Autoren.
 *         ... isoliert aus TooCoM, welches unter GPL-Lizenz steht.
 * @version 23/12/2003
 */

public class TreeNode extends javax.swing.tree.DefaultMutableTreeNode
{
  //Les variables suivantes sont utilisées par l'algorthme de WALKER
  protected int ordonnee;
  protected double prelim;
  protected double mod;
  protected double shift;
  protected double change;
  protected TreeNode thread;
  protected TreeNode ancestor;
  public int content = 0;

  public TreeNode(int content){
    super(content);
    this.content = content;

    //Initialise valeurs pour WALKER
    mod = 0;
    thread = null;
    ancestor = this;

    //Initialise l'
ordonnée
    ordonnee = 0;
  }
}

 

Walker-Implementierung:

import java.util.LinkedList;
/**
 * This class display a tree in two dimensions by using the optimised Walker algorithm,
 * that is an optimized version of the Reingold-Tilford algorithm.
 *
 * @author Stefan Petrik
 * @version 23/12/2003
 */

public final class Walker{
  private static int viewDepth;
  private static int max_ordonnee;
  private static TreeNode defAncestor;
  private static double shift;
  private static double change;
  private static double midpoint;
  private static double distance;

  /** Returns the max y coordinate for the display of the tree that has r
   *  as root. */

  public static int layoutTree(TreeNode r, double heightBox){
    viewDepth = 1;
    distance = heightBox + 1.0;
    shift = change = 0.0;
    midpoint = 0.0;
    max_ordonnee = 0;
    firstWalk(r);
    secondWalk(r,-r.prelim);
    return max_ordonnee;
  }

  private static void firstWalk(TreeNode v){
    TreeNode w;
    if(v.isLeaf()){
      v.prelim = 0.0;
      if (viewDepth < v.getLevel() - 1) viewDepth = v.getLevel() - 1;
    }
    else{
      defAncestor = (TreeNode)v.getFirstChild();//ainé (à gauche)
      for(int wi = 0;wi < v.getChildCount(); wi++){
        firstWalk((TreeNode)v.getChildAt(wi));
        apportion((TreeNode)v.getChildAt(wi),defAncestor);
      }
      executeShifts(v);
      w = (TreeNode)v.getFirstChild();
      midpoint = w.prelim;
      w = (TreeNode)v.getLastChild();     
      midpoint = midpoint + w.prelim;
      midpoint = midpoint / 2.0;
      if(v.getPreviousSibling() != null){
        w = (TreeNode)v.getPreviousSibling();//frère précédent (à droite) dans la fratrie, null si v est déjà le plus à droite ou n'a pas de père
        v.prelim = w.prelim + distance;
        v.mod = v.prelim - midpoint;
      }
      else v.prelim = midpoint;     
    }
  }

  private static void secondWalk(TreeNode v, double m){
    v.ordonnee = (int)(v.prelim + m);
    if (v.ordonnee > max_ordonnee) max_ordonnee = v.ordonnee;
    TreeNode w;
    for (int wi = 0; wi < v.getChildCount(); wi++){
      w = (TreeNode)v.getChildAt(wi);
      secondWalk(w, m + v.mod);
    }
   
  }

  private static void apportion(TreeNode v, TreeNode defaultAncestor){
    //v_i = v inside, v_o = v outside, v_?_minus = v_?_gauche, v_?_plus = v_?_droit
    TreeNode v_i_plus, v_o_plus, v_i_minus, v_o_minus, w, d;
    double s_i_plus, s_o_plus, s_i_minus, s_o_minus;
    if(v.getPreviousSibling() != null){
      v_i_plus = v_o_plus = v;
      w = (TreeNode)v.getPreviousSibling();
      v_i_minus = w;
      d = (TreeNode)v_i_plus.getParent();
      v_o_minus = (TreeNode)d.getFirstChild();
      s_i_plus = v_i_plus.mod;
      s_o_plus = v_o_plus.mod;
      s_i_minus = v_i_minus.mod;
      s_o_minus = v_o_minus.mod;
      while((nextRight(v_i_minus) != null) && (nextLeft(v_i_plus) != null)){
        v_i_minus = nextRight(v_i_minus);
        v_i_plus = nextLeft(v_i_plus);
        v_o_minus = nextLeft(v_o_minus);
        v_o_plus = nextRight(v_o_plus);
        v_o_plus.ancestor = v;
        shift = v_i_minus.prelim + s_i_minus - v_i_plus.prelim - s_i_plus + distance;
        if (shift > 0.0){
          moveSubtree(getAncestor(v_i_minus, v, defAncestor), v, shift);
          s_i_plus += shift;
          s_o_plus += shift;
        }
        s_i_minus += v_i_minus.mod;
        s_i_plus += v_i_plus.mod;
        s_o_minus += v_o_minus.mod;
        s_o_plus += v_o_plus.mod;
      }
      if((nextRight(v_i_minus) != null) && (nextRight(v_o_plus) == null)){
        v_o_plus.thread = nextRight(v_i_minus);
        v_o_plus.mod = v_o_plus.mod + s_i_minus - s_o_plus;
      }
      if ((nextLeft(v_i_plus) != null) && (nextLeft(v_o_minus) == null)){
        v_o_minus.thread = nextLeft(v_i_plus);
        v_o_minus.mod = v_o_minus.mod + s_i_plus - s_o_minus;
        defAncestor = v;
      }   
    }
  }

  private static void executeShifts(TreeNode v){
    TreeNode w;
    shift = 0.0;
    change = 0.0;
    for(int wi = v.getChildCount() - 1; wi > -1; wi--){
      w = (TreeNode)v.getChildAt(wi);
      w.prelim = w.prelim + shift;
      w.mod = w.mod + shift;
      change = change + w.change;
      shift = shift + w.shift + change;
    }
  }

  private static void moveSubtree(TreeNode w_minus, TreeNode w_plus, double shift){
    //Inverse le sous-arbre courant dont la racine est w_plus -> incrémentation de w+.premlim et w+.mod par shift
    //Les autres inversions, appliquées aux arbres plus petits entre w- et w+, sont effectuées plus tard par executeShifts;
    //pour préparer cela, on ajuste w+.change, w+.shift et w-.change
    TreeNode p = (TreeNode)w_plus.getParent();
    double subtrees = p.getIndex(w_plus) - p.getIndex(w_minus);//nb d'
enfant entre w_- et w_+
    w_plus.change = w_plus.change - (shift / subtrees);
    w_plus.shift = w_plus.shift + shift;
    w_minus.change = w_minus.change + (shift / subtrees);
    w_plus.prelim = w_plus.prelim + shift;
    w_plus.mod = w_plus.mod + shift;
  }

  //noeud suivant sur le contour droit du sous-arbre dont la racine est v
  private static TreeNode nextRight(TreeNode v){
    if(!(v.isLeaf())) return (TreeNode)v.getLastChild();
    else return v.thread;
  }

  //noeud suivant sur le contour gauche du sous-arbre dont la racine est v
  private static TreeNode nextLeft(TreeNode v){
    if(!(v.isLeaf())) return (TreeNode)v.getFirstChild();
    else return v.thread;
  }

  //calcule le noeud gauche du plus ancien ancetre non-commun
  private static TreeNode getAncestor(TreeNode v_i_minus, TreeNode v, TreeNode defaultAncestor){
    TreeNode p = (TreeNode)v.getParent();
    if(p.getIndex((TreeNode)v_i_minus.getParent()) > -1)
      return (TreeNode)v_i_minus.getParent();
    else
      return defaultAncestor;
  }
 
}

 

Monats-Liste