MeshKit  1.0
DijkstraShortestPath.cpp
Go to the documentation of this file.
00001 #include "meshkit/DijkstraShortestPath.hpp"
00002 #include "meshkit/StopWatch.hpp"
00003 #include <limits>
00005 
00006 int DijkstraShortestPath::atomicOp(LVertex &currnode)
00007 {
00008      Vertex *vi = currnode.vertex;
00009 
00010      if (vi == vdst) return 0;
00011 
00012      if( filter ) {
00013           if( vi != vsrc  ) {
00014                if( !filter->pass( vi ) ) {
00015                     vdst = vi;
00016                     return 0;
00017                }
00018           }
00019      }
00020 
00021      NodeSequence vneighs;
00022      vi->getRelations( vneighs );
00023      int nSize = vneighs.size();
00024 
00025 //   int offset = Math::random_value((int)0, nSize-1);
00026      int offset = 0;
00027 
00028      LVertex lv;
00029      for (int i = 0; i < nSize; i++) {
00030           Vertex *vj = vneighs[(i+offset)%nSize];
00031           assert( !vj->isRemoved() );
00032           miter = vmap.find( vj );
00033           if( miter == vmap.end()) {
00034                lv.distance = std::numeric_limits< double >:: max();
00035                lv.vertex   = vj;
00036                lv.previous = vi;
00037                vmap.insert(make_pair(vj,lv));
00038           } else {
00039                lv = miter->second;
00040           }
00041           assert( lv.vertex == vj );
00042 
00043           double vcost = getCost(currnode, lv);
00044           if (vcost < lv.distance) {
00045                lv.previous = vi;
00046                lv.distance = vcost;
00047                vmap[vj]    = lv;
00048                vertexQ.push(lv);
00049           }
00050      }
00051 
00052      return 1;
00053 }
00054 
00056 
00057 void DijkstraShortestPath::traceback()
00058 {
00059      nodepath.clear();
00060      if( vdst == NULL ) return;
00061 
00062      miter = vmap.find(vdst);
00063      if( miter == vmap.end() ) return;
00064 
00065      LVertex currnode = miter->second;
00066      while(1) {
00067           nodepath.push_back( currnode.vertex );
00068           Vertex *v = currnode.previous;
00069           if (v == NULL) break;
00070           currnode = vmap[v];
00071      }
00072 
00073      assert( nodepath.front() == vdst );
00074      assert( nodepath.back()  == vsrc );
00075 }
00077 
00078 void DijkstraShortestPath::fastmarching()
00079 {
00080      assert( mesh->getAdjTable(0,0) );
00081 
00082      while (!vertexQ.empty()) vertexQ.pop();
00083 
00084      vmap.clear();
00085 
00086      LVertex lv;
00087      lv.vertex   = vsrc;
00088      lv.distance = 0.0;
00089      lv.previous = NULL;
00090      vmap[vsrc]  = lv;
00091      vertexQ.push( lv );
00092 
00093      assert( !vsrc->isRemoved() );
00094 
00095      int progress;
00096      while (!vertexQ.empty()) {
00097           LVertex currVertex = vertexQ.top();
00098           vertexQ.pop();
00099           progress = atomicOp(currVertex);
00100           if (!progress) break;
00101      }
00102 }
00104 
00105 int Jaal::dijkstra_shortest_path_test()
00106 {
00107      double origin[]   = { 0.0, 0.0, 0.0};
00108      double length[]   = { 1.0, 1.0, 1.0};
00109      int    gridim[]   = { 5, 5, 5};
00110 
00111      Jaal::Mesh *mesh = Jaal::create_structured_mesh(origin, length, gridim, 2 );
00112 
00113      struct MyFilter: public MeshFilter {
00114           MyFilter( int i ) {
00115                id = i;
00116           }
00117           size_t id;
00118           bool pass( const Vertex *v) const{
00119                return v->getID() != id;
00120           }
00121      };
00122 
00123      MeshFilter *filter = new MyFilter(18);
00124 
00125      DijkstraShortestPath djk(mesh);
00126 
00127      NodeSequence sq = djk.getPath(mesh->getNodeAt(0), filter);
00128 
00129      for( size_t i = 0; i < sq.size(); i++)
00130           cout << sq[i]->getID() << endl;
00131 
00132      delete filter;
00133 
00134      return 0;
00135 }
00136 
00138 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines