GENERAL INFO ======= ==== The purpose of this Flash project is to demonstrate the Floyd-Warshall all shortest paths graph algorithm. Outline of the program's behavior: * Prompt for GraphML file. * Parse the graph out of the file, building structure in memory. (If parsing fails, an error is presented and the user may provide another file.) * The graph will be displayed and the algorithm will be stepped through. Controls allow for enabling/disabling the audio and "automatic advance," as well as for viewing the two matrices (only if automatic advance is off). Note that negative loops in a graph will cause the algorithm to fail. In this project, the presentation will continue, but the negative loop will be detected and reported. Notes on the GraphML format expected: The GraphML document is expected to be laid out generally like this: 1.0 5.5 A key defining an attribute with the name "weight" is required if weights are to be used; if one is not found, all weights will be assumed to be 1. The declaration of the default value for this attribute is optional; if no default weight is declared, it will be assumed to be 1. There should be no nodes under the "graphml" node that are neither "key" nodes nor "graph" nodes. The "key" node defining weight must appear before the "graph" node, and additional "key" nodes will be ignored. If there are multiple "graph" nodes, only the first will be considered. The graph must consist of only "node" and "edge" nodes. Hyperedges are not supported. Nested graphs are not supported. If the attribute "edgedefault" is omitted, the graph is assumed to be undirected. Using attributes not shown in the example above is fine; they will be ignored. Using node types not shown in the example above will generate an error. ALGORITHM ========= The Floyd-Warshall algorithm finds the shortest path between every pair of nodes in a graph. We maintain an N-by-N matrix (where N is the number of nodes). In this presentation, when the matrix is displayed, you choose the "source" node across the top and the "destination" node across the left, and the number in that position represents the total distance between those two nodes along the shortest path. (For an unweighted graph, this is just the number of "hops" needed to get from one node to the other; if the graph is weighted, it is the sum of the values of the weights on the edges that you would have to traverse.) In this presentation, this matrix is referred to as the "Path Values" matrix. We maintain another N-by-N matrix called the "Next Nodes" matrix in this presentation. You choose the source and destination nodes as above, and this matrix tells you what your next hop should be to get to your intended destination. In this algorithm, we take the cost of traveling between two nodes (without going through any other nodes) to be 0 if the nodes are actually the same node, infinity if the nodes are not directly connected (represented by a "-" in this presentation), and the weight of the edge connecting them if they are connected. The "Path Values" matrix is initialized with this cost for all pairs of nodes. The "Next Nodes" matrix is also initialized accordingly. Next, we search for shorter or unknown paths by considering paths going through each node and the information that we have already discovered. We choose a node to consider paths through, and then ask this question for all other pairs of nodes: 'k' is the node through which paths are being considered. For all other pairs of nodes 'i' and 'j', is the shortest path from 'i' to 'k' plus the path from 'k' to 'j' shorter than shortest path from 'i' to 'j' that we currently know about? If so, update both matrices with the new information. That's all there is to it. Once we consider every node 'k', we know all of the shortest paths. USING THE PROGRAM ===== === ======= When the Flash program is started, you are prompted for the URL of the GraphML file to be used. The GraphML file will be loaded when you click on "Submit" (subject to security restrictions on where you can load files from imposed by Flash or by the web browser), and if there are any errors parsing or building the graph, an error message will be displayed and the prompt for a URL will be given again. Upon the successful loading of a graph, you will be given the choice of "Step-by-Step" or "Continuous" modes. In "Step-by-Step", you can proceed through the algorithm at your own pace, and view the two matrices whenever you want. In "Continuous" mode, the program will step through the algorithm, showing the matrices only when a notable change occurs. The voice-over is also enabled by default in "Continuous" mode. Here is what the buttons on the screen during the presentation of the algorithm do: * Show Weights: This button toggles the display of weights and directions on the graph on and off. * Auto Advance: This button toggles between the "at your own pace" mode of the "Step-by-Step" presentation and the automatic mode of the "Continuous" presentation. * Voice-Over: This button toggles the voice-over on and off. * Sound Effects: This button toggles the sound effects from button clicks or advances on and off. The following are available only when "Auto Advance" is off: * Continue: Move on to the next step in the algorithm. At the end of the algorithm, this button changes to "Done," and clicking on it one more time removes any red elements from the display. * Show Next Nodes: Shows the "next nodes" matrix. * Show Path Values: Shows the "shortest path values" matrix. The following is available only when "Auto Advance" is on: * Skip Intro: Skips the opening discussion on the algorithm in general. All toggle buttons are "on" when they are yellow and "off" when they are green.