source: src/main/java/weka/gui/graphvisualizer/HierarchicalBCEngine.java @ 16

/*
 *    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.
 */

/*
 *    HierarchicalBCEngine.java
 *    Copyright (C) 2003 University of Waikato, Hamilton, New Zealand
 *
 */

package weka.gui.graphvisualizer;

import weka.core.FastVector;
import weka.gui.graphvisualizer.GraphNode;
import weka.gui.graphvisualizer.GraphEdge;

import javax.swing.JPanel;
import javax.swing.JRadioButton;
import javax.swing.JCheckBox;
import javax.swing.ButtonGroup;
import javax.swing.BorderFactory;
import javax.swing.JProgressBar;

import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;
import java.awt.GridBagLayout;
import java.awt.GridBagConstraints;

/**
 * This class lays out the vertices of a graph in a
 * hierarchy of vertical levels, with a number of nodes
 * in each level. The number of levels is the depth of
 * the deepest child reachable from some parent at level
 * 0. It implements a layout technique as described by
 * K. Sugiyama, S. Tagawa, and M. Toda. in "Methods for
 * visual understanding of hierarchical systems", IEEE
 * Transactions on Systems, Man and Cybernetics,
 * SMC-11(2):109-125, Feb. 1981.
 * <p>There have been a few modifications made, however.
 * The crossings function is changed as it was non-linear
 * in time complexity. Furthermore, we don't have any
 * interconnection matrices for each level, instead we
 * just have one big interconnection matrix for the
 * whole graph and a int[][] array which stores the
 * vertices present in each level.
 *
 * @author Ashraf M. Kibriya (amk14@cs.waikato.ac.nz)
 * @version $Revision: 1.6 $ - 24 Apr 2003 - Initial version (Ashraf M. Kibriya)
 *
 */
public class HierarchicalBCEngine implements GraphConstants, LayoutEngine {
  
  /** FastVector containing nodes and edges */
  protected FastVector m_nodes, m_edges;
  /**  FastVector containing listeners for
    * layoutCompleteEvent generated by this
    * LayoutEngine  */
  protected FastVector layoutCompleteListeners;
  /**   Interconnection matrix for the graph  */
  protected int graphMatrix[][];
  /** Array containing the indices of nodes in each level.
    * The nodeLevels.length is equal to the number of levels  */
  protected int nodeLevels[][];
  /** The nodeWidth and nodeHeight */
  protected int m_nodeWidth, m_nodeHeight;
  
  /* The following radio buttons control the
     way the layout is performed. If any
     of the following is changed then we
     need to perform a complete relayout
   */
  protected JRadioButton m_jRbNaiveLayout;
  protected JRadioButton m_jRbPriorityLayout;
  protected JRadioButton m_jRbTopdown;
  protected JRadioButton m_jRbBottomup;
  
  /** controls edge concentration by concentrating multilple singular dummy
   * child nodes into one plural dummy child node
   */
  protected JCheckBox m_jCbEdgeConcentration;
  
  /** The panel containing extra options,
   * specific to this LayoutEngine, for
   * greater control over layout of the graph */
  protected JPanel m_controlsPanel;
  
  /** The progress bar to show the progress
   * of the layout process */
  protected JProgressBar m_progress;
  
  /** This tells the the LayoutGraph method if
   * a completeReLayout should be performed
   * when it is called. */
  protected boolean m_completeReLayout=false;
  
  /** This contains the original size of the nodes vector
   * when it was passed in through the constructor, before
   * adding all the dummy vertices */
  private int origNodesSize;
  
  /** Constructor - takes in FastVectors of nodes and edges, and the initial
   *  width and height of a node
   */
  public HierarchicalBCEngine(FastVector nodes, FastVector edges, int nodeWidth, 
                              int nodeHeight) {
    m_nodes = nodes; m_edges = edges; m_nodeWidth = nodeWidth; 
    m_nodeHeight = nodeHeight;
    makeGUIPanel(false);
  }
  
  /** Constructor - takes in FastVectors of nodes and edges, the initial width
   * and height of a node, and a boolean value to indicate if the edges
   * should be concentrated.
   * @param nodes - FastVector containing all the nodes
   * @param edges - FastVector containing all the edges
   * @param nodeWidth - A node's allowed width
   * @param nodeHeight - A node's allowed height
   * @param edgeConcentration - True: if want to concentrate edges,
   * False: otherwise
   */
  public HierarchicalBCEngine(FastVector nodes, FastVector edges,
  int nodeWidth, int nodeHeight, boolean edgeConcentration) {
    m_nodes = nodes; m_edges = edges; m_nodeWidth = nodeWidth; 
    m_nodeHeight = nodeHeight;
    makeGUIPanel(edgeConcentration);
  }
  
  /** SimpleConstructor
   * If we want to instantiate the class first, and if information for
   * nodes and edges is not available. However, we would have to manually
   * provide all the information later on by calling setNodesEdges and
   * setNodeSize methods
   */
  public HierarchicalBCEngine() {   }
  
  /**
   * This methods makes the gui extra controls panel "m_controlsPanel"
   */
  protected void makeGUIPanel(boolean edgeConc) {
    m_jRbNaiveLayout = new JRadioButton("Naive Layout");
    m_jRbPriorityLayout = new JRadioButton("Priority Layout");
    ButtonGroup bg = new ButtonGroup();
    bg.add(m_jRbNaiveLayout);
    bg.add(m_jRbPriorityLayout);
    m_jRbPriorityLayout.setSelected(true);
    
    ActionListener a = new ActionListener() {
      public void actionPerformed(ActionEvent ae) {
        m_completeReLayout=true;
      }
    };
    
    m_jRbTopdown = new JRadioButton("Top Down");
    m_jRbBottomup = new JRadioButton("Bottom Up");
    m_jRbTopdown.addActionListener(a);
    m_jRbBottomup.addActionListener(a);
    bg = new ButtonGroup();
    bg.add(m_jRbTopdown);
    bg.add(m_jRbBottomup);
    m_jRbBottomup.setSelected(true);
    
    m_jCbEdgeConcentration = new JCheckBox("With Edge Concentration", edgeConc);
    m_jCbEdgeConcentration.setSelected(edgeConc);
    m_jCbEdgeConcentration.addActionListener(a);
    
    JPanel jp1 = new JPanel( new GridBagLayout() );
    GridBagConstraints gbc = new GridBagConstraints();
    gbc.gridwidth = gbc.REMAINDER;
    gbc.anchor = gbc.NORTHWEST;
    gbc.weightx = 1;
    gbc.fill = gbc.HORIZONTAL;
    jp1.add(m_jRbNaiveLayout, gbc);
    jp1.add(m_jRbPriorityLayout, gbc);
    jp1.setBorder( BorderFactory.createTitledBorder("Layout Type") );
    
    JPanel jp2 = new JPanel( new GridBagLayout() );
    jp2.add(m_jRbTopdown, gbc);
    jp2.add(m_jRbBottomup, gbc);
    jp2.setBorder( BorderFactory.createTitledBorder("Layout Method") );
    
    
    m_progress = new JProgressBar(0, 11);
    m_progress.setBorderPainted(false);
    m_progress.setStringPainted(true);
    m_progress.setString("");
    
    m_progress.setValue(0);
    
    m_controlsPanel = new JPanel( new GridBagLayout() );
    m_controlsPanel.add(jp1, gbc);
    m_controlsPanel.add(jp2, gbc);
    m_controlsPanel.add(m_jCbEdgeConcentration, gbc);
  }
  
    /** give access to set of graph nodes */
    public FastVector getNodes() {
        return m_nodes;
    }
  
  /** This method returns a handle to the extra
   * controls panel, so that the visualizing
   * class can add it to some of it's own
   * gui panel.
   */
  public JPanel getControlPanel() {
    return m_controlsPanel;
  }
  
  /** Returns a handle to the progressBar
   * of this LayoutEngine.
   */
  public JProgressBar getProgressBar() {
    return m_progress;
  }
  
  /** Sets the nodes and edges for this LayoutEngine.
   * Must be used if the class created by simple
   * HierarchicalBCEngine() constructor.
   * @param nodes - FastVector containing all the nodes
   * @param edges - FastVector containing all the edges
   */
  public void setNodesEdges(FastVector nodes, FastVector edges) {
    m_nodes = nodes; m_edges = edges;
  }
  
  /**
   * Sets the size of a node. This method must be
   *    used if the class created by simple
   *    HierarchicalBCEngine() constructor.
   *    @param nodeWidth - A node's allowed width
   *    @param nodeHeight - A node's allowed height
   */
  public void setNodeSize(int nodeWidth, int nodeHeight) {
    m_nodeWidth = nodeWidth;
    m_nodeHeight = nodeHeight;
  }
  
  /**
   * Method to add a LayoutCompleteEventListener
   * @param l - Listener to receive the LayoutCompleteEvent by this
   *            class.
   */
  public void addLayoutCompleteEventListener(LayoutCompleteEventListener l) {
    if(layoutCompleteListeners==null)
      layoutCompleteListeners = new FastVector();
    layoutCompleteListeners.addElement(l);
  }
  
