Satsuma.Drawing.ForceDirectedLayout Class Reference

Attempts to draw a graph to the plane such that a certain equilibrium is attained. More...

Public Member Functions
	ForceDirectedLayout (IGraph graph, Func< Node, PointD > initialPositions=null)
void	Initialize (Func< Node, PointD > initialPositions=null)
	Initializes the layout with the given one and resets the temperature. More...
void	Run (double minimumTemperature=DefaultMinimumTemperature)
	Runs the algorithm until a low temperature is reached. More...
void	Step ()
	Performs an optimization step. More...

Public Attributes
const double	DefaultMinimumTemperature = 0.01
	The temperature where the simulated annealing should stop. More...
const double	DefaultStartingTemperature = 0.2
	The default initial temperature for the simulated annealing. More...
const double	DefaultTemperatureAttenuation = 0.95
	The ratio between two successive temperatures in the simulated annealing. More...

Properties
Func< double, double >	ElectricForce [get, set]
	The function defining the repulsion force between two nodes. More...
IGraph	Graph [get, set]
	The input graph. More...
Dictionary< Node, PointD >	NodePositions [get, set]
	The current layout, which assigns positions to the nodes. More...
Func< double, double >	SpringForce [get, set]
	The function defining the attraction force between two connected nodes. More...
double	Temperature [get, set]
	The current temperature in the simulated annealing. More...
double	TemperatureAttenuation [get, set]
	The temperature attenuation factor used during the simulated annealing. More...

Detailed Description

Attempts to draw a graph to the plane such that a certain equilibrium is attained.

Models the graph as electrically charged nodes connected with springs. Nodes are attracted by the springs and repelled by electric forces.

By default, the springs behave logarithmically, and (as in reality) the electric repulsion force is inversely proportional to the square of the distance. The formulae for the attraction/repulsion forces can be configured through SpringForce and ElectricForce.

The algorithm starts from a given configuration (e.g. a random placement) and lets the forces move the graph to an equilibrium. Simulated annealing is used to ensure good convergence. Each convergence step requires O(n²) time, where n is the number of the nodes.

Force-directed layout algorithms work best for graphs with a few nodes (under about 100). Not only because of the running time, but also the probability of running into a poor local minimum is quite high for a large graph. This decreases the chance that a nice arrangement is attained.

Example:

var g = new CompleteGraph(7);
var layout = new ForceDirectedLayout(g);
layout.Run();
foreach (var node in g.Nodes())
    Console.WriteLine("Node "+node+" is at "+layout.NodePositions[node]);

Definition at line 138 of file Layout.cs.

Constructor & Destructor Documentation

Satsuma.Drawing.ForceDirectedLayout.ForceDirectedLayout	(	IGraph	graph,
		Func< Node, PointD >	initialPositions = null
	)

Definition at line 168 of file Layout.cs.

Member Function Documentation

void Satsuma.Drawing.ForceDirectedLayout.Initialize

(

Func< Node, PointD >

initialPositions = null

)

Initializes the layout with the given one and resets the temperature.

Parameters

initialPositions

If null, a random layout is used.

Definition at line 181 of file Layout.cs.

void Satsuma.Drawing.ForceDirectedLayout.Run

(

double

minimumTemperature = DefaultMinimumTemperature

)

Runs the algorithm until a low temperature is reached.

Definition at line 234 of file Layout.cs.

void Satsuma.Drawing.ForceDirectedLayout.Step

(

)

Performs an optimization step.

Definition at line 198 of file Layout.cs.

Member Data Documentation

const double Satsuma.Drawing.ForceDirectedLayout.DefaultMinimumTemperature = 0.01

The temperature where the simulated annealing should stop.

Definition at line 143 of file Layout.cs.

const double Satsuma.Drawing.ForceDirectedLayout.DefaultStartingTemperature = 0.2

The default initial temperature for the simulated annealing.

Definition at line 141 of file Layout.cs.

const double Satsuma.Drawing.ForceDirectedLayout.DefaultTemperatureAttenuation = 0.95

The ratio between two successive temperatures in the simulated annealing.

Definition at line 145 of file Layout.cs.

Property Documentation

Func<double, double> Satsuma.Drawing.ForceDirectedLayout.ElectricForce

getset

The function defining the repulsion force between two nodes.

Nodes are viewed as electrically charged particles which repel each other. The function takes a single parameter, which is the distance of the two nodes.

The default force function is 1/d².

Definition at line 162 of file Layout.cs.

IGraph Satsuma.Drawing.ForceDirectedLayout.Graph

getset

The input graph.

Definition at line 148 of file Layout.cs.

Dictionary<Node, PointD> Satsuma.Drawing.ForceDirectedLayout.NodePositions

getset

The current layout, which assigns positions to the nodes.

Definition at line 150 of file Layout.cs.

Func<double, double> Satsuma.Drawing.ForceDirectedLayout.SpringForce

getset

The function defining the attraction force between two connected nodes.

Arcs are viewed as springs that want to bring the two connected nodes together. The function takes a single parameter, which is the distance of the two nodes.

The default force function is 2 ln(d).

Definition at line 156 of file Layout.cs.

double Satsuma.Drawing.ForceDirectedLayout.Temperature

getset

The current temperature in the simulated annealing.

Definition at line 164 of file Layout.cs.

double Satsuma.Drawing.ForceDirectedLayout.TemperatureAttenuation

getset

The temperature attenuation factor used during the simulated annealing.

Definition at line 166 of file Layout.cs.

---

The documentation for this class was generated from the following file:

• src/Layout.cs