Rappid - alg

alg.Dijkstra is an implementation of the Dijkstra's shortest path algorithm. It can efficiently find the shortest path in both directed and undirected graphs. This implementation uses a binary heap based priority queue. The time complexity of this algorithm is O(|E| + |V| log |V|), where |E| is the number of edges in the graph and |V| is the number of nodes.

Install

Include both joint.alg.dijkstra.js and its priority queue dependency files into your HTML:

<script src="joint.alg.priorityQueue.js"></script>
<script src="joint.alg.dijkstra.js"></script>

Usage

Even though alg.Dijkstra is listed as a separate plugin, you usually don't use it directly. Instead, you can use the dia.GraphUtils plugin which extends the joint.dia.Graph with a convenience method for finding the shortest path between two nodes shortestPath(source, target [, opt]). However, it could be useful to use alg.Dijkstra directly in some situations. The reason is that alg.Dijkstra calculates not only the shortest path between two nodes but the shortest path between a node and all the other nodes in the graph.

joint.alg.Dijkstra is a function that takes a graph represented as an adjacency list, a source node and optionally a weight function. The adjacency list is an object where a key is a node ID and value is an array or IDs of the neighbouring nodes of that node. If you want to use alg.Dijkstra directly on a JointJS graph, you first have to convert the graph into the adjacency list. (This is what the shortestPath() method from the alg.GraphUtils plugin does for you internally.) weight function is a function that takes two nodes and returns a distance between them. How you define distance between two nodes is completely on you. By default, the distance is always 1. Only keep in mind that the Dijkstra's algorithm requires the weight to be a positive integer.

The function returns a special object that encodes the shortest paths between the node provided and all the other nodes in the graph.

var graph = {
    a: ['b', 'c'],
    b: ['d', 'e'],
    c: ['f', 'g'],
    f: ['b'],
    e: ['c'],
    h: ['f', 'g'],
    i: ['h', 'a', 'd', 'g'],
    j: ['a']
};

var previous = joint.alg.Dijkstra(graph, 'a');
// { b: "a", c: "a", e: "b", f: "c" }

The above example shows the result of the joint.alg.Dijkstra function. This special object allows us to get the shortest path to all the nodes in the graph starting at node 'a'. For example, the shortest path to the node 'f' is a path ['a', 'c', 'f']. How did we get there? You simply start from your target node and keep asking the returned object node by node till you reach your source node. In other words, we start by previous['f'] which gives us 'c' Then we ask for previous['c'] which gives us 'a' and we're done since we reached our source node.

API

alg.PriorityQueue is an implementation of the Priority Queue abstract data type. It is like a normal stack or queue, but where each item has assigned a priority (a number). Items with higher priority are served before items with lower priority. This implementation uses binary heap as an internal representation of the queue. The time complexity of all the methods is as follows:

• create: O(n)
• insert: O(log n)
• peek: O(1)
• peekPriority: O(1)
• remove: O(log n)
• isEmpty: O(1)

alg.PriorityQueue is used internally by the alg.Dijkstra algorithm for finding the shortest path in a graph. It is however useful on its own, that's why it is listed as a separate plugin.

Install

Include joint.alg.priorityQueue.js file into your HTML:

<script src="joint.alg.priorityQueue.js"></script>

Usage

The usage of alg.PriorityQueue is pretty simple. You just have to create an object of the joint.alg.PriorityQueue type. Then you can insert, remove or retrieve elements from the queue similarly as you would do with a normal JavaScript array.

var q = new joint.alg.PriorityQueue;
q.insert(1, 'one');
q.insert(3, 'three');
q.insert(2, 'two');

q.peek()  // the first value is 'one'
q.peekPriority()  // the first priority is 1
q.remove() // the first value was 'one'
q.remove() // the second value was 'two'
q.remove() // the third value was 'three'
q.isEmpty() // true

Moreover, this implementation of the priority queue allows you to update priorities of any item that you have inserted into the queue. This is also known as the decreaseKey operation. For this to work, you have to give each item you insert into the queue a unique ID. This is because in JavaScript, objects do not have unique IDs by default. Therefore, there is no way the alg.PriorityQueue can know which item you'd like to update priority for. Here is an example of priority queue that uses the updatePriority() operation:

var q = new joint.alg.PriorityQueue;
q.insert(1, 'one', 'id1');
q.insert(3, 'three', 'id3');
q.insert(2, 'two', 'id2');

q.peek() // the first value is 'one'
q.updatePriority('id1', 5);
q.peek() // now the first value is 'two'
q.updatePriority('id1', 1);
q.peek() // the first value 'one' got again back to the top

API