COIN-OR::LEMON - Graph Library

Changeset 340:a2ce3c4780b7 in lemon-0.x for src


Ignore:
Timestamp:
04/16/04 15:42:03 (20 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@459
Message:
 
Location:
src/work/deba
Files:
1 added
5 edited

Legend:

Unmodified
Added
Removed
  • src/work/deba/edge_map_base.h

    r336 r340  
    22#define EDGE_MAP_BASE_H
    33
    4 template <class G, class K>
     4/**
     5        Template base class for implementing mapping on edges.
     6        \param The first template parameter is the Graph class. The Graph
     7                must have an \emp edge_maps member with \emp EdgeMapRegistry class.
     8        \param The second template parameter is the Edge type of the class.
     9       
     10*/
     11
     12template <typename G, typename K>
    513class EdgeMapBase {
    614public:
     
    917        typedef K KeyType;
    1018       
     19        /**
     20                Default constructor.
     21        */     
     22       
    1123        EdgeMapBase() : graph(0) {}
     24
     25        /**
     26                Simple constructor to register into a graph.
     27        */
     28       
    1229        EdgeMapBase(Graph& g) : graph(&g) {
    1330                graph->edge_maps.add(*this);
    1431        }
     32
     33        /**
     34                Copy constructor with registering into the map.
     35        */     
     36       
     37        EdgeMapBase(const EdgeMapBase& copy) : graph(copy.graph) {
     38                if (graph) {
     39                        graph->edge_maps.add(*this);
     40                }
     41        }
     42       
     43        /**
     44                Assign operator.
     45        */     
     46
     47        const EdgeMapBase& operator=(const EdgeMapBase& copy) {
     48                if (graph) {
     49                        graph.edge_maps.erase(*this);
     50                }
     51                graph = copy.graph;
     52                if (graph) {
     53                        graph->edge_maps.add(*this);
     54                }
     55               
     56        }
     57       
     58
     59        /**
     60                Destructor.
     61        */     
    1562
    1663        virtual ~EdgeMapBase() {
     
    2673        int graph_index;
    2774       
     75        /**
     76                Helper function to implement the default constructor in the subclasses.
     77        */
     78       
    2879        void init() {
    2980                for (Graph::EdgeIt it(g); g.valid(it); g.next(it)) {
     
    3182                }
    3283        }
     84       
     85        /**
     86                Helper function to implement the destructor in the subclasses.
     87        */
    3388       
    3489        void destroy() {
     
    3893        }
    3994       
     95        /**
     96                The add member function should be overloaded in the subclasses.
     97                \e Add extends the map with the new edge.
     98        */
     99       
    40100        virtual void add(const KeyType&) = 0;
     101       
     102        /**
     103                The erase member function should be overloaded in the subclasses.
     104                \e Erase removes the edge from the map.
     105        */
     106       
    41107        virtual void erase(const KeyType&) = 0;
     108       
     109        /**
     110                Exception class to throw at unsupported operation.
     111        */
     112       
     113        class NotSupportedOperationException {};
    42114
    43115        friend class Graph;
  • src/work/deba/edge_map_registry.h

    r337 r340  
    33
    44#include <vector>
     5
     6#include "edge_map_base.h"
    57
    68template <typename G, typename E>
     
    1012        typedef E Edge
    1113       
    12         typedef EdgeMapBase<Graph, Edge> EdgeMapBase;
     14        typedef EdgeMapBase<Graph, Edge> MapBase;
    1315
    1416protected:
     
    1719        Container container;
    1820       
    19         void add(EdgeMapBase& map_base) {
     21        void add(MapBase& map_base) {
    2022                if (map_base.graph) {
    2123                        map_base.graph->edge_maps.erase(map_base);
     
    2628        }
    2729       
    28         void erase(EdgeMapBase& map_base) {
     30        void erase(MapBase& map_base) {
    2931                if (map_base.graph != this) return;
    3032                container.back()->graph_index = map_base.graph_index;
     
    3436        }
    3537       
    36         void addEdge(Edge& edge) {
     38        void add(Edge& edge) {
    3739                typename Container::iterator it;
    3840                for (it = container.begin(); it != container.end(); ++it) {
     
    4143        }
    4244       
    43         void eraseEdge(Edge& edge) {
     45        void erase(Edge& edge) {
    4446                typename Container::iterator it;
    4547                for (it = container.begin(); it != container.end(); ++it) {
     
    4850        }
    4951
    50         friend class EdgeMapBase;
     52        friend class MapBase;
    5153};
    5254
  • src/work/deba/node_map_base.h

    r336 r340  
    22#define NODE_MAP_BASE_H
    33
    4 template <class G, class K>
     4/**
     5        Template base class for implementing mapping on nodes.
     6        \param The first template parameter is the Graph class. The Graph
     7                must have an \emp node_maps member with \emp NodeMapRegistry class.
     8        \param The second template parameter is the Node type of the class.
     9       
     10*/
     11
     12template <typename G, typename K>
    513class NodeMapBase {
    614public:
     
    917        typedef K KeyType;
    1018       
     19        /**
     20                Default constructor.
     21        */     
     22       
    1123        NodeMapBase() : graph(0) {}
     24
     25        /**
     26                Simple constructor to register into a graph.
     27        */
     28       
    1229        NodeMapBase(Graph& g) : graph(&g) {
    1330                graph->node_maps.add(*this);
    1431        }
     32
     33        /**
     34                Copy constructor with registering into the map.
     35        */     
     36       
     37        NodeMapBase(const NodeMapBase& copy) : graph(copy.graph) {
     38                if (graph) {
     39                        graph->node_maps.add(*this);
     40                }
     41        }
     42       
     43        /**
     44                Assign operator.
     45        */     
     46
     47        const NodeMapBase& operator=(const NodeMapBase& copy) {
     48                if (graph) {
     49                        graph.node_maps.erase(*this);
     50                }
     51                graph = copy.graph;
     52                if (graph) {
     53                        graph->node_maps.add(*this);
     54                }
     55               
     56        }
     57       
     58
     59        /**
     60                Destructor.
     61        */     
    1562
    1663        virtual ~NodeMapBase() {
     
    2673        int graph_index;
    2774       
     75        /**
     76                Helper function to implement the default constructor in the subclasses.
     77        */
     78       
    2879        void init() {
    2980                for (Graph::NodeIt it(g); g.valid(it); g.next(it)) {
     
    3182                }
    3283        }
     84       
     85        /**
     86                Helper function to implement the destructor in the subclasses.
     87        */
    3388       
    3489        void destroy() {
     
    3893        }
    3994       
     95        /**
     96                The add member function should be overloaded in the subclasses.
     97                \e Add extends the map with the new node.
     98        */
     99       
    40100        virtual void add(const KeyType&) = 0;
     101       
     102        /**
     103                The erase member function should be overloaded in the subclasses.
     104                \e Erase removes the node from the map.
     105        */
     106       
    41107        virtual void erase(const KeyType&) = 0;
     108       
     109        /**
     110                Exception class to throw at unsupported operation.
     111        */
     112       
     113        class NotSupportedOperationException {};
    42114
    43115        friend class Graph;
  • src/work/deba/node_map_registry.h

    r337 r340  
    33
    44#include <vector>
     5
     6#include "node_map_base.h"
    57
    68template <typename G, typename E>
     
    3436        }
    3537       
    36         void addNode(Node& node) {
     38        void add(Node& node) {
    3739                typename Container::iterator it;
    3840                for (it = container.begin(); it != container.end(); ++it) {
     
    4143        }
    4244       
    43         void eraseNode(Node& node) {
     45        void erase(Node& node) {
    4446                typename Container::iterator it;
    4547                for (it = container.begin(); it != container.end(); ++it) {
  • src/work/deba/test_graph.h

    r262 r340  
    77
    88#include <invalid.h>
     9
     10#include "vector_map.h"
     11#include "edge_map_registry.h"
     12#include "node_map_registry.h"
     13#include "edge_map_base.h"
     14#include "node_map_base.h"
    915
    1016namespace hugo {
     
    2935    class SymEdgeIt;
    3036   
    31     template <typename T> class NodeMap;
    32     template <typename T> class EdgeMap;
     37//    template <typename T> class NodeMap;
     38//    template <typename T> class EdgeMap;
    3339  private:
    34     template <typename T> friend class NodeMap;
    35     template <typename T> friend class EdgeMap;
     40//    template <typename T> friend class NodeMap;
     41 //   template <typename T> friend class EdgeMap;
    3642 
     43                NodeMapRegistry<ListGraph, Node> node_maps;
     44
    3745    template <typename T>
    38     class NodeMap {
    39       const ListGraph& G;
    40       std::vector<T> container;
    41     public:
    42       typedef T ValueType;
    43       typedef Node KeyType;
    44       NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { }
    45       NodeMap(const ListGraph& _G, T a) :
    46         G(_G), container(G.node_id, a) { }
    47       void set(Node n, T a) { container[/*G.id(n)*/n.node->id]=a; }
    48       T get(Node n) const { return container[/*G.id(n)*/n.node->id]; }
    49       typename std::vector<T>::reference operator[](Node n) {
    50         return container[/*G.id(n)*/n.node->id]; }
    51       typename std::vector<T>::const_reference operator[](Node n) const {
    52         return container[/*G.id(n)*/n.node->id];
    53       }
    54       void update() { container.resize(G.node_id); }
    55       void update(T a) { container.resize(G.node_id, a); }
    56     };
     46    class NodeMap : public VectorMap<ListGraph, Edge, T, EdgeMapBase> {};
     47               
     48                EdgeMapRegistry<ListGraph, Edge> edge_maps;
    5749
    5850    template <typename T>
    59     class EdgeMap {
    60       const ListGraph& G;
    61       std::vector<T> container;
    62     public:
    63       typedef T ValueType;
    64       typedef Edge KeyType;
    65       EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { }
    66       EdgeMap(const ListGraph& _G, T a) :
    67         G(_G), container(G.edge_id, a) { }
    68       void set(Edge e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
    69       T get(Edge e) const { return container[/*G.id(e)*/e.edge->id]; }
    70       typename std::vector<T>::reference operator[](Edge e) {
    71         return container[/*G.id(e)*/e.edge->id]; }
    72       typename std::vector<T>::const_reference operator[](Edge e) const {
    73         return container[/*G.id(e)*/e.edge->id];
    74       }
    75       void update() { container.resize(G.edge_id); }
    76       void update(T a) { container.resize(G.edge_id, a); }
    77     };
     51    class EdgeMap : public VectorMap<Graph, Node, T, NodeMapBase> {};
     52
    7853
    7954    int node_id;
     
    324299    /* adding nodes and edges */
    325300
    326     Node addNode() { return Node(_add_node()); }
     301    Node addNode() {
     302                        Node n = _add_node();
     303                        node_maps.add(n);
     304                        return n;
     305                }
    327306    Edge addEdge(Node u, Node v) {
    328       return Edge(_add_edge(u.node, v.node));
     307                        Edge e = _add_edge(u.node, v.node);
     308                        edge_maps.add(e);
     309      return e;
    329310    }
    330311
    331312    void erase(Node i) {
     313                        node_map.erase(i);
    332314      while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
    333315      while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
     
    335317    }
    336318 
    337     void erase(Edge e) { _delete_edge(e.edge); }
     319    void erase(Edge e) {
     320                        edge_maps.erase(e);
     321                        _delete_edge(e.edge);
     322                }
    338323
    339324    void clear() {
Note: See TracChangeset for help on using the changeset viewer.