code: ///////////////////////////////////////////////////////////////////////////////
  // For information as to what this class does, see the Javadoc, below.       //
  // Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,       //
  // 2007, 2008, 2009, 2010, 2014, 2015 by Peter Spirtes, Richard Scheines, Joseph   //
  // Ramsey, and Clark Glymour.                                                //
  //                                                                           //
  // 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA //
  ///////////////////////////////////////////////////////////////////////////////
  
  package edu.cmu.tetrad.graph;
  
  
  import java.util.*;
  
  /**
   * Lays out a graph by linearly summing repulsive force between all nodes and
   * attractive force between adjacent nodes.
   *
   * @author Joseph Ramsey
   */
  public final class FruchtermanReingoldLayout {
  
      /**
       * The graph being laid out.
       */
      private Graph graph;
  
      /**
       * Array of e for the graph. The ith edge is e[i][0]-->e[i][[1].
       */
      private int[][] edges;
  
      /**
       * The position of each node. The position of the ith node is (pos[i][0],
       * pos[i][1]).
       */
      private double[][] nodePosition;
  
      /**
       * The disposition of each node. The disposition of the ith node is
       * (disp[i][0], disp[i][1]).
       */
      private double[][] nodeDisposition;
  
      /**
       * Optimal distance between vertices.
       */
      private double optimalDistance = 100;
  
      /**
       * Temperature.
       */
      private double temperature;
  
      /**
       * Leftmost x position to help layout components left to right.
       */
      private double leftmostX = -50.;
  
      //==============================CONSTRUCTORS===========================//
  
      public FruchtermanReingoldLayout(Graph graph) {
          if (graph == null) {
              throw new NullPointerException();
          }
  
          this.graph = graph;
      }
  
      //============================PUBLIC METHODS==========================//
  
      public void doLayout() {
          GraphUtils.circleLayout(graph, 300, 300, 200);
  
          List<List<Node>> components =
                  GraphUtils.connectedComponents(this.graph());
  
          Collections.sort(components, new Comparator<List<Node>>() {
              public int compare(List<Node> o1, List<Node> o2) {
                  int i1 = o1.size();
                  int i2 = o2.size();
                  return i2 < i1 ? -1 : i2 == i1 ? 0 : 1;
              }
          });
  
          for (List<Node> component1 : components) {
              layoutComponent(component1);
          }
      }
  
      private void layoutComponent(List<Node> nodes) {
          int numNodes = nodes.size();
          nodePosition = new double[numNodes][2];
          nodeDisposition = new double[numNodes][2];
  
          for (int i = 0; i < numNodes; i++) {
              Node node = nodes.get(i);
              nodePosition()[i][0] = node.getCenterX();
              nodePosition()[i][1] = node.getCenterY();
  
              //pos[i][0] = RandomUtil.nextInt(600);
              //pos[i][1] = RandomUtil.nextInt(600);
          }
  
          List<Edge> edges = new ArrayList<>(GraphUtils.undirectedGraph(graph()).getEdges());
  
          for (Iterator<Edge> i = edges.iterator(); i.hasNext(); ) {
              Edge edge = i.next();
              if (!nodes.contains(edge.getNode1()) ||
                      !nodes.contains(edge.getNode2())) {
                  i.remove();
              }
          }
  
          this.edges = new int[edges.size()][2];
  
          for (int i = 0; i < edges.size(); i++) {
              Edge edge = edges.get(i);
              int v = nodes.indexOf(edge.getNode1());
              int u = nodes.indexOf(edge.getNode2());
              this.edges()[i][0] = v;
              this.edges()[i][1] = u;
          }
  
          double avgDegree = 2 * graph.getNumEdges() / graph.getNumNodes();
  
          setOptimalDistance(20.0 + 20.0 * avgDegree);
          setTemperature(5.0);
  
          for (int i = 0; i < numIterations(); i++) {
  
              // Calculate repulsive forces.
              for (int v = 0; v < numNodes; v++) {
                  nodeDisposition()[v][0] = 0.1;
                  nodeDisposition()[v][1] = 0.1;
  
                  for (int u = 0; u < numNodes; u++) {
                      double deltaX = nodePosition()[u][0] - nodePosition()[v][0];
                      double deltaY = nodePosition()[u][1] - nodePosition()[v][1];
  
                      double norm = norm(deltaX, deltaY);
  
                      if (norm == 0.0) {
                          norm = 0.1;
  //                        continue;
                      }
  //
  //                    if (norm > 4.0 * getOptimalDistance()) {
  //                        continue;
  //                    }
  
                      double repulsiveForce = fr(norm);
  
                      nodeDisposition()[v][0] += (deltaX / norm) * repulsiveForce;
                      nodeDisposition()[v][1] += (deltaY / norm) * repulsiveForce;
                  }
              }
  
              // Calculate attractive forces.
              for (int j = 0; j < edges.size(); j++) {
                  int u = this.edges()[j][0];
                  int v = this.edges()[j][1];
  
                  double deltaX = nodePosition()[v][0] - nodePosition()[u][0];
                  double deltaY = nodePosition()[v][1] - nodePosition()[u][1];
  
                  double norm = norm(deltaX, deltaY);
  
                  if (norm == 0.0) {
                      norm = 0.1;
  //                    continue;
                  }
  
  //                if (norm < 1.5 * getOptimalDistance()) {
  //                    continue;
  //                }
  
                  double attractiveForce = fa(norm);
                  double attractX = (deltaX / norm) * attractiveForce;
                  double attractY = (deltaY / norm) * attractiveForce;
  
                  nodeDisposition()[v][0] -= attractX;
                  nodeDisposition()[v][1] -= attractY;
  
                  if (Double.isNaN(nodeDisposition()[v][0]) ||
                          Double.isNaN(nodeDisposition()[v][1])) {
                      throw new IllegalStateException("Undefined disposition.");
                  }
  
                  nodeDisposition()[u][0] += attractX;
                  nodeDisposition()[u][1] += attractY;
  
                  if (Double.isNaN(nodeDisposition()[u][0]) ||
                          Double.isNaN(nodeDisposition()[u][1])) {
                      throw new IllegalStateException("Undefined disposition.");
                  }
              }
  
              for (int v = 0; v < numNodes; v++) {
                  double norm = norm(nodeDisposition()[v][0], nodeDisposition()[v][1]);
  
  //                if (norm == 0.0) {
  //                    continue;
  //                }
  
                  nodePosition()[v][0] += (nodeDisposition()[v][0] / norm) *
                          Math.min(norm, getTemperature());
                  nodePosition()[v][1] += (nodeDisposition()[v][1] / norm) *
                          Math.min(norm, getTemperature());
  
                  if (Double.isNaN(nodePosition()[v][0]) ||
                          Double.isNaN(nodePosition()[v][1])) {
                      throw new IllegalStateException("Undefined position.");
                  }
              }
          }
  
          shiftComponentToRight(nodes);
      }
  
      private void shiftComponentToRight(List<Node> componentNodes) {
          double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE;
  
          for (int i = 0; i < componentNodes.size(); i++) {
              if (nodePosition()[i][0] < minX) {
                  minX = nodePosition()[i][0];
              }
              if (nodePosition()[i][1] < minY) {
                  minY = nodePosition()[i][1];
              }
          }
  
          leftmostX = leftmostX() + 100.;
  
          for (int i = 0; i < componentNodes.size(); i++) {
              nodePosition()[i][0] += leftmostX() - minX;
              nodePosition()[i][1] += 40.0 - minY;
          }
  
          for (int i = 0; i < componentNodes.size(); i++) {
              if (nodePosition()[i][0] > leftmostX()) {
                  leftmostX = nodePosition()[i][0];
              }
          }
  
          for (int i = 0; i < componentNodes.size(); i++) {
              Node node = componentNodes.get(i);
              node.setCenterX((int) nodePosition()[i][0]);
              node.setCenterY((int) nodePosition()[i][1]);
          }
      }
  
      //============================PRIVATE METHODS=========================//  \
  
      private double fa(double d) {
          return (d * d) / getOptimalDistance();
      }
  
      private double fr(double d) {
          return -(getOptimalDistance() * getOptimalDistance()) / d;
      }
  
      private double norm(double x, double y) {
          return Math.sqrt(x * x + y * y);
      }
  
      private Graph graph() {
          return graph;
      }
  
      private int[][] edges() {
          return edges;
      }
  
      private double[][] nodePosition() {
          return nodePosition;
      }
  
      private double[][] nodeDisposition() {
          return nodeDisposition;
      }
  
      private int numIterations() {
          return 500;
      }
  
      private double leftmostX() {
          return leftmostX;
      }
  
      private double getOptimalDistance() {
          return optimalDistance;
      }
  
      private void setOptimalDistance(double optimalDistance) {
          this.optimalDistance = optimalDistance;
      }
  
      private double getTemperature() {
          return temperature;
      }
  
      private void setTemperature(double temperature) {
          this.temperature = temperature;
      }
  }
  
  
  
  
  
  