  /**
   * Method to remove a LayoutCompleteEventListener.
   * @param e - The LayoutCompleteEventListener to remove.
   */
  public void removeLayoutCompleteEventListener(LayoutCompleteEventListener e){
    if(layoutCompleteListeners!=null) {
      LayoutCompleteEventListener l;
      
      for(int i=0; i<layoutCompleteListeners.size(); i++) {
        l = (LayoutCompleteEventListener) layoutCompleteListeners.elementAt(i);
        if(l==e) {
          layoutCompleteListeners.removeElementAt(i);
          return;
        }
      }
      System.err.println("layoutCompleteListener to be remove not present");
    }
    else
      System.err.println("layoutCompleteListener to be remove not present");
  }
  
  /**
   * Fires a LayoutCompleteEvent.
   * @param e - The LayoutCompleteEvent to fire
   */
  public void fireLayoutCompleteEvent(LayoutCompleteEvent e) {
    if(layoutCompleteListeners!=null && layoutCompleteListeners.size()!=0) {
      LayoutCompleteEventListener l;
      
      for(int i=0; i<layoutCompleteListeners.size(); i++) {
        l = (LayoutCompleteEventListener) layoutCompleteListeners.elementAt(i);
        l.layoutCompleted(e);
      }
    }
  }
  
  
  /**
   * This method does a complete layout of the graph which includes
   * removing cycles, assigning levels to nodes, reducing edge crossings
   * and laying out the vertices horizontally for better visibility.
   * The removing of cycles and assignment of levels is only performed
   * if hasn't been performed earlier or if some layout option has been
   * changed and it is necessary to do so. It is necessary to do so,
   * if the user selects/deselects edge concentration or topdown/bottomup
   * options.
   * <p> The layout is performed in a separate thread and the progress
   * bar of the class is updated for each of the steps as the process
   * continues.
   */
  public void layoutGraph() {
  //cannot perform a layout if no description of nodes and/or edges is provided
    if(m_nodes==null || m_edges==null)
      return; 
    
    Thread th = new Thread() {
      public void run() {
        m_progress.setBorderPainted(true);
        if(nodeLevels==null) {
          makeProperHierarchy();
        }
        else if(m_completeReLayout==true) {
          clearTemps_and_EdgesFromNodes(); makeProperHierarchy(); 
          m_completeReLayout=false;
        }
        
        //minimizing crossings
        if(m_jRbTopdown.isSelected()) {
          int crossbefore=crossings(nodeLevels), crossafter=0, i=0;
          do {
            m_progress.setValue(i+4);
            m_progress.setString("Minimizing Crossings: Pass"+(i+1));
            if(i!=0)
              crossbefore = crossafter;
            nodeLevels = minimizeCrossings(false, nodeLevels);
            crossafter = crossings(nodeLevels);
            i++;
          }
          while(crossafter<crossbefore && i<6);
        }
        else {
          int crossbefore=crossings(nodeLevels), crossafter=0, i=0;
          do {
            m_progress.setValue(i+4);
            m_progress.setString("Minimizing Crossings: Pass"+(i+1));
            if(i!=0)
              crossbefore = crossafter;
            nodeLevels = minimizeCrossings(true, nodeLevels);
            crossafter = crossings(nodeLevels);
            i++;
          }
          while(crossafter<crossbefore && i<6);
        }
        //System.out.println("\nCrossings at the end "+
        //                   crossings(nodeLevels)+
        //                   "\n---------------------------------");
        
        m_progress.setValue(10);
        m_progress.setString("Laying out vertices");
        //Laying out graph
        if(m_jRbNaiveLayout.isSelected())
          naiveLayout();
        else
          priorityLayout1();
        m_progress.setValue(11);
        m_progress.setString("Layout Complete");
        m_progress.repaint();
        
        fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
        m_progress.setValue(0);
        m_progress.setString("");
        m_progress.setBorderPainted(false);
      }
    };
    th.start();
  }
  
  /**
   * This method removes the temporary nodes that were
   * added to fill in the gaps, and removes all edges
   * from all nodes in their edges[][] array
   */
  protected void clearTemps_and_EdgesFromNodes() {
    /*
    System.out.println("Before.............");
    for(int i=0; i<m_nodes.size(); i++) {
      GraphNode n = (GraphNode)m_nodes.elementAt(i);
      System.out.println("N: "+n.ID+","+i);
    }
    System.out.println("origNodesSize: "+origNodesSize);
    */
    
    int curSize = m_nodes.size();
    for(int i=origNodesSize; i<curSize; i++)
      m_nodes.removeElementAt(origNodesSize);
    for(int j=0; j<m_nodes.size(); j++)
      ((GraphNode)m_nodes.elementAt(j)).edges = null;
    
    nodeLevels=null;
    
    /*
    System.out.println("After..............");
    for(int i=0; i<m_nodes.size(); i++) {
      GraphNode n = (GraphNode)m_nodes.elementAt(i);
      System.out.println("N: "+n.ID+","+i);
    }
    */
  }
  
  /**
   * This method makes the "graphMatrix" interconnection
   * matrix for the graph given by m_nodes and m_edges
   * vectors. The matix is used by other methods.
   */
  protected void processGraph() {
    origNodesSize = m_nodes.size();
    graphMatrix = new int[m_nodes.size()][m_nodes.size()];
    /*
    System.out.println("The "+m_nodes.size()+" nodes are: ");
    for(int i=0; i<m_nodes.size(); i++)
      System.out.println((String)m_nodes.elementAt(i)+" ");
    System.out.println("\nThe "+m_edges.size()+" edges are: ");
    for(int i=0; i<m_edges.size(); i++)
      System.out.println((GraphEdge)m_edges.elementAt(i));
    */
    for(int i=0; i<m_edges.size(); i++)
      graphMatrix[((GraphEdge)m_edges.elementAt(i)).src]
                 [((GraphEdge)m_edges.elementAt(i)).dest] = 
                                         ((GraphEdge)m_edges.elementAt(i)).type;
    /*
    System.out.print("\t");
    for(int i=0; i<graphMatrix.length; i++)
      System.out.print(((GraphNode)m_nodes.elementAt(i)).ID+" ");
    System.out.println("");
    for(int i=0; i<graphMatrix.length; i++) {
      GraphNode n = (GraphNode)m_nodes.elementAt(i);
      System.out.print(n.ID+"\t");
      for(int j=0; j<graphMatrix[i].length; j++)
        System.out.print(graphMatrix[i][j]+" ");
      System.out.println("");
    }
    */
  }
  
