Graph Operations
Underlying each instance of the Toolkit there is a directed graph. This object - accessed via the getGraph
method of a jsPlumbToolkitInstance
- offers a complete set of methods for querying the state of the graph - from questions like "is node A connected to node B" through to "what is the shortest path from node A and node B?", or "what is the centrality of Node C?".
The code snippets on this page all refer to this dataset:
toolkit.load({
data:{
nodes:[ { id:"1" }, { id:"2" }, { id:"3" }, { id:"4" }, { id:"5" } ],
edges:[
{ source:"1", target:"2", cost:10 },
{ source:"2", target:"3", cost:5 },
{ source:"3", target:"4", cost:10 },
{ source:"3", target:"5", cost:10 }
]
}
});
Paths
Distance between objects
To find the distance between two objects, use the getDistance
method:
toolkit.getGraph().getDistance("1", "3")
-> 15
toolkit.getGraph().getDistance("1", "4")
-> 25
toolkit.getGraph().getDistance("4", "5")
-> undefined
Note the last example returns undefined
: remember that Edges in the Toolkit are, by default, directed. If you look again at the dataset you can see that there is no route from Node 4 to Node 5, since both of these Nodes are connected to the Graph only as targets of Edges from Node 3.
Shortest Paths
To get the shortest path from some Node/Port to another Node/Port, use the getPath
method:
The return value from this method is a Path. This is a complex object with many helper functions; if you need a more simple return value you can access the Graph's findPath
method directly:
toolkit.getGraph().findPath("1","3")
-> Object {dist: Object, previous: Object, edges: Object, path: Array[3], pathDistance: 15}
Centrality
Degree Centrality
The degree centrality of a node is the sum of the number of Edges entering and exiting the node divided by the total number of Edges in the Graph. Looking at the dataset we're using on this page you may have noticed that Node 3 has more connections than any other node, and this observation is reflected in the output of getDegreeCentrality
:
toolkit.getGraph().getDegreeCentrality("3")
-> 0.75
toolkit.getGraph().getDegreeCentrality("1")
-> 0.25
toolkit.getGraph().getDegreeCentrality("2")
-> 0.5
toolkit.getGraph().getDegreeCentrality("4")
-> 0.25
toolkit.getGraph().getDegreeCentrality("5")
-> 0.25
Indegree Centrality
The indegree centrality of a node is the number of edges entering the node, divided by the number of Edges in the Graph:
toolkit.getGraph().getIndegreeCentrality("3")
-> 0.25
toolkit.getGraph().getIndegreeCentrality("1")
-> 0
toolkit.getGraph().getIndegreeCentrality("2")
-> 0.25
toolkit.getGraph().getIndegreeCentrality("4")
-> 0.25
toolkit.getGraph().getIndegreeCentrality("5")
-> 0.25
Outdegree Centrality
The outdegree centrality of a node is the number of edges exiting the node, divided by the number of Edges in the Graph:
toolkit.getGraph().getOutdegreeCentrality("3")
-> 0.5
toolkit.getGraph().getOutdegreeCentrality("1")
-> 0.25
toolkit.getGraph().getOutdegreeCentrality("2")
-> 0.25
toolkit.getGraph().getOutdegreeCentrality("4")
-> 0
toolkit.getGraph().getOutdegreeCentrality("5")
-> 0
Farness
The farness
of a node is the sum of its distance from all other Nodes, where the distance from one Node to another is given by the associated cost of the Edge joining the two Nodes. As with degree centrality, this is divided by the number of Edges, to normalise the results. Note that here we have a Graph that has Nodes which cannot "reach" every other Node (because all Edges are directed
), so the "farness" of every Node is Infinity except Node 1, which can trace a path to every other Node.
toolkit.getGraph().getFarness("3")
-> Infinity
toolkit.getGraph().getFarness("1")
-> 18.75
toolkit.getGraph().getFarness("2")
-> Infinity
toolkit.getGraph().getFarness("4")
-> Infinity
toolkit.getGraph().getFarness("5")
-> Infinity
Closeness
This is the inverse of a Node's farness
:
toolkit.getGraph().getCloseness("3")
-> 0
toolkit.getGraph().getCloseness("1")
-> 0.05333333333333334
toolkit.getGraph().getCloseness("2")
-> 0
toolkit.getGraph().getCloseness("4")
-> 0
toolkit.getGraph().getCloseness("5")
-> 0
...so the only Node that has a useful value for closeness is Node 1. At the bottom of this page we present a revised version of the dataset in which Edges are all marked directed:false
, and then we show that the output of getFarness
and getCloseness
provides a usable value for every Node.
Betweenness Centrality
The betweenness centrality of a Node measures how central the Node is in the Graph. It is the number of shortest paths between any two Nodes in the Graph that pass through the given Nodes. The jsPlumb Toolkit computes this by first computing all the shortest paths in the Graph using the Floyd-Warshall algorithm.
toolkit.getGraph().getBetweenness("3")
-> 1.6666666666666667
toolkit.getGraph().getBetweenness("1")
-> 0
toolkit.getGraph().getBetweenness("2")
-> 0.6666666666666666
toolkit.getGraph().getBetweenness("4")
-> 0
toolkit.getGraph().getBetweenness("5")
-> 0
We see from the output here that Node 3 is the most "central" Node in this Graph, with Node 2 next. Nodes 1, 4 and 5 are not "central" as no paths go through these Nodes.
Graph Diameter
Use the getDiameter
method to find the Graph's diameter - the length of the "longest shortest path" in the Graph.
In a Graph that contains at least one pair of Nodes for which there is no available path, this value, strictly speaking, is Infinity. Our dataset on this page is one such Graph, but it doesn't seem like an unreasonable dataset, right? So the Toolkit allows you to specify that you're happy to ignore the case that there are one or more pairs of Nodes for which no Path exists:
The second result - 25 - is the distance of the path from Node 1 to Node 4 or 5, which is to say, the "longest shortest path" in the Graph:
Undirected Graphs
If we take the data from above and make every edge bidirectional, we get vastly different results for the centrality methods:
toolkit.load({
data:{
nodes:[ { id:"1" }, { id:"2" }, { id:"3" }, { id:"4" }, { id:"5" } ],
edges:[
{ source:"1", target:"2", cost:10, directed:false },
{ source:"2", target:"3", cost:5, directed:false },
{ source:"3", target:"4", cost:10, directed:false },
{ source:"3", target:"5", cost:10, directed:false }
]
}
});
For instance, here are the values for getFarness
:
toolkit.getGraph().getFarness("3")
-> 10
toolkit.getGraph().getFarness("1")
-> 18.75
toolkit.getGraph().getFarness("2")
-> 11.25
toolkit.getGraph().getFarness("4")
-> 17.5
toolkit.getGraph().getFarness("5")
-> 17.5
Note how the value for Node 1 - the only Node in the previous Graph that could "reach" all the other Nodes - is the same as in the previous Graph.
Here are the results for getCloseness
: