diff -r d8475431bbbb -r 8e85e6bbefdf lemon/concept/undir_graph.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/concept/undir_graph.h Mon May 23 04:48:14 2005 +0000 @@ -0,0 +1,531 @@ +/* -*- 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 + +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) : 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; + }; + + }; + + /// 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) 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