import java.awt.*; import java.io.*; import java.util.*; import java.net.*; import ciips.animation.*; import ciips.animation.graph.*; public class GraphDij { private GraphPanel graph_dp; private DrawingPanel dp; static final double infinity = 1.0e300; static final double zero = 0.00; static String start = "Source Node = Node "; static String adj = "Adjacent Node = Node "; static String distance = ", Cost = "; static String current = "Node "; static String chosen = " Chosen; Shortest Distance "; static String empty = "Priority queue is empty "; String sentence; AlgThread alg; Graph graph; Vector set; PriorityQueue PQ; CostMatrix CM; static final boolean DEBUG = true; public GraphDij( AlgThread alg, Graph graph, GraphPanel gp ) { this.alg = alg; this.graph = graph; /*-*/ graph_dp = gp; dp = gp.dp; Shortest_Paths( graph.Source() ); } /*------------------------*/ public void Shortest_Paths( Node s ) { Node source, trial_node; int i; /*-*/ Edge e; /*-*/ alg.frame.setText(0, "Running Dijkstra's Algorithm... Souce Node = 'A'"); source = s; /*-*/ alg.frame.Highlight(4); set = new Vector(); PQ = new PriorityQueue( graph.node_cnt ); /*-*/ graph_dp.setNodeComment(s, "Initial Graph"); Initialise( source ); /*-*/ alg.frame.Highlight(7); /*-*/ alg.frame.setText(1, "Initialization"); /*-*/ graph_dp.setNodeComment(s, /*-*/ "All nodes have infinite cost except the source"); /*-*/ AlgAnimFrame.pauseStep(); while ( !PQ.Empty() ) { /*-*/alg.frame.Highlight(9); trial_node = (Node)(PQ.Extract_First_Element_Dij()); /*-*/ AlgAnimFrame.highlightText(10); /*-*/ graph_dp.setNodeComment(trial_node, /*-*/ "Choose the node with lowest cost..."); /*-*/ graph_dp.flashNode( trial_node ); /*-*/ graph_dp.Highlight_Node_Final( trial_node ); /*-*/ AlgAnimFrame.pauseStep(); /*-*/ e = Unique_Edge(trial_node); /*-*/ graph_dp.Highlight_Edge_Final(e); /*-*/ graph_dp.Show_Cost_Node(trial_node); set.addElement( (Object)trial_node ); /*-*/ alg.frame.Highlight(11); /*-*/ sentence = new String(current+trial_node.Get_ID()+chosen); /*-*/ alg.frame.setText(1, sentence); /*-*/ alg.frame.Highlight(12); /*-*/ graph_dp.setNodeComment(trial_node, "Relax all adjacent nodes..."); Relax( trial_node ); /*-*/ dp.shuffleDown(); AlgAnimFrame.pauseStep(); /*-*/ graph_dp.hideNodeComment(); } /*-*/ sentence = new String(empty); /*-*/ AlgAnimFrame.showText(2, sentence); /*-*/ alg.frame.Highlight(14); } //---------------- private void Initialise( Node s ) { int i, pivot = 0; Node neg_one; CM = new CostMatrix(graph); CM.Fill_Matrix(); neg_one = new Node(-1, 0, 0); for (i = 0; i < graph.node_cnt; i++) { graph.nodes[i].Set_Rep( neg_one ); graph.nodes[i].Set_Cost( infinity ); graph.nodes[i].Show_Infinite(); PQ.Add( (Object)graph.nodes[i]); } /*-*/graph_dp.Highlight_Node_Focus(s); s.Set_Cost( zero ); /*-*/graph_dp.Show_Cost_Node(s); } private void Relax( Node n ) { int pivot = 0; PQ.Remove_Element( n ); Update(); PQ.Sort( pivot, PQ.Num_Items() ); } private void Update( ) { int i, j, id, max, pos; Node n, p; double cost, temp_cost; Vector buffer = new Vector(); Vector buffer_1 = new Vector(); //for (i = 0; i < set.size(); i++) { if (set.size() > 0) { n = (Node)(set.lastElement()); id = n.Get_ID(); //System.out.println("PQ: node in set is "+id); for (j = 0; j < CM.Length(); j++) { //id of end node is j+1 if ( PQ.Exist_In_PQ( j+1 ) ) { if ( (cost = CM.Cost(id-1, j)) > 0.00) { temp_cost = cost + n.Cost(); //System.out.println("PQ: adjacent node is "+(j+1)); p = PQ.Adjacent_Node( j+1 ); buffer.addElement((Object)p); if (temp_cost <= p.Cost() ) { if (p.Rep() != null) { // remove the focus from the edge /*-*/graph_dp.Highlight_Edge_Ori(Unique_Edge(p)); } p.Set_Rep(n); p.Set_Cost( temp_cost ); PQ.Input_New_Cost( temp_cost, p ); } } } } } Unique(buffer); } private void Unique(Vector buffer) { int i, j; Node n, p; Edge e; boolean flag = false; i = 0; do { flag = false; for (j = i; j < buffer.size(); j++) { n = (Node)(buffer.elementAt(i)); p = (Node)(buffer.elementAt(j)); if (i != j) { if (n.Get_ID() == p.Get_ID()) { if (n.Cost() < p.Cost() ) { buffer.removeElementAt(j); flag = false; } else if (n.Cost() >= p.Cost()) { buffer.removeElementAt(i); flag = true; break; } } } } if (!flag) { i++; } if (i >= buffer.size()) { break; } //System.out.println("i = "+i+", size = "+buffer.size()); } while(true); n = null; for (i = 0; i < buffer.size(); i++) { n = (Node)(buffer.elementAt(i)); /*-*/graph_dp.flashNode(n); /*-*/graph_dp.Highlight_Node_Focus(n); /*-*/graph_dp.Show_Cost_Node(n); } /*-*/graph_dp.repaint(); graph_dp.delay(); /*-*/graph_dp.delay(); /*-*/graph_dp.delay(); /*-*/alg.frame.waitStep(); /*-*/graph_dp.setNodeComment(n, /*-*/ "Update predecessors for relaxed nodes..."); for (i = 0; i < buffer.size(); i++) { n = (Node)(buffer.elementAt(i)); sentence = new String(adj+n.Get_ID()+distance+n.Cost()); //System.out.println(sentence+" "); e = Unique_Edge(n); /*-*/alg.frame.setText(2, sentence); /*-*/graph_dp.flashEdge(e); /*-*/graph_dp.Highlight_Edge_Focus(e); } } private Edge Unique_Edge(Node n) { Node p; Edge e; int i; p = n.Rep(); e = graph.edges[0]; for (i = 0; i < graph.edge_cnt; i++) { e = graph.edges[i]; if (e.From_Node() == p && e.To_Node() == n) { break; } } if (i==graph.edge_cnt) return null; else return e; } private void Print_Ans( ) { int i; Node n; for(i = 0; i < set.size(); i++) { n = (Node)(set.elementAt(i)); } } }