hyper_dijkstra.h

// g2o - General Graph Optimization
// Copyright (C) 2011 R. Kuemmerle, G. Grisetti, W. Burgard
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright notice,
//   this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright
//   notice, this list of conditions and the following disclaimer in the
//   documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
// TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
#ifndef G2O_AIS_GENERAL_DIJKSTRA_HH
#define G2O_AIS_GENERAL_DIJKSTRA_HH
 
#include <limits>
#include "Base/Headers/Dictionary.h"
#include "hyper_graph.h"
 
namespace NDEVR
{

  struct  HyperDijkstra{
    struct  CostFunction {
      virtual g_type operator() (HyperGraph::HGEdge* e, HyperGraph::HGVertex* from, HyperGraph::HGVertex* to)=0;
      virtual ~CostFunction() { }
    };

    struct  TreeAction {
      virtual g_type perform(HyperGraph::HGVertex* v, HyperGraph::HGVertex* vParent, HyperGraph::HGEdge* e);
      virtual g_type perform(HyperGraph::HGVertex* v, HyperGraph::HGVertex* vParent, HyperGraph::HGEdge* e, g_type distance);
    };
 

    struct  AdjacencyMapEntry{
      friend struct HyperDijkstra;
      AdjacencyMapEntry(HyperGraph::HGVertex* _child=0,
          HyperGraph::HGVertex* _parent=0,
          HyperGraph::HGEdge* _edge=0,
          g_type _distance=std::numeric_limits<g_type>::max());
      HyperGraph::HGVertex* child() const {return _child;}
      HyperGraph::HGVertex* parent() const {return _parent;}
      HyperGraph::HGEdge* edge() const {return _edge;}
      g_type distance() const {return _distance;}
      Set<HyperGraph::HGVertex*>& children() {return _children;}
      const Set<HyperGraph::HGVertex*>& children() const {return _children;}
      protected:
      HyperGraph::HGVertex* _child;             
      HyperGraph::HGVertex* _parent;                
      HyperGraph::HGEdge* _edge;                    
      g_type _distance;                             
      Set<HyperGraph::HGVertex*> _children;         
    };
 
    typedef Dictionary<HyperGraph::HGVertex*, AdjacencyMapEntry> AdjacencyMap;  
    HyperDijkstra(HyperGraph* g);
    Set<HyperGraph::HGVertex*>& visited() {return _visited; }
    AdjacencyMap& adjacencyMap() {return _adjacencyMap; }
    HyperGraph* graph() {return _graph;}

    void shortestPaths(HyperGraph::HGVertex* v,
           HyperDijkstra::CostFunction* cost, 
           g_type maxDistance=std::numeric_limits< g_type >::max(), 
           g_type comparisonConditioner=1e-3, 
           bool directed=false,
           g_type maxEdgeCost=std::numeric_limits< g_type >::max());

    void shortestPaths(Set<HyperGraph::HGVertex*>& vset,
           HyperDijkstra::CostFunction* cost, 
           g_type maxDistance=std::numeric_limits< g_type >::max(), 
           g_type comparisonConditioner=1e-3, 
           bool directed=false,
           g_type maxEdgeCost=std::numeric_limits< g_type >::max());
 

    static void computeTree(AdjacencyMap& amap);
    static void visitAdjacencyMap(AdjacencyMap& amap, TreeAction* action, bool useDistance=false);
    static void connectedSubset(Set<HyperGraph::HGVertex*>& connected, Set<HyperGraph::HGVertex*>& visited,
        Set<HyperGraph::HGVertex*>& startingSet,
           HyperGraph* g, HyperGraph::HGVertex* v,
           HyperDijkstra::CostFunction* cost, g_type distance, g_type comparisonConditioner,
           g_type maxEdgeCost=std::numeric_limits< g_type >::max() );
 
  protected:
    void reset();
 
    AdjacencyMap _adjacencyMap;                 
    Set<HyperGraph::HGVertex*> _visited;        
    HyperGraph* _graph;                         
  };

  struct UniformCostFunction : public HyperDijkstra::CostFunction {
    virtual g_type operator ()(HyperGraph::HGEdge* edge, HyperGraph::HGVertex* from, HyperGraph::HGVertex* to);
  };
 
}
#endif