placenode2.java

wekaUT是 university texas austin 开发的基于weka的半指导学习(semi supervised learning)的分类器

/*
 *    This program 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 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program 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 this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    PlaceNode2.java
 *    Copyright (C) 1999 Malcolm Ware
 *
 */

package weka.gui.treevisualizer;

import java.util.*;

/**
 * This class will place the Nodes of a tree. <p>
 * 
 * It will place these nodes so that they fall at evenly below their parent.
 * It will then go through and look for places where nodes fall on the wrong 
 * side of other nodes
 * when it finds one it will trace back up the tree to find the first common 
 * sibling group these two nodes have
 * And it will adjust the spacing between these two siblings so that the two 
 * nodes no longer overlap.
 * This is nasty to calculate with , and takes a while with the current 
 * algorithm I am using to do this.<p>
 *
 *
 * @author Malcolm Ware ([e-mail])
 * @version $Revision: 1.1.1.1 $
 */
public class PlaceNode2 implements NodePlace {
  /** The space each row will take up. */
  private double m_yRatio;

  /** An array that lists the groups and information about them. */
  private Group[] m_groups;

  /** An array that lists the levels and information about them. */
  private Level[] m_levels;

  /** The Number of groups the tree has */
  private int m_groupNum;

  /** The number of levels the group tree has */
  private int m_levelNum;
  
  /** 
   * The Funtion to call to have the nodes arranged.
   *
   * @param r The top node of the tree to arrange.
   */
  public void place(Node r) {
    //note i might write count groups into the node class as well as
    //it may be useful too;
    
    m_groupNum = Node.getGCount(r,0); //i could swap over to the node class 
    //group count,but this works os i'm not gonna
    m_groups = new Group[m_groupNum];
        
    for (int noa = 0;noa < m_groupNum;noa++) {
      m_groups[noa] = new Group();
      m_groups[noa].m_gap = 3;
      m_groups[noa].m_start = -1;
    }
    
    groupBuild(r);
    m_levelNum = Node.getHeight(r,0);
    m_yRatio = 1 / (double)(m_levelNum + 1);
    
    m_levels = new Level[m_levelNum];
    
    for (int noa = 0;noa < m_levelNum;noa++) {
      m_levels[noa] = new Level();
    }
    r.setTop(m_yRatio);
    yPlacer();
    r.setCenter(0);
    xPlacer(0);


    //ok now i just have to untangle then scale down
    //note instead of starting with coords between 1 and 0 i will
    //use ints then scale them down 
    //i will scale them down either by all relative to the largest
    //line or by each line individually

    untangle2();
    
    scaleByMax();
    //scaleByInd();
  }


  /*
  private void thinner()
  {
    //what this function does is it retains the symmetry of the
     // parent node about the children but the children are no longer evenly
      //spaced this stops children from being pushed too far to the sides
      //,note this algorithm may need the method altered as it may 
     // require heavy optimisation to go at any decent speed   
  
    Node r,s;
    Edge e;
    double parent_x;
    for (int noa = group_num - 1;noa >= 0;noa--)
      {
	Vector shifts = new Vector(20,10);
	shifts.addElement(0);
	int g_num = 0;//this is the offset from groups.m_start to get the right 1
	r = groups[noa].m_p;
	parent_x = r.getCenter();
	for (int nob = 1;(e = r.getChild(nob)) != null;nob++)
	  {
	    double margin;
	    s = e.getTarget();
	    margin = s_getCenter - r.getChild(nob - 1).getTarget().getCenter-1
	             - shift.elementAt(nob-1);
	    if (margin > 0)
	      {
		margin = check_down(s,g_num,margin);
		if (margin > 0)
		  {
		    shift.addElement(-margin);
		  }
		else
		  {
		    shift.addElement(0);
		  }
	      }
	    else
	      {
		shift.addElement(0);
	      }
	    if (s.getChild(0) != null)
	      {
		g_num++;
	      }
	  }
      }
  }


  private double check_down(Node r,int gn,double m)
  {
    //note i need to know where the children of the 
    //other changers are to properly overlap check
    //to do this i think the best way is to go up the other group
    //parents line and see if it goes through the current group
    //this means to save time i need to know the level that is being 
    //worked with along with the group
    
    Edge e;
    for (int noa = 0;(e = r.getChild(noa)) != null;noa++)
      {
	
      }
  }
*/


