diff -r d8475431bbbb -r 8e85e6bbefdf src/lemon/concept/undir_graph.h --- a/src/lemon/concept/undir_graph.h Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,531 +0,0 @@ -/* -*- 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 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