basegraph.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_BASEGRAPH
#define BIOPROCESSING_GRAPH_BASEGRAPH
 
//--- cartobase --------------------------------------------------------------
#include <cartobase/smart/rcptr.h>                            // carto::rc_ptr
//--- std --------------------------------------------------------------------
#include <set>                                                     // std::set
//----------------------------------------------------------------------------
 
namespace bio {
 
  template <typename E> class BaseGraph;
  template <typename E> class BaseGraphRef;
 
//============================================================================
// BASE GRAPH: DECLARATION
//============================================================================
  template <typename E>
  class BaseGraph: public carto::RCObject
  {
    //--- typedef ------------------------------------------------------------
  protected:
    typedef BaseGraph<E>                  This;   
  public:
    typedef E                             Edge;   
    typedef typename Edge::Vertex         Vertex; 
    typedef BaseGraphRef<E>               Graph;  
    typedef BaseGraphRef<E>               Ref;    
 
    //--- constructor --------------------------------------------------------
  public:
    virtual ~BaseGraph() {}
 
    //--- virtual methods ----------------------------------------------------
    // These methods depend on the chosen implementation and must be defined
    // by the inheriting class.
  public:
    virtual void insert( Vertex v )                 { throw; } //< not defined
    virtual void insert( Edge e )                   { throw; } //< not defined
    virtual bool contains( const Vertex & v ) const { throw; } //< not defined
    virtual bool contains( const Edge & e ) const   { throw; } //< not defined
    virtual bool empty() const                      { throw; } //< not defined
    virtual void clear()                            { throw; } //< not defined
 
    //--- virtual operators --------------------------------------------------
    // These comparison operators must be defined in the implementation class
  public:
    virtual bool operator== ( const This & other ) const { throw; } //< not defined
    virtual bool operator!= ( const This & other ) const { throw; } //< not defined
    virtual bool operator>  ( const This & other ) const { throw; } //< not defined
    virtual bool operator<  ( const This & other ) const { throw; } //< not defined
    virtual bool operator>= ( const This & other ) const { throw; } //< not defined
    virtual bool operator<= ( const This & other ) const { throw; } //< not defined
    virtual bool operator=  ( const This & other )       { throw; } //< not defined
 
    //--- virtual properties -------------------------------------------------
    // Classic graph properties.
    // A number of static utility methods templated on the implemented graph
    // class are defined below. They can be used to easily defined these
    // methods in the implementation class
  public:
    virtual bool isAdjacent( const Vertex & x, const Vertex & y ) const       { throw; } //< not defined
    virtual bool isLinked( const Vertex & x, const Vertex & y ) const         { throw; } //< not defined
    virtual bool isSubGraph( const Graph & g ) const                          { throw; } //< not defined
    virtual bool isConnectedComponent( const Graph & g ) const                { throw; } //< not defined
    virtual bool isAdjacentTo( const Vertex & v, const Graph & g ) const      { throw; } //< not defined
    virtual bool isAdjacentFrom( const Vertex & v, const Graph & g ) const    { throw; } //< not defined
    virtual bool isAdjacent( const Edge & e ) const                           { throw; } //< not defined
    virtual bool isLinked( const Vertex & v ) const                           { throw; } //< not defined
    virtual bool isExtension( const Graph & h, const Graph & g ) const        { throw; } //< not defined
    virtual bool isForestRelativeTo( const Graph & h, const Graph & g ) const { throw; } //< not defined
    virtual bool isSpanningForestRelativeTo( const Graph & h, const Graph & g ) const { throw; } //< not defined
    virtual bool isTree( const Graph & g ) const                              { throw; } //< not defined
    virtual bool isSpanningTree( const Graph & g ) const                      { throw; } //< not defined
    virtual bool isForest( const Graph & g ) const                            { throw; } //< not defined
    virtual bool isSpanningForest( const Graph & g ) const                    { throw; } //< not defined
    template <typename EdgeIterator>
    bool isGraphCut( EdgeIterator begin, EdgeIterator end, const Graph & g ) const { throw; } //< not defined
    template <typename EdgeSet>
    bool isGraphCut( const EdgeSet & es, const Graph & g ) const              { throw; } //< not defined
 
    //--- defined static methods ---------------------------------------------
  public:
    template <typename Set>
    static Set getComplement( const Set & s, const Set & e );
 
    //--- utility templated methods ------------------------------------------
  protected:
    template <typename G>
    static bool isAdjacent( const G & thisg, const Vertex & x, const Vertex & y );
    template <typename G>
    static bool isLinked( const G & thisg, const Vertex & x, const Vertex & y );
    template <typename VertexSet, typename G>
    static bool isLinked( const G & thisg, const Vertex & x, const Vertex & y, VertexSet & s );
    template <typename G>
    static bool isSubGraph( const G & thisg, const typename G::Ref & g );
    template <typename G>
    static bool isConnectedComponent( const G & thisg, const typename G::Ref & g );
    template <typename G>
    static bool isAdjacent( const G & thisg, const Edge & e );
    template <typename G>
    static bool isAdjacentTo( const G & thisg, const Vertex & v, const typename G::Ref & g );
    template <typename G>
    static bool isAdjacentFrom( const G & thisg, const Vertex & v, const typename G::Ref & g );
    template <typename G>
    static typename G::Ref getConnectedComponent( G & thisg, Vertex & v );
    template <typename G>
    static void getConnectedComponent( G & thisg, Vertex & v, typename G::Ref & g );
 
 
    //--- friends ------------------------------------------------------------
    friend class BaseGraphRef<E>;
  };
 
 
//============================================================================
// BASE GRAPH: DEFINITION
//============================================================================
 
