OR-Objects Tutorial 1: Shortest Path Applet

In this tutorial you will learn how to use OR-Objects to build a graph like the one pictured above and use it in a shortest path algorithm. This graph has seven vertices which are labeled 'A' through 'G'. It has ten edges which connect the vertices and there is a cost associated with each edge. Eight of the edges are undirected and the two with arrows are directed. An undirected edge is one that can be crossed in both directions and a directed edge is one that can only be crossed in a single direction.

For example, it costs '2' to cross the edge between 'A' and 'B' and it can be crossed both ways. It costs '1' to cross the edge between 'E' and 'B', but it can only be crossed from 'E' to 'B'. The algorithm will find the shortest path from a beginning vertex to a ending vertex making sure it only crosses the edges in the correct direction. There are many other properties that can be associated with the vertices and edges, but this tutorial only uses cost to keep things simple. If you would like to see an example of a more complex problem see Tutorial-2.

Since this tutorial is about using OR-Objects and not writing applets some of the applet details will be skipped. You can view the complete source if you would like more details.

Add Vertices
Add Edges

DisplayPath

Generate Path
Get Cost
Get Path

The Applet

The following code fragment shows the definition of the 'Tutorial_1' applet and the declaration of the variable 'algorithm' which will hold the shortest path algorithm. 'SingleVertexI' is an interface and interfaces in OR-Objects end with a capital 'I', this is only a convention and isn't required. There will be more about interfaces later. Notice the 'import' statement, this tells the compiler where to find the graph classes we are using.

import drasys.or.graph.*;

import drasys.or.graph.sp.*;

public class Tutorial_1
extends Applet
{
SingleVertexI algorithm;

Initialization

This is the initialization function that is called when the browser starts the applet. It is where the graph is built and the algorithm is initialized. The following code fragment shows the creation of the graph. Notice that the graph variable is an interface 'GraphI' and not the class 'SparseGraph'. This is possible because the 'GraphI' interface is implemented by 'SparseGraph' and it provides all the functionality we need to operate on the graph. This is an advantage because 'DenseGraph' implements the 'GraphI' interface as well, and if we decide to change to a dense graph, all we need to do is change the creation statement. You will see interfaces used this way throughout OR-Objects.

    public void
    init()
    {
        SparseGraph graph = new SparseGraph();

Initialization - Add Vertices

The next step in the initialization function is to add the vertices. The vertices are added before the edges because an edge can not be added before its vertices. The argument to 'addVertex' is the vertex key. In this tutorial the vertex keys are strings but they can be any object. All vertices must have a key and no two vertices can have the same key.

        // Add the vertices
        try{
            graph.addVertex("a");
            graph.addVertex("b");
            graph.addVertex("c");
            graph.addVertex("d");
            graph.addVertex("e");
            graph.addVertex("f");
            graph.addVertex("g");

            graph.addVertex("h");
        }
        catch(DuplicateVertexException e){}

Initialization - Add Edges

This code fragment adds the edges to the graph and constructs the algorithm. The first two arguments to 'addEdge' are the vertices adjacent to the edge. The third argument is the value of the edge, this can be any object. Notice that the last two calls to 'addEdge' have an additional argument, if this argument is 'true' the edge is directed. Otherwise; it is undirected. For a directed edge the first vertex is the 'from' vertex and the second is the 'to'.

        // Add the edges
        try{
            graph.addEdge("a","b",new Double(2));
            graph.addEdge("a","c",new Double(2));
            graph.addEdge("d","b",new Double(3));

            graph.addEdge("d","c",new Double(2));
            graph.addEdge("d","e",new Double(2));
            graph.addEdge("d","f",new Double(3));
            graph.addEdge("g","e",new Double(2));
            graph.addEdge("g","f",new Double(2));
            graph.addEdge("e","b",new Double(1),true); // directed
            graph.addEdge("c","f",new Double(1),true); // directed
        }
        catch(DuplicateEdgeException e){}
        catch(VertexNotFoundException e){}

        algorithm = new Dijkstra(graph);
    }

DisplayPath

This is the method that generates the path and displays the results. The source and destination keys are passed as arguments and first step is to check to see if the source and destination are the same.

    public void
    displayPath(Object src, Object dst)
    {
        if(src.equals(dst)){
            pathLabel.setText(src);
            costLabel.setText("0.0");
            return;
        }

DisplayPath - Generate Path

The algorithm generates paths from a source vertex to a group of vertices that are marked as candidates. In this example we only have one candidate and it is the destination vertex where we want the path to end. The first call to 'setCandidate' clears all the candidates and the second makes 'dst' a candidate. Then 'generatePathsFrom' is used to create the path from 'src' to 'dst'..

        try{
            algorithm.setCandidate(false);
            algorithm.setCandidate(dst, true);
            algorithm.generatePathsFrom(src);

The algorithm has a 'generatePathsTo' that is not used here. It creates the paths starting at the candidates and ending at the destination vertex passed as the argument.

DisplayPath - Get Cost

The 'getNearestCandidate' method is used to get the candidate that has the shortest path. In this example the destination is the only candidate so it will be returned and 'getCost' returns the cost of the path.

            VertexI nearest = algorithm.getNearestCandidate();
            double cost = algorithm.getEdgeValue(nearest).getCost(false);
            costLabel.setText(String.valueOf(cost));

DisplayPath - Get Path

This section gets the path from the algorithm and builds the string representation. The call to 'getPath' returns a 'Vector' object that contains all the vertices and edges that make up the path. Then 'elements' method returns an enumeration that is used to sequence through the elements. The first vertex is added to the string and the while loop adds the rest.

            Vector path = algorithm.getPath(nearest);
            Enumeration enum = path.elements();
            VertexI vertex = (VertexI)enum.nextElement();
            String pathStr = String.valueOf(vertex.getKey());

            while(enum.hasMoreElements()){
                enum.nextElement();// Discard Edge //
                vertex = (VertexI)enum.nextElement();
                pathStr += " - " + vertex.getKey();
            }
            pathLabel.setText(pathStr);

        }
        catch(VertexNotFoundException e){}
        catch(InvalidPropertyException e){}
    }

Tutorial 1 - Shortest Path Applet