Quick Directions

Manual Graph Editing:


• Add Node: Mouse click while holding CTRL key down in an empty space.
• Add Edge: Mouse click on a node, drag the mouse, and release on another node.
• Move Node: Hold down the SHIFT key when mouse click on a node, and drag.
• Delete Node: Click on a node. The node is painted in red. To delete the node, hit the DELETE key.
• Delete Edge: Do as if adding the edge. The edge is painted in red. To delete the edge, hit the DELETE key.
• Zoom In: Drag the mouse to the desired region to zoom in on.
• Zoom Out: Press the ESCAPE key.
• Tour vs. Overall: To toggle between a manipulated graph (in blue) and the original graph, simply press the SPACEBAR.

Menus:


• File
  • Clear Graph: Resets the graph by clearing all the nodes and edges.
  • Exit: Exits the applet window.
  
  
• Generation: Various graph node/edge generation algorithms. Length of an edge is always the Euclidean distance between its extremities in the 10000x10000 grid. Graph construction only applies on the nodes that are displayed in the applet window.
  • Kn: Generates a complete graph.
  • Random Gn,p: Adds an edge between every pair of nodes with a given probability.
  • Geometric: Considers every pair of nodes and adds an edge between them if their distance is less than some threshold.
  • Triangulation: Creates a Delaunay traingulation of the nodes. Note: This construction is rather slow!!
  • Create Nodes: Creates a given number of nodes to the grid. The nodes have a random location in the 10,000x10.000 grid. The graph is reset.
  
  
• Graph Heuristics: Various heuristic algorithms that act on a defined graph. At present, the applet features several Traveling Salesperson Problem (TSP) heuristics. The Traveling Salesperson Problem is a well known difficult problem in combinatorial optimization. The objective is to find a tour of minimum length that visits every city of a given set. At any time the user may stop the algorithm by a mouse click in the applet window.
  • Insertion: Starts with the convex hull of the cities. The remaining cities are inserted one at a time. At each iteration, the added city is the "cheapest one"; i.e. the one whose addition yields the smallest increase in the tour length. The current implementation of this algorithm runs in O(n^2 log n).
  • Barycenter: Also starts with the convex hull of the cities. The barycenter of all cities is computed. Remaining cities are sorted by decreasing distance from the barycenter and added one by one into the tour. This algotrithm runs in O(n log n).
  • Simulated Annealing: Starts with a random tour. Each phase of the algorithm attempts a series of random 2-exchanges. An exchange is made if it decreases the size of the tour. Otherwise, the exchange is done with a probability that depends on a base value and the potential increase in the tour length. Between the two phases, the base probability is decreased. It follows that accepting an increase in the tour length becomes less and less more likely to occur.
  • Next neighbor: Starts from random city and adds one city at a time in the tour. The next city is a neighbor of the last added city in the tour. If last added city has more than one neighbor, the selected one has minimum degree in the subgraph induced on the cities not in the tour yet. In case of failure, next neighbor picks a neighbor of the last added city. This neighbor is not necessarily already in the tour, otherwise it would not have failed. Let 1,2,...k be the current path and let a be a neighbor of k. It rotates the path and replaces it with 1,2,...,a,k,(k-1),...(a+2),(a+1). (a+1) is now the current last city in the path and it resumes from (a+1). This heuristic is called a random walk because, in case of failure, it randomly select a neighbor in the path.
  • Nearest neighbor: Starts from a random city and adds one city at a time in the tour. The next city is the closest neighbor of the last added city in the tour. In case of failure, the algorithm attempts to recover the same way as the next neighbor algorithm.
  • Minimum Spanning Tree: Finds the minimum spanning tree. This procedure uses the well known algorithm to find the optimum solution.