  //--- utility templated methods --------------------------------------------
 
  template <typename E>
  template <typename G>
  bool BaseGraph<E>::isAdjacent( const G & thisg,
                                 const Vertex & x,
                                 const Vertex & y )
  {
    typename G::edge_const_iterator e;
    for( e = thisg.beginEdge(x); e != thisg.endEdge(x); ++e )
      if( e->other(x) == y )
        return true;
    return false;
  }
 
  template <typename E>
  template <typename G>
  bool BaseGraph<E>::isLinked( const G & thisg,
                               const Vertex & x,
                               const Vertex & y )
  {
    if( x == y )
      return false;
    std::set<Vertex> viewed;
    viewed.insert( x );
    typename G::edge_const_iterator e;
    for( e = thisg.beginEdge(x); e != thisg.endEdge(x); ++e )
      if( isLinked( thisg, e->other(x), y, viewed ) )
        return true;
    return false;
  }
 
  template <typename E>
  template <typename VertexSet, typename G>
  bool BaseGraph<E>::isLinked( const G & thisg,
                               const Vertex & x,
                               const Vertex & y,
                               VertexSet & s )
  {
    if( x == y )
      return true;
    if( s.insert( x ).second )
    {
      typename G::edge_const_iterator e;
      for( e = thisg.beginEdge(x); e != thisg.endEdge(x); ++e )
        if( isLinked( thisg, e->other(x), y, s ) )
          return true;
    }
    return false;
  }
 
  template <typename E>
  template <typename G>
  bool BaseGraph<E>::isSubGraph( const G & thisg,
                                 const typename G::Ref & g )
  {
    if( g.empty() )
      return false;
 
    typename G::vertex_const_iterator v;
    for( v = g.beginVertex(); v != g.endVertex(); ++v )
      if( !thisg.contains(*v) )
        return false;
 
    typename G::edge_const_iterator e;
    for( e = g.beginEdge(); e != g.endEdge(); ++e )
      if( !thisg.contains(*e) )
        return false;
 
    return true;
  }
 
  template <typename E>
  template <typename G>
  bool BaseGraph<E>::isConnectedComponent( const G & thisg,
                                           const typename G::Ref & g )
  {
    if( g.empty() )
      return false;
 
    Vertex one = *( g.beginVertex() );
    return g == thisg.getConnectedComponent( one );
  }
 
  template <typename E>
  template <typename G>
  bool BaseGraph<E>::isAdjacent( const G & thisg,
                                 const Edge & e )
  {
    return ( thisg.contains( e.x() ) || thisg.contains( e.y() ) ) && !thisg.contains( e );
  }
 
  template <typename E>
  template <typename G>
  bool BaseGraph<E>::isAdjacentTo( const G & thisg,
                                   const Vertex & v,
                                   const typename G::Ref & g )
  {
    typename G::edge_const_iterator e;
    for( e = thisg.beginEdge(v); e != thisg.endEdge(v); ++e )
      if( g.isAdjacent( *e ) )
        return true;
    return false;
  }
 
  template <typename E>
  template <typename G>
  bool BaseGraph<E>::isAdjacentFrom( const G & thisg,
                                     const Vertex & v,
                                     const typename G::Ref & g )
  {
    typename G::edge_const_iterator e;
    for( e = g.beginEdge(v); e != g.endEdge(v); ++e )
      if( thisg.isAdjacent( *e ) )
        return true;
    return false;
  }
 
  template <typename E>
  template <typename G>
  typename G::Ref BaseGraph<E>::getConnectedComponent( G & thisg,
                                                       Vertex & v )
  {
    typename G::Ref out;
    thisg.getConnectedComponent( v, out );
    return out;
  }
 
  template <typename E>
  template <typename G>
  void BaseGraph<E>::getConnectedComponent( G & thisg,
                                            Vertex & v,
                                            typename G::Ref & g )
  {
    g.insert( v );
    typename G::edge_iterator e;
    for( e = thisg.beginEdge(v); e != thisg.endEdge(v); ++e ) {
      g.insert( *e );
      if( !g.contains( e->other(v) ) )
        thisg.getConnectedComponent( e->other(v), g );
    }
  }
 
  //--- defined methods ------------------------------------------------------
 
  template <typename E>
  template <typename Set>
  Set BaseGraph<E>::getComplement( const Set & s, const Set & e )
  {
    Set out;
    typename Set::const_iterator i;
    for( i = e.begin(); i != e.end(); ++i ) {
      if( !s.count(*i) )
        out.insert(*i);
    }
    return out;
  }
 
//============================================================================
// BASE GRAPH REF
//============================================================================
  template <typename E>
  class BaseGraphRef: public carto::rc_ptr<BaseGraph<E> >
  {
    //--- typedef ------------------------------------------------------------
  protected:
    typedef typename carto::rc_ptr<BaseGraph<E> >  Base;
    typedef BaseGraph<E>                           Pointed;
    typedef BaseGraphRef<E>                        This;
  public:
    typedef typename Pointed::Vertex   Vertex;
    typedef typename Pointed::Edge     Edge;
    typedef typename Pointed::Graph    Graph;
 
    //--- constructors -------------------------------------------------------
  public:
    BaseGraphRef(): Base( new Pointed() ) {}
    BaseGraphRef( Pointed * g ): Base( g ) {}
    BaseGraphRef( const Base & other ): Base(other) {}
    virtual ~BaseGraphRef() {}
 
    //--- none factory -------------------------------------------------------
  public:
    static Graph none() { return This( (Pointed*)0 ); }
 
    //--- virtual methods ----------------------------------------------------
  public:
    virtual void insert( Vertex v ) { return (*this)->insert(v); }
    virtual void insert( Edge e ) { return (*this)->insert(e); }
    virtual bool contains( const Vertex & v ) const { return (*this)->contains(v); }
    virtual bool contains( const Edge & e ) const { return (*this)->contains(e); }
    virtual bool empty() const { return (*this)->empty(); }
    virtual void clear() { return (*this)->clear(); }
 
    //--- virtual operators ----------------------------------------------------
  public:
    virtual bool operator== ( const This & other ) const
    {
      if( !(*this) && !other )
        return true;
      else if( !(*this) || !other )
        return false;
      else
        return *(this->get()) == *(other.get());
    }
    virtual bool operator!= ( const This & other ) const
    {
      return !( *this == other );
    }
    virtual bool operator>  ( const This & other ) const
    {
      if( *this == other )
        return false;
      else
        return this > &other;
    }
    virtual bool operator<  ( const This & other ) const
    {
      if( *this == other )
        return false;
      else
        return this < &other;
    }
    virtual bool operator>= ( const This & other ) const
    {
      return ( *this == other ) || ( *this > other );
    }
    virtual bool operator<= ( const This & other ) const
    {
      return ( *this == other ) || ( *this < other );
    }
 
    //--- virtual properties -------------------------------------------------
  public:
    virtual bool isAdjacent( const Vertex & x, const Vertex & y ) const { return (*this)->isAdjacent(x,y); }
    virtual bool isLinked( const Vertex & x, const Vertex & y ) const { return (*this)->isLinked(x,y); }
    virtual bool isSubGraph( const Graph & g ) const { return (*this)->isSubGraph(g); }
    virtual bool isConnectedComponent( const Graph & g ) const { return (*this)->isConnectedComponent(g); }
    virtual bool isAdjacentTo( const Vertex & v, const Graph & g ) const { return (*this)->isAdjacentTo(v,g); }
    virtual bool isAdjacentFrom( const Vertex & v, const Graph & g ) const { return (*this)->isAdjacentFrom(v,g); }
    virtual bool isAdjacent( const Edge & e ) const { return (*this)->isAdjacent(e); }
    virtual bool isLinked( const Vertex & v ) const  { return (*this)->isLinked(v); }
    virtual bool isExtension( const Graph & h, const Graph & g ) const { return (*this)->isExtension(h,g); }
    virtual bool isForestRelativeTo( const Graph & h, const Graph & g ) const { return (*this)->isForestRelativeTo(h,g); }
    virtual bool isSpanningForestRelativeTo( const Graph & h, const Graph & g ) const { return (*this)->isSpanningForestRelativeTo(h,g); }
    virtual bool isTree( const Graph & g ) const { return (*this)->isTree(g); }
    virtual bool isSpanningTree( const Graph & g ) const { return (*this)->isSpanningTree(g); }
    virtual bool isForest( const Graph & g ) const { return (*this)->isForest(g); }
    virtual bool isSpanningForest( const Graph & g ) const { return (*this)->isSpanningForest(g); }
    template <typename EdgeIterator>
    bool isGraphCut( EdgeIterator begin, EdgeIterator end, const Graph & g ) const { return (*this)->isGraphCut(begin,end,g); }
    template <typename EdgeSet>
    bool isGraphCut( const EdgeSet & es, const Graph & g ) const { return (*this)->isGraphCut(es,g); }
 
    //--- defined static methods ---------------------------------------------
  public:
    template <typename Set>
    static Set getComplement( const Set & s, const Set & e ) { return Pointed::getComplement(s,e); }
 
    //--- friends ------------------------------------------------------------
    friend class BaseGraph<E>;
  };
 
} // namespace bio
 
#endif // BIOPROCESSING_GRAPH_BASEGRAPH