TWiki > Doc > CodeExamples > GraphParametricTypeExample > GraphTestExample	TWiki webs: Dev | Doc | Main | TWiki | Sandbox
	Doc . { Changes | Index | Search | Go }

// compilation unit Tests.nice
package graph;

void main(String[] args){
   println("");
   println("Breadth First Search Test");
   println("=========================");   
   bfsTest();
   println("");

   println("Dijkstra Shortest Paths Test");
   println("============================");     
   dijkstraTest();
   println("");   

   println("Prim Minimum Spanning Tree Test");
   println("===============================");     
   primTest();
   println("");
   
   println("Bellman-Ford Shortest Paths Test");
   println("================================");     
   bellmanFordTest();
   println("");   
   
   println("Johnson All-Pairs Shortest Paths Test");
   println("=====================================");     
   johnsonTest();
   println("");  
}


AdjacencyList <int, AdjacencyListEdge<int>> simpleGraph(){
   let g = new AdjacencyList();
   g.addVertex(3);
   g.addVertex(4);
   g.addVertex(5);
   g.addVertex(6);
   
   g.addEdge(3, 6);
   g.addEdge(3, 5);
   g.addEdge(4, 5);
   g.addEdge(6, 4);
   g.addEdge(4, 3);
   return g;
}

HashPropertyMap<int, double> simpleDistanceMap(){
   let d = new HashPropertyMap();
   d.set(3, 0.0);          
   d.set(4, Double.POSITIVE_INFINITY);
   d.set(5, Double.POSITIVE_INFINITY);
   d.set(6, Double.POSITIVE_INFINITY);
   return d;
}

HashPropertyMap<AdjacencyListEdge<int>, double> negativeWeights(){
   let w = new HashPropertyMap();
   w.set(new AdjacencyListEdge(3, 6), 5.0);
   w.set(new AdjacencyListEdge(3, 5), 8.0);
   w.set(new AdjacencyListEdge(4, 5), -1.0);
   w.set(new AdjacencyListEdge(6, 4), -2.0); 
   w.set(new AdjacencyListEdge(4, 3), 3.0); 
   return w;
}


void bfsTest(){ 
   let g = simpleGraph();   
   let color = new HashPropertyMap();
   let p = new PrintingVisitor();
   
   breadthFirstSearch(g, 3, p, color);
}


void dijkstraTest(){ 
   let g = simpleGraph(); 
   let distanceMap = simpleDistanceMap();   

   let predMap = new HashPropertyMap();
   let weightMap = new HashPropertyMap();

   weightMap.set(new AdjacencyListEdge(3, 6), 5.0);
   weightMap.set(new AdjacencyListEdge(3, 5), 8.0);
   weightMap.set(new AdjacencyListEdge(4, 5), 1.0);
   weightMap.set(new AdjacencyListEdge(6, 4), 2.0); 
   weightMap.set(new AdjacencyListEdge(4, 3), 3.0);
     
   dijkstraShortestPaths(
      g, 
      3, 
      predMap,
      distanceMap,
      weightMap,
      (double a, double b) => { return a < b; },
      (double a, double b) => { return a + b; },
      Double.POSITIVE_INFINITY,
      0.0
      );
  
   for (i : 3..6) 
      println(
         "Dist(" i ")=" distanceMap.get(i) 
         ", Pred(" i ")=" predMap.get(i) 
         );                            
}


void primTest(){ 
   let g = simpleGraph(); 
   let distanceMap = simpleDistanceMap();  

   let predMap = new HashPropertyMap();
   let weightMap = new HashPropertyMap(); 

   weightMap.set(new AdjacencyListEdge(3, 6), 1.0);
   weightMap.set(new AdjacencyListEdge(3, 5), 8.0);
   weightMap.set(new AdjacencyListEdge(4, 5), 1.0);
   weightMap.set(new AdjacencyListEdge(6, 4), 2.0); 
   weightMap.set(new AdjacencyListEdge(4, 3), 3.0);

   g.addEdge(6, 3);
   g.addEdge(5, 3);
   g.addEdge(5, 4);      
   g.addEdge(4, 6);
   g.addEdge(3, 4);       
   
   weightMap.set(new AdjacencyListEdge(6, 3), 1.0);
   weightMap.set(new AdjacencyListEdge(5, 3), 8.0);
   weightMap.set(new AdjacencyListEdge(5, 4), 1.0);
   weightMap.set(new AdjacencyListEdge(4, 6), 2.0);
   weightMap.set(new AdjacencyListEdge(3, 4), 3.0);

   primMinimumSpanningTree(
      g, 
      3, 
      predMap,
      distanceMap,
      weightMap,
      (double a, double b) => { return a < b; },
      Double.POSITIVE_INFINITY,
      0.0
      );

   for (i : 3..6) 
      println("Pred(" i ") = " predMap.get(i) );
}


void bellmanFordTest(){ 
   let g = simpleGraph(); 
   let distanceMap = simpleDistanceMap();  
   let weightMap = negativeWeights();    
   
   let predMap = new HashPropertyMap();  
    
   bellmanFordShortestPaths(
      g, 
      4,
      weightMap,
      predMap,
      distanceMap,
      (double a, double b) => { return a + b; },
      (double a, double b) => { return a < b; }
      );

   for (i : 3..6) {
      print("Dist(" i ")="   distanceMap.get(i));                     
      print(", Pred(" i ")=");
      
      // Maybe a Vertex has no predecessors? 3
      try { print( predMap.get(i) ); 
      } catch (NoSuchElementException ex){}    
        
      println("");
   }
}


void johnsonTest(){ 
   let g = simpleGraph(); 
   let distanceMap = simpleDistanceMap();     
   let weightMap = negativeWeights();
   
   let newWeightMap = new HashPropertyMap();
   let distanceMatrix = new HashPropertyMap();      
   
   distanceMatrix[3] = new HashPropertyMap();
   distanceMatrix[4] = new HashPropertyMap();
   distanceMatrix[5] = new HashPropertyMap();
   distanceMatrix[6] = new HashPropertyMap();         
       
   johnsonAllPairsShortestPaths(
      g,    
      weightMap,
      newWeightMap,
      distanceMap,
      distanceMatrix,
      0.0,
      Double.POSITIVE_INFINITY,
      (double a, double b) => { return a + b; },
      (double a) => { return -a; },      
      (double a, double b) => { return a < b; }
   );
  
   for (i : 3..6) {
      print("" i ": ");
      for (j : 3..6)  
         print("" distanceMatrix.get(i).get(j) " ");     
      println("");
    }              
}

-- IsaacGouy - 22 Apr 2004