Nice TWiki > Doc > CodeExamples > GraphParametricTypeExample (r1.1) TWiki webs:
Dev | Doc | Main | TWiki | Sandbox
Doc . { Changes | Index | Search | Go }
"A Comparative Study of Language Support for Generic Programming" used a sample of the Boost Graph Library to compare the generic programming techniques available in C++, ML, Haskell, Eiffel, Java Generics, Generic C# (Source code). These Nice implementations use parameterised interfaces to represent most concepts (a few are represented by functions).

The generic algorithms BreadthFirstSearchExample, DijkstraShortestPathsExample, PrimMinimumSpanningTreeExample, BellmanFordShortestPathsExample, and JohnsonAllPairsShortestPathsExample, make use of GraphConceptsExamples and GraphClassesExamples.

Bellman Ford Shortest Paths

package graph;

<Vertex, Edge, Distance, T | Edge <: GraphEdge<Vertex> > 
boolean bellmanFordShortestPaths(
   EdgeListGraph<Vertex,Edge> graph,
   int size,
   ReadablePropertyMap<Edge,Distance> weightMap,
   ReadWritePropertyMap<Vertex,Vertex> predecessor,
   ReadWritePropertyMap<Vertex,Distance> distance,
   (Distance, Distance)->Distance combine,
   (Distance, Distance)->boolean compare
   ){
   
   for (int i = 0; i < size; ++i) {
      boolean anyRelaxed = false; // Optimization from BGL
      for ( Edge edge : graph.edges )
         if( relax(edge, weightMap, distance, predecessor, combine, compare) )
            anyRelaxed = true; 
                       
      if (!anyRelaxed) break;
   }

   for ( Edge edge : graph.edges() )
      if (compare( 
         combine(weightMap[edge], distance[edge.source]), 
         distance[edge.target])
         )
            return false;

   return true;
}


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("");
   }
}

Test Results

(For tests in GraphTestExample.)
Breadth First Search Test
=========================
initialize 40003
initialize 40004
initialize 40005
initialize 40006
discover 40003
discover 40003
examine edge(40003 -> 40006)
tree edge(40003 -> 40006)
examine edge(40003 -> 40005)
tree edge(40003 -> 40005)
finish 40003
discover 40006
examine edge(40006 -> 40004)
tree edge(40006 -> 40004)
finish 40006
discover 40005
finish 40005
discover 40004
examine edge(40004 -> 40005)
nontree edge(40004 -> 40005)
black target edge(40004 -> 40005)
examine edge(40004 -> 40003)
nontree edge(40004 -> 40003)
black target edge(40004 -> 40003)
finish 40004

Dijkstra Shortest Paths Test
============================
Dist(40003)=0.0, Pred(40003)=40003
Dist(40004)=7.0, Pred(40004)=40006
Dist(40005)=8.0, Pred(40005)=40003
Dist(40006)=5.0, Pred(40006)=40003

Prim Minimum Spanning Tree Test
===============================
Pred(40003) = 40003
Pred(40004) = 40006
Pred(40005) = 40004
Pred(40006) = 40003

Bellman-Ford Shortest Paths Test
================================
Dist(40003)=0.0, Pred(40003)=
Dist(40004)=3.0, Pred(40004)=40006
Dist(40005)=2.0, Pred(40005)=40004
Dist(40006)=5.0, Pred(40006)=40003

Johnson All-Pairs Shortest Paths Test
=====================================
40003: 0.0 3.0 2.0 5.0
40004: 3.0 0.0 -1.0 8.0
40005: Infinity Infinity 0.0 Infinity
40006: 1.0 -2.0 -3.0 0.0

-- IsaacGouy - 07 Jan 2004

Topic GraphParametricTypeExample . { Edit | Attach | Ref-By | Printable | Diffs | r1.8 | > | r1.7 | > | r1.6 | More }
Revision r1.1 - 07 Jan 2004 - 21:54 GMT - IsaacGouy
Parents: WebHome > CodeExamples
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.