lemon-main: comparison lemon/concepts/graph

equal deleted inserted replaced

-:d20759e5d736
+:1de95988bd99
 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
-* Copyright (C) 2003-2009
+* Copyright (C) 2003-2010
 * 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
 /// This class describes the concept of \c Node, \c Arc and \c Edge
 /// subtypes of digraph and graph types.
 ///
 /// \note This class is a template class so that we can use it to
 /// create graph skeleton classes. The reason for this is that \c Node
 /// and \c Arc (or \c Edge) types should \e not derive from the same
 /// base class. For \c Node you should instantiate it with character
 /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
 #ifndef DOXYGEN
 template <char sel = '0'>
 #endif
 bool operator!=(const GraphItem&) const { return false; }
 /// \brief Ordering operator.
 ///
 /// This operator defines an ordering of the items.
 /// It makes possible to use graph item types as key types in
 /// associative containers (e.g. \c std::map).
 ///
 /// \note This operator only has to define some strict ordering of
 /// the items; this order has nothing to do with the iteration
 /// ordering of the items.
 /// \brief Base skeleton class for directed graphs.
 ///
 /// This class describes the base interface of directed graph types.
 /// All digraph %concepts have to conform to this class.
 /// It just provides types for nodes and arcs and functions
 /// to get the source and the target nodes of arcs.
 class BaseDigraphComponent {
 public:
 typedef BaseDigraphComponent Digraph;
 };
 };
 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
 ///
 /// This class describes the concept of \c NodeIt, \c ArcIt and
 /// \c EdgeIt subtypes of digraph and graph types.
 template <typename GR, typename Item>
 class GraphItemIt : public Item {
 public:
 /// \brief Default constructor.
 /// \brief Increment the iterator.
 ///
 /// This operator increments the iterator, i.e. assigns it to the
 /// next item.
 GraphItemIt& operator++() { return *this; }
 /// \brief Equality operator
 ///
 /// Equality operator.
 /// Two iterators are equal if and only if they point to the
 /// same object or both are invalid.
 }
 const GR& g;
 };
 };
 /// \brief Concept class for \c InArcIt, \c OutArcIt and
 /// \c IncEdgeIt types.
 ///
 /// This class describes the concept of \c InArcIt, \c OutArcIt
 /// and \c IncEdgeIt subtypes of digraph and graph types.
 ///
 /// \note Since these iterator classes do not inherit from the same
 /// base class, there is an additional template parameter (selector)
 /// \c sel. For \c InArcIt you should instantiate it with character
 /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
 template <typename GR,
 typename Item = typename GR::Arc,
 typename Base = typename GR::Node,
 char sel = '0'>
 /// \brief Copy constructor.
 ///
 /// Copy constructor.
 GraphIncIt(const GraphIncIt& it) : Item(it) {}
 /// \brief Constructor that sets the iterator to the first
 /// incoming or outgoing arc.
 ///
 /// Constructor that sets the iterator to the first arc
 /// incoming to or outgoing from the given node.
 explicit GraphIncIt(const GR&, const Base&) {}
 /// \brief Constructor for conversion from \c INVALID.
 ///
 /// This function gives back the next edge in the iteration order.
 void next(Edge&) const {}
 /// \brief Return the first edge incident to the given node.
 ///
 /// This function gives back the first edge incident to the given
 /// node. The bool parameter gives back the direction for which the
 /// source node of the directed arc representing the edge is the
 /// given node.
 void firstInc(Edge&, bool&, const Node&) const {}
 /// \brief Gives back the next of the edges from the
 /// given node.
 ///
 /// This function gives back the next edge incident to the given
 /// node. The bool parameter should be used as \c firstInc() use it.
 void nextInc(Edge&, bool&) const {}
 using IterableDigraphComponent<Base>::baseNode;
 using IterableDigraphComponent<Base>::runningNode;
 };
 /// \brief Concept class for standard graph maps.
 ///
 /// This class describes the concept of standard graph maps, i.e.
 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
 /// graph types, which can be used for associating data to graph items.
 /// The standard graph maps must conform to the ReferenceMap concept.
 template <typename GR, typename K, typename V>
 class GraphMap : public ReferenceMap<K, V, V&, const V&> {
 typedef ReferenceMap<K, V, V&, const V&> Parent;
 void constraints() {
 checkConcept
 <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
 _Map m1(g);
 _Map m2(g,t);
 // Copy constructor
 // _Map m3(m);
 // Assignment operator
 // ReadMap<Key, Value> cmap;
 };
 /// \brief Skeleton class for mappable directed graphs.
 ///
 /// This class describes the interface of mappable directed graphs.
 /// It extends \ref BaseDigraphComponent with the standard digraph
 /// map classes, namely \c NodeMap and \c ArcMap.
 /// This concept is part of the Digraph concept.
 template <typename BAS = BaseDigraphComponent>
 class MappableDigraphComponent : public BAS  {
 public:
 };
 /// \brief Skeleton class for mappable undirected graphs.
 ///
 /// This class describes the interface of mappable undirected graphs.
 /// It extends \ref MappableDigraphComponent with the standard graph
 /// map class for edges (\c EdgeMap).
 /// This concept is part of the Graph concept.
 template <typename BAS = BaseGraphComponent>
 class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
 public:
 };
 /// \brief Skeleton class for extendable directed graphs.
 ///
 /// This class describes the interface of extendable directed graphs.
 /// It extends \ref BaseDigraphComponent with functions for adding
 /// nodes and arcs to the digraph.
 /// This concept requires \ref AlterableDigraphComponent.
 template <typename BAS = BaseDigraphComponent>
 class ExtendableDigraphComponent : public BAS {
 public:
 };
 /// \brief Skeleton class for extendable undirected graphs.
 ///
 /// This class describes the interface of extendable undirected graphs.
 /// It extends \ref BaseGraphComponent with functions for adding
 /// nodes and edges to the graph.
 /// This concept requires \ref AlterableGraphComponent.
 template <typename BAS = BaseGraphComponent>
 class ExtendableGraphComponent : public BAS {
 public:
 };
 /// \brief Skeleton class for erasable directed graphs.
 ///
 /// This class describes the interface of erasable directed graphs.
 /// It extends \ref BaseDigraphComponent with functions for removing
 /// nodes and arcs from the digraph.
 /// This concept requires \ref AlterableDigraphComponent.
 template <typename BAS = BaseDigraphComponent>
 class ErasableDigraphComponent : public BAS {
 public:
 typedef typename Base::Node Node;
 typedef typename Base::Arc Arc;
 /// \brief Erase a node from the digraph.
 ///
 /// This function erases the given node from the digraph and all arcs
 /// connected to the node.
 void erase(const Node&) {}
 /// \brief Erase an arc from the digraph.
 ///
 };
 /// \brief Skeleton class for erasable undirected graphs.
 ///
 /// This class describes the interface of erasable undirected graphs.
 /// It extends \ref BaseGraphComponent with functions for removing
 /// nodes and edges from the graph.
 /// This concept requires \ref AlterableGraphComponent.
 template <typename BAS = BaseGraphComponent>
 class ErasableGraphComponent : public BAS {
 public:

changeset 899	7d166b8b8018
parent 786	e20173729589
child 976	426a704d7483
child 998	7fdaa05a69a1