  /*
   * This method makes a proper hierarchy of the graph
   * by first removing cycles, then assigning levels
   * to the nodes and then removing gaps by adding
   * dummy vertices.
   */
  protected void makeProperHierarchy() {
    processGraph();
    
    m_progress.setValue(1);
    m_progress.setString("Removing Cycles");
    //****removing cycles
    removeCycles();
    
    m_progress.setValue(2);
    m_progress.setString("Assigning levels to nodes");
    //****Assigning vertical level to each node
    int nodesLevel[] = new int[m_nodes.size()];
    int depth=0;
    for(int i=0; i<graphMatrix.length; i++) {
      assignLevels(nodesLevel, depth, i, 0);
    }
    
    for(int i=0; i<nodesLevel.length; i++) {
      if(nodesLevel[i]==0) {
        int min=65536;
        for(int j=0; j<graphMatrix[i].length; j++) {
          if(graphMatrix[i][j]==DIRECTED)
            if(min>nodesLevel[j])
              min = nodesLevel[j];
        }
        //if the shallowest child of a parent has a depth greater than 1
        // and it is not a lone parent with no children
        if(min!=65536 && min>1) 
          nodesLevel[i]=min-1;       
      }
    }
    
    //System.out.println("");
    int maxLevel=0;
    for(int i=0; i<nodesLevel.length; i++) {
      if(nodesLevel[i]>maxLevel)
        maxLevel = nodesLevel[i];
      //System.out.println( ((GraphNode)m_nodes.elementAt(i)).ID+" "+i+">"+
      //                    nodesLevel[i]);
    }
    int levelCounts[] = new int[maxLevel+1];
    
    for(int i=0; i<nodesLevel.length; i++) {
      levelCounts[nodesLevel[i]]++;
    }
    //System.out.println("------------------------------------------");
    //****Assigning nodes to each level
    int levelsCounter[] = new int[maxLevel+1];
    nodeLevels = new int[maxLevel+1][];
    for(byte i=0; i<nodesLevel.length; i++) {
      if(nodeLevels[nodesLevel[i]]==null)
        nodeLevels[nodesLevel[i]] = new int[ levelCounts[nodesLevel[i]] ];
      //nodeLevels[nodesLevel[i]].addElement(new Integer(i));
      //System.out.println(((GraphNode)m_nodes.elementAt(i)).ID+" "+
      //                   nodesLevel[i]+">"+levelCounts[nodesLevel[i]]);
      nodeLevels[nodesLevel[i]][levelsCounter[nodesLevel[i]]++] = i;
    }
    
    m_progress.setValue(3);
    m_progress.setString("Removing gaps by adding dummy vertices");
    //*Making a proper Hierarchy by putting in dummy vertices to close all gaps
    if(m_jCbEdgeConcentration.isSelected())
      removeGapsWithEdgeConcentration(nodesLevel);
    else
      removeGaps(nodesLevel);
    
    //After assigning levels and adding dummy vertices
    //System.out.print("\n\t");
    //for(int i=0; i<graphMatrix.length; i++)
    //    System.out.print(((GraphNode)m_nodes.elementAt(i)).ID+" ");
    //System.out.println("");
    //for(int i=0; i<graphMatrix.length; i++) {
    //    System.out.print(((GraphNode)m_nodes.elementAt(i)).ID+"\t");
    //    for(int j=0; j<graphMatrix[i].length; j++)
    //  System.out.print(graphMatrix[i][j]+" ");
    //    System.out.println("");
    //}
    
    //****Updating edges[][] array of nodes from
    //****the interconnection matrix, which will be used
    //****by the Visualizer class to draw edges
    for(int i=0; i<graphMatrix.length; i++) {
      GraphNode n = (GraphNode)m_nodes.elementAt(i);
      int sum=0;
      for(int j=0; j<graphMatrix[i].length; j++)
        if(graphMatrix[i][j]!=0)
          sum++;
      
      n.edges = new int[sum][2];
      for(int j=0, k=0; j<graphMatrix[i].length; j++)
        if(graphMatrix[i][j]!=0) {
          n.edges[k][0] = j;
          n.edges[k][1] = graphMatrix[i][j]; k++;
        }
      //n.edges = graphMatrix[i];
    }
    
    //Interconnection matrices at each level, 1 to n-1
    //printMatrices(nodeLevels);
  }
  
  
  /**
   * This method removes gaps from the graph. It doesn't perform
   * any concentration. It takes as an argument of int[]
   * of length m_nodes.size() containing the level of each
   * node.
   */
  private void removeGaps(int nodesLevel[]) {
    int temp = m_nodes.size();
    int temp2=graphMatrix[0].length, tempCnt=1;
    
    for(int n=0; n<temp; n++) {
      for(int i=0; i<temp2; i++) {
        int len = graphMatrix.length;
        if(graphMatrix[n][i]>0)
          if(nodesLevel[i]>nodesLevel[n]+1) {
            int tempMatrix[][] =
            new int[graphMatrix.length+(nodesLevel[i]-nodesLevel[n]-1)]
                   [graphMatrix.length+(nodesLevel[i]-nodesLevel[n]-1)];
            int level = nodesLevel[n]+1;
            copyMatrix(graphMatrix, tempMatrix);
            
            String s1 = new String("S"+tempCnt++);
            m_nodes.addElement(new GraphNode(s1, s1, SINGULAR_DUMMY)); //true));
            int temp3 [] = new int[nodeLevels[level].length+1];
            //for(int j=0; j<nodeLevels[level].length; j++)
            //    temp3[j] = nodeLevels[level][j];
            System.arraycopy(nodeLevels[level], 0, temp3, 
                             0, nodeLevels[level].length);
            temp3[temp3.length-1] = m_nodes.size()-1;
            nodeLevels[level] = temp3; level++;
            //nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
            //System.out.println("len:"+len+","+nodesLevel[i]+","+
            //                   nodesLevel[n]);
            
            int k;
            for(k=len; k<len+nodesLevel[i]-nodesLevel[n]-1-1; k++) {
              String s2 =  new String("S"+tempCnt);
              m_nodes.addElement( new GraphNode(s2, s2, SINGULAR_DUMMY) ); //true) );
              temp3 = new int[nodeLevels[level].length+1];
              //for(int j=0; j<nodeLevels[level].length; j++)
              //        temp3[j] = nodeLevels[level][j];
              System.arraycopy(nodeLevels[level], 0, temp3, 
                               0, nodeLevels[level].length);
              temp3[temp3.length-1] = m_nodes.size()-1;
              nodeLevels[level++] = temp3;
              //nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
              tempMatrix[k][k+1]=tempMatrix[n][i]; tempCnt++;
              if(k>len)
                tempMatrix[k][k-1]=-1*tempMatrix[n][i];
            }
            
            //temp[lastTempNodeCreated][targetNode]=temp[origNode][targetNode]
            tempMatrix[k][i]=tempMatrix[n][i];
            //System.out.println("k "+((GraphNode)m_nodes.elementAt(k)).ID+
            //             " i "+((GraphNode)m_nodes.elementAt(i)).ID+
            //             " n "+((GraphNode)m_nodes.elementAt(n)).ID+
            //             " len "+((GraphNode)m_nodes.elementAt(len)).ID );
            //temp[origNode][firstTempNodecreated] = temp[origNode][targetNode]
            tempMatrix[n][len] = tempMatrix[n][i]; 
            //temp[firstTempNodeCreated][origNode]  for reverse tracing
            tempMatrix[len][n] = -1*tempMatrix[n][i];
             //temp[targetNode][lastTempNodecreated]  for reverse tracing
            tempMatrix[i][k]   = -1*tempMatrix[n][i]; 
            
            //temp[lastTempNodeCreated][secondlastNode] for reverse tracing
            //but only do this if more than 1 temp nodes are created
            if(k>len)                                  
              tempMatrix[k][k-1] = -1*tempMatrix[n][i];
            
            //temp[origNode][targetNode] = 0 unlinking as they have been
            // linked by a chain of temporary nodes now.
            tempMatrix[n][i]   = 0;                    
            tempMatrix[i][n]   = 0;                    
            
            graphMatrix = tempMatrix;
          }
          else {
            //****Even if there is no gap just add a reference for the
            //****parent to the child for reverse tracing, useful if the
            //****there is a reversed edge from parent to child and therefore
            //****visualizer would know to highlight this edge  when 
            //****highlighting the child.
            graphMatrix[i][n]=-1*graphMatrix[n][i];
          }
      }
    }
    //Interconnection matrices at each level, 1 to n-1 after minimizing edges
    //printMatrices(nodeLevels);
  }
  
  
  /**
   * This method removes gaps from the graph. It tries to minimise the number
   * of edges by concentrating multiple dummy nodes from the same parent and
   * on the same vertical level into one. It takes as an argument of int[]
   * of length m_nodes.size() containing the level of each
   * node.
   */
  private void removeGapsWithEdgeConcentration(int nodesLevel[]) {
    
    final int  temp = m_nodes.size(), temp2=graphMatrix[0].length;
    int tempCnt=1;
    
    for(int n=0; n<temp; n++) {
      for(int i=0; i<temp2; i++) {
        if(graphMatrix[n][i]>0)
          if(nodesLevel[i]>nodesLevel[n]+1) {
            //System.out.println("Processing node "+
            //                   ((GraphNode)m_nodes.elementAt(n)).ID+
            //                   " for "+((GraphNode)m_nodes.elementAt(i)).ID);
            int tempLevel=nodesLevel[n];
            boolean tempNodePresent=false;
            int k=temp;
            int tempnode = n;
            
            while(tempLevel < nodesLevel[i]-1 ) {
              tempNodePresent=false;
              for(; k<graphMatrix.length; k++) {
                if(graphMatrix[tempnode][k]>0) {
                  //System.out.println("tempnode will be true");
                  tempNodePresent = true; break;
                }
              }
              if(tempNodePresent) {
                tempnode=k; k=k+1;
                tempLevel++;
              }
              else {
                if(tempnode!=n)
                  tempnode=k-1;
                //System.out.println("breaking from loop");
                break;
              }
            }
            if(((GraphNode)m_nodes.elementAt(tempnode)).nodeType==SINGULAR_DUMMY)
              ((GraphNode)m_nodes.elementAt(tempnode)).nodeType=PLURAL_DUMMY;
            if(tempNodePresent) {
              //Link the last known temp node to target
              graphMatrix[tempnode][i] = graphMatrix[n][i];
              //System.out.println("modifying "+
              //                   ((GraphNode)nodes.elementAt(tempnode)).ID+
              //                   ", "+((GraphNode)nodes.elementAt(n)).ID);
              /////matrix[lastknowntempnode][source]=-original_val
              /////graphMatrix[tempnode][n] = -graphMatrix[n][i];
              //System.out.println("modifying "+
              //                   ((GraphNode)nodes.elementAt(i)).ID+
              //                   ", "+
              //                   ((GraphNode)nodes.elementAt(tempnode)).ID);
              
              //and matrix[target][lastknowntempnode]=-original_val
              //for reverse tracing
              graphMatrix[i][tempnode] = -graphMatrix[n][i];
              //unlink source from the target
              graphMatrix[n][i] = 0;
              graphMatrix[i][n] = 0;
              continue;
              
            }
            
            int len = graphMatrix.length;
            int tempMatrix[][] =
            new int[graphMatrix.length+(nodesLevel[i]-nodesLevel[tempnode]-1)]
            [graphMatrix.length+(nodesLevel[i]-nodesLevel[tempnode]-1)];
            int level = nodesLevel[tempnode]+1;
            copyMatrix(graphMatrix, tempMatrix);
            
            String s1 = new String("S"+tempCnt++);
            //System.out.println("Adding dummy "+s1);
            m_nodes.addElement(new GraphNode(s1, s1, SINGULAR_DUMMY));
            
            int temp3 [] = new int[nodeLevels[level].length+1];
            System.arraycopy(nodeLevels[level], 0, temp3, 
                             0, nodeLevels[level].length);
            temp3[temp3.length-1] = m_nodes.size()-1;
            nodeLevels[level] = temp3;
            temp3 = new int[m_nodes.size()+1];
            System.arraycopy(nodesLevel, 0, temp3, 0, nodesLevel.length);
            temp3[m_nodes.size()-1] = level;
            nodesLevel = temp3;
            level++;
            //nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
            //System.out.println("len:"+len+"("+
            //                   ((GraphNode)m_nodes.elementAt(len)).ID+"),"+
            //                   nodesLevel[i]+","+nodesLevel[tempnode]);
            
            int m;
            for(m=len; m<len+nodesLevel[i]-nodesLevel[tempnode]-1-1; m++) {
              String s2 =  new String("S"+tempCnt++);
              //System.out.println("Adding dummy "+s2);
              m_nodes.addElement( new GraphNode(s2, s2, SINGULAR_DUMMY) );
              temp3 = new int[nodeLevels[level].length+1];
              //for(int j=0; j<nodeLevels[level].length; j++)
              //        temp3[j] = nodeLevels[level][j];
              System.arraycopy(nodeLevels[level], 0, temp3, 
                               0, nodeLevels[level].length);
              temp3[temp3.length-1] = m_nodes.size()-1;
              nodeLevels[level] = temp3;
              temp3 = new int[m_nodes.size()+1];
              System.arraycopy(nodesLevel, 0, temp3, 0, nodesLevel.length);
              temp3[m_nodes.size()-1] = level;
              nodesLevel = temp3;
              level++;
              //nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
              //System.out.println("modifying "+
              //                   ((GraphNode)nodes.elementAt(m)).ID+", "+
              //                   ((GraphNode)nodes.elementAt(m+1)).ID);
              tempMatrix[m][m+1]=tempMatrix[n][i]; //tempCnt++;
              if(m>len) {
                //System.out.println("modifying "+
                //                   ((GraphNode)nodes.elementAt(m)).ID+
                //                   ", "+((GraphNode)nodes.elementAt(m-1)).ID);
                tempMatrix[m][m-1]=-1*tempMatrix[n][i];
              }
            }
            //System.out.println("m "+((GraphNode)m_nodes.elementAt(m)).ID+
            //     " i "+((GraphNode)m_nodes.elementAt(i)).ID+
            //     " tempnode "+((GraphNode)m_nodes.elementAt(tempnode)).ID+
            //     " len "+((GraphNode)m_nodes.elementAt(len)).ID );
            //System.out.println("modifying "+
            //                   ((GraphNode)nodes.elementAt(m)).ID+", "+
            //                   ((GraphNode)nodes.elementAt(i)).ID);
            
            //temp[lastTempNodeCreated][targetNode]=temp[origNode][targetNode]
            tempMatrix[m][i]=tempMatrix[n][i];
            //System.out.println("modifying "+
            //                   ((GraphNode)nodes.elementAt(tempnode)).ID+", "+
            //                   ((GraphNode)nodes.elementAt(len)).ID);
            
            //temp[origNode][firstTempNodecreated] = temp[origNode][targetNode]
            tempMatrix[tempnode][len] =  tempMatrix[n][i];
            //System.out.println("modifying "+
            //                   ((GraphNode)nodes.elementAt(len)).ID+", "+
            //                   ((GraphNode)nodes.elementAt(tempnode)).ID);
            
            //temp[firstTempNodeCreated][origNode]  for reverse tracing
            tempMatrix[len][tempnode] = -1*tempMatrix[n][i]; 
            //System.out.println("modifying "+
            //                   ((GraphNode)nodes.elementAt(i)).ID+", "+
            //                   ((GraphNode)nodes.elementAt(m)).ID);
            
            //temp[targetNode][lastTempNodecreated]  for reverse tracing
            tempMatrix[i][m] = -1*tempMatrix[n][i];
            if(m>len) {
              //System.out.println("modifying "+
              //                   ((GraphNode)nodes.elementAt(m)).ID+
              //                   ", "+((GraphNode)nodes.elementAt(m-1)).ID);

              //temp[lastTempNodeCreated][secondlastNode] for reverse tracing
              //but only do this if more than 1 temp nodes are created
              tempMatrix[m][m-1] = -1*tempMatrix[n][i]; 
            }

            //temp[origNode][targetNode] = 0 unlinking as they have been
            tempMatrix[n][i]   = 0;
            
            //linked by a chain of temporary nodes now.
            tempMatrix[i][n]   = 0;
            
            graphMatrix = tempMatrix;
          }
          else {
            //System.out.println("modifying "+
            //                   ((GraphNode)nodes.elementAt(i)).ID+", "+
            //                   ((GraphNode)nodes.elementAt(n)).ID);
            //****Even if there is no gap just add a reference for the
            //****parent to the child for reverse tracing, useful if the
            //****there is a reversed edge from parent to child and therefore
            //****visualizer would know to highlight this edge  when
            //****highlighting the child.
            graphMatrix[i][n]=-1*graphMatrix[n][i];
          }
      }
    }
    
  }
  
  
  /**
   * Returns the index of an element in a level.
   * Must never be called with the wrong element and
   * the wrong level, will throw an exception otherwise.
   * It takes as agrument the index of the element (in the m_nodes vector)
   * and the level it is supposed to be in (as each level contains the indices
   * of the nodes present in that level).
   */
  private int indexOfElementInLevel(int element, int level[]) throws Exception {
    int idx;
    
    for(int i=0; i<level.length; i++)
      if(level[i]==element)
        return i;
    throw new Exception("Error. Didn't find element "+
                        ((GraphNode)m_nodes.elementAt(element)).ID+
                        " in level. Inspect code for "+
                        "weka.gui.graphvisualizer.HierarchicalBCEngine");
  }
  
  
  
