Nice TWiki > Doc > GenericProgrammingIntermediateExample? > GraphTestExample (r1.1) 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(){
   AdjacencyList <int, AdjacencyListEdge<int>> g = new AdjacencyList();
   g.addVertex(40003);
   g.addVertex(40004);
   g.addVertex(40005);
   g.addVertex(40006);
   
   g.addEdge(40003, 40006);
   g.addEdge(40003, 40005);
   g.addEdge(40004, 40005);
   g.addEdge(40006, 40004);
   g.addEdge(40004, 40003);
   return g;
}

HashPropertyMap<int, double> simpleDistanceMap(){
   HashPropertyMap<int, double> d = new HashPropertyMap();
   d.set(40003, 0.0);          
   d.set(40004, Double.POSITIVE_INFINITY);
   d.set(40005, Double.POSITIVE_INFINITY);
   d.set(40006, Double.POSITIVE_INFINITY);
   return d;
}

HashPropertyMap<AdjacencyListEdge<int>, double> negativeWeights(){
      HashPropertyMap<AdjacencyListEdge<int>, double> 
   w = new HashPropertyMap();
   w.set(new AdjacencyListEdge(40003, 40006), 5.0);
   w.set(new AdjacencyListEdge(40003, 40005), 8.0);
   w.set(new AdjacencyListEdge(40004, 40005), -1.0);
   w.set(new AdjacencyListEdge(40006, 40004), -2.0); 
   w.set(new AdjacencyListEdge(40004, 40003), 3.0); 
   return w;
}


void bfsTest(){ 
   AdjacencyList <int, AdjacencyListEdge<int>> g = simpleGraph();   
   HashPropertyMap<int, ColorValue> color = new HashPropertyMap();

      PrintingVisitor 
      < 
      AdjacencyList < int, AdjacencyListEdge<int> >, 
      int, 
      AdjacencyListEdge<int>, 
      int 
      > 
   p = new PrintingVisitor();
   
   breadthFirstSearch(g, 40003, p, color);
}


void dijkstraTest(){ 
   AdjacencyList <int, AdjacencyListEdge<int>> g = simpleGraph(); 
   HashPropertyMap<int, double> distanceMap = simpleDistanceMap();   

   HashPropertyMap<int, int> predMap = new HashPropertyMap();
   HashPropertyMap<AdjacencyListEdge<int>, double> weightMap = new HashPropertyMap();

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


void primTest(){ 
   AdjacencyList <int, AdjacencyListEdge<int>> g = simpleGraph(); 
   HashPropertyMap<int, double> distanceMap = simpleDistanceMap();  

   HashPropertyMap<int, int> predMap = new HashPropertyMap();
   HashPropertyMap<AdjacencyListEdge<int>, double> weightMap = new HashPropertyMap(); 

   weightMap.set(new AdjacencyListEdge(40003, 40006), 1.0);
   weightMap.set(new AdjacencyListEdge(40003, 40005), 8.0);
   weightMap.set(new AdjacencyListEdge(40004, 40005), 1.0);
   weightMap.set(new AdjacencyListEdge(40006, 40004), 2.0); 
   weightMap.set(new AdjacencyListEdge(40004, 40003), 3.0);

   g.addEdge(40006, 40003);
   g.addEdge(40005, 40003);
   g.addEdge(40005, 40004);      
   g.addEdge(40004, 40006);
   g.addEdge(40003, 40004);       
   
   weightMap.set(new AdjacencyListEdge(40006, 40003), 1.0);
   weightMap.set(new AdjacencyListEdge(40005, 40003), 8.0);
   weightMap.set(new AdjacencyListEdge(40005, 40004), 1.0);
   weightMap.set(new AdjacencyListEdge(40004, 40006), 2.0);
   weightMap.set(new AdjacencyListEdge(40003, 40004), 3.0);

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

   for (i : 40003..40006) 
      println("Pred(" i ") = " predMap.get(i) );
}


void bellmanFordTest(){ 
   AdjacencyList <int, AdjacencyListEdge<int>> g = simpleGraph(); 
   HashPropertyMap<int, double> distanceMap = simpleDistanceMap();  
   HashPropertyMap<AdjacencyListEdge<int>, double> weightMap = negativeWeights();    
   
   HashPropertyMap<int, int> 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 : 40003..40006) {
      print("Dist(" i ")="   distanceMap.get(i));                     
      print(", Pred(" i ")=");
      
      // Maybe a Vertex has no predecessors? 40003
      try { print( predMap.get(i) ); 
      } catch (NoSuchElementException ex){}    
        
      println("");
   }
}


void johnsonTest(){ 
   AdjacencyList <int, AdjacencyListEdge<int>> g = simpleGraph(); 
   HashPropertyMap<int, double> distanceMap = simpleDistanceMap();     
   HashPropertyMap<AdjacencyListEdge<int>, double> 
      weightMap = negativeWeights();
   
   HashPropertyMap<AdjacencyListEdge<int>, double> 
      newWeightMap = new HashPropertyMap();
   
   HashPropertyMap<int, HashPropertyMap<int,double> > 
      distanceMatrix = new HashPropertyMap();      
   
   distanceMatrix[40003] = new HashPropertyMap();
   distanceMatrix[40004] = new HashPropertyMap();
   distanceMatrix[40005] = new HashPropertyMap();
   distanceMatrix[40006] = 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 : 40003..40006) {
      print("" i ": ");
      for (j : 40003..40006)  
         print("" distanceMatrix.get(i).get(j) " ");     
      println("");
    }              
}

-- IsaacGouy - 07 Jan 2004

Topic GraphTestExample . { Edit | Attach | Ref-By | Printable | Diffs | r1.7 | > | r1.6 | > | r1.5 | More }
Revision r1.1 - 07 Jan 2004 - 22:29 GMT - IsaacGouy
Parents: GenericProgrammingIntermediateExample?
Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.