Path Tracing

A graph is a structure that consists of a set of objects in which some set of pairs are related. The objects in the set are variously referred to as vertices or nodes, and sometimes points. The relationship between any two vertices is referred to as an edge, or link. Edges may be directed or undirected.Wikipedia gives a good example of directed vs undirected edges:

For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person A can shake hands with a person B only if B also shakes hands with A. In contrast, if an edge from a person A to a person B means that A owes money to B, then this graph is directed, because owing money is not necessarily reciprocated

Edges may also be weighted, which is the concept of how "expensive" it is to travel along that edge. A good analogy for this can be found in road networks: when a particular road is choked with traffic, we'd assign it a high weight value, whereas roads that have little to no traffic would be assigned a low value. Of course this is a simplified take: the weight of a road segment is more properly a measure of its current throughput, and in the real world we'd take into account how many lanes has, what the average speed is, etc. Interestingly, the nucleus of JsPlumb's data model came directly from some JS code we wrote many years ago as part of a road traffic simulation.

A Path is a sequence of vertices in which the target vertex of one edge is the source vertex of the next edge in the path. Where a graph contains directed edges, it may be the case that some vertex is not reachable from some other vertex, ie. there is no path available.

There are a number of different algorithms that are used to calculate paths in graphs. One of the most well-known, and the one that the Toolkit uses, isDjikstra's algorithm. In summary, Djikstra's algorithm works by assigning a 'distance' value for every vertex in the graph except for the source vertex, with an initial value of Infinity for each vertex. From the source vertex we find its neighbours, and then compute the distance to that neighbour from the weight of the edge. We then repeat the process using each of the neighbours as the focus. Each time we process a neighbour we check to see if our new computed distance to that neighbour is less than a previously computed distance, and if so, we store it. Once all the distance to every vertex has been computed we track back from the target vertex along the path represented by the minimum distance.

JsPlumb has at its core an implementation of a graph. Whenever you add a node to an instance of the Toolkit, that node is added as a vertex to the underlying graph. Whenever you establish a connection between two nodes, that connection is added as an edge to the underlying graph. This foundation adds a great deal of power to the Toolkit - you can reason with and interrogate its data model.

As mentioned above, JsPlumb uses the Djikstra algorithm to computer paths between vertices, but in fact we use a modified version which is able to take "ports" into account.

JsPlumb offers a number of methods for working with paths, which are discussed on our site here: https://docs.jsplumbtoolkit.com/toolkit/6.x/lib/paths.

JsPlumb's Surface renderer offers a complete solution for tracing paths through the UI. As shown in the demo above, there is a transport control available, and throughout the lifecycle of a path trace a number of CSS classes are used. You can read about path tracing in full on our site here: https://docs.jsplumbtoolkit.com/toolkit/7.x/lib/path-tracing.