content: /*
   *    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
  