/* -*- C++ -*- * * lemon/concept/undir_graph_component.h - Part of LEMON, a generic * C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi * Kutatocsoport (Egervary Research Group on Combinatorial Optimization, * EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ ///\ingroup graph_concepts ///\file ///\brief Undirected graphs and components of. #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H #define LEMON_CONCEPT_UNDIR_GRAPH_H #include #include #include namespace lemon { namespace concept { /// Skeleton class which describes an edge with direction in \ref /// UndirGraph "undirected graph". template class UndirGraphEdge : public UndirGraph::UndirEdge { typedef typename UndirGraph::UndirEdge UndirEdge; typedef typename UndirGraph::Node Node; public: /// \e UndirGraphEdge() {} /// \e UndirGraphEdge(const UndirGraphEdge& e) : UndirGraph::UndirEdge(e) {} /// \e UndirGraphEdge(Invalid) {} /// \brief Directed edge from undirected edge and a source node. /// /// Constructs a directed edge from undirected edge and a source node. /// /// \note You have to specify the graph for this constructor. UndirGraphEdge(const UndirGraph &g, UndirEdge undir_edge, Node n) { ignore_unused_variable_warning(undir_edge); ignore_unused_variable_warning(g); ignore_unused_variable_warning(n); } /// \e UndirGraphEdge& operator=(UndirGraphEdge) { return *this; } /// \e bool operator==(UndirGraphEdge) const { return true; } /// \e bool operator!=(UndirGraphEdge) const { return false; } /// \e bool operator<(UndirGraphEdge) const { return false; } template struct Constraints { void constraints() { const_constraints(); } void const_constraints() const { /// \bug This should be is_base_and_derived ... UndirEdge ue = e; ue = e; Edge e_with_source(graph,ue,n); ignore_unused_variable_warning(e_with_source); } Edge e; UndirEdge ue; UndirGraph graph; Node n; }; }; struct BaseIterableUndirGraphConcept { template struct Constraints { typedef typename Graph::UndirEdge UndirEdge; typedef typename Graph::Edge Edge; typedef typename Graph::Node Node; void constraints() { checkConcept(); checkConcept, UndirEdge>(); //checkConcept, Edge>(); graph.first(ue); graph.next(ue); const_constraints(); } void const_constraints() { Node n; n = graph.target(ue); n = graph.source(ue); n = graph.oppositeNode(n0, ue); bool b; b = graph.forward(e); ignore_unused_variable_warning(b); } Graph graph; Edge e; Node n0; UndirEdge ue; }; }; struct IterableUndirGraphConcept { template struct Constraints { void constraints() { /// \todo we don't need the iterable component to be base iterable /// Don't we really??? //checkConcept< BaseIterableUndirGraphConcept, Graph > (); checkConcept (); typedef typename Graph::UndirEdge UndirEdge; typedef typename Graph::UndirEdgeIt UndirEdgeIt; typedef typename Graph::IncEdgeIt IncEdgeIt; checkConcept, UndirEdgeIt>(); checkConcept, IncEdgeIt>(); } }; }; struct MappableUndirGraphConcept { template struct Constraints { struct Dummy { int value; Dummy() : value(0) {} Dummy(int _v) : value(_v) {} }; void constraints() { checkConcept(); typedef typename Graph::template UndirEdgeMap IntMap; checkConcept, IntMap >(); typedef typename Graph::template UndirEdgeMap BoolMap; checkConcept, BoolMap >(); typedef typename Graph::template UndirEdgeMap DummyMap; checkConcept, DummyMap >(); } }; }; struct ExtendableUndirGraphConcept { template struct Constraints { void constraints() { node_a = graph.addNode(); uedge = graph.addEdge(node_a, node_b); } typename Graph::Node node_a, node_b; typename Graph::UndirEdge uedge; Graph graph; }; }; struct ErasableUndirGraphConcept { template struct Constraints { void constraints() { graph.erase(n); graph.erase(e); } Graph graph; typename Graph::Node n; typename Graph::UndirEdge e; }; }; /// \addtogroup graph_concepts /// @{ /// Class describing the concept of Undirected Graphs. /// This class describes the common interface of all Undirected /// Graphs. /// /// As all concept describing classes it provides only interface /// without any sensible implementation. So any algorithm for /// undirected graph should compile with this class, but it will not /// run properly, of couse. /// /// In LEMON undirected graphs also fulfill the concept of directed /// graphs (\ref lemon::concept::Graph "Graph Concept"). For /// explanation of this and more see also the page \ref undir_graphs, /// a tutorial about undirected graphs. class UndirGraph : public StaticGraph { public: ///\e ///\todo undocumented /// typedef True UndirTag; /// The base type of the undirected edge iterators. /// The base type of the undirected edge iterators. /// class UndirEdge { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. UndirEdge() { } /// Copy constructor. /// Copy constructor. /// UndirEdge(const UndirEdge&) { } /// Edge -> UndirEdge conversion /// Edge -> UndirEdge conversion /// UndirEdge(const Edge&) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// UndirEdge(Invalid) { } /// Equality operator /// Two iterators are equal if and only if they point to the /// same object or both are invalid. bool operator==(UndirEdge) const { return true; } /// Inequality operator /// \sa operator==(UndirEdge n) /// bool operator!=(UndirEdge) const { return true; } ///\e ///\todo Do we need this? /// bool operator<(const UndirEdge &that) const { return true; } }; /// This iterator goes through each undirected edge. /// This iterator goes through each undirected edge of a graph. /// Its usage is quite simple, for example you can count the number /// of edges in a graph \c g of type \c Graph as follows: /// \code /// int count=0; /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count; /// \endcode class UndirEdgeIt : public UndirEdge { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. UndirEdgeIt() { } /// Copy constructor. /// Copy constructor. /// UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// UndirEdgeIt(Invalid) { } /// This constructor sets the iterator to the first edge. /// This constructor sets the iterator to the first edge of \c g. UndirEdgeIt(const UndirGraph&) { } /// UndirEdge -> UndirEdgeIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the edge-set, the iteration order is the same. UndirEdgeIt(const UndirGraph&, const UndirEdge&) { } ///Next edge /// Assign the iterator to the next edge. UndirEdgeIt& operator++() { return *this; } }; /// This iterator goes trough the incident undirected edges of a node. /// This iterator goes trough the incident undirected edges /// of a certain node /// of a graph. /// Its usage is quite simple, for example you can compute the /// degree (i.e. count the number /// of incident edges of a node \c n /// in graph \c g of type \c Graph as follows. /// \code /// int count=0; /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; /// \endcode class IncEdgeIt : public UndirEdge { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. IncEdgeIt() { } /// Copy constructor. /// Copy constructor. /// IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// IncEdgeIt(Invalid) { } /// This constructor sets the iterator to first incident edge. /// This constructor set the iterator to the first incident edge of /// the node. IncEdgeIt(const UndirGraph&, const Node&) { } /// UndirEdge -> IncEdgeIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the edge-set, the iteration order is the same. IncEdgeIt(const UndirGraph&, const UndirEdge&) { } /// Next incident edge /// Assign the iterator to the next incident edge /// of the corresponding node. IncEdgeIt& operator++() { return *this; } }; /// Read write map of the undirected edges to type \c T. /// Reference map of the edges to type \c T. /// \sa Reference /// \warning Making maps that can handle bool type (UndirEdgeMap) /// needs some extra attention! template class UndirEdgeMap : public ReadWriteMap { public: ///\e UndirEdgeMap(const UndirGraph&) { } ///\e UndirEdgeMap(const UndirGraph&, T) { } ///Copy constructor UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap(em) { } ///Assignment operator UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; } // \todo fix this concept }; /// Is the Edge oriented "forward"? /// Returns whether the given directed edge is same orientation as /// the corresponding undirected edge. /// /// \todo "What does the direction of an undirected edge mean?" bool forward(Edge) const { return true; } /// Opposite node on an edge /// \return the opposite of the given Node on the given Edge /// /// \todo What should we do if given Node and Edge are not incident? Node oppositeNode(Node, UndirEdge) const { return INVALID; } /// First node of the undirected edge. /// \return the first node of the given UndirEdge. /// /// Naturally undirectected edges don't have direction and thus /// don't have source and target node. But we use these two methods /// to query the two endnodes of the edge. The direction of the edge /// which arises this way is called the inherent direction of the /// undirected edge, and is used to define the "forward" direction /// of the directed versions of the edges. /// \sa forward Node source(UndirEdge) const { return INVALID; } /// Second node of the undirected edge. Node target(UndirEdge) const { return INVALID; } /// Source node of the directed edge. Node source(Edge) const { return INVALID; } /// Target node of the directed edge. Node target(Edge) const { return INVALID; } /// First node of the graph /// \note This method is part of so called \ref /// developpers_interface "Developpers' interface", so it shouldn't /// be used in an end-user program. void first(Node&) const {} /// Next node of the graph /// \note This method is part of so called \ref /// developpers_interface "Developpers' interface", so it shouldn't /// be used in an end-user program. void next(Node&) const {} /// First undirected edge of the graph /// \note This method is part of so called \ref /// developpers_interface "Developpers' interface", so it shouldn't /// be used in an end-user program. void first(UndirEdge&) const {} /// Next undirected edge of the graph /// \note This method is part of so called \ref /// developpers_interface "Developpers' interface", so it shouldn't /// be used in an end-user program. void next(UndirEdge&) const {} /// First directed edge of the graph /// \note This method is part of so called \ref /// developpers_interface "Developpers' interface", so it shouldn't /// be used in an end-user program. void first(Edge&) const {} /// Next directed edge of the graph /// \note This method is part of so called \ref /// developpers_interface "Developpers' interface", so it shouldn't /// be used in an end-user program. void next(Edge&) const {} /// First outgoing edge from a given node /// \note This method is part of so called \ref /// developpers_interface "Developpers' interface", so it shouldn't /// be used in an end-user program. void firstOut(Edge&, Node) const {} /// Next outgoing edge to a node /// \note This method is part of so called \ref /// developpers_interface "Developpers' interface", so it shouldn't /// be used in an end-user program. void nextOut(Edge&) const {} /// First incoming edge to a given node /// \note This method is part of so called \ref /// developpers_interface "Developpers' interface", so it shouldn't /// be used in an end-user program. void firstIn(Edge&, Node) const {} /// Next incoming edge to a node /// \note This method is part of so called \ref /// developpers_interface "Developpers' interface", so it shouldn't /// be used in an end-user program. void nextIn(Edge&) const {} /// Base node of the iterator /// /// Returns the base node (the source in this case) of the iterator Node baseNode(OutEdgeIt e) const { return source(e); } /// Running node of the iterator /// /// Returns the running node (the target in this case) of the /// iterator Node runningNode(OutEdgeIt e) const { return target(e); } /// Base node of the iterator /// /// Returns the base node (the target in this case) of the iterator Node baseNode(InEdgeIt e) const { return target(e); } /// Running node of the iterator /// /// Returns the running node (the source in this case) of the /// iterator Node runningNode(InEdgeIt e) const { return source(e); } /// Base node of the iterator /// /// Returns the base node of the iterator Node baseNode(IncEdgeIt) const { return INVALID; } /// Running node of the iterator /// /// Returns the running node of the iterator Node runningNode(IncEdgeIt) const { return INVALID; } template struct Constraints { void constraints() { checkConcept(); checkConcept(); checkConcept(); } }; }; class ExtendableUndirGraph : public UndirGraph { public: template struct Constraints { void constraints() { checkConcept(); checkConcept(); checkConcept(); checkConcept(); checkConcept(); checkConcept(); } }; }; class ErasableUndirGraph : public ExtendableUndirGraph { public: template struct Constraints { void constraints() { checkConcept(); checkConcept(); } }; }; /// @} } } #endif