COIN-OR::LEMON - Graph Library

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


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

.

Location:
src/work/alpar
Files:
1 added
2 edited

Legend:

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

    r183 r186  
    1313  /// An empty graph class.
    1414 
    15   /// This class provides all the common features of a grapf structure,
    16   /// however completely without implementations or real data structures
     15  /// This class provides all the common features of a graph structure,
     16  /// however completely without implementations and real data structures
    1717  /// behind the interface.
    1818  /// All graph algorithms should compile with this class, but it will not
     
    3232    /// The base type of the node iterators.
    3333
    34     /// This \c Node is the base type of each node iterators,
     34    /// This is the base type of each node iterators,
    3535    /// thus each kind of node iterator will convert to this.
    3636    class Node {
     
    5959   
    6060    /// This iterator goes through each node.
     61
     62    /// This iterator goes through each node.
     63    /// Its usage is quite simple, for example you can count the number
     64    /// of nodes in graph \c G of type \c Graph like this:
     65    /// \code
     66    ///int count=0;
     67    ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
     68    /// \endcode
    6169    class NodeIt : public Node {
    6270    public:
     
    92100    };
    93101   
    94     /// This iterator goes trought the outgoing edges of a certain graph.
     102    /// This iterator goes trought the outgoing edges of a node.
     103
     104    /// This iterator goes trought the \e outgoing edges of a certain node
     105    /// of a graph.
     106    /// Its usage is quite simple, for example you can count the number
     107    /// of outgoing edges of a node \c n
     108    /// in graph \c G of type \c Graph as follows.
     109    /// \code
     110    ///int count=0;
     111    ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
     112    /// \endcode
    95113   
    96114    class OutEdgeIt : public Edge {
     
    110128    };
    111129
     130    /// This iterator goes trought the incoming edges of a node.
     131
     132    /// This iterator goes trought the \e incoming edges of a certain node
     133    /// of a graph.
     134    /// Its usage is quite simple, for example you can count the number
     135    /// of outgoing edges of a node \c n
     136    /// in graph \c G of type \c Graph as follows.
     137    /// \code
     138    ///int count=0;
     139    ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
     140    /// \endcode
     141
    112142    class InEdgeIt : public Edge {
    113143    public:
     
    120150    };
    121151    //  class SymEdgeIt : public Edge {};
     152
     153    /// This iterator goes through each edge.
     154
     155    /// This iterator goes through each edge of a graph.
     156    /// Its usage is quite simple, for example you can count the number
     157    /// of edges in a graph \c G of type \c Graph as follows:
     158    /// \code
     159    ///int count=0;
     160    ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
     161    /// \endcode
    122162    class EdgeIt : public Edge {
    123163    public:
     
    174214
    175215    /// Checks if a node iterator is valid
     216
     217    ///\todo Maybe, it would be better if iterator converted to
     218    ///bool directly, as Jacint prefers.
    176219    bool valid(const Node) const { return true;}
    177220    /// Checks if an edge iterator is valid
     221
     222    ///\todo Maybe, it would be better if iterator converted to
     223    ///bool directly, as Jacint prefers.
    178224    bool valid(const Edge) const { return true;}
    179225
     
    195241
    196242    /// \return the new node.
     243    ///
    197244    Node addNode() { return INVALID;}
    198245    ///Add a new edge to the graph.
     
    228275 
    229276
    230     ///Read/write map of the nodes to type \c T.
    231 
     277    ///Read/write/reference map of the nodes to type \c T.
     278
     279    ///Read/write/reference map of the nodes to type \c T.
     280    /// \sa MemoryMapSkeleton
    232281    /// \todo We may need copy constructor
    233282    /// \todo We may need conversion from other nodetype
     
    263312    };
    264313
    265     ///Read/write map of the edges to type \c T.
    266 
    267     ///Read/write map of the edges to type \c T.
    268     ///It behaves exactly the same way as \ref NodeMap.
     314    ///Read/write/reference map of the edges to type \c T.
     315
     316    ///Read/write/reference map of the edges to type \c T.
     317    ///It behaves exactly in the same way as \ref NodeMap.
     318    /// \sa NodeMap
     319    /// \sa MemoryMapSkeleton
     320    /// \todo We may need copy constructor
     321    /// \todo We may need conversion from other edgetype
     322    /// \todo We may need operator=
    269323    template<class T> class EdgeMap
    270324    {
  • 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.