Class FR91Layout

java.lang.Object
FR91Layout
public class FR91Layout extends Object
A class implementing the force directed algorithm by Fruchterman and Reingold (1991)
Version:
jan 2024
Author:
Luca Castelli Aleardi, Ecole Polytechnique

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    double
    area
    area of the drawing region (width times height)
    double
    C
    step: by default step=1, in the original algorithm FR91
    protected double
    coolingConstant
    cooling constant: temperature decreases (e.g.
    private int
    countRepulsive
     
    AdjacencyListGraph
    g
    Input graph to draw
    double
    h
    dimensions of the drawing region
    int
    iterationCount
     
    double
    k
    strength of the spring ("optimal distance")
    static int
    maxIterations
    maximum number of iterations to perform
    protected double
    minTemperature
    minimal temperature (strictly positive)
    Jcg.geometry.Point_2[]
    points
    3D positions of the vertices of the graph defining the planar layout.
    protected double
    temperature
    initial temperature
    protected boolean
    useCooling
    decide whether to make use of simulated annealing
    double
    w
    dimensions of the drawing region

  • Constructor Summary

    Constructors
    Constructor
    Description
    FR91Layout(AdjacencyListGraph g, double w, double h)
    Initialize the parameters of the force-directed method, according to the original FR91 algorithm

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    attractiveForce(double distance)
    Compute the (intensity of the) attractive force between two nodes at a given distance
    Jcg.geometry.Vector_2[]
    computeAllAttractiveForces()
    Compute attractive forces for all vertices (between neighboring vertices)
    Jcg.geometry.Vector_2[]
    computeAllRepulsiveForces()
    Compute repulsive forces for all vertices (between all vertices)
    Jcg.geometry.Vector_2
    computeAttractiveForce(Node u)
     
    Jcg.geometry.Vector_2
    computeRepulsiveForce(Node u)
     
    protected void
    cooling()
    Cooling system: the temperature decreases at each iteration of a multiplicative factor Remark: the temperature is assumed to remain strictly positive (>=minTemperature)
    void
    disableCooling()
    Disable cooling process
    void
    enableCooling()
    Enable cooling process
    void
    oneIteration()
    Perform one iteration of the Force-Directed algorithm.
    double
    repulsiveForce(double distance)
    Compute the (intensity of the) repulsive force between two nodes at a given distance
    void
    repulsiveForce(Node u, Jcg.geometry.Vector_2[] disp)
    Compute the resultant of all repulsive forces acting on node 'u'.
    Jcg.geometry.Vector_2
    slowRepulsiveForce(Node u)
     
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • g

      public AdjacencyListGraph g
      Input graph to draw

    • points

      public Jcg.geometry.Point_2[] points
      3D positions of the vertices of the graph defining the planar layout.
      Remark: vertices are indexed from 0..n-1

    • maxIterations

      public static int maxIterations
      maximum number of iterations to perform

    • k

      public double k
      strength of the spring ("optimal distance")

    • C

      public double C
      step: by default step=1, in the original algorithm FR91

    • w

      public double w
      dimensions of the drawing region

    • h

      public double h
      dimensions of the drawing region

    • area

      public double area
      area of the drawing region (width times height)

    • temperature

      protected double temperature
      initial temperature

    • minTemperature

      protected double minTemperature
      minimal temperature (strictly positive)

    • coolingConstant

      protected double coolingConstant
      cooling constant: temperature decreases (e.g. linearly) at each iteration

    • useCooling

      protected boolean useCooling
      decide whether to make use of simulated annealing

    • iterationCount

      public int iterationCount

    • countRepulsive

      private int countRepulsive

  • Constructor Details

    • FR91Layout

      public FR91Layout(AdjacencyListGraph g, double w, double h)
      Initialize the parameters of the force-directed method, according to the original FR91 algorithm
      Parameters:
      g - the input graph to draw
      w - width of the drawing area
      h - height of the drawing area

  • Method Details

    • enableCooling

      public void enableCooling()
      Enable cooling process

    • disableCooling

      public void disableCooling()
      Disable cooling process

    • attractiveForce

      public double attractiveForce(double distance)
      Compute the (intensity of the) attractive force between two nodes at a given distance
      Parameters:
      distance - distance between two nodes

    • repulsiveForce

      public double repulsiveForce(double distance)
      Compute the (intensity of the) repulsive force between two nodes at a given distance
      Parameters:
      distance - distance between two nodes

    • oneIteration

      public void oneIteration()
      Perform one iteration of the Force-Directed algorithm. Positions of vertices are updated according to their mutual attractive and repulsive forces.

      This function computes first the node displacements vectors, and the updates node locations (stored in the array

    • slowRepulsiveForce

      public Jcg.geometry.Vector_2 slowRepulsiveForce(Node u)

    • computeRepulsiveForce

      public Jcg.geometry.Vector_2 computeRepulsiveForce(Node u)

    • repulsiveForce

      public void repulsiveForce(Node u, Jcg.geometry.Vector_2[] disp)
      Compute the resultant of all repulsive forces acting on node 'u'. The result is stored in the vector 'disp'

    • computeAttractiveForce

      public Jcg.geometry.Vector_2 computeAttractiveForce(Node u)

    • computeAllRepulsiveForces

      public Jcg.geometry.Vector_2[] computeAllRepulsiveForces()
      Compute repulsive forces for all vertices (between all vertices)
      Returns:
      a vector v[]: v[i] represent the geometric displacement of vertex i

    • computeAllAttractiveForces

      public Jcg.geometry.Vector_2[] computeAllAttractiveForces()
      Compute attractive forces for all vertices (between neighboring vertices)
      Returns:
      a vector v[]: v[i] represent the geometric displacement of vertex i

    • cooling

      protected void cooling()
      Cooling system: the temperature decreases at each iteration of a multiplicative factor Remark: the temperature is assumed to remain strictly positive (>=minTemperature)

    • toString

      public String toString()
      Overrides:
      toString in class Object