Nice TWiki > Doc > CodeExamples > GraphParametricTypeExample > DijkstraShortestPathsExample (r1.2) TWiki webs:
Dev | Doc | Main | TWiki | Sandbox
Doc . { Changes | Index | Search | Go }
// compilation unit Dijkstra.nice
package graph;

<Vertex, Edge, GraphT, Distance, T | 
Edge <: GraphEdge<Vertex>, 
GraphT <: VertexListAndIncidenceGraph<Vertex, Edge> 
>
void dijkstraShortestPaths(
   GraphT g,
   Vertex s,
   ReadWritePropertyMap<Vertex,Vertex> predecessor,
   ReadWritePropertyMap<Vertex,Distance> distance,
   ReadablePropertyMap<Edge,Distance> weight,
   (Distance,Distance)->boolean compare,
   (Distance,Distance)->Distance combine,
   Distance inf,
   Distance zero
   ){
   
   for (Vertex u : g.vertices()) {
      distance[u] = inf;
      predecessor[u] = u;
   }
   distance[s] = zero;
   
   MutableBuffer<Vertex> Q = new MutableQueue( compare: 
      (Vertex a, Vertex b) => 
         { return compare(distance[a], distance[b]); }
      );
      
   DijkstraVisitor<GraphT, Vertex, Edge, Distance> vis = 
      new DijkstraVisitor(
         m_Q: Q, 
         m_weight: weight, 
         m_predecessor: predecessor, 
         m_distance: distance, 
         m_combine: combine, 
         m_compare: compare, 
         m_zero: zero
      );

   ReadWritePropertyMap<Vertex, ColorValue> color = new HashPropertyMap();

   // Initialize color map
   for (Vertex v : g.vertices())
      color[v] = white;

   graphSearch(g, s, vis, color, Q);
}


public class DijkstraVisitor
<Graph, Vertex, Edge, Distance | Edge <: GraphEdge<Vertex> > 
implements Visitor<Graph, Vertex, Edge, Distance>
{
   private ReadablePropertyMap<Edge,Distance> m_weight;
   private (Distance, Distance)->boolean m_compare;
   private (Distance, Distance)->Distance m_combine;
   private Distance m_zero;
   private ReadWritePropertyMap<Vertex,Distance> m_distance;
   private ReadWritePropertyMap<Vertex,Vertex> m_predecessor;
   private MutableBuffer<Vertex> m_Q;

   initializeVertex(u, g) {}

   discoverVertex(u, g) {}

   examineEdge(e, g) {      
      try { 
         let f = m_compare;
         if ( f(m_weight[e], m_zero) )
            throw new NegativeEdge();                
      }
      catch (NoSuchElementException ex) {  }             
   }

   treeEdge(e, g) {
      relax(e, m_weight, m_distance, m_predecessor, m_combine, m_compare);
   }

   nonTreeEdge(e, g) {}

   grayTarget(e, g) {
      let relaxed = relax(e, m_weight, m_distance, m_predecessor, m_combine, m_compare);
      if (relaxed)
         m_Q.update(e.target);
   }

   blackTarget(e, g) {} 

   finishVertex( u, g) {}
}

public class NegativeEdge extends Exception {}

-- IsaacGouy - 07 Jan 2004

Topic DijkstraShortestPathsExample . { Edit | Attach | Ref-By | Printable | Diffs | r1.6 | > | r1.5 | > | r1.4 | More }
Revision r1.2 - 07 Feb 2004 - 16:22 GMT - IsaacGouy
Parents: WebHome > CodeExamples > GraphParametricTypeExample
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.