lemon-0.x: src/lemon/concept/undir

     1 /* -*- C++ -*-

     2  *

     3  * src/lemon/concept/undir_graph_component.h - Part of LEMON, a generic

     4  * C++ optimization library

     5  *

     6  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi

     7  * Kutatocsoport (Egervary Combinatorial Optimization Research Group,

     8  * EGRES).

     9  *

    10  * Permission to use, modify and distribute this software is granted

    11  * provided that this copyright notice appears in all copies. For

    12  * precise terms see the accompanying LICENSE file.

    13  *

    14  * This software is provided "AS IS" with no warranty of any kind,

    15  * express or implied, and with no claim as to its suitability for any

    16  * purpose.

    17  *

    18  */

    20 ///\ingroup concept

    21 ///\file

    22 ///\brief Undirected graphs and components of.

    25 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H

    26 #define LEMON_CONCEPT_UNDIR_GRAPH_H

    28 #include <lemon/concept/graph_component.h>

    30 namespace lemon {

    31   namespace concept {

    33     /// \todo to be done

    35     struct BaseIterableUndirGraphConcept {

    37       template <typename Graph>

    38       struct Constraints {

    40 	typedef typename Graph::UndirEdge UndirEdge;

    41 	typedef typename Graph::Edge Edge;

    42 	typedef typename Graph::Node Node;

    44 	void constraints() {

    45 	  checkConcept<BaseIterableGraphComponent, Graph>();

    46 	  checkConcept<GraphItem<'u'>, UndirEdge >();

    48 	  /// \bug this should be base_and_derived:

    49 	  UndirEdge ue = e;

    50 	  ue = e;

    52 	  Node n;

    53 	  n = graph.target(ue);

    54 	  n = graph.source(ue);

    56 	  graph.first(ue);

    57 	  graph.next(ue);

    58 	}

    59 	const Graph &graph;

    60 	Edge e;

    61       };

    63     };

    66     struct IterableUndirGraphConcept {

    68       template <typename Graph>

    69       struct Constraints {

    70 	void constraints() {

    71 	  /// \todo we don't need the iterable component to be base iterable

    72 	  /// Don't we really???

    73 	  //checkConcept< BaseIterableUndirGraphConcept, Graph > ();

    75 	  checkConcept<IterableGraphComponent, Graph> ();

    77 	  typedef typename Graph::UndirEdge UndirEdge;

    78 	  typedef typename Graph::UndirEdgeIt UndirEdgeIt;

    79 	  typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;

    81 	  checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();

    82 	  checkConcept<GraphIncIterator<Graph, UndirEdge>, UndirIncEdgeIt>();

    83 	}

    84       };

    86     };

    88     struct MappableUndirGraphConcept {

    90       template <typename Graph>

    91       struct Constraints {

    93 	struct Dummy {

    94 	  int value;

    95 	  Dummy() : value(0) {}

    96 	  Dummy(int _v) : value(_v) {}

    97 	};

    99 	void constraints() {

   100 	  checkConcept<MappableGraphComponent, Graph>();

   102 	  typedef typename Graph::template UndirEdgeMap<int> IntMap;

   103 	  checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,

   104 	    IntMap >();

   106 	  typedef typename Graph::template UndirEdgeMap<bool> BoolMap;

   107 	  checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,

   108 	    BoolMap >();

   110 	  typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;

   111 	  checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,

   112 	    DummyMap >();

   113 	}

   114       };

   116     };

   118     struct ExtendableUndirGraphConcept {

   120       template <typename Graph>

   121       struct Constraints {

   122 	void constraints() {

   123 	  node_a = graph.addNode();

   124 	  uedge = graph.addEdge(node_a, node_b);

   125 	}

   126 	typename Graph::Node node_a, node_b;

   127 	typename Graph::UndirEdge uedge;

   128 	Graph graph;

   129       };

   131     };

   133     struct ErasableUndirGraphConcept {

   135       template <typename Graph>

   136       struct Constraints {

   137 	void constraints() {

   138 	  graph.erase(n);

   139 	  graph.erase(e);

   140 	}

   141 	Graph graph;

   142 	typename Graph::Node n;

   143 	typename Graph::UndirEdge e;

   144       };

   146     };

   148     class UndirGraph {

   149     public:

   151       template <typename Graph>

   152       struct Constraints {

   153 	void constraints() {

   154 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   155 	  checkConcept<IterableUndirGraphConcept, Graph>();

   156 	  checkConcept<MappableUndirGraphConcept, Graph>();

   157 	}

   158       };

   160     };

   162     class ExtendableUndirGraph : public UndirGraph {

   163     public:

   165       template <typename Graph>

   166       struct Constraints {

   167 	void constraints() {

   168 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   169 	  checkConcept<IterableUndirGraphConcept, Graph>();

   170 	  checkConcept<MappableUndirGraphConcept, Graph>();

   172 	  checkConcept<UndirGraph, Graph>();

   173 	  checkConcept<ExtendableUndirGraphConcept, Graph>();

   174 	  checkConcept<ClearableGraphComponent, Graph>();

   175 	}

   176       };

   178     };

   180     class ErasableUndirGraph : public ExtendableUndirGraph {

   181     public:

   183       template <typename Graph>

   184       struct Constraints {

   185 	void constraints() {

   186 	  checkConcept<ExtendableUndirGraph, Graph>();

   187 	  checkConcept<ErasableUndirGraphConcept, Graph>();

   188 	}

   189       };

   191     };

   193   }

   195 }

   197 #endif

author	marci
	Thu, 02 Dec 2004 17:36:07 +0000
changeset 1027	4ec35d1cd897
parent 1021	fd1d073b6557
child 1030	c8a41699e613
permissions	-rw-r--r--