Using the Path Calculator

THE SCIENCE AND TECHNOLOGY OF DECISION-MAKING
CIV 105 - Princeton University

Using the Path Calculator

Introduction: What is a network?

A network consists of nodes and links (or arcs). Nodes are usually drawn as circles and links are drawn as lines connecting the nodes. A path is a route from one node to another across a specific series of links. The following is an example of a network consisting of 4 nodes and 5 links:

Node 0 (in green) represents the origin node and Node 1 (in red) represents the destination node. The links have directional arrows with numbers next to them, which represent the cost associated with that link. A path can be written as the sequence of nodes through which the path travels.

In this example, there are 3 paths from the origin to the destination: 0-2-1, 0-3-1, and 0-2-3-1. The optimal path is the path with the least total cost of all the links used on the path. In this case, we can see that the optimal path from the origin to the destination is path 0-2-3-1, with a total cost of 30. The Path Calculator would display this result as follows, with the links and nodes used by the optimal path in blue:

Attributes of a Network

A network attribute is a factor by which the links of that network are valued. In the example above, the general term ``cost'' was used as the attribute of the network. A network can have many attributes associated with its links. For example, if you think of the network as roads (the links) connecting various cities (the nodes), some important attributes could be travel time, distance, and traffic.

The network may have different optimal paths depending on which attribute is used to place values on the links. Notice that all the attributes listed above are ones whose values should be MINIMIZED on the optimal path. This is important to remember, since this program only finds the path from the origin to the destination that has the SMALLEST total value of the links used in the path.

About the Path Calculator

The Path Calculator can be used to create networks and to find optimal paths across networks with respect to different attributes.

The Path Calculator window appears as follows (this will look different on different machines):

The various buttons that control the execution of the program appear at the top of the window. The network is drawn in the middle of the window. The bottom of the window has two long white areas where information and directions are placed. The upper area will contain the results of finding an optimal path; the lower will contain directions for carrying out the actions of the current mode, as well as display error messages when those happen to occur.

Commands/Buttons

All commands are initiated using the buttons at the top of the Path Calculator window.

Exit: Close the Path Calculator window and terminate the program.
Load: Load a pre-defined network.
Clear: Clear (i.e., delete) the current network.
Run: Find the ``best'' path from the given origin to the given destination (based on the current link attribute).
Reset: Reset the current network so that another path can be calculated.

Creating Netwoks

When the Path Calculator window is first started, you will see a box directly below the row of buttons that says ``Add node''. This is one of several MODES which the program can be in for creating a network. Click on this box and hold down the mouse button to view the rest of the choices. Releasing the mouse button on any of these choices will place the program into that mode or carry out that command. The text line at the bottom of the Path Calculator contains directions for carrying out the actions of the current mode. You can always tell what mode the program is in by reading the directions in this line. If the line is empty, or if it contains something other than directions, then the program is not in any mode and clicking on the network will do nothing. The different options of the choice list are listed and explained as follows:

Add Node: In this mode, you can add a new node to the existing network by clicking the mouse on the appropriate location.
Delete Node: In this mode, you can delete an existing node by clicking on it with the mouse.
Move Node: In this mode, you can move an existing node (and the links connected to it). First click on the node that you want to move. Then click on the new location.
Set Origin: In this mode, you can select the origin node (i.e., the node that the path will start from) by clicking on it with the mouse. The origin node appears in green. If you try to put the origin node where the destination node currently is, the origin will not move and an error message will appear.
Set Destination: In this mode, you can select the destination node (i.e., the node that the path will end at) by clicking on it with the mouse. The destination node appears in red. If you try to put the destination node where the origin node currently is, the destination will not move and an error message will appear.
Add Link: In this mode, you can add a new link to the existing network. First click on the starting (i.e., tail) node. Then click on the ending (i.e., head) node. Note that all links are uni-directional. However, you can have two links connecting the same pair of nodes in opposite directions. The value displayed next to the arrowhead of the new link will be the distance between the nodes that the link connects (in pixels). This number can be changed in the Modify Link mode.
Delete Link: In this mode, you can delete an existing link by clicking on it's arrowhead.
Modify Link: In this mode, you can change the value of a link's attribute by clicking on the link's arrowhead and then entering the new value in a dialogue box. [Remember: Each link can have several attributes (e.g., length, time, cost). The current attribute is selected using the Set Attribute command.] The dialog box appears as follows:

The number in the white box is initially set to the current value of the link under the active attribute. Change the number in this box to the desired value and click on the Replace button. This will close the Link Adjust window and replace the value next to the chosen link's arrowhead to the value you entered. Clicking the Cancel button will close the Link Adjust window and leave the link value unchanged. There must be an INTEGER value in the white box when the Replace button is clicked, or the procedure will not work.
The final four options do not change the mode by which the network can be created or modified, but instead are commands within themselves:
Add Attribute: Add an additional link attribute. Choosing this option will immediately produce a window, which appears as follows:

You can either keep the name which is displayed (Cost plus the number of the attribute) by clicking the Replace button immediately, or you can change the entry in the white box to whatever name you'd like and then click the Replace button. When the Replace button is clicked, the window will disappear and values of the links will be replaced with those of the new attribute (initially set to be the distance in pixels between the nodes). You can switch back to one of the other attributes using the Set Attribute command. If you decide not to add a new attribute, click the Cancel button. Either way, you must click one of these two buttons in order to close the window and continue.
Modify Attribute: Change the name of the current attribute. Choosing this option will produce the same window that appears when Add Attribute is chosen, except the name in the white box will be the name of the current attribute rather than a new one. Change the entry in this box and click the Replace button, which will set the new name and close the window.
Set Attribute: Select the active attribute (i.e., the attribute that is displayed and that can be modified in the Modify Link mode). When this option is chosen a window such as the following will appear (may look different on different machines):

In order to select the active attribute, DOUBLE CLICK on the name of the attribute. This will close the window and set the link labels of the network to their values under the chosen attribute. Clicking the Cancel button will keep the active attribute the same as it was before the Attribute Choice window appeared.
Switch Tree Type: Change the tree display presentation. The presentation starts out by showing large circles for the nodes and labeling the links with their respective costs. If this becomes too cluttered, choosing this option will switch the presentation to one with small dots for nodes and no numbers next to the links. Choose this option again to switch back.