Improve spring_layout() and other layout algorithms. (migrated from Trac #229)

[networkx-trac]

Original ticket https://networkx.lanl.gov/trac/ticket/229 Reported 2009-02-16 by @hagberg, assigned to @hagberg.

Spring layout can be improved using numpy.

Other layouts need documentation and speed improvements.

[networkx-trac]

Comment in Trac by @hagberg, 2009-02-16

(In [1146]) Update layout.py

• Improved Fruchterman-Reingold that uses numpy matrix operations
• Use numpy dense eigensolver or scipy sparse eigensolver for spectral_layout
• Simpler random and circular layouts
• Documentation

Fixes #216

Fixes #223

Addresses #229

[networkx-trac]

Comment in Trac by @hagberg, 2009-02-16

These versions of the layout algorithms are an order of magnitude or two faster than the previous ones.

The Fruchterman-Reingold algorithm is still O(V^2) so it won't be appropriate for very large layouts. It also uses a lot of memory as trade-off to speed. Probably one can do in the thousands of nodes before you run out of memory or patience. Using a multilevel solver would make this go much faster.

The spectral layout uses a SciPy sparse matrix eigensolver for large networks. That is only available in scipy-0.7.0 or later.

It would be a good homework problem to implement the Kamada Kawai algorithm (it is simpler than Fruchterman Reingold) or the "LGL" algorithm that uses spanning trees http://www.ncbi.nlm.nih.gov/pubmed/15184029?dopt=Abstract

[networkx-trac]

Comment in Trac by @chebee7i, 2009-12-12

[networkx-trac]

Comment in Trac by @hagberg, 2010-03-10

[networkx-trac]

Comment in Trac by @hagberg, 2010-07-22

[networkx-trac]

Comment in Trac by @hagberg, 2010-09-06

[networkx-trac]

Comment in Trac by @hagberg, 2010-09-06

Kamada-Kawai and LGL algorithms are still interesting but can be addressed by opening other tickets.