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

The generic algorithms Breadth First Search, Dijkstra Shortest Paths, Prim's Minimum Spanning Tree, Bellman Ford Shortest Paths, and Johnson All Pairs Shortest Paths, make use of Graph Concepts and Graph Classes and Graph Tests.

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

Test Results

Breadth First Search Test
=========================
initialize 3
initialize 4
initialize 5
initialize 6
discover 3
discover 3
examine edge(3 -> 6)
tree edge(3 -> 6)
examine edge(3 -> 5)
tree edge(3 -> 5)
finish 3
discover 6
examine edge(6 -> 4)
tree edge(6 -> 4)
finish 6
discover 5
finish 5
discover 4
examine edge(4 -> 5)
nontree edge(4 -> 5)
black target edge(4 -> 5)
examine edge(4 -> 3)
nontree edge(4 -> 3)
black target edge(4 -> 3)
finish 4

Dijkstra Shortest Paths Test
============================
Dist(3)=0.0, Pred(3)=3
Dist(4)=7.0, Pred(4)=6
Dist(5)=8.0, Pred(5)=3
Dist(6)=5.0, Pred(6)=3

Prim Minimum Spanning Tree Test
===============================
Pred(3) = 3
Pred(4) = 6
Pred(5) = 4
Pred(6) = 3

Bellman-Ford Shortest Paths Test
================================
Dist(3)=0.0, Pred(3)=
Dist(4)=3.0, Pred(4)=6
Dist(5)=2.0, Pred(5)=4
Dist(6)=5.0, Pred(6)=3

Johnson All-Pairs Shortest Paths Test
=====================================
3: 0.0 3.0 2.0 5.0
4: 3.0 0.0 -1.0 8.0
5: Infinity Infinity 0.0 Infinity
6: 1.0 -2.0 -3.0 0.0

-- IsaacGouy - 07 Jan 2004