lemon/graph_utils.h
changeset 154 f4e4dbc1d467
parent 147 7c39a090cfc3
child 157 2ccc1afc2c52
equal deleted inserted replaced
3:19c58ad68615 4:82636f6c00ff
    40 namespace lemon {
    40 namespace lemon {
    41 
    41 
    42   /// \addtogroup gutils
    42   /// \addtogroup gutils
    43   /// @{
    43   /// @{
    44 
    44 
    45   namespace _graph_utils_bits {
       
    46     template <typename Graph>
       
    47     struct Node { typedef typename Graph::Node type; };
       
    48 
       
    49     template <typename Graph>
       
    50     struct NodeIt { typedef typename Graph::NodeIt type; };
       
    51 
       
    52     template <typename Graph>
       
    53     struct Arc { typedef typename Graph::Arc type; };
       
    54 
       
    55     template <typename Graph>
       
    56     struct ArcIt { typedef typename Graph::ArcIt type; };
       
    57 
       
    58     template <typename Graph>
       
    59     struct Edge { typedef typename Graph::Edge type; };
       
    60 
       
    61     template <typename Graph>
       
    62     struct EdgeIt { typedef typename Graph::EdgeIt type; };
       
    63 
       
    64     template <typename Graph>
       
    65     struct OutArcIt { typedef typename Graph::OutArcIt type; };
       
    66 
       
    67     template <typename Graph>
       
    68     struct InArcIt { typedef typename Graph::InArcIt type; };
       
    69 
       
    70     template <typename Graph>
       
    71     struct IncEdgeIt { typedef typename Graph::IncEdgeIt type; };
       
    72 
       
    73     template <typename Graph>
       
    74     struct BoolNodeMap { 
       
    75       typedef typename Graph::template NodeMap<bool> type; 
       
    76     };
       
    77 
       
    78     template <typename Graph>
       
    79     struct IntNodeMap { 
       
    80       typedef typename Graph::template NodeMap<int> type; 
       
    81     };
       
    82 
       
    83     template <typename Graph>
       
    84     struct DoubleNodeMap { 
       
    85       typedef typename Graph::template NodeMap<double> type; 
       
    86     };
       
    87 
       
    88     template <typename Graph>
       
    89     struct BoolArcMap { 
       
    90       typedef typename Graph::template ArcMap<bool> type; 
       
    91     };
       
    92 
       
    93     template <typename Graph>
       
    94     struct IntArcMap { 
       
    95       typedef typename Graph::template ArcMap<int> type; 
       
    96     };
       
    97 
       
    98     template <typename Graph>
       
    99     struct DoubleArcMap { 
       
   100       typedef typename Graph::template ArcMap<double> type; 
       
   101     };
       
   102 
       
   103     template <typename Graph>
       
   104     struct BoolEdgeMap { 
       
   105       typedef typename Graph::template EdgeMap<bool> type; 
       
   106     };
       
   107 
       
   108     template <typename Graph>
       
   109     struct IntEdgeMap { 
       
   110       typedef typename Graph::template EdgeMap<int> type; 
       
   111     };
       
   112 
       
   113     template <typename Graph>
       
   114     struct DoubleEdgeMap { 
       
   115       typedef typename Graph::template EdgeMap<double> type; 
       
   116     };
       
   117 
       
   118     
       
   119   }
       
   120 
       
   121   ///Creates convenience typedefs for the digraph types and iterators
    45   ///Creates convenience typedefs for the digraph types and iterators
   122 
    46 
   123   ///This \c \#define creates convenience typedefs for the following types
    47   ///This \c \#define creates convenience typedefs for the following types
   124   ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
    48   ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
   125   ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 
    49   ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 
   126   ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. 
    50   ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
       
    51   ///
       
    52   ///\note If the graph type is a dependent type, ie. the graph type depend
       
    53   ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
       
    54   ///macro.
   127 #define DIGRAPH_TYPEDEFS(Digraph)					\
    55 #define DIGRAPH_TYPEDEFS(Digraph)					\
   128   typedef typename ::lemon::_graph_utils_bits::				\
    56   typedef Digraph::Node Node;						\
   129   Node<Digraph>::type Node;						\
    57   typedef Digraph::NodeIt NodeIt;					\
   130   typedef typename ::lemon::_graph_utils_bits::				\
    58   typedef Digraph::Arc Arc;						\
   131   NodeIt<Digraph>::type	NodeIt;						\
    59   typedef Digraph::ArcIt ArcIt;						\
   132   typedef typename ::lemon::_graph_utils_bits::				\
    60   typedef Digraph::InArcIt InArcIt;					\
   133   Arc<Digraph>::type Arc;						\
    61   typedef Digraph::OutArcIt OutArcIt;					\
   134   typedef typename ::lemon::_graph_utils_bits::				\
    62   typedef Digraph::NodeMap<bool> BoolNodeMap;				\
   135   ArcIt<Digraph>::type ArcIt;						\
    63   typedef Digraph::NodeMap<int> IntNodeMap;				\
   136   typedef typename ::lemon::_graph_utils_bits::				\
    64   typedef Digraph::NodeMap<double> DoubleNodeMap;			\
   137   OutArcIt<Digraph>::type OutArcIt;					\
    65   typedef Digraph::ArcMap<bool> BoolArcMap;				\
   138   typedef typename ::lemon::_graph_utils_bits::				\
    66   typedef Digraph::ArcMap<int> IntArcMap;				\
   139   InArcIt<Digraph>::type InArcIt;					\
    67   typedef Digraph::ArcMap<double> DoubleArcMap
   140   typedef typename ::lemon::_graph_utils_bits::				\
    68 
   141   BoolNodeMap<Digraph>::type BoolNodeMap;				\
    69   ///Creates convenience typedefs for the digraph types and iterators
   142   typedef typename ::lemon::_graph_utils_bits::				\
    70 
   143   IntNodeMap<Digraph>::type IntNodeMap;					\
    71   ///\see DIGRAPH_TYPEDEFS
   144   typedef typename ::lemon::_graph_utils_bits::				\
    72   ///
   145   DoubleNodeMap<Digraph>::type DoubleNodeMap;				\
    73   ///\note Use this macro, if the graph type is a dependent type,
   146   typedef typename ::lemon::_graph_utils_bits::				\
    74   ///ie. the graph type depend on a template parameter.
   147   BoolArcMap<Digraph>::type BoolArcMap;					\
    75 #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)				\
   148   typedef typename ::lemon::_graph_utils_bits::				\
    76   typedef typename Digraph::Node Node;					\
   149   IntArcMap<Digraph>::type IntArcMap;					\
    77   typedef typename Digraph::NodeIt NodeIt;				\
   150   typedef typename ::lemon::_graph_utils_bits::				\
    78   typedef typename Digraph::Arc Arc;					\
   151   DoubleArcMap<Digraph>::type DoubleArcMap
    79   typedef typename Digraph::ArcIt ArcIt;				\
   152 
    80   typedef typename Digraph::InArcIt InArcIt;				\
   153 
    81   typedef typename Digraph::OutArcIt OutArcIt;				\
       
    82   typedef typename Digraph::template NodeMap<bool> BoolNodeMap;		\
       
    83   typedef typename Digraph::template NodeMap<int> IntNodeMap;		\
       
    84   typedef typename Digraph::template NodeMap<double> DoubleNodeMap;	\
       
    85   typedef typename Digraph::template ArcMap<bool> BoolArcMap;		\
       
    86   typedef typename Digraph::template ArcMap<int> IntArcMap;		\
       
    87   typedef typename Digraph::template ArcMap<double> DoubleArcMap
       
    88   
   154   ///Creates convenience typedefs for the graph types and iterators
    89   ///Creates convenience typedefs for the graph types and iterators
   155 
    90 
   156   ///This \c \#define creates the same convenience typedefs as defined
    91   ///This \c \#define creates the same convenience typedefs as defined
   157   ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
    92   ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
   158   ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
    93   ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
   159   ///\c DoubleEdgeMap.
    94   ///\c DoubleEdgeMap.
       
    95   ///
       
    96   ///\note If the graph type is a dependent type, ie. the graph type depend
       
    97   ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
       
    98   ///macro.
   160 #define GRAPH_TYPEDEFS(Graph)						\
    99 #define GRAPH_TYPEDEFS(Graph)						\
   161   DIGRAPH_TYPEDEFS(Graph);						\
   100   DIGRAPH_TYPEDEFS(Graph);						\
   162   typedef typename ::lemon::_graph_utils_bits::				\
   101   typedef Graph::Edge Edge;						\
   163   Edge<Graph>::type Edge;						\
   102   typedef Graph::EdgeIt EdgeIt;						\
   164   typedef typename ::lemon::_graph_utils_bits::				\
   103   typedef Graph::IncEdgeIt IncEdgeIt;					\
   165   EdgeIt<Graph>::type EdgeIt;						\
   104   typedef Graph::EdgeMap<bool> BoolEdgeMap;				\
   166   typedef typename ::lemon::_graph_utils_bits::				\
   105   typedef Graph::EdgeMap<int> IntEdgeMap;				\
   167   IncEdgeIt<Graph>::type IncEdgeIt;					\
   106   typedef Graph::EdgeMap<double> DoubleEdgeMap
   168   typedef typename ::lemon::_graph_utils_bits::				\
   107 
   169   BoolEdgeMap<Graph>::type BoolEdgeMap;					\
   108   ///Creates convenience typedefs for the graph types and iterators
   170   typedef typename ::lemon::_graph_utils_bits::				\
   109 
   171   IntEdgeMap<Graph>::type IntEdgeMap;					\
   110   ///\see GRAPH_TYPEDEFS
   172   typedef typename ::lemon::_graph_utils_bits::				\
   111   ///
   173   DoubleEdgeMap<Graph>::type DoubleEdgeMap
   112   ///\note Use this macro, if the graph type is a dependent type,
   174 
   113   ///ie. the graph type depend on a template parameter.
       
   114 #define TEMPLATE_GRAPH_TYPEDEFS(Graph)					\
       
   115   TEMPLATE_DIGRAPH_TYPEDEFS(Graph);					\
       
   116   typedef typename Graph::Edge Edge;					\
       
   117   typedef typename Graph::EdgeIt EdgeIt;				\
       
   118   typedef typename Graph::IncEdgeIt IncEdgeIt;				\
       
   119   typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;		\
       
   120   typedef typename Graph::template EdgeMap<int> IntEdgeMap;		\
       
   121   typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
   175 
   122 
   176   /// \brief Function to count the items in the graph.
   123   /// \brief Function to count the items in the graph.
   177   ///
   124   ///
   178   /// This function counts the items (nodes, arcs etc) in the graph.
   125   /// This function counts the items (nodes, arcs etc) in the graph.
   179   /// The complexity of the function is O(n) because
   126   /// The complexity of the function is O(n) because
  2159   {
  2106   {
  2160   public:
  2107   public:
  2161     typedef typename ItemSetTraits<G, typename G::Arc>
  2108     typedef typename ItemSetTraits<G, typename G::Arc>
  2162     ::ItemNotifier::ObserverBase Parent;
  2109     ::ItemNotifier::ObserverBase Parent;
  2163 
  2110 
  2164     DIGRAPH_TYPEDEFS(G);
  2111     TEMPLATE_DIGRAPH_TYPEDEFS(G);
  2165     typedef G Digraph;
  2112     typedef G Digraph;
  2166 
  2113 
  2167   protected:
  2114   protected:
  2168 
  2115 
  2169     class AutoNodeMap : public DefaultMap<G, Node, Arc> {
  2116     class AutoNodeMap : public DefaultMap<G, Node, Arc> {
  2596   ///\sa AllArcLookUp  
  2543   ///\sa AllArcLookUp  
  2597   template<class G>
  2544   template<class G>
  2598   class ArcLookUp 
  2545   class ArcLookUp 
  2599   {
  2546   {
  2600   public:
  2547   public:
  2601     DIGRAPH_TYPEDEFS(G);
  2548     TEMPLATE_DIGRAPH_TYPEDEFS(G);
  2602     typedef G Digraph;
  2549     typedef G Digraph;
  2603 
  2550 
  2604   protected:
  2551   protected:
  2605     const Digraph &_g;
  2552     const Digraph &_g;
  2606     typename Digraph::template NodeMap<Arc> _head;
  2553     typename Digraph::template NodeMap<Arc> _head;
  2713     using ArcLookUp<G>::_g;
  2660     using ArcLookUp<G>::_g;
  2714     using ArcLookUp<G>::_right;
  2661     using ArcLookUp<G>::_right;
  2715     using ArcLookUp<G>::_left;
  2662     using ArcLookUp<G>::_left;
  2716     using ArcLookUp<G>::_head;
  2663     using ArcLookUp<G>::_head;
  2717 
  2664 
  2718     DIGRAPH_TYPEDEFS(G);
  2665     TEMPLATE_DIGRAPH_TYPEDEFS(G);
  2719     typedef G Digraph;
  2666     typedef G Digraph;
  2720     
  2667     
  2721     typename Digraph::template ArcMap<Arc> _next;
  2668     typename Digraph::template ArcMap<Arc> _next;
  2722     
  2669     
  2723     Arc refreshNext(Arc head,Arc next=INVALID)
  2670     Arc refreshNext(Arc head,Arc next=INVALID)