Open in CoCalc with one click!

Springboard Graphs

Here we attempt to model graphs as systems of charged particles, connected by springs, in order to determine "optimal" plotting positions for nodes. We will do a time-step approximation of the movement of the nodes, based on spring and electrostatic forces. We will assume that the graph has no self-loops.

Let each spring (graph connection) have unstretched length 11 and spring constant k>0k>0. Let each node AA have mass and charge deg(A)\deg(A), and let the electric field constant be Q<0Q<0.

So, for every node AA, the force due to a spring connecting node AA to BB is k(1AB)ABABk (1-\|\vec{AB}\|)\frac{\vec{AB}}{\|\vec{AB}\|} and the electrostatic force between node AA and any other node BB is Qdeg(A)deg(B)AB2ABAB.Q\frac{\deg(A)\deg(B)}{\|\vec{AB}\|^2}\frac{\vec{AB}}{\|\vec{AB}\|}.

We will also add a universal attractive force to all of the nodes from the origin, Adeg(A)0.001A\frac{-\vec{A}\deg(A)*0.001}{|A||}

Since each node AA has mass deg(A)\deg(A), we can relate the net force on a node to a time-step approximation of accelaration in order to approximate the movement of the nodes: ΔdΔt2deg(A)ma=F    ΔdΔt2deg(A)F.\frac{\Delta \vec{d}}{\Delta t^2}\deg(A)\approx m\vec{a}= \vec{F}\implies \Delta \vec{d} \approx \frac{\Delta t^2}{\deg(A)}\vec{F}.

Given any node AA, let X\mathcal{X} denote the set of all nodes not equal to AA, and let YX\mathcal{Y}\subseteq\mathcal{X} denote the set of nodes connected to AA. Then, for the time step Δt\Delta t, the displacement of node AA is Adeg(A)0.001A+BYΔt2k(AB1)deg(A)ABAB+BXQΔt2deg(B)AB2ABAB.\frac{-\vec{A}\deg(A)*0.001}{|A||} + \sum_{B\in\mathcal{Y}}\frac{\Delta t^2k (\|\vec{AB}\|-1)}{\deg(A)}\frac{\vec{AB}}{\|\vec{AB}\|}+\sum_{B\in\mathcal{X}}\frac{Q\Delta t^2\deg(B)}{\|\vec{AB}\|^2}\frac{\vec{AB}}{\|\vec{AB}\|}.

In [6]:
from graph-plot import * # See: https://github.com/francisp336/diGraph
File "<ipython-input-6-936544eda53d>", line 1 from graph-plot import * # See: https://github.com/francisp336/diGraph ^ SyntaxError: invalid syntax
In [2]:
help(diGraph)
Help on module diGraph.diGraph in diGraph: NAME diGraph.diGraph CLASSES builtins.object DiGraph Graph Node SpringBoard class DiGraph(builtins.object) | DiGraph object | | Methods defined here: | | __init__(self, nodesDict:dict) | Construct DiGraph object | nodesDict - adjacency dictionary of first positive integers | | force(self, n:int) | Move forward time step simulation | n - number of time steps | | plot(self, saveAs:str='_') | Plot the Graph | saveAs - (optional) a file path to save the plot | | random_reset(self) | Randomly reset node positions and let time step simulation resettle | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class Graph(builtins.object) | Graph object | | Methods defined here: | | __init__(self, nodesDict:dict) | Construct Graph object | nodesDict - adjacency of first positive integers | | force(self, n:int) | Move forward time step simulation | n - number of time steps | | plot(self, saveAs:str='_') | Plot the Graph | saveAs - (optional) a file path to save the plot | | random_reset(self) | Randomly reset node positions and let time step simulation resettle | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class Node(builtins.object) | Node object | | Methods defined here: | | __init__(self, ID:int=-1, connections:list=None, pos:<built-in function array>=None) | Initialize Node object. | ID - node identifier | connections - list of connected nodes | pos - (x,y) position of node | | __repr__(self) | retrurn string representation of (self) node | | addConnection(self, connection) | Add connection to node and update the node degree | connection - connected node | | addConnections(self, connections:list) | Add connection to node and update the node degree | connection - list of connected nodes | | distanceTo(self, node) | Return distance to node | node - Node object | | equals(self, node) | Return if equal to node | node - Node object | | setCoord(self, pos:<built-in function array>) | Set node position | pos - (x,y) position of node | | setDisplacement(self) | Add displacement to node position | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class SpringBoard(builtins.object) | SpringBoard object | | Methods defined here: | | __init__(self, nodesDict:dict, k:float, Q:float) | nodes - an adjacency dictionary of first positive integers | k - coefficient of spring | Q - coefficient of electric field | | move(self, deltaT:float, n:int) | Iterate _increment() | deltaT - simulation time step | n - number of time steps | | move_plot_save(self, deltaT:float, n:int, saveAs:str) | Move forward in simulation and save image after each timestep | deltaT - simulation time step | n - number of time steps | saveAs - folder path to save images | | plot(self, saveAs:str='_') | Plot the graph. | saveAs - (optional) file path to save | | random_reset(self) | Randomly reset node positions | | settle(self, deltaT:float) | Increment timestep simulation until objects have settled | deltaT - simulation time step | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) FILE /home/user/.local/lib/python3.6/site-packages/diGraph/diGraph.py
In [3]:
nodesForBinTree= {1:[2,3], 2:[4,5], 3:[6,7], 4:[], 5:[], 6:[], 7:[]} binTree = SpringBoard(nodesForBinTree, k=1, Q=-1) binTree.plot()
In [4]:
binTree.move(0.1,8000) binTree.plot()
In [5]:
nodesForPageRank = {1:[2,3,7], 2:[3,4], 3:[5], 4:[5,6], 5:[6,7,8], 6:[8], 7:[8], 8:[] } pageRank = SpringBoard(nodesForPageRank, k=1.5, Q=-1) pageRank.plot()
In [6]:
pageRank.move(0.1,8000) pageRank.plot()

The DiGraph Class

In [7]:
digraph = DiGraph({1: [3,2], 2: [4], 3: [], 4: [2, 5, 6], 5: [7, 8, 6], 6: [8], 7: [1, 5, 8], 8: [6, 7, 9], 9:[]}) digraph.plot()
In [8]:
digraph.adjacencyMatrix
array([[0, 0, 0, 0, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 1, 0, 0], [0, 0, 0, 1, 1, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0, 0, 1, 0], [0, 0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0]])
In [9]:
fromDanielSpielman = DiGraph({1:[2,5,4], 2:[1,3], 3:[2,6,4], 4:[1,3], 5:[1,7,8], 6:[7,8,3], 7:[5,6], 8:[5,6]}) fromDanielSpielman.plot()
In [10]:
fromDanielSpielman.random_reset() fromDanielSpielman.plot()
In [11]:
nonPlanar = DiGraph({1:[2,3,6], 2:[1,5,4], 3:[1,4,5], 4:[2,3,6], 5:[2,3,6], 6:[1,4,5]}) nonPlanar.plot()
In [12]:
nonPlanar.force(30000) nonPlanar.plot()
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]: