COIN-OR::LEMON - Graph Library

Changeset 186:47cd1716870e in lemon-0.x for src/work/alpar/smart_graph.h


Ignore:
Timestamp:
03/15/04 17:30:20 (18 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@262
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/smart_graph.h

    r185 r186  
    1313  class SymSmartGraph;
    1414
    15   //  template<typename T> class SymSmartGraph::SymEdgeMap;
    16  
     15  ///A smart graph class.
     16
     17  ///This is a simple and fast graph implementation.
     18  ///It is also quite memory efficient, but at the price
     19  ///that <b> it does not support node and edge deletion</b>.
     20  ///Apart from this it conforms to the graph interface documented under
     21  ///the description of \ref GraphSkeleton.
     22  ///\sa \ref GraphSkeleton.
    1723  class SmartGraph {
    1824
     
    5662    //  protected:
    5763    // HELPME:
    58   public:
     64  protected:
    5965    ///\bug It must be public because of SymEdgeMap.
    6066    ///
     
    100106    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
    101107
     108    ///\bug This function does something different than
     109    ///its name would suggests...
    102110    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
     111    ///\bug This function does something different than
     112    ///its name would suggests...
    103113    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
    104114
    105    
    106115    Node tail(Edge e) const { return edges[e.n].tail; }
    107116    Node head(Edge e) const { return edges[e.n].head; }
     
    481490  ///The purpose of this graph structure is to handle graphs
    482491  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
    483   ///of oppositely directed edges. You can define edge maps which
    484   ///stores a common value for the edge pairs. The usual edge maps can be used
     492  ///of oppositely directed edges.
     493  ///There is a new edge map type called
     494  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
     495  ///that complements this
     496  ///feature by
     497  ///storing shared values for the edge pairs. The usual
     498  ///\ref GraphSkeleton::EdgeMap "EdgeMap"
     499  ///can be used
    485500  ///as well.
    486501  ///
    487   ///The oppositely directed edge can also be obtained easily.
     502  ///The oppositely directed edge can also be obtained easily
     503  ///using \ref opposite.
     504  ///\warning It shares the similarity with \ref SmartGraph that
     505  ///it is not possible to delete edges or nodes from the graph.
     506  //\sa \ref SmartGraph.
    488507
    489508  class SymSmartGraph : public SmartGraph
    490509  {
    491510  public:
     511    template<typename T> class SymEdgeMap;
     512    template<typename T> friend class SymEdgeMap;
     513
    492514    SymSmartGraph() : SmartGraph() { }
    493515    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
     
    499521    }
    500522
     523    ///The oppositely directed edge.
     524
     525    ///Returns the oppositely directed
     526    ///pair of the edge \c e.
    501527    Edge opposite(Edge e) const
    502528    {
     
    506532    }
    507533   
     534    ///Common data storage for the edge pairs.
     535
     536    ///This map makes it possible to store data shared by the oppositely
     537    ///directed pairs of edges.
    508538    template <typename T> class SymEdgeMap : public DynMapBase<Edge>
    509539    {
     
    514544      typedef Edge KeyType;
    515545
    516       SymEdgeMap(const SmartGraph &_G) :
     546      SymEdgeMap(const SymSmartGraph &_G) :
    517547        DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
    518548      {
    519         G->dyn_edge_maps.push_back(this);
    520       }
    521       SymEdgeMap(const SmartGraph &_G,const T &t) :
     549        static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
     550      }
     551      SymEdgeMap(const SymSmartGraph &_G,const T &t) :
    522552        DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
    523553      {
     
    551581        if(G) {
    552582          std::vector<DynMapBase<Edge>* >::iterator i;
    553           for(i=G->dyn_edge_maps.begin();
    554               i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
     583          for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
     584              i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
     585                && *i!=this; ++i) ;
    555586          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    556587          //A better way to do that: (Is this really important?)
    557588          if(*i==this) {
    558             *i=G->dyn_edge_maps.back();
    559             G->dyn_edge_maps.pop_back();
     589            *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
     590            static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
    560591          }
    561592        }
Note: See TracChangeset for help on using the changeset viewer.