/* -*- C++ -*- * * src/lemon/concept/undir_graph_component.h - Part of LEMON, a generic * C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi * Kutatocsoport (Egervary Combinatorial Optimization Research Group, * 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 namespace lemon { namespace concept { /// \addtogroup graph_concepts /// @{ /// 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 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; }; }; /// 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: /// Type describing a node in the graph typedef GraphNode Node; /// Type describing an undirected edge typedef GraphItem<'u'> UndirEdge; /// Type describing an UndirEdge with direction #ifndef DOXYGEN typedef UndirGraphEdge Edge; #else typedef UndirGraphEdge Edge; #endif /// Iterator type which iterates over all nodes #ifndef DOXYGEN typedef GraphIterator NodeIt; #else typedef GraphIterator NodeIt; #endif /// Iterator type which iterates over all undirected edges #ifndef DOXYGEN typedef GraphIterator UndirEdgeIt; #else typedef GraphIterator UndirEdgeIt; #endif /// Iterator type which iterates over all directed edges. /// Iterator type which iterates over all edges (each undirected /// edge occurs twice with both directions. #ifndef DOXYGEN typedef GraphIterator EdgeIt; #else typedef GraphIterator EdgeIt; #endif /// Iterator of undirected edges incident to a node #ifndef DOXYGEN typedef GraphIncIterator IncEdgeIt; #else typedef GraphIncIterator IncEdgeIt; #endif /// Iterator of edges incoming to a node #ifndef DOXYGEN typedef GraphIncIterator InEdgeIt; #else typedef GraphIncIterator InEdgeIt; #endif /// Iterator of edges outgoing from a node #ifndef DOXYGEN typedef GraphIncIterator OutEdgeIt; #else typedef GraphIncIterator OutEdgeIt; #endif /// NodeMap template #ifdef DOXYGEN typedef GraphMap NodeMap; #endif /// UndirEdgeMap template #ifdef DOXYGEN typedef GraphMap UndirEdgeMap; #endif /// EdgeMap template #ifdef DOXYGEN typedef GraphMap EdgeMap; #endif template class NodeMap : public GraphMap { typedef GraphMap Parent; public: explicit NodeMap(const UndirGraph &g) : Parent(g) {} NodeMap(const UndirGraph &g, T t) : Parent(g, t) {} }; template class UndirEdgeMap : public GraphMap { typedef GraphMap Parent; public: explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {} UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} }; template class EdgeMap : public GraphMap { typedef GraphMap Parent; public: explicit EdgeMap(const UndirGraph &g) : Parent(g) {} EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} }; /// 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 e) const { return INVALID; } /// Running node of the iterator /// /// Returns the running node of the iterator Node runningNode(IncEdgeIt e) 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