# Graph Operations

Underlying each instance of the Toolkit there is a directed graph. This object - accessed via the `getGraph` method of a Toolkit - 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 vertex C?".

``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 vertex 4 to vertex 5, since both of these Nodes are connected to the graphonly as targets of edges from vertex 3.

### Shortest Paths#

To get the shortest path from some vertex to another vertex, use the `getPath` method:

``toolkit.getPath({source:"1",target:"3"})-> e…s.Path {path: Object}``

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, 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 vertex 3 has more connections than any other node, and this observation is reflected in the output of `getDegreeCentrality` :

``toolkit.getGraph().getDegreeCentrality("3")-> 0.75toolkit.getGraph().getDegreeCentrality("1")-> 0.25toolkit.getGraph().getDegreeCentrality("2")-> 0.5toolkit.getGraph().getDegreeCentrality("4")-> 0.25toolkit.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.25toolkit.getGraph().getIndegreeCentrality("1")-> 0toolkit.getGraph().getIndegreeCentrality("2")-> 0.25toolkit.getGraph().getIndegreeCentrality("4")-> 0.25toolkit.getGraph().getIndegreeCentrality("5")-> 0.25``

### Outdegree Centrality#

The outdegree centrality of a node is the number of edges exiting the vertex, divided by the number of edges in the graph:

``toolkit.getGraph().getOutdegreeCentrality("3")-> 0.5toolkit.getGraph().getOutdegreeCentrality("1")-> 0.25toolkit.getGraph().getOutdegreeCentrality("2")-> 0.25toolkit.getGraph().getOutdegreeCentrality("4")-> 0toolkit.getGraph().getOutdegreeCentrality("5")-> 0``

### Farness#

The `farness` of a vertex is the sum of its distance from all other vertices, where the distance from one vertex to another is given by the associated cost of the edge joining the two vertices. 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 vertices which cannot "reach" every other vertex (because all edges are `directed`), so the "farness" of every vertex is Infinity except vertex 1, which can trace a path to every other vertex.

``toolkit.getGraph().getFarness("3")-> Infinitytoolkit.getGraph().getFarness("1")-> 18.75toolkit.getGraph().getFarness("2")-> Infinitytoolkit.getGraph().getFarness("4")-> Infinitytoolkit.getGraph().getFarness("5")-> Infinity``

### Closeness#

This is the inverse of a vertex's `farness`:

``toolkit.getGraph().getCloseness("3")-> 0toolkit.getGraph().getCloseness("1")-> 0.05333333333333334toolkit.getGraph().getCloseness("2")-> 0toolkit.getGraph().getCloseness("4")-> 0toolkit.getGraph().getCloseness("5")-> 0``

...so the only vertex that has a useful value for closeness is vertex 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 vertex.

### Betweenness Centrality#

The betweenness centrality of a vertex measures how central the vertex is in the graph. It is the number of shortest paths between any two vertices in the graphthat pass through the given Nodes. The jsPlumb Toolkit computes this by first computing all the shortest paths in the graphusing the Floyd-Warshall algorithm.

``toolkit.getGraph().getBetweenness("3")-> 1.6666666666666667toolkit.getGraph().getBetweenness("1")-> 0toolkit.getGraph().getBetweenness("2")-> 0.6666666666666666toolkit.getGraph().getBetweenness("4")-> 0toolkit.getGraph().getBetweenness("5")-> 0``

We see from the output here that vertex 3 is the most "central" vertex in this graph, with vertex 2 next. vertices 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 vertices 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 vertices for which no Path exists:

``````toolkit.getGraph().getDiameter()->Infinity
toolkit.getGraph().getDiameter(true)-> 25``````

The second result - 25 - is the distance of the path from vertex 1 to vertex 4 or 5, which is to say, the "longest shortest path" in the graph:

``toolkit.getGraph().getDistance("1","5")-> 25``

### 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")-> 10toolkit.getGraph().getFarness("1")-> 18.75toolkit.getGraph().getFarness("2")-> 11.25toolkit.getGraph().getFarness("4")-> 17.5toolkit.getGraph().getFarness("5")-> 17.5``

Note how the value for vertex 1 - the only vertex in the previous graph that could "reach" all the other vertices - is the same as in the previous graph.

Here are the results for `getCloseness` :

``toolkit.getGraph().getCloseness("3")-> 0.1toolkit.getGraph().getCloseness("1")-> 0.05333333333333334toolkit.getGraph().getCloseness("2")-> 0.08888888888888889toolkit.getGraph().getCloseness("4")-> 0.05714285714285714toolkit.getGraph().getCloseness("5")-> 0.05714285714285714``