Skip to content

Implementation of Fruchterman-Reingold algorithm for directed force Graph Drawing

License

Notifications You must be signed in to change notification settings

Average-user/fruchterman-reingold

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Fruchterman-Reingold algorithm for directed force Graph drawing

This implementation is not focused on performance, but in experimenting with this relatively simple algorithm, and visualising its process.

Main Idea

The idea of a Graph drawing is simply to take a graph and display it on a screen in a "pleasing" way whatever this means. The way that Fruchterman and Reingold approach this, is to think vertices as particles in space that exert repulsive force to the others and attractive force to the ones that are connected by some edge.

Visualisation

Live visualisation is implemented with quil. Here are some examples of starting positions (random) and resulting ones:

Starting Position Result Gif

Starting Position Result

Twin K5

Starting Position Result

Random Graph of 10 vertices. [Generated with p=0.41, seed=-957442595]

Starting Position Result Gif

Random Graph of 20 vertices. [Generated with p=0.15, seed=-173247684]

Starting Position Result Gif

Usage

Execute with

lein run

In order to try out other graphs is likely that you only need to change some of the following lines of core.clj:

(def W 600)
(def H 600)
(def line-weight 3)
(def node-radius 15)

(defn setup []
  (q/ellipse-mode :center)
  (q/frame-rate 60)
  {:states (al/fruchterman-reingold g/Durer (- W 30) (- H 30) 0.7)
   ;; We need to make with and height a little smaller since in the actual drawing
   ;; points have area i.e are not really points
   :i -50})

W (width), H (height), line-weight, node-radius and frame-rate all explain themselves. The first of the al/fruchterman-reingold arguments is the graph (undirected) to be drawn, to exemplify how is that we represent graphs, here's the complete graph of three vertices:

{:V #{:a :b :c}
 :E #{#{:a :b} #{:a :c} #{:b :c}}}

You can either try out some of the graphs in graphs.clj or create your own. In the later case some important observations are that the graph must be connected and that the elements do not need to be keywords, since we are only interested in the structural properties of a graph and not its content.

The last argument (0.7 as default) is the ideal edge length coefficient C. Fruchterman and Reingold approximate the ideal length of edges as C*sqrt(W*H/|V|), in some cases if we set C too small the graph will look too dense, and if we set it too large It will run out of space.

About

Implementation of Fruchterman-Reingold algorithm for directed force Graph Drawing

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published