  /**
   * Computes the number of edge crossings in the whole graph
   * Takes as an argument levels of nodes. It is essentially the
   * same algorithm provided in Universitat des Saarlandes
   * technical report A03/94 by Georg Sander.
   */
  protected int crossings(final int levels[][]) {
    int sum=0;
    
    for(int i=0; i<levels.length-1; i++) {
      //System.out.println("*****************Processing level "+i+
      //                   "*****************************");
      MyList upper = new MyList(), lower = new MyList();
      MyListNode lastOcrnce[] = new MyListNode[m_nodes.size()];
      int edgeOcrnce[] = new int[m_nodes.size()];
      
      for(int j=0,uidx=0,lidx=0; j<(levels[i].length+levels[i+1].length); j++) {
        if((j%2==0 && uidx<levels[i].length) || lidx>=levels[i+1].length) {
          int k1=0, k2=0, k3=0;
          GraphNode n = (GraphNode) m_nodes.elementAt(levels[i][uidx]);
          //Deactivating and counting crossings for all edges ending in it
          //coming from bottom left
          if(lastOcrnce[levels[i][uidx]]!=null) {
            MyListNode temp = new MyListNode(-1); temp.next = upper.first;
            try {
              do {
                temp = temp.next;
                if(levels[i][uidx]==temp.n) {
                  k1 = k1+1;
                  k3 = k3+k2;
                  //System.out.println("Removing from upper: "+temp.n);
                  upper.remove(temp);
                }
                else
                  k2 = k2+1;
              } while(temp!=lastOcrnce[levels[i][uidx]]);
            }
            catch(NullPointerException ex) {
              System.out.println("levels[i][uidx]: "+levels[i][uidx]+
              " which is: "+((GraphNode)m_nodes.elementAt(levels[i][uidx])).ID+
              " temp: "+temp+
              " upper.first: "+upper.first);
            ex.printStackTrace();
            System.exit(-1);}
            
            lastOcrnce[levels[i][uidx]]=null;
            sum = sum + k1*lower.size() + k3;
          }
          //Activating all the edges going out towards the bottom 
          //and bottom right
          for(int k=0; k<n.edges.length; k++) {
            if(n.edges[k][1]>0)
              try {
                if( indexOfElementInLevel(n.edges[k][0], levels[i+1]) >= uidx) {
                  edgeOcrnce[n.edges[k][0]]=1;
                }
              }
              catch(Exception ex) {
                ex.printStackTrace();
              }
          }
          for(int k=0; k<levels[i+1].length; k++) {
            if(edgeOcrnce[levels[i+1][k]]==1) {
              MyListNode temp = new MyListNode(levels[i+1][k]); //new MyListNode(n.edges[k][0]);
              lower.add(temp);
              lastOcrnce[levels[i+1][k]] = temp;
              edgeOcrnce[levels[i+1][k]] = 0;
              //System.out.println("Adding to lower: "+levels[i+1][k]+
              //" which is: "+((GraphNode)m_nodes.elementAt(levels[i+1][k])).ID+
              //" first's n is: "+lower.first.n);
            }
            
          }
          uidx++;
        }
        else {
          int k1=0, k2=0, k3=0;
          GraphNode n = (GraphNode) m_nodes.elementAt(levels[i+1][lidx]);
          //Deactivating and counting crossings for all edges ending in it
          //coming from up and upper left
          if(lastOcrnce[levels[i+1][lidx]]!=null) {
            
            MyListNode temp = new MyListNode(-1); temp.next = lower.first;
            try {
              do {
                temp = temp.next;
                if(levels[i+1][lidx]==temp.n) {
                  k1 = k1+1;
                  k3 = k3+k2;
                  lower.remove(temp);
                  //System.out.println("Removing from lower: "+temp.n);
                }
                else
                  k2 = k2+1;
                //System.out.println("temp: "+temp+" lastOcrnce: "+
                //                   lastOcrnce[levels[i+1][lidx]]+" temp.n: "+
                //                   temp.n+" lastOcrnce.n: "+
                //                   lastOcrnce[levels[i+1][lidx]].n);
              } while(temp!=lastOcrnce[levels[i+1][lidx]]);
            }
            catch(NullPointerException ex) {
              System.out.print("levels[i+1][lidx]: "+levels[i+1][lidx]+
              " which is: "+
              ((GraphNode)m_nodes.elementAt(levels[i+1][lidx])).ID+
              " temp: "+temp);
              System.out.println(" lower.first: "+lower.first);
              ex.printStackTrace();
              System.exit(-1); 
            }
            
            lastOcrnce[levels[i+1][lidx]]=null;
            sum = sum + k1*upper.size() + k3;
          }
          
          //Activating all the edges going out towards the upper right
          for(int k=0; k<n.edges.length; k++) {
            if(n.edges[k][1]<0)
              try {
                if( indexOfElementInLevel(n.edges[k][0], levels[i]) > lidx) {
                  edgeOcrnce[n.edges[k][0]]=1;
                }
              }
              catch(Exception ex) {
                ex.printStackTrace();
              }
          }
          for(int k=0; k<levels[i].length; k++) {
            if(edgeOcrnce[levels[i][k]]==1) {
              MyListNode temp = new MyListNode(levels[i][k]);
              upper.add(temp);
              lastOcrnce[levels[i][k]]=temp;
              edgeOcrnce[levels[i][k]]=0;
              //System.out.println("Adding to upper: "+levels[i][k]+
              //               " which is : "+
              //                ((GraphNode)m_nodes.elementAt(levels[i][k])).ID+
              //               " from node: "+n.ID+", "+k+
              //               " first's value: "+upper.first.n);
            }
          }
          lidx++;
        }
      }
      //System.out.println("Sum at the end is: "+sum);
    }
    
    return sum;
  }
  
  
  /**
   * The following two methods remove cycles from the graph.
   */
  protected void removeCycles() {
    //visited[x]=1 is only  visited AND visited[x]=2 means node is visited
    // and is on the current path
    int visited[]  = new int[m_nodes.size()];
    
    for(int i=0; i<graphMatrix.length; i++) {
      if(visited[i]==0){
        removeCycles2(i, visited);
        visited[i]=1;
      }
    }
  }
  
