Springboard Graphs.ipynb

Kernel: Python 3 (system-wide)

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 $1$ and spring constant $k>0$. Let each node $A$ have mass and charge $\deg(A)$, and let the electric field constant be $Q<0$.

So, for every node $A$, the force due to a spring connecting node $A$ to $B$ is $$k (1-\|\vec{AB}\|)\frac{\vec{AB}}{\|\vec{AB}\|}$$ and the electrostatic force between node $A$ and any other node $B$ is $$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, $$\frac{-\vec{A}\deg(A)*0.001}{|A||}$$

Since each node $A$ has mass $\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: $$\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 $A$, let $\mathcal{X}$ denote the set of all nodes not equal to $A$, and let $\mathcal{Y}\subseteq\mathcal{X}$ denote the set of nodes connected to $A$. Then, for the time step $\Delta t$, the displacement of node $A$ is $$\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}\|}.$$

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

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

nodesForBinTree= {1:[2,3], 2:[4,5], 3:[6,7], 4:[], 5:[], 6:[], 7:[]}
binTree = SpringBoard(nodesForBinTree, k=1, Q=-1)

binTree.plot()

binTree.move(0.1,8000)
binTree.plot()

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()

pageRank.move(0.1,8000)

pageRank.plot()

The DiGraph Class

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()

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]])

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()

fromDanielSpielman.random_reset()
fromDanielSpielman.plot()

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()

nonPlanar.force(30000)
nonPlanar.plot()