src/lemon/concept/undir_graph.h
changeset 1099 91a8ee9d088d
parent 1022 567f392d1d2e
child 1158 29961fa390a3
equal deleted inserted replaced
4:dcaf775a04d7 5:f4ffd77825dc
    15  * express or implied, and with no claim as to its suitability for any
    15  * express or implied, and with no claim as to its suitability for any
    16  * purpose.
    16  * purpose.
    17  *
    17  *
    18  */
    18  */
    19 
    19 
    20 ///\ingroup concept
    20 ///\ingroup graph_concepts
    21 ///\file
    21 ///\file
    22 ///\brief Undirected graphs and components of.
    22 ///\brief Undirected graphs and components of.
    23 
    23 
    24 
    24 
    25 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
    25 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
    28 #include <lemon/concept/graph_component.h>
    28 #include <lemon/concept/graph_component.h>
    29 
    29 
    30 namespace lemon {
    30 namespace lemon {
    31   namespace concept {
    31   namespace concept {
    32 
    32 
    33     /// \todo to be done
    33     /// \addtogroup graph_concepts
       
    34     /// @{
       
    35 
       
    36 
       
    37     /// Skeleton class which describes an edge with direction in \ref
       
    38     /// UndirGraph "undirected graph".
       
    39     template <typename UndirEdge>
       
    40     class UndirGraphEdge : public UndirEdge {
       
    41     public:
       
    42 
       
    43       /// \e
       
    44       UndirGraphEdge() {}
       
    45 
       
    46       /// \e
       
    47       UndirGraphEdge(const UndirGraphEdge&) {}
       
    48 
       
    49       /// \e
       
    50       UndirGraphEdge(Invalid) {}
       
    51 
       
    52       /// \brief Constructs a directed version of an undirected edge
       
    53       ///
       
    54       /// \param forward If \c true the direction of the contructed edge
       
    55       /// is the same as the inherent direction of the \c undir_edge; if
       
    56       /// \c false --- the opposite.
       
    57       UndirGraphEdge(UndirEdge undir_edge, bool forward) {
       
    58 	ignore_unused_variable_warning(undir_edge);
       
    59 	ignore_unused_variable_warning(forward);
       
    60       }
       
    61 
       
    62       /// \e
       
    63       UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
       
    64 
       
    65       /// \e
       
    66       bool operator==(UndirGraphEdge) const { return true; }
       
    67       /// \e
       
    68       bool operator!=(UndirGraphEdge) const { return false; }
       
    69 
       
    70       /// \e
       
    71       bool operator<(UndirGraphEdge) const { return false; }
       
    72 
       
    73       template <typename Edge>
       
    74       struct Constraints {
       
    75 	void constraints() {
       
    76 	  /// \bug This should be is_base_and_derived ...
       
    77 	  UndirEdge ue = e;
       
    78 	  ue = e;
       
    79 	  Edge forward(ue, true);
       
    80 	  Edge backward(ue, false);
       
    81 
       
    82 	  ignore_unused_variable_warning(forward);
       
    83 	  ignore_unused_variable_warning(backward);
       
    84 	}
       
    85 	Edge e;
       
    86       };
       
    87     };
       
    88     
    34 
    89 
    35     struct BaseIterableUndirGraphConcept {
    90     struct BaseIterableUndirGraphConcept {
    36 
    91 
    37       template <typename Graph>
    92       template <typename Graph>
    38       struct Constraints {
    93       struct Constraints {
    41 	typedef typename Graph::Edge Edge;
    96 	typedef typename Graph::Edge Edge;
    42 	typedef typename Graph::Node Node;
    97 	typedef typename Graph::Node Node;
    43 
    98 
    44 	void constraints() {
    99 	void constraints() {
    45 	  checkConcept<BaseIterableGraphComponent, Graph>();
   100 	  checkConcept<BaseIterableGraphComponent, Graph>();
    46 	  checkConcept<GraphItem<'u'>, UndirEdge >();
   101 	  checkConcept<GraphItem<>, UndirEdge>();
    47 
   102 	  checkConcept<UndirGraphEdge<UndirEdge>, Edge>();
    48 	  /// \bug this should be base_and_derived:
   103 
    49 	  UndirEdge ue = e;
   104 	  graph.first(ue);
    50 	  ue = e;
   105 	  graph.next(ue);
    51 
   106 
       
   107 	  const_constraints();
       
   108 	}
       
   109 	void const_constraints() {
    52 	  Node n;
   110 	  Node n;
    53 	  n = graph.target(ue);
   111 	  n = graph.target(ue);
    54 	  n = graph.source(ue);
   112 	  n = graph.source(ue);
    55 
   113 	  n = graph.oppositeNode(n0, ue);
    56 	  graph.first(ue);
   114 
    57 	  graph.next(ue);
   115 	  bool b;
    58 	}
   116 	  b = graph.forward(e);
    59 	const Graph &graph;
   117 	  ignore_unused_variable_warning(b);
       
   118 	}
       
   119 
       
   120 	Graph graph;
    60 	Edge e;
   121 	Edge e;
       
   122 	Node n0;
       
   123 	UndirEdge ue;
    61       };
   124       };
    62 
   125 
    63     };
   126     };
    64 
   127 
    65 
   128 
    74 
   137 
    75 	  checkConcept<IterableGraphComponent, Graph> ();
   138 	  checkConcept<IterableGraphComponent, Graph> ();
    76 
   139 
    77 	  typedef typename Graph::UndirEdge UndirEdge;
   140 	  typedef typename Graph::UndirEdge UndirEdge;
    78 	  typedef typename Graph::UndirEdgeIt UndirEdgeIt;
   141 	  typedef typename Graph::UndirEdgeIt UndirEdgeIt;
    79 	  typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
   142 	  typedef typename Graph::IncEdgeIt IncEdgeIt;
    80 
   143 
    81 	  checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
   144 	  checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
    82 	  checkConcept<GraphIncIterator<Graph, UndirEdge>, UndirIncEdgeIt>();
   145 	  checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
    83 	}
   146 	}
    84       };
   147       };
    85 
   148 
    86     };
   149     };
    87 
   150 
   143 	typename Graph::UndirEdge e;
   206 	typename Graph::UndirEdge e;
   144       };
   207       };
   145 
   208 
   146     };
   209     };
   147 
   210 
       
   211     /// Class describing the concept of Undirected Graphs.
       
   212 
       
   213     /// This class describes the common interface of all Undirected
       
   214     /// Graphs.
       
   215     ///
       
   216     /// As all concept describing classes it provides only interface
       
   217     /// without any sensible implementation. So any algorithm for
       
   218     /// undirected graph should compile with this class, but it will not
       
   219     /// run properly, of couse.
       
   220     ///
       
   221     /// In LEMON undirected graphs also fulfill the concept of directed
       
   222     /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
       
   223     /// explanation of this and more see also the page \ref undir_graphs,
       
   224     /// a tutorial about undirected graphs.
       
   225 
   148     class UndirGraph {
   226     class UndirGraph {
   149     public:
   227     public:
       
   228 
       
   229       /// Type describing a node in the graph
       
   230       typedef GraphNode Node;
       
   231 
       
   232       /// Type describing an undirected edge
       
   233       typedef GraphItem<'u'> UndirEdge;
       
   234 
       
   235       /// Type describing an UndirEdge with direction
       
   236 #ifndef DOXYGEN
       
   237       typedef UndirGraphEdge<UndirEdge> Edge;
       
   238 #else
       
   239       typedef UndirGraphEdge Edge;
       
   240 #endif
       
   241 
       
   242       /// Iterator type which iterates over all nodes
       
   243 #ifndef DOXYGEN
       
   244       typedef GraphIterator<UndirGraph, Node> NodeIt;
       
   245 #else
       
   246       typedef GraphIterator NodeIt;
       
   247 #endif
       
   248 
       
   249       /// Iterator type which iterates over all undirected edges
       
   250 #ifndef DOXYGEN
       
   251       typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
       
   252 #else
       
   253       typedef GraphIterator UndirEdgeIt;
       
   254 #endif
       
   255 
       
   256       /// Iterator type which iterates over all directed edges.
       
   257 
       
   258       /// Iterator type which iterates over all edges (each undirected
       
   259       /// edge occurs twice with both directions.
       
   260 #ifndef DOXYGEN
       
   261       typedef GraphIterator<UndirGraph, Edge> EdgeIt;
       
   262 #else
       
   263       typedef GraphIterator EdgeIt;
       
   264 #endif
       
   265 
       
   266 
       
   267       /// Iterator of undirected edges incident to a node
       
   268 #ifndef DOXYGEN
       
   269       typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
       
   270 #else
       
   271       typedef GraphIncIterator IncEdgeIt;
       
   272 #endif
       
   273 
       
   274       /// Iterator of edges incoming to a node
       
   275 #ifndef DOXYGEN
       
   276       typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
       
   277 #else
       
   278       typedef GraphIncIterator InEdgeIt;
       
   279 #endif
       
   280 
       
   281       /// Iterator of edges outgoing from a node
       
   282 #ifndef DOXYGEN
       
   283       typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
       
   284 #else
       
   285       typedef GraphIncIterator OutEdgeIt;
       
   286 #endif
       
   287 
       
   288       /// NodeMap template
       
   289 #ifdef DOXYGEN
       
   290       typedef GraphMap NodeMap<T>;
       
   291 #endif
       
   292 
       
   293       /// UndirEdgeMap template
       
   294 #ifdef DOXYGEN
       
   295       typedef GraphMap UndirEdgeMap<T>;
       
   296 #endif
       
   297 
       
   298       /// EdgeMap template
       
   299 #ifdef DOXYGEN
       
   300       typedef GraphMap EdgeMap<T>;
       
   301 #endif
       
   302 
       
   303       template <typename T>
       
   304       class NodeMap : public GraphMap<UndirGraph, Node, T> {
       
   305 	typedef GraphMap<UndirGraph, Node, T> Parent;
       
   306       public:
       
   307 
       
   308 	explicit NodeMap(const UndirGraph &g) : Parent(g) {}
       
   309 	NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
       
   310       };
       
   311 
       
   312       template <typename T>
       
   313       class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
       
   314 	typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
       
   315       public:
       
   316 
       
   317 	explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
       
   318 	UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
       
   319       };
       
   320 
       
   321       template <typename T>
       
   322       class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
       
   323 	typedef GraphMap<UndirGraph, Edge, T> Parent;
       
   324       public:
       
   325 
       
   326 	explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
       
   327 	EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
       
   328       };
       
   329 
       
   330       /// Is the Edge oriented "forward"?
       
   331 
       
   332       /// Returns whether the given directed edge is same orientation as
       
   333       /// the corresponding undirected edge.
       
   334       ///
       
   335       /// \todo "What does the direction of an undirected edge mean?"
       
   336       bool forward(Edge) const { return true; }
       
   337 
       
   338       /// Opposite node on an edge
       
   339 
       
   340       /// \return the opposite of the given Node on the given Edge
       
   341       ///
       
   342       /// \todo What should we do if given Node and Edge are not incident?
       
   343       Node oppositeNode(Node, UndirEdge) const { return INVALID; }
       
   344 
       
   345       /// First node of the undirected edge.
       
   346 
       
   347       /// \return the first node of the given UndirEdge.
       
   348       ///
       
   349       /// Naturally undirectected edges don't have direction and thus
       
   350       /// don't have source and target node. But we use these two methods
       
   351       /// to query the two endnodes of the edge. The direction of the edge
       
   352       /// which arises this way is called the inherent direction of the
       
   353       /// undirected edge, and is used to define the "forward" direction
       
   354       /// of the directed versions of the edges.
       
   355       /// \sa forward
       
   356       Node source(UndirEdge) const { return INVALID; }
       
   357 
       
   358       /// Second node of the undirected edge.
       
   359       Node target(UndirEdge) const { return INVALID; }
       
   360 
       
   361       /// Source node of the directed edge.
       
   362       Node source(Edge) const { return INVALID; }
       
   363 
       
   364       /// Target node of the directed edge.
       
   365       Node target(Edge) const { return INVALID; }
       
   366 
       
   367       /// First node of the graph
       
   368 
       
   369       /// \note This method is part of so called \ref
       
   370       /// developpers_interface "Developpers' interface", so it shouldn't
       
   371       /// be used in an end-user program.
       
   372       void first(Node&) const {}
       
   373       /// Next node of the graph
       
   374 
       
   375       /// \note This method is part of so called \ref
       
   376       /// developpers_interface "Developpers' interface", so it shouldn't
       
   377       /// be used in an end-user program.
       
   378       void next(Node&) const {}
       
   379 
       
   380       /// First undirected edge of the graph
       
   381 
       
   382       /// \note This method is part of so called \ref
       
   383       /// developpers_interface "Developpers' interface", so it shouldn't
       
   384       /// be used in an end-user program.
       
   385       void first(UndirEdge&) const {}
       
   386       /// Next undirected edge of the graph
       
   387 
       
   388       /// \note This method is part of so called \ref
       
   389       /// developpers_interface "Developpers' interface", so it shouldn't
       
   390       /// be used in an end-user program.
       
   391       void next(UndirEdge&) const {}
       
   392 
       
   393       /// First directed edge of the graph
       
   394 
       
   395       /// \note This method is part of so called \ref
       
   396       /// developpers_interface "Developpers' interface", so it shouldn't
       
   397       /// be used in an end-user program.
       
   398       void first(Edge&) const {}
       
   399       /// Next directed edge of the graph
       
   400 
       
   401       /// \note This method is part of so called \ref
       
   402       /// developpers_interface "Developpers' interface", so it shouldn't
       
   403       /// be used in an end-user program.
       
   404       void next(Edge&) const {}
       
   405 
       
   406       /// First outgoing edge from a given node
       
   407 
       
   408       /// \note This method is part of so called \ref
       
   409       /// developpers_interface "Developpers' interface", so it shouldn't
       
   410       /// be used in an end-user program.
       
   411       void firstOut(Edge&, Node) const {}
       
   412       /// Next outgoing edge to a node
       
   413 
       
   414       /// \note This method is part of so called \ref
       
   415       /// developpers_interface "Developpers' interface", so it shouldn't
       
   416       /// be used in an end-user program.
       
   417       void nextOut(Edge&) const {}
       
   418 
       
   419       /// First incoming edge to a given node
       
   420 
       
   421       /// \note This method is part of so called \ref
       
   422       /// developpers_interface "Developpers' interface", so it shouldn't
       
   423       /// be used in an end-user program.
       
   424       void firstIn(Edge&, Node) const {}
       
   425       /// Next incoming edge to a node
       
   426 
       
   427       /// \note This method is part of so called \ref
       
   428       /// developpers_interface "Developpers' interface", so it shouldn't
       
   429       /// be used in an end-user program.
       
   430       void nextIn(Edge&) const {}
       
   431 
   150 
   432 
   151       template <typename Graph>
   433       template <typename Graph>
   152       struct Constraints {
   434       struct Constraints {
   153 	void constraints() {
   435 	void constraints() {
   154 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();
   436 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();
   188 	}
   470 	}
   189       };
   471       };
   190 
   472 
   191     };
   473     };
   192 
   474 
       
   475     /// @}
       
   476 
   193   }
   477   }
   194 
   478 
   195 }
   479 }
   196 
   480 
   197 #endif
   481 #endif