edgeweightedgraph.h

Go to the documentation of this file.

/* Copyright (C) 2000-2013 CEA
 *
 * This software and supporting documentation were developed by
 *     bioPICSEL
 *     CEA/DSV/I²BM/MIRCen/LMN, Batiment 61,
 *     18, route du Panorama
 *     92265 Fontenay-aux-Roses
 *     France
 */

#ifndef BIOPROCESSING_GRAPH_EWGRAPH
#define BIOPROCESSING_GRAPH_EWGRAPH

//--- bioprocessing ----------------------------------------------------------
#include <bioprocessing/graph/basegraph.h>                   // bio::BaseGraph
//--- cartobase --------------------------------------------------------------
#include <cartobase/smart/rcptr.h>                            // carto::rc_ptr
//--- std --------------------------------------------------------------------
#include <limits>                                       // std::numeric_limits
//----------------------------------------------------------------------------

namespace bio {

  template <typename E, typename W> class EWBaseGraph;
  template <typename E, typename W> class EWBaseGraphRef;

//============================================================================
// EW GRAPH
//============================================================================
  template <typename E, typename W>
  class EWBaseGraph: public BaseGraph<E>
  {
    //--- typedef ------------------------------------------------------------
  protected:
    typedef EWBaseGraph<E,W>               This;    
    typedef BaseGraph<E>                   Base;    
  public:
    typedef W                              Weight;  
    typedef typename Base::Edge            Edge;    
    typedef typename Base::Vertex          Vertex;  
    typedef EWBaseGraphRef<E,W>            Graph;   
    typedef EWBaseGraphRef<E,W>            Ref;     

    //--- constructor --------------------------------------------------------
  public:
    virtual ~EWBaseGraph() {}

    //--- virtual methods ----------------------------------------------------
  public:
    virtual void insert( Edge e, Weight w = (Weight)0 )   { throw; } //< not defined
    virtual Weight weight( const Edge & e )       { throw; } //< not defined
    virtual Weight weight( const Edge & e ) const { throw; } //< not defined

    //--- virtual properties -------------------------------------------------
    // Methods specific to Edge weighted graph that may be defined in the
    // implementation class. Utility methods are defined below and can be
    // used to rapidely define these methods.
  public:
    virtual bool isMinimum( const Graph & g ) const { throw; } //< not defined
    virtual bool isMinimumSpanningForestRelativeTo( const Graph & h, const Graph & g ) const { throw; } //< not defined
    virtual bool isMinimumSpanningTree( const Graph & g ) const { throw; } //< not defined
    template <typename Path>
    bool isDescending( const Path & p ) const { throw; } //< not defined
    template <typename Path>
    bool isPathofSteepestdescent( const Path & p ) const { throw; } //< not defined
    template <typename EdgeSet>
    bool isWatershedCut( const EdgeSet & s ) const { throw; } //< not defined
    template <typename EdgeSet>
    bool isBasinCut( const EdgeSet & es ) const { throw; } //< not defined

    //--- virtual computation ------------------------------------------------
    // Methods specific to Edge weighted graph that may be defined in the
    // implementation class. Utility methods are defined below and can be
    // used to rapidely define these methods.
  public:
    virtual Graph getMinOfF() const                 { throw; } //< not defined
    virtual Weight weight( const Graph & g ) const  { throw; } //< not defined
    virtual Weight Fm( const Vertex & v ) const     { throw; } //< not defined

    //--- utility templated methods ------------------------------------------
  protected:
    template <typename G>
    static Weight Fm( const G & thisg, const Vertex & v );

    //--- friend -------------------------------------------------------------
    friend class EWBaseGraphRef<E,W>;
  };

  template <typename E, typename W>
  template <typename G>
  W EWBaseGraph<E,W>::Fm( const G & thisg, const Vertex & v )
  {
    typename G::edge_const_iterator e;
    W min = std::numeric_limits<W>::max();
    W cur;
    for( e = thisg.beginEdge(v); e != thisg.endEdge(v); ++e )
    {
      cur = thisg.weight( *e );
      if( min > cur )
        min = cur;
    }
    return min;
  }

//============================================================================
// EW GRAPH REF
//============================================================================
  template <typename E, typename W>
  class EWBaseGraphRef: public BaseGraphRef<E>
  {
    //--- typedef ------------------------------------------------------------
  protected:
    typedef EWBaseGraphRef<E,W>             This;
    typedef BaseGraphRef<E>                 Base;
    typedef EWBaseGraph<E,W>                Pointed;
  public:
    typedef typename Pointed::Weight        Weight;
    typedef typename Pointed::Edge          Edge;
    typedef typename Pointed::Vertex        Vertex;
    typedef typename Pointed::Graph         Graph;

    //--- constructors -------------------------------------------------------
  public:
    EWBaseGraphRef(): Base( new Pointed() ) {}
    EWBaseGraphRef( Pointed * g ): Base( g ) {}
    EWBaseGraphRef( const Base & other ): Base(other) {}
    virtual ~EWBaseGraphRef() {}

    //--- none factory -------------------------------------------------------
  public:
    static Graph none() { return This( (Pointed*)0 ); }

    //--- virtual methods ----------------------------------------------------
  public:
    virtual void insert( Edge e, Weight w = (Weight)0 ) { return ((Pointed*)(this->get()))->insert(e,w); }
    virtual Weight weight( const Edge & e ) { return ((Pointed*)(this->get()))->weight(e); }
    virtual Weight weight( const Edge & e ) const { return ((Pointed*)(this->get()))->weight(e); }

    //--- virtual properties -------------------------------------------------
  public:
    // virtual bool isMinimum( const Graph & g ) const { return ((Pointed*)(this->get()))->isMinimum(g); }
    // virtual bool isMinimumSpanningForestRelativeTo( const Graph & h, const Graph & g ) const { return ((Pointed*)(this->get()))->isMinimumSpanningForestRelativeTo(h,g); }
    // virtual bool isMinimumSpanningTree( const Graph & g ) const { return ((Pointed*)(this->get()))->isMinimumSpanningTree(g); }
    // template <typename Path>
    // bool isDescending( const Path & p ) const { return ((Pointed*)(this->get()))->isDescending(p); }
    // template <typename Path>
    // bool isPathofSteepestdescent( const Path & p ) const { return ((Pointed*)(this->get()))->isPathofSteepestdescent(p); }
    // template <typename EdgeSet>
    // bool isWatershedCut( const EdgeSet & s ) const { return ((Pointed*)(this->get()))->isWatershedCut(s); }
    // template <typename EdgeSet>
    // bool isBasinCut( const EdgeSet & es ) const { return ((Pointed*)(this->get()))->isBasinCut(es); }

    //--- virtual computation ------------------------------------------------
  public:
    // virtual Graph getMinOfF() const { return ((Pointed*)(this->get()))->getMinOfF(); }
    // virtual Weight weight( const Graph & g ) const { return ((Pointed*)(this->get()))->weight(g); }
    virtual Weight Fm( const Vertex & v ) const { return ((Pointed*)(this->get()))->Fm(v); }

    //--- friends ------------------------------------------------------------
    friend class EWBaseGraph<E,W>;
  };

} // namesapce bio

#endif // BIOPROCESSING_GRAPH_EWGRAPH