lemon/graph_utils.h
changeset 145 95d905b6e33d
parent 139 701c529ba737
child 147 7c39a090cfc3
equal deleted inserted replaced
1:92f30b941bb1 2:db50e28bffed
    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 
    45   ///Creates convenience typedefs for the digraph types and iterators
   121   ///Creates convenience typedefs for the digraph types and iterators
    46 
   122 
    47   ///This \c \#define creates convenience typedefs for the following types
   123   ///This \c \#define creates convenience typedefs for the following types
    48   ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
   124   ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
    49   ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 
   125   ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 
    50   ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. 
   126   ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. 
    51 #define DIGRAPH_TYPEDEFS(Digraph)					\
   127 #define DIGRAPH_TYPEDEFS(Digraph)					\
    52   typedef Digraph::Node Node;						\
   128   typedef typename ::lemon::_graph_utils_bits::				\
    53   typedef Digraph::NodeIt NodeIt;					\
   129   Node<Digraph>::type Node;						\
    54   typedef Digraph::Arc Arc;						\
   130   typedef typename ::lemon::_graph_utils_bits::				\
    55   typedef Digraph::ArcIt ArcIt;						\
   131   NodeIt<Digraph>::type	NodeIt;						\
    56   typedef Digraph::InArcIt InArcIt;					\
   132   typedef typename ::lemon::_graph_utils_bits::				\
    57   typedef Digraph::OutArcIt OutArcIt
   133   Arc<Digraph>::type Arc;						\
       
   134   typedef typename ::lemon::_graph_utils_bits::				\
       
   135   ArcIt<Digraph>::type ArcIt;						\
       
   136   typedef typename ::lemon::_graph_utils_bits::				\
       
   137   OutArcIt<Digraph>::type OutArcIt;					\
       
   138   typedef typename ::lemon::_graph_utils_bits::				\
       
   139   InArcIt<Digraph>::type InArcIt;					\
       
   140   typedef typename ::lemon::_graph_utils_bits::				\
       
   141   BoolNodeMap<Digraph>::type BoolNodeMap;				\
       
   142   typedef typename ::lemon::_graph_utils_bits::				\
       
   143   IntNodeMap<Digraph>::type IntNodeMap;					\
       
   144   typedef typename ::lemon::_graph_utils_bits::				\
       
   145   DoubleNodeMap<Digraph>::type DoubleNodeMap;				\
       
   146   typedef typename ::lemon::_graph_utils_bits::				\
       
   147   BoolArcMap<Digraph>::type BoolArcMap;					\
       
   148   typedef typename ::lemon::_graph_utils_bits::				\
       
   149   IntArcMap<Digraph>::type IntArcMap;					\
       
   150   typedef typename ::lemon::_graph_utils_bits::				\
       
   151   DoubleArcMap<Digraph>::type DoubleArcMap
       
   152 
    58 
   153 
    59   ///Creates convenience typedefs for the graph types and iterators
   154   ///Creates convenience typedefs for the graph types and iterators
    60 
   155 
    61   ///This \c \#define creates the same convenience typedefs as defined
   156   ///This \c \#define creates the same convenience typedefs as defined
    62   ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
   157   ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
    63   ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
   158   ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
    64   ///\c DoubleEdgeMap.
   159   ///\c DoubleEdgeMap.
    65 #define GRAPH_TYPEDEFS(Graph)						\
   160 #define GRAPH_TYPEDEFS(Graph)						\
    66   DIGRAPH_TYPEDEFS(Graph);						\
   161   DIGRAPH_TYPEDEFS(Graph);						\
    67   typedef Graph::Edge Edge;						\
   162   typedef typename ::lemon::_graph_utils_bits::				\
    68   typedef Graph::EdgeIt EdgeIt;						\
   163   Edge<Graph>::type Edge;						\
    69   typedef Graph::IncEdgeIt IncEdgeIt
   164   typedef typename ::lemon::_graph_utils_bits::				\
       
   165   EdgeIt<Graph>::type EdgeIt;						\
       
   166   typedef typename ::lemon::_graph_utils_bits::				\
       
   167   IncEdgeIt<Graph>::type IncEdgeIt					\
       
   168   typedef typename ::lemon::_graph_utils_bits::				\
       
   169   BoolEdgeMap<Graph>::type BoolEdgeMap;					\
       
   170   typedef typename ::lemon::_graph_utils_bits::				\
       
   171   IntEdgeMap<Graph>::type IntEdgeMap;					\
       
   172   typedef typename ::lemon::_graph_utils_bits::				\
       
   173   DoubleEdgeMap<Graph>::type DoubleEdgeMap
       
   174 
    70 
   175 
    71   /// \brief Function to count the items in the graph.
   176   /// \brief Function to count the items in the graph.
    72   ///
   177   ///
    73   /// This function counts the items (nodes, arcs etc) in the graph.
   178   /// This function counts the items (nodes, arcs etc) in the graph.
    74   /// The complexity of the function is O(n) because
   179   /// The complexity of the function is O(n) because
  2054   {
  2159   {
  2055   public:
  2160   public:
  2056     typedef typename ItemSetTraits<G, typename G::Arc>
  2161     typedef typename ItemSetTraits<G, typename G::Arc>
  2057     ::ItemNotifier::ObserverBase Parent;
  2162     ::ItemNotifier::ObserverBase Parent;
  2058 
  2163 
  2059     DIGRAPH_TYPEDEFS(typename G);
  2164     DIGRAPH_TYPEDEFS(G);
  2060     typedef G Digraph;
  2165     typedef G Digraph;
  2061 
  2166 
  2062   protected:
  2167   protected:
  2063 
  2168 
  2064     class AutoNodeMap : public DefaultMap<G, Node, Arc> {
  2169     class AutoNodeMap : public DefaultMap<G, Node, Arc> {
  2491   ///\sa AllArcLookUp  
  2596   ///\sa AllArcLookUp  
  2492   template<class G>
  2597   template<class G>
  2493   class ArcLookUp 
  2598   class ArcLookUp 
  2494   {
  2599   {
  2495   public:
  2600   public:
  2496     DIGRAPH_TYPEDEFS(typename G);
  2601     DIGRAPH_TYPEDEFS(G);
  2497     typedef G Digraph;
  2602     typedef G Digraph;
  2498 
  2603 
  2499   protected:
  2604   protected:
  2500     const Digraph &_g;
  2605     const Digraph &_g;
  2501     typename Digraph::template NodeMap<Arc> _head;
  2606     typename Digraph::template NodeMap<Arc> _head;
  2608     using ArcLookUp<G>::_g;
  2713     using ArcLookUp<G>::_g;
  2609     using ArcLookUp<G>::_right;
  2714     using ArcLookUp<G>::_right;
  2610     using ArcLookUp<G>::_left;
  2715     using ArcLookUp<G>::_left;
  2611     using ArcLookUp<G>::_head;
  2716     using ArcLookUp<G>::_head;
  2612 
  2717 
  2613     DIGRAPH_TYPEDEFS(typename G);
  2718     DIGRAPH_TYPEDEFS(G);
  2614     typedef G Digraph;
  2719     typedef G Digraph;
  2615     
  2720     
  2616     typename Digraph::template ArcMap<Arc> _next;
  2721     typename Digraph::template ArcMap<Arc> _next;
  2617     
  2722     
  2618     Arc refreshNext(Arc head,Arc next=INVALID)
  2723     Arc refreshNext(Arc head,Arc next=INVALID)