  /** This method should not be called directly. It should be called only from 
      to call removeCycles() */
  private void removeCycles2(int nindex, int visited[]) {
    visited[nindex]=2;
    for(int i=0; i<graphMatrix[nindex].length; i++) {
      if(graphMatrix[nindex][i]==DIRECTED)
        if(visited[i]==0) {
          removeCycles2(i, visited);
          visited[i]=1;
        }
        else if(visited[i]==2) {
          if(nindex==i) {
            graphMatrix[nindex][i]=0;
          }
          else if(graphMatrix[i][nindex]==DIRECTED) {
            //System.out.println("\nFound double "+nindex+','+i);
            graphMatrix[i][nindex]=DOUBLE;
            graphMatrix[nindex][i]=-DOUBLE;
          }
          else {
            //System.out.println("\nReversing "+nindex+','+i);
            graphMatrix[i][nindex]=REVERSED;
            graphMatrix[nindex][i]=-REVERSED;
          }
        }
    }
  }
  
  /**
   * This method assigns a vertical level to each node.
   * See makeProperHierarchy() to see how to use it.
   */
  protected void assignLevels(int levels[], int depth, int i, int j) {
    //System.out.println(i+","+j);
    if(i>=graphMatrix.length)
      return;
    else if(j>=graphMatrix[i].length)
      return;
    if(graphMatrix[i][j]<=0)
      assignLevels(levels, depth, i, ++j);
    else if(graphMatrix[i][j]==DIRECTED || graphMatrix[i][j]==DOUBLE) {
      if(depth+1>levels[j]) {
        levels[j]=depth+1;
        assignLevels(levels, depth+1, j, 0);
      }
      assignLevels(levels, depth, i, ++j);
    }
  }
  
  
  /**
   * This method minimizes the number of edge crossings using the BaryCenter
   * heuristics given by Sugiyama et al. 1981
   * This method processes the graph topdown if reversed is false,
   * otherwise it does bottomup.
   */
  private int[][] minimizeCrossings(boolean reversed, int nodeLevels[][]) {
    
    //Minimizing crossings using Sugiyama's method
    if(reversed==false) {
      for(int times=0; times<1; times++) {
        int tempLevels[][] = new int[nodeLevels.length][];
        
        //System.out.println("---------------------------------");
        //System.out.println("Crossings before PHaseID: "+
        //                   crossings(nodeLevels));
        copy2DArray(nodeLevels, tempLevels);
        for(int i=0; i<nodeLevels.length-1; i++)   //Down
          phaseID(i, tempLevels);
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        
        //System.out.println("\nCrossings before PHaseIU: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=nodeLevels.length-2; i>=0; i--)  //Up
          phaseIU(i, tempLevels);
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        
        //System.out.println("\nCrossings before PHaseIID: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=0; i<nodeLevels.length-1; i++) {   //Down
          phaseIID(i, tempLevels);
        }
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        //System.out.println("Crossings temp:"+crossings(tempLevels)+
        //                   " graph:"+crossings(nodeLevels));
        //printMatrices(nodeLevels);
        
        //System.out.println("\nCrossings before PHaseIIU: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=nodeLevels.length-2; i>=0; i--) {   //Up
          phaseIIU(i, tempLevels);
        }
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        ///System.out.println("Crossings temp:"+crossings(tempLevels)+
        //                    " graph:"+crossings(nodeLevels));
        ///printMatrices(nodeLevels);
        //System.out.println("\nCrossings after phaseIIU: "+
        //                   crossings(nodeLevels));
      }
      return nodeLevels;
    }
    else {
      for(int times=0; times<1; times++) {
        int tempLevels[][] = new int[nodeLevels.length][];
        
        //System.out.println("---------------------------------");
        //System.out.println("\nCrossings before PHaseIU: "+
        //                   crossings(nodeLevels));
        copy2DArray(nodeLevels, tempLevels);
        for(int i=nodeLevels.length-2; i>=0; i--)  //Up
          phaseIU(i, tempLevels);
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        //printMatrices(nodeLevels);
        
        //System.out.println("Crossings before PHaseID: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=0; i<nodeLevels.length-1; i++)   //Down
          phaseID(i, tempLevels);
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        ///printMatrices(nodeLevels);
        
        //System.out.println("\nCrossings before PHaseIIU: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=nodeLevels.length-2; i>=0; i--) {   //Up
          phaseIIU(i, tempLevels);
        }
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        //printMatrices(nodeLevels);
        
        //System.out.println("\nCrossings before PHaseIID: "+
        //                   crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for(int i=0; i<nodeLevels.length-1; i++) {   //Down
          phaseIID(i, tempLevels);
        }
        if(crossings(tempLevels)<crossings(nodeLevels))
          nodeLevels = tempLevels;
        ///printMatrices(nodeLevels);
        //System.out.println("\nCrossings after phaseIID: "+
        //                   crossings(nodeLevels));
      }
      return nodeLevels;
    }
  }
  
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   * lindex is the index of the level we want to process.
   * In this method we'll sort the vertices at the level one
   * below lindex according to their UP-barycenters (or column
   * barycenters).
   */
  protected void phaseID(final int lindex, final int levels[][]) {
    float colBC[]; //= new float[levels[lindex+1].size()];
    colBC = calcColBC(lindex, levels);
    
    //System.out.println("In ID Level"+(lindex+1)+":");
    //System.out.print("\t");
    //for(int i=0; i<colBC.length; i++)
    //   {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
    //    }
    //System.out.println("");
    //colBC = calcColBC1(lindex, levels);
    //for(int i=0; i<colBC.length; i++)
    //  {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
    //    }
    //System.out.println("");
    //System.out.print("\n\tNodes ");
    //for(int i=0; i<levels[lindex+1].length; i++)
    //    System.out.print(levels[lindex+1][i]+" ");
    //System.out.println("");
    //System.out.println("\nCrossings: "+crossings(levels));
    //inspect(false, lindex, levels, colBC);
    
    isort(levels[lindex+1], colBC);
    //combSort11(levels[lindex+1], colBC);
    //System.out.println("After sorting");
    //System.out.print("\t");
    //for(int i=0; i<colBC.length; i++)
    //    {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
    //    }
    //System.out.print("\n\tNodes ");
    //for(int i=0; i<levels[lindex+1].length; i++)
    //    System.out.print(levels[lindex+1][i]+" ");
    //System.out.println("\nCrossings: "+crossings(levels));
    ///System.out.println("");
  }
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   * lindex is the index of the level we want to process.
   * In this method we'll sort the vertices at the level
   * lindex according to their DOWN-barycenters (or row
   * barycenters).
   */
  public void phaseIU(final int lindex, final int levels[][]) {
    float rowBC[];
    rowBC = calcRowBC(lindex, levels);
    
    //System.out.println("In IU Level"+(lindex+1)+":");
    //System.out.print("\t");
    //for(int i=0; i<rowBC.length; i++)
    //    {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
    //    }
    //    System.out.print("\n\t");
    //    rowBC = calcRowBC1(lindex, levels);
    //    for(int i=0; i<rowBC.length; i++)
    //      {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
    //      }
    //    System.out.println("");
    //System.out.print("\n\tNodes ");
    //for(int i=0; i<levels[lindex].length; i++)
    //    System.out.print(levels[lindex][i]+" ");
    //System.out.println("\nCrossings: "+crossings(levels));
    //inspect(true, lindex, levels, rowBC);
    
    isort(levels[lindex], rowBC);
    //combSort11(levels[lindex], rowBC);
    //System.out.println("After sorting\n\t");
    //for(int i=0; i<rowBC.length; i++)
    //    {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
    //    }
    //System.out.print("\n\tNodes ");
    //for(int i=0; i<levels[lindex].length; i++)
    //    System.out.print(levels[lindex][i]+" ");
    //System.out.println("\nCrossings: "+crossings(levels));
  }
  
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  public void phaseIID(final int lindex, final int levels[][]) {
    float colBC[];
    colBC = calcColBC(lindex, levels);
    
    //System.out.println("getting into phase IID");
    for(int i=0; i<colBC.length-1; i++) {
      if(colBC[i]==colBC[i+1]) {
        //System.out.println("Crossings before begining of iteration: "+
        //                   crossings(levels));
        int tempLevels[][] = new int[levels.length][];
        copy2DArray(levels, tempLevels);
        //System.out.println("Interchanging: "+
        //       ((GraphNode)m_nodes.elementAt(levels[lindex+1][i])).ID+
        //       " & "+
        //       ((GraphNode)m_nodes.elementAt(levels[lindex+1][(i+1)])).ID+
        //       " at level "+(lindex+1) );
        int node1 = levels[lindex+1][i];
        int node2 = levels[lindex+1][i+1];
        levels[lindex+1][i+1] = node1;
        levels[lindex+1][i] = node2;
        
        for(int k=lindex+1; k<levels.length-1; k++)
          phaseID(k, levels);
        //System.out.println("Crossings temp:"+crossings(tempLevels)+
        //                   " graph:"+crossings(levels));
        if(crossings(levels)<=crossings(tempLevels)) {
          //System.out.println("Crossings temp: "+crossings(tempLevels)+
          //                   " Crossings levels: "+crossings(levels));
          copy2DArray(levels, tempLevels); } //printMatrices(levels); }
        else {
          copy2DArray(tempLevels, levels);
          levels[lindex+1][i+1] = node1;
          levels[lindex+1][i] = node2;
        }
        //System.out.println("Crossings after PhaseID of phaseIID, "+
        //                   "in iteration "+i+" of "+(colBC.length-1)+" at "+
        //                   lindex+", levels: "+crossings(levels)+
        //                   " temp: "+crossings(tempLevels));
        
        //tempLevels = new int[levels.length][];
        //copy2DArray(levels, tempLevels);
        for(int k=levels.length-2; k>=0; k--)
          phaseIU(k, levels);
        //System.out.println("Crossings temp:"+crossings(tempLevels)+
        //                   " graph:"+crossings(levels));
        //if(crossings(tempLevels)<crossings(levels)) {
        // System.out.println("Crossings temp: "+crossings(tempLevels)+
        //                    " Crossings levels: "+crossings(levels));
        //      copy2DArray(tempLevels, levels); } //printMatrices(levels); }
        if(crossings(tempLevels)<crossings(levels))
          copy2DArray(tempLevels, levels);
        
        //System.out.println("Crossings after PhaseIU of phaseIID, in"+
        //                   " iteration "+i+" of "+(colBC.length-1)+" at "
        //                   +lindex+", levels: "+crossings(levels)+" temp: "+
        //                   crossings(tempLevels));
        //colBC = calcColBC(lindex, levels);
      }
    }
  }
  
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  public void phaseIIU(final int lindex, final int levels[][]) {
    float rowBC[];
    rowBC = calcRowBC(lindex, levels);
    
    //System.out.println("Getting into phaseIIU");
    for(int i=0; i<rowBC.length-1; i++) {
      if(rowBC[i]==rowBC[i+1]) {
        //System.out.println("Crossings before begining of iteration: "+
        //                   crossings(levels));
        int tempLevels[][] = new int[levels.length][];
        copy2DArray(levels, tempLevels);
        //System.out.println("Interchanging: "+
        //          ((GraphNode)m_nodes.elementAt(levels[lindex][i])).ID+" & "+
        //          ((GraphNode)m_nodes.elementAt(levels[lindex][i+1])).ID+
        //          " at level "+(lindex+1) );
        int node1 = levels[lindex][i];
        int node2 = levels[lindex][i+1];
        levels[lindex][i+1] = node1;
        levels[lindex][i] = node2;
        
        for(int k=lindex-1; k>=0; k--)
          phaseIU(k, levels);
        if(crossings(levels)<=crossings(tempLevels)) { 
          //System.out.println("Crossings temp: "+crossings(tempLevels)+
          //                   " Crossings levels: "+crossings(levels));
          copy2DArray(levels, tempLevels); } //printMatrices(levels);
        else {
          copy2DArray(tempLevels, levels);
          levels[lindex][i+1] = node1;
          levels[lindex][i] = node2;
        }
        //System.out.println("Crossings after PhaseIU of PhaseIIU, in "+
        //                   "iteration "+i+" of "+(rowBC.length-1)+" at "
        //                   +lindex+", levels: "+crossings(levels)+
        //                   " temp: "+crossings(tempLevels));
        
        //tempLevels = new int[levels.length][];
        //copy2DArray(levels, tempLevels);
        for(int k=0; k<levels.length-1; k++) //lindex-1; k++)
          phaseID(k, levels);
        //if(crossings(tempLevels)<crossings(levels)) { 
        //  System.out.println("Crossings temp: "+crossings(tempLevels)+
        //                     " Crossings levels: "+crossings(levels));
        //      copy2DArray(tempLevels, levels); } //printMatrices(levels); }
        if(crossings(tempLevels)<=crossings(levels))
          copy2DArray(tempLevels, levels);
        //System.out.println("Crossings after PhaseID of phaseIIU, in "+
        //                   "iteration "+i+" of "+(rowBC.length-1)+" at "
        //                   +lindex+", levels: "+crossings(levels)+
        //                   " temp: "+crossings(tempLevels));
        //rowBC = calcRowBC(lindex, levels);
      }
    }
  }
  
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  protected float [] calcRowBC(final int lindex, final int levels[][]){
    float rowBC[] = new float[levels[lindex].length];
    GraphNode n;
    
    for(int i=0; i<levels[lindex].length; i++) {
      int sum=0;
      n = (GraphNode)m_nodes.elementAt(levels[lindex][i]);
      
      for(int j=0; j<n.edges.length; j++) {
        if(n.edges[j][1]>0) {
          sum++;
          try {
            rowBC[i] = 
              rowBC[i]+indexOfElementInLevel(n.edges[j][0], levels[lindex+1])+1;
          }
          catch(Exception ex) { return null; }
        }
      }
      if(rowBC[i]!=0)
        rowBC[i] = rowBC[i]/sum;
    }
    return rowBC;
  }
  
  
  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  protected float [] calcColBC(final int lindex, final int levels[][]) {
    float colBC[] = new float[levels[lindex+1].length];
    GraphNode n;
    
    for(int i=0; i<levels[lindex+1].length; i++) {
      int sum=0;
      n = (GraphNode)m_nodes.elementAt(levels[lindex+1][i]);
      
      for(int j=0; j<n.edges.length; j++) {
        if(n.edges[j][1]<1) {
          sum++;
          try{
            colBC[i] =
                colBC[i]+indexOfElementInLevel(n.edges[j][0], levels[lindex])+1;
          }
          catch(Exception ex) { return null; }
        }
      }
      if(colBC[i]!=0)
        colBC[i]=colBC[i]/sum;
    }
    return colBC;
  }
  
  /**
   * Prints out the interconnection matrix at each level.
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  protected void printMatrices(final int levels[][]) {
    int i=0;
    for(i=0; i<levels.length-1; i++) {
      float rowBC[]=null; float colBC[]=null;
      try{
        rowBC = calcRowBC(i, levels); colBC = calcColBC(i, levels);
      }
      catch(NullPointerException ne) {
        System.out.println("i: "+i+" levels.length: "+levels.length);
        ne.printStackTrace();
        return;
      }
      
      System.out.print("\nM"+(i+1)+"\t");
      for(int j=0; j<levels[i+1].length; j++) {
        System.out.print( ((GraphNode)m_nodes.elementAt(levels[i+1][j])).ID +
                          " ");
        //((Integer)levels[i+1].elementAt(j)).intValue())+" ");
      }
      System.out.println("");
      
      for(int j=0; j<levels[i].length; j++) {
        System.out.print( ((GraphNode)m_nodes.elementAt(levels[i][j])).ID+"\t");
        //((Integer)levels[i].elementAt(j)).intValue())+"\t");
        for(int k=0; k<levels[i+1].length; k++) {
          
          System.out.print(graphMatrix[levels[i][j]] 
                                 //((Integer)levels[i].elementAt(j)).intValue()]
                                      [levels[i+1][k]]+" "); 
                         //((Integer)levels[i+1].elementAt(k)).intValue()]+" ");
          
        }
        System.out.println(rowBC[j]);
      }
      System.out.print("\t");
      for(int k=0; k<levels[i+1].length; k++)
        System.out.print(colBC[k]+" ");
    }
    System.out.println("\nAt the end i: "+i+" levels.length: "+levels.length);
  }
  
  /**
   * This methods sorts the vertices in level[] according to their
   * barycenters in BC[], using combsort11. It, however, doesn't touch the
   * vertices with barycenter equal to zero.
   */
    /*
     *  //This method should be removed
     protected static void combSort11(int level[], float BC[]) {  
        int switches, j, top, gap, lhold;
        float hold;
        gap = BC.length;
        do {
            gap=(int)(gap/1.3);
            switch(gap) {
            case 0:
                gap = 1;
                break;
            case 9:
            case 10:
                gap=11;
                break;
            default:
                break;
            }
            switches=0;
            top = BC.length-gap;
            for(int i=0; i<top; i++) {
                j=i+gap;
                if(BC[i]==0 || BC[j]==0)
                    continue;
                if(BC[i] > BC[j]) {
                    hold=BC[i];
                    BC[i]=BC[j];
                    BC[j]=hold;
                    lhold = level[i];
                    level[i] = level[j];
                    level[j] = lhold;
                    switches++;
                }//endif
            }//endfor
        }while(switches>0 || gap>1);
    }
     */
  
  
  /**
   * This methods sorts the vertices in level[] according to their
   * barycenters in BC[], using insertion sort. It, however, doesn't touch the
   * vertices with barycenter equal to zero.
   */
   //Both level and BC have elements in the same order
  protected static void isort(int level[], float BC[]) { 
    float temp;
    int temp2;
    for(int i=0; i<BC.length-1; i++) {
      
      int j=i;
      temp=BC[j+1];
      temp2=level[j+1];
      if(temp==0)
        continue;
      int prej=j+1;
      
      while( j>-1 && (temp<BC[j]|| BC[j]==0) ) {
        if(BC[j]==0){
          j--; continue;}
        else {
          BC[prej] = BC[j];
          level[prej] = level[j];
          prej=j;
          j--;
        }
      }
      //j++;
      BC[prej]    = temp;
      level[prej] = temp2;
      //Integer node = (Integer)level.elementAt(i+1);
      //level.removeElementAt(i+1);
      //level.insertElementAt(node, prej);
    }
  }
  
  
  /**
   * Copies one Matrix of type int[][] to another.
   */
  protected void copyMatrix(int from[][], int to[][]) {
    for(int i=0; i<from.length; i++)
      for(int j=0; j<from[i].length; j++)
        to[i][j]=from[i][j];
  }
  
  /**
   * Copies one array of type int[][] to another.
   */
  protected void copy2DArray(int from[][], int to[][]) {
    for(int i=0; i<from.length; i++) {
      to[i] = new int[from[i].length];
      System.arraycopy(from[i], 0, to[i], 0, from[i].length);
      //for(int j=0; j<from[i].length; j++)
      //        to[i][j] = from[i][j];
    }
  }
  
  /**
   * This method lays out the vertices horizontally, in each level.
   * It simply assings an x value to a vertex according to its
   * index in the level.
   */
  protected void naiveLayout() {
    /*
    if(maxStringWidth==0) {
      int strWidth;
      for(int i=0; i<m_nodes.size(); i++) {
        strWidth = m_fm.stringWidth(((GraphNode)m_nodes.elementAt(i)).lbl);
        if(strWidth>maxStringWidth)
          maxStringWidth=strWidth;
      }
      
      if(m_nodeSize<maxStringWidth)
      {m_nodeSize = maxStringWidth+4; m_nodeArea = m_nodeSize+8; }
    }
    */
    if(nodeLevels==null)
      makeProperHierarchy();
    
    //int nodeHeight = m_nodeHeight*2; //m_fm.getHeight()*2;
    for(int i=0, temp=0; i<nodeLevels.length; i++) {
      for(int j=0; j<nodeLevels[i].length; j++) {
        temp=nodeLevels[i][j];
        //horPositions[temp]=j;
        GraphNode n = (GraphNode)m_nodes.elementAt(temp);
        n.x = j*m_nodeWidth; //horPositions[temp]*m_nodeWidth;
        n.y = i*3*m_nodeHeight;
      }
    }
    //setAppropriateSize();
  }
  
  
  protected int uConnectivity(int lindex, int eindex) {
    int n=0;
    for(int i=0; i<nodeLevels[lindex-1].length; i++)
      if(graphMatrix[ nodeLevels[lindex-1][i] ][ nodeLevels[lindex][eindex] ]>0)
        n++;
    
    return n;
  }
  
  protected int lConnectivity(int lindex, int eindex) {
    int n=0;
    for(int i=0; i<nodeLevels[lindex+1].length; i++)
      if(graphMatrix[ nodeLevels[lindex][eindex] ][ nodeLevels[lindex+1][i] ]>0)
        n++;
    
    return n;
  }
  
  protected int uBCenter(int lindex, int eindex, int horPositions[]) {
    int sum=0;
    
    for(int i=0; i<nodeLevels[lindex-1].length; i++)
      if(graphMatrix[nodeLevels[lindex-1][i]][nodeLevels[lindex][eindex]]>0)
        sum = sum + (horPositions[nodeLevels[lindex-1][i]]);
    if(sum!=0) { // To avoid 0/0
      //System.out.println("uBC Result: "+sum+"/"+
      //                   uConnectivity(lindex,eindex)+
      //                   " = "+(sum/uConnectivity(lindex,eindex)) );
      sum = sum/uConnectivity(lindex,eindex);
    }
    return sum;
  }
  
  
  protected int lBCenter(int lindex, int eindex, int horPositions[]) {
    int sum=0;
    
    for(int i=0; i<nodeLevels[lindex+1].length; i++)
      if(graphMatrix[nodeLevels[lindex][eindex]][nodeLevels[lindex+1][i]]>0)
        sum = sum + (horPositions[nodeLevels[lindex+1][i]]);
    if(sum!=0)  // To avoid 0/0
      sum = sum/lConnectivity(lindex, eindex); //lConectivity;
    return sum;
  }
  
  private void tempMethod(int horPositions[]) {
    
    int minPosition = horPositions[0];
    
    for(int i=0; i<horPositions.length; i++)
      if(horPositions[i]<minPosition)
        minPosition=horPositions[i];
    if(minPosition<0) {
      minPosition = minPosition*-1;
      for(int i=0; i<horPositions.length; i++){
        //System.out.print(horPositions[i]);
        horPositions[i]+=minPosition;
        //System.out.println(">"+horPositions[i]);
      }
    }
    
    //int nodeHeight = m_nodeHeight*2; //m_fm.getHeight()*2;
    for(int i=0, temp=0; i<nodeLevels.length; i++) {
      for(int j=0; j<nodeLevels[i].length; j++) {
        temp=nodeLevels[i][j];
        //horPositions[temp]=j;
        GraphNode n = (GraphNode)m_nodes.elementAt(temp);
        n.x = horPositions[temp]*m_nodeWidth;
        n.y = i*3*m_nodeHeight;
      }
    }
  }
  
  /**
   * This method lays out the vertices horizontally, in each level.
   * See Sugiyama et al. 1981 for full reference.
   */
  protected void priorityLayout1() {
    
    int [] horPositions = new int[m_nodes.size()];
    int maxCount=0;
    
    for(int i=0; i<nodeLevels.length; i++) {
      int count=0;
      for(int j=0; j<nodeLevels[i].length; j++) {
        horPositions[nodeLevels[i][j]]=j;
        count++;
      }
      if(count>maxCount)
        maxCount=count;
    }
    //fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
    int priorities[], BC[];
    //System.out.println("********Going from 2 to n********");
    for(int i=1; i<nodeLevels.length; i++) {
      priorities = new int[nodeLevels[i].length];
      BC = new int[nodeLevels[i].length];
      for(int j=0; j<nodeLevels[i].length; j++) {
        if(((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID.startsWith("S"))
          priorities[j] = maxCount+1;
        else
          priorities[j] = uConnectivity(i, j);
        BC[j] = uBCenter(i, j, horPositions);
      }
      //for(int j=0; j<nodeLevels[i].length; j++)
      //  System.out.println("Level: "+(i+1)+" Node: "
      //        +((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID
      //        +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
      //        +horPositions[nodeLevels[i][j]]);
      priorityLayout2(nodeLevels[i], priorities, BC, horPositions);
      //repaint
      //try {
      //        tempMethod(horPositions);
      //        fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
      //        Thread.sleep(1000);
      //} catch(InterruptedException ie) { ie.printStackTrace(); }
      
      //for(int j=0; j<nodeLevels[i].length; j++)
      //    System.out.println("Level: "+(i+1)+" Node: "
      //        +((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID
      //        +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
      //        +horPositions[nodeLevels[i][j]]);
    }
    
    //System.out.println("********Going from n-1 to 1********");
    for(int i=nodeLevels.length-2; i>=0; i--) {
      priorities = new int[nodeLevels[i].length];
      BC = new int[nodeLevels[i].length];
      for(int j=0; j<nodeLevels[i].length; j++) {
        if(((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID.startsWith("S"))
          priorities[j] = maxCount+1;
        else
          priorities[j] = lConnectivity(i, j);
        BC[j] = lBCenter(i, j, horPositions); //, priorities[j]);
      }
      priorityLayout2(nodeLevels[i], priorities, BC, horPositions);
      //repaint();
      //try {
      //        tempMethod(horPositions);
      //        fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
      //        Thread.sleep(1000);
      //} catch(InterruptedException ie) { ie.printStackTrace(); }
      
      //for(int j=0; j<nodeLevels[i].length; j++)
      //    System.out.println("Level: "+(i+1)+" Node: "
      //        +((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID
      //        +" lConnectivity: "+priorities[j]+" lBC: "+BC[j]+" position: "
      //        +horPositions[nodeLevels[i][j]]);
    }
    
    //System.out.println("********Going from 2 to n again********");
    for(int i=2; i<nodeLevels.length; i++) {
      priorities = new int[nodeLevels[i].length];
      BC = new int[nodeLevels[i].length];
      for(int j=0; j<nodeLevels[i].length; j++) {
        if(((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID.startsWith("S"))
          priorities[j] = maxCount+1;
        else
          priorities[j] = uConnectivity(i, j);
        BC[j] = uBCenter(i, j, horPositions);
      }
      //for(int j=0; j<nodeLevels[i].length; j++)
      //    System.out.println("Level: "+(i+1)+" Node: "
      //        +((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID
      //        +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
      //        +horPositions[nodeLevels[i][j]]);
      priorityLayout2(nodeLevels[i], priorities, BC, horPositions);
      //repaint();
      //try {
      //        tempMethod(horPositions);
      //        fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
      //        Thread.sleep(1000);
      //} catch(InterruptedException ie) { ie.printStackTrace(); }
      //for(int j=0; j<nodeLevels[i].length; j++)
      //    System.out.println("Level: "+(i+1)+" Node: "
      //        +((GraphNode)m_nodes.elementAt(nodeLevels[i][j])).ID
      //        +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
      //        +horPositions[nodeLevels[i][j]]);
    }
    
    int minPosition = horPositions[0];
    
    for(int i=0; i<horPositions.length; i++)
      if(horPositions[i]<minPosition)
        minPosition=horPositions[i];
    if(minPosition<0) {
      minPosition = minPosition*-1;
      for(int i=0; i<horPositions.length; i++){
        //System.out.print(horPositions[i]);
        horPositions[i]+=minPosition;
        //System.out.println(">"+horPositions[i]);
      }
    }
    
    //int nodeHeight = m_nodeHeight*2; //m_fm.getHeight()*2;
    for(int i=0, temp=0; i<nodeLevels.length; i++) {
      for(int j=0; j<nodeLevels[i].length; j++) {
        temp=nodeLevels[i][j];
        //horPositions[temp]=j;
        GraphNode n = (GraphNode)m_nodes.elementAt(temp);
        n.x = horPositions[temp]*m_nodeWidth;
        n.y = i*3*m_nodeHeight;
      }
    }
    //setAppropriateSize();
  }
  
  /**
   * This method is used by priorityLayout1(). It should
   * not be called directly.
   * This method does the actual moving of the vertices in each level
   * based on their priorities and barycenters.
   */
  private void priorityLayout2(int level[], int priorities[], 
                               int bCenters[], int horPositions[]) {
    int descOrder[] = new int[priorities.length];
    
    //Getting the indices of priorities in descending order
    descOrder[0]=0;
    for(int i=0; i<priorities.length-1; i++) {
      int j=i;
      int temp=i+1;
      
      while( j>-1 && priorities[descOrder[j]]<priorities[temp] ) {
        descOrder[j+1] = descOrder[j];
        j--;
      }
      j++;
      descOrder[j] = temp;
    }
    
    //System.out.println("\nPriorities:");
    //for(int i=0; i<priorities.length; i++)
    //    System.out.print(priorities[i]+" ");
    //System.out.println("\nDescOrder:");
    //for(int i=0; i<descOrder.length; i++)
    //    System.out.print(descOrder[i]+" ");
    
    for(int k=0; k<descOrder.length; k++)
      for(int i=0; i<descOrder.length; i++) {
        
        int leftCount=0, rightCount=0, leftNodes[], rightNodes[];
        for(int j=0; j<priorities.length; j++) {
          if( horPositions[level[descOrder[i]]] > horPositions[level[j]] )
            leftCount++;
          else if( horPositions[level[descOrder[i]]] < horPositions[level[j]] )
            rightCount++;
        }
        leftNodes = new int[leftCount];
        rightNodes = new int[rightCount];
        
        for(int j=0, l=0, r=0; j<priorities.length; j++)
          if( horPositions[level[descOrder[i]]] > horPositions[level[j]] )
            leftNodes[l++]=j;
          else if( horPositions[level[descOrder[i]]] < horPositions[level[j]] )
            rightNodes[r++]=j;
        
        
        //****Moving left
        while(Math.abs(horPositions[level[descOrder[i]]]-1
                                    -bCenters[descOrder[i]])  <
          Math.abs(horPositions[level[descOrder[i]]]-bCenters[descOrder[i]]) ) {
          
          //****Checking if it can be moved to left
          int temp = horPositions[level[descOrder[i]]];
          boolean cantMove=false;
          
          for(int j=leftNodes.length-1; j>=0; j--) {
            if(temp-horPositions[level[leftNodes[j]]] > 1)
              break;
            else if(priorities[descOrder[i]]<=priorities[leftNodes[j]])
            { cantMove=true; break; }
            else
              temp = horPositions[level[leftNodes[j]]];
          }
          //if(horPositions[level[descOrder[i]]]-1==
          //   horPositions[level[leftNodes[j]]])
          //    cantMove = true;
          if(cantMove)
            break;
          
          temp = horPositions[level[descOrder[i]]]-1;
          //****moving other vertices to left
          for(int j=leftNodes.length-1; j>=0; j--) {
            if(temp==horPositions[level[leftNodes[j]]]) {
              //System.out.println("Moving "+
              //     ((Node)m_nodes.elementAt(level[leftNodes[j]])).ID+" from "
              //     +horPositions[level[leftNodes[j]]]+" to "
              //     +(horPositions[level[leftNodes[j]]]-1) );
              horPositions[level[leftNodes[j]]] = 
                                    temp = horPositions[level[leftNodes[j]]]-1; 
            }
            
          }
          //System.out.println("Moving main "+
          //    ((GraphNode)m_nodes.elementAt(level[descOrder[i]])).ID+" from "
          //     +horPositions[level[descOrder[i]]]+" to "
          //     +(horPositions[level[descOrder[i]]]-1));
          horPositions[level[descOrder[i]]]=horPositions[level[descOrder[i]]]-1;
        }
        
        //****Moving right
        while(Math.abs(horPositions[level[descOrder[i]]]+1
                                            -bCenters[descOrder[i]])  <
          Math.abs(horPositions[level[descOrder[i]]]-bCenters[descOrder[i]]) ) {
          //****checking if the vertex can be moved
          int temp = horPositions[level[descOrder[i]]];
          boolean cantMove=false;
          
          for(int j=0; j<rightNodes.length; j++) {
            if(horPositions[level[rightNodes[j]]]-temp > 1)
              break;
            else if(priorities[descOrder[i]]<=priorities[rightNodes[j]])
            { cantMove=true; break; }
            else
              temp = horPositions[level[rightNodes[j]]];
          }
          //if(horPositions[level[descOrder[i]]]-1==
          //   horPositions[level[leftNodes[j]]])
          //    cantMove = true;
          if(cantMove)
            break;
          
          temp = horPositions[level[descOrder[i]]]+1;
          //****moving other vertices to left
          for(int j=0; j<rightNodes.length; j++) {
            if(temp==horPositions[level[rightNodes[j]]]) {
              //System.out.println("Moving "+
              //     (Node)m_nodes.elementAt(level[rightNodes[j]])).ID+" from "
              //     +horPositions[level[rightNodes[j]]]+" to "
              //     +(horPositions[level[rightNodes[j]]]+1) );
              horPositions[level[rightNodes[j]]] = 
                                    temp = horPositions[level[rightNodes[j]]]+1;
            }
          }
          //System.out.println("Moving main "+
          //    ((GraphNode)m_nodes.elementAt(level[descOrder[i]])).ID+" from "
          //    +horPositions[level[descOrder[i]]]+" to "
          //    +(horPositions[level[descOrder[i]]]+1));
          horPositions[level[descOrder[i]]]=horPositions[level[descOrder[i]]]+1;
        }
      }
  }
  
  
  /**
   * The following classes implement a double linked list to
   * be used in the crossings function.
   */
  private class MyList {
    int size;
    MyListNode first=null;
    MyListNode last=null;
    
    public void add(int i) {
      if(first==null)
        first = last = new MyListNode(i);
      else
        if(last.next==null) {
          last.next = new MyListNode(i);
          last.next.previous = last;
          last = last.next;
        }
        else {
          System.err.println("Error shouldn't be in here. Check MyList code"); 
          size--;
        }
      size++;
    }
    
    public void add(MyListNode n) {
      if(first==null)
        first = last = n;
      else
        if(last.next==null) {
          last.next = n;
          last.next.previous = last;
          last = last.next;
        }
        else {
          System.err.println("Error shouldn't be in here. Check MyList code"); 
          size--; 
        }
      
      size++;
    }
    
    public void remove(MyListNode n) {
      if(n.previous!=null)
        n.previous.next = n.next;
      if(n.next!=null)
        n.next.previous = n.previous;
      if(last==n)
        last = n.previous;
      if(first==n)
        first = n.next;
      
      size--;
    }
    
    public void remove(int i) {
      MyListNode temp=first;
      while(temp!=null && temp.n!=i) temp=temp.next;
      
      if(temp==null){ 
        System.err.println("element "+i+"not present in the list");
        return;
      }
      
      if(temp.previous!=null)
        temp.previous.next = temp.next;
      if(temp.next!=null)
        temp.next.previous = temp.previous;
      if(last==temp)
        last = temp.previous;
      if(first==temp)
        first = temp.next;
      
      size--;
    }
    
    public int size() {
      return size;
    }
    
  }
  
  private class MyListNode {
    int n;
    MyListNode next, previous;
    
    public MyListNode(int i) {
      n = i; next=null; previous=null;
    }
  }
  
} // HierarchicalBCEngine