COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Timestamp:
11/04/04 23:04:51 (20 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1344
Message:
  • Somewhat less redundant and a bit more correct graph concepts.
  • graph_wrapper_test does not compile
File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/lemon/concept/graph_component.h

    r959 r961  
    2929  namespace concept {
    3030
     31
     32    /****************   Graph iterator concepts   ****************/
     33
     34    /// Skeleton class for graph Node and Edge
     35
     36    /// \note Because Node and Edge are forbidden to inherit from the same
     37    /// base class, this is a template. For Node you shoul instantiate it
     38    /// with character 'n' and for Edge with 'e'.
     39
     40    template<char Ch>
     41    class GraphItem {
     42    public:
     43      GraphItem() {}
     44      GraphItem(Invalid) {}
     45
     46      // We explicitely list these:
     47      GraphItem(GraphItem const&) {}
     48      GraphItem& operator=(GraphItem const&) { return *this; }
     49
     50      bool operator==(GraphItem) const { return false; }
     51      bool operator!=(GraphItem) const { return false; }
     52
     53      // Technical requirement. Do we really need this?
     54      bool operator<(GraphItem) const { return false; }
     55    };
     56
     57
     58    template<typename GI>
     59    struct GraphItemConcept {
     60      void constraints() {
     61        GI i1;
     62        GI i2 = i1;
     63        GI i3 = INVALID;
     64       
     65        i1 = i2 = i3;
     66
     67        bool b;
     68        b = (ia == ib) && (ia != ib) && (ia < ib);
     69        b = (ia == INVALID) && (ib != INVALID);
     70      }
     71
     72      const GI &ia;
     73      const GI &ib;
     74    };
     75
     76
     77    template<typename Iter, typename Graph, typename BaseItem>
     78    struct GraphIteratorConcept {
     79      void constraints() {
     80        function_requires< GraphItemConcept<Iter> >();
     81        Iter it1(g);
     82
     83        /// \todo Do we need NodeIt(Node) kind of constructor?
     84        //      Iter it2(bj);
     85        Iter it2;
     86
     87        it2 = ++it1;
     88        ++it2 = it1;
     89        ++(++it1);
     90        /// \bug This should be: is_base_and_derived<BaseItem, Iter>
     91        BaseItem bi = it1;
     92        bi = it2;
     93      }
     94
     95      BaseItem bj;
     96      Graph g;
     97    };
     98
     99    template<typename Iter, typename Graph>
     100    struct GraphIncIteratorConcept {
     101      typedef typename Graph::Node Node;
     102      typedef typename Graph::Edge Edge;
     103      void constraints() {
     104        function_requires< GraphItemConcept<Iter> >();
     105        Iter it1(graph, node);
     106        /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
     107        //      Iter it2(edge);
     108        Iter it2;
     109
     110        it2 = ++it1;
     111        ++it2 = it1;
     112        ++(++it1);
     113        Edge e = it1;
     114        e = it2;
     115      }
     116
     117      Edge edge;
     118      Node node;
     119      Graph graph;
     120    };
     121
     122
     123
    31124    /// An empty base graph class.
    32125 
    33     /// This class provides the most minimal features of a graph structure.
    34     /// All the graph concepts have to be conform to this base graph.
     126    /// This class provides the minimal set of features needed for a graph
     127    /// structure. All graph concepts have to be conform to this base
     128    /// graph.
     129    ///
     130    /// \bug This is not true. The minimal graph concept is the
     131    /// BaseIterableGraphComponent.
    35132
    36133    class BaseGraphComponent {
    … …  
    71168        /// Two iterators are equal if and only if they represents the
    72169        /// same node in the graph or both are invalid.
    73         bool operator==(const Node&) { return true;}
     170        bool operator==(const Node&) const { return true;}
    74171
    75172
    … …  
    78175        /// \sa operator==(const Node& n)
    79176        ///
    80         bool operator!=(const Node&) { return true;}
     177        bool operator!=(const Node&) const { return true;}
    81178
    82179        /// Comparison operator.
    … …  
    86183        /// This ordering can be different from the iterating order of nodes.
    87184        /// \todo Possibly we don't need it.
    88         bool operator<(const Node&) { return true;}
     185        bool operator<(const Node&) const { return true;}
    89186      };
    90187
    … …  
    121218        /// Two iterators are equal if and only if they represents the
    122219        /// same edge in the graph or both are invalid.
    123         bool operator==(const Edge&) { return true;}
     220        bool operator==(const Edge&) const { return true;}
    124221
    125222
    … …  
    128225        /// \sa operator==(const Edge& n)
    129226        ///
    130         bool operator!=(const Edge&) { return true;}
     227        bool operator!=(const Edge&) const { return true;}
    131228
    132229        /// Comparison operator.
    … …  
    136233        /// This ordering can be different from the iterating order of edges.
    137234        /// \todo Possibly we don't need it.
    138         bool operator<(const Edge&) { return true;}
     235        bool operator<(const Edge&) const { return true;}
    139236      };
    140237
    … …  
    151248      Node tail(const Edge&) const { return INVALID;}
    152249    };
     250
    153251
    154252    /// Concept check structure for BaseGraph.
    … …  
    163261     
    164262      void constraints() {
    165         {
    166           Node ni;
    167           Node nj(ni);
    168           Node nk(INVALID);
    169           ni = nj;
    170           bool b; b = true;
    171           b = (ni == INVALID); b = (ni != INVALID);
    172           b = (ni==nj); b = (ni != nj); b=( ni < nj);
    173         }
    174         {
    175           Edge ei;
    176           Edge ej(ei);
    177           Edge ek(INVALID);
    178           ei = ej;
    179           bool b; b = true;
    180           b = (ei == INVALID); b = (ei != INVALID);
    181           b = (ei==ej); b = (ei != ej); b=( ei < ej);
    182         }
     263        function_requires< GraphItemConcept<Node> >();
     264        function_requires< GraphItemConcept<Edge> >();
    183265        {
    184266          const Graph& const_graph = graph;
    … …  
    263345    struct BaseIterableGraphComponentConcept {
    264346     
    265       void constraints() { 
    266         const Graph& const_graph = graph;
     347      void constraints() {
     348        function_requires< BaseGraphComponentConcept<Graph> >();
    267349        typename Graph::Node node;     
    268350        typename Graph::Edge edge;
    269351        {
    270           const_graph.first(node);
    271           const_graph.next(node);
     352          graph.first(node);
     353          graph.next(node);
    272354        }
    273355        {
    274           const_graph.first(edge);
    275           const_graph.next(edge);
     356          graph.first(edge);
     357          graph.next(edge);
    276358        }
    277359        {
    278           const_graph.firstIn(edge, node);
    279           const_graph.nextIn(edge);
     360          graph.firstIn(edge, node);
     361          graph.nextIn(edge);
    280362        }
    281363        {
    282           const_graph.firstOut(edge, node);
    283           const_graph.nextOut(edge);
     364          graph.firstOut(edge, node);
     365          graph.nextOut(edge);
    284366        }
    285367      }
    286368
    287       Graph& graph;
     369      const Graph& graph;
    288370    };
    289371
    … …  
    323405
    324406      void constraints() {
    325         const Graph& const_graph = graph;
     407        function_requires< BaseGraphComponentConcept<Graph> >();
    326408        typename Graph::Node node;
    327         int nid = const_graph.id(node);
    328         nid = const_graph.id(node);
     409        int nid = graph.id(node);
     410        nid = graph.id(node);
    329411        typename Graph::Edge edge;
    330         int eid = const_graph.id(edge);
    331         eid = const_graph.id(edge);
    332       }
    333 
    334       Graph& graph;
     412        int eid = graph.id(edge);
     413        eid = graph.id(edge);
     414      }
     415
     416      const Graph& graph;
    335417    };
    336418
    … …  
    366448
    367449      void constraints() {
    368         const Graph& const_graph = graph;
    369         int nid = const_graph.maxEdgeId();
     450        function_requires< BaseGraphComponentConcept<Graph> >();
     451        int nid = graph.maxEdgeId();
    370452        ignore_unused_variable_warning(nid);
    371         int eid = const_graph.maxNodeId();
     453        int eid = graph.maxNodeId();
    372454        ignore_unused_variable_warning(eid);
    373455      }
    374456
    375       Graph& graph;
     457      const Graph& graph;
    376458    };
    377459
    … …  
    412494    struct BaseExtendableGraphComponentConcept {
    413495      void constraints() {
     496        function_requires< BaseGraphComponentConcept<Graph> >();
    414497        typename Graph::Node node_a, node_b;
    415498        node_a = graph.addNode();
    … …  
    453536    struct BaseErasableGraphComponentConcept {
    454537      void constraints() {
     538        function_requires< BaseGraphComponentConcept<Graph> >();
    455539        typename Graph::Node node;
    456540        graph.erase(node);
    … …  
    484568    struct BaseClearableGraphComponentConcept {
    485569      void constraints() {
     570        function_requires< BaseGraphComponentConcept<Graph> >();
    486571        graph.clear();
    487572      }
    … …  
    491576
    492577
    493     class IterableGraphComponent : virtual public BaseGraphComponent {
     578    class IterableGraphComponent :
     579      virtual public BaseIterableGraphComponent {
    494580
    495581    public:
    … …  
    504590        NodeIt() {}
    505591        NodeIt(Invalid) {}
    506         NodeIt(const Graph&) {}
     592        // explicit NodeIt(Node) {}
     593        explicit NodeIt(const Graph&) {}
    507594
    508595        NodeIt& operator++() { return *this; }
    509596        //      Node operator*() const { return INVALID; }
    510597
    511         bool operator==(const NodeIt&) { return true;}
    512         bool operator!=(const NodeIt&) { return true;}
     598        bool operator==(const NodeIt&) const { return true;}
     599        bool operator!=(const NodeIt&) const { return true;}
    513600      };
    514601
    … …  
    517604        EdgeIt() {}
    518605        EdgeIt(Invalid) {}
    519         EdgeIt(const Graph&) {}
     606        // explicit EdgeIt(Edge) {}
     607        explicit EdgeIt(const Graph&) {}
    520608
    521609        EdgeIt& operator++() { return *this; }
    522610        //      Edge operator*() const { return INVALID; }
    523611
    524         bool operator==(const EdgeIt&) { return true;}
    525         bool operator!=(const EdgeIt&) { return true;}
     612        bool operator==(const EdgeIt&) const { return true;}
     613        bool operator!=(const EdgeIt&) const { return true;}
    526614      };
    527615
    … …  
    530618        InEdgeIt() {}
    531619        InEdgeIt(Invalid) {}
    532         InEdgeIt(const Graph&, const Node&) {}
     620        // explicit InEdgeIt(Edge) {}
     621        explicit InEdgeIt(const Graph&, const Node&) {}
    533622
    534623        InEdgeIt& operator++() { return *this; }
    535624        //      Edge operator*() const { return INVALID; }
    536625
    537         bool operator==(const InEdgeIt&) { return true;}
    538         bool operator!=(const InEdgeIt&) { return true;}
     626        bool operator==(const InEdgeIt&) const { return true;}
     627        bool operator!=(const InEdgeIt&) const { return true;}
    539628      };
    540629
    … …  
    543632        OutEdgeIt() {}
    544633        OutEdgeIt(Invalid) {}
    545         OutEdgeIt(const Graph&, const Node&) {}
     634        // explicit OutEdgeIt(Edge) {}
     635        explicit OutEdgeIt(const Graph&, const Node&) {}
    546636
    547637        OutEdgeIt& operator++() { return *this; }
    548638        //      Edge operator*() const { return INVALID; }
    549639
    550         bool operator==(const OutEdgeIt&) { return true;}
    551         bool operator!=(const OutEdgeIt&) { return true;}
     640        bool operator==(const OutEdgeIt&) const { return true;}
     641        bool operator!=(const OutEdgeIt&) const { return true;}
    552642      };
    553643
    … …  
    558648
    559649      void constraints() {
    560  
     650        function_requires< BaseIterableGraphComponentConcept<Graph> >();
     651
    561652        typedef typename Graph::Node Node;
    562653        typedef typename Graph::NodeIt NodeIt;
    … …  
    566657        typedef typename Graph::OutEdgeIt OutEdgeIt;
    567658 
    568         {
    569           NodeIt it;
    570           NodeIt jt(it);
    571           NodeIt kt(INVALID);
    572           NodeIt lt(graph);
    573           it = jt;
    574           jt = ++it;
    575           bool b;
    576           b = (it == INVALID);
    577           b = (it != INVALID);
    578           b = (it == jt);
    579           b = (it != jt);
    580           Node node = it;
    581           node = it;
    582         }
    583         {
    584           EdgeIt it;
    585           EdgeIt jt(it);
    586           EdgeIt kt(INVALID);
    587           EdgeIt lt(graph);
    588           it = jt;
    589           jt = ++it;
    590           bool b;
    591           b = (it == INVALID);
    592           b = (it != INVALID);
    593           b = (it == jt);
    594           b = (it != jt);
    595           Edge edge = it;
    596           edge = it;
    597         }
    598         {
    599           InEdgeIt it;
    600           InEdgeIt jt(it);
    601           InEdgeIt kt(INVALID);
    602           Node node;
    603           InEdgeIt lt(graph, node);
    604           it = jt;
    605           jt = ++it;
    606           bool b;
    607           b = (it == INVALID);
    608           b = (it != INVALID);
    609           b = (it == jt);
    610           b = (it != jt);
    611           Edge edge = it;
    612           edge = it;
    613         }
    614         {
    615           OutEdgeIt it;
    616           OutEdgeIt jt(it);
    617           OutEdgeIt kt(INVALID);
    618           Node node;
    619           OutEdgeIt lt(graph, node);
    620           it = jt;
    621           jt = ++it;
    622           bool b;
    623           b = (it == INVALID);
    624           b = (it != INVALID);
    625           b = (it == jt);
    626           b = (it != jt);
    627           Edge edge = it;
    628           edge = it;
    629         }
     659        function_requires< GraphIteratorConcept<NodeIt, Graph, Node> >();
     660        function_requires< GraphIteratorConcept<EdgeIt, Graph, Edge> >();
     661        function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
     662        function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
    630663      }
    631664      Graph& graph;
    … …  
    637670      typedef IdMappableGraphComponent Graph;
    638671
    639       typedef BaseGraphComponent::Node Node;
    640       typedef BaseGraphComponent::Edge Edge;
    641 
    642     public:
     672    public:
     673
     674      typedef BaseGraphComponent::Node Node;
     675      typedef BaseGraphComponent::Edge Edge;
    643676
    644677      class NodeIdMap : public ReadMap<Node, int> {
    … …  
    659692    struct IdMappableGraphComponentConcept {
    660693      void constraints() {     
     694        function_requires< BaseGraphComponentConcept<Graph> >();
    661695        {
    662696          typedef typename Graph::EdgeIdMap EdgeIdMap;
    … …  
    720754
    721755      void constraints() {
     756        function_requires< BaseGraphComponentConcept<Graph> >();
    722757        { // int map test
    723758          typedef typename Graph::template NodeMap<int> IntNodeMap;
    … …  
    768803    struct ExtendableGraphComponentConcept {
    769804      void constraints() {
     805        function_requires< BaseGraphComponentConcept<Graph> >();
    770806        typename Graph::Node node_a, node_b;
    771807        node_a = graph.addNode();
    … …  
    792828    struct ErasableGraphComponentConcept {
    793829      void constraints() {
     830        function_requires< BaseGraphComponentConcept<Graph> >();
    794831        typename Graph::Node node;
    795832        graph.erase(node);
    … …  
    816853    struct ClearableGraphComponentConcept {
    817854      void constraints() {
     855        function_requires< BaseGraphComponentConcept<Graph> >();
    818856        graph.clear();
    819857      }
Note: See TracChangeset for help on using the changeset viewer.