  /**
   * This will set initial places for the x coord of the nodes.
   * @param start The `number for the first group to start on (I think).
   */
  private void xPlacer(int start) {
    //this can be one of a few x_placers (the first)
    //it will work by placing 1 space inbetween each node
    //ie the first at 0 the second at 1 and so on
    //then it will add to this value the place of the parent 
    //node - half of the size
    //i will break this up into several functions
    //first the gap setter;
    //then the shifter
    //it will require a vector shift function added to the node class
    //i will write an additional shifter for the untangler 
    //for its particular situation

    Node r;
    Edge e;
    if (m_groupNum > 0) {
      m_groups[0].m_p.setCenter(0);
      for (int noa = start;noa < m_groupNum;noa++) {
	int nob,alter =0;
	double c = m_groups[noa].m_gap;
	r = m_groups[noa].m_p;
	for (nob = 0;(e = r.getChild(nob)) != null;nob++) {
	  if (e.getTarget().getParent(0) == e) {
	    e.getTarget().setCenter(nob * c);
	  }
	  else {
	    alter++;
	  }
	}
	m_groups[noa].m_size = (nob - 1 - alter) * c;
	xShift(noa);
      }
    }
  }

  /**
   * This will shift a group of nodes to be aligned under their parent.
   * @param n The group number to shift
   */
  private void xShift(int n) {
    Edge e;
    Node r = m_groups[n].m_p;
    double h = m_groups[n].m_size / 2;
    double c = m_groups[n].m_p.getCenter();
    double m = c - h;
    m_groups[n].m_left = m;
    m_groups[n].m_right = c + h;
    
    for (int noa = 0;(e = r.getChild(noa)) != null;noa++) {
      if (e.getTarget().getParent(0) == e) {
	e.getTarget().adjustCenter(m);
      }
    }
  }

  /**
   * This scales all the x values to be between 0 and 1.
   */
  private void scaleByMax() {
    //ammendment to what i may have commented before
    //this takes the lowest x and highest x  and uses that as the scaling
    //factor
    double l_x = 5000,h_x = -5000;
    for (int noa = 0;noa < m_groupNum;noa++) {
      if (l_x > m_groups[noa].m_left) {
	l_x = m_groups[noa].m_left;
      }

      if (h_x < m_groups[noa].m_right) {
	h_x = m_groups[noa].m_right;
      }
    }
    
    Edge e;
    Node r,s;
    double m_scale = h_x - l_x + 1;
    if (m_groupNum > 0) {
      r = m_groups[0].m_p;
      r.setCenter((r.getCenter() - l_x) / m_scale);
      //System.out.println("from scaler " + l_x + " " + m_scale);
      for (int noa = 0; noa < m_groupNum;noa++) {
	r = m_groups[noa].m_p;
	for (int nob = 0;(e = r.getChild(nob)) != null;nob++) {
	  s = e.getTarget();
	  if (s.getParent(0) == e) {
	    s.setCenter((s.getCenter() - l_x) / m_scale);
	  }
	}
      }
    }
  }
  
  /**
   * This scales the x values to between 0 and 1 for each individual line
   * rather than doing them all at once.
   */
  private void scaleByInd() {
    //ammendment to what i may have commented before
    //this takes the lowest x and highest x  on each line and uses that for 
    //the line in question
    double l_x,h_x;

    Edge e;
    Node r,s;
    r = m_groups[0].m_p;
    r.setCenter(.5);
    double m_scale;
    for (int noa = 0;noa < m_levelNum;noa++) {
      l_x = m_groups[m_levels[noa].m_start].m_left;
      h_x = m_groups[m_levels[noa].m_end].m_right;
      m_scale = h_x - l_x + 1;
      for (int nob = m_levels[noa].m_start; nob <= m_levels[noa].m_end;nob++) {
	r = m_groups[nob].m_p;
	for (int noc = 0;(e = r.getChild(noc)) != null;noc++) {
	  s = e.getTarget();
	  if (s.getParent(0) == e) {
	    s.setCenter((s.getCenter() - l_x) / m_scale);
	  }
	}
      }
    }
  }
  
  /**
   * This untangles the nodes so that they will will fall on the correct
   * side of the other nodes along their row.
   */
  private void untangle2() {
    Ease a;
    Edge e;
    Node r,nf = null,ns = null,mark;
    int l = 0,times = 0;
    int f,s,tf = 0,ts = 0,pf,ps;
    while ((a = overlap(l)) != null) {
      times++;
      //System.out.println("from untang 2 " + group_num);
      f = a.m_place;
      s = a.m_place + 1;
      while (f != s) {
	a.m_lev--;
	tf = f;
	ts = s;
	f = m_groups[f].m_pg;
	s = m_groups[s].m_pg;
      }
      l = a.m_lev;
      pf = 0;
      ps = 0;
      r = m_groups[f].m_p;
      mark = m_groups[tf].m_p;
      nf = null;
      ns = null;
      for (int noa = 0; nf != mark;noa++) {
	pf++;
	nf = r.getChild(noa).getTarget();
      }
      mark = m_groups[ts].m_p;
      for (int noa = pf; ns != mark;noa++) {
	ps++; //the number of gaps between the two nodes