RhodeCode

  /// \brief Dummy type to make it easier to create invalid iterators.

  ///

  /// Dummy type to make it easier to create invalid iterators.

  /// See \ref INVALID for the usage.

  struct Invalid {

  public:

    bool operator==(Invalid) { return true;  }

    bool operator!=(Invalid) { return false; }

    bool operator< (Invalid) { return false; }

  };

  /// \brief Invalid iterators.

  ///

  /// \ref Invalid is a global type that converts to each iterator

  /// in such a way that the value of the target iterator will be invalid.

#ifdef LEMON_ONLY_TEMPLATES

  const Invalid INVALID = Invalid();

#else

  extern const Invalid INVALID;

#endif

  /// \addtogroup gutils

  /// @{

  ///This \c \#define creates convenient type definitions for the following

  ///types of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,

  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,

  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.

  ///

  ///\note If the graph type is a dependent type, ie. the graph type depend

  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()

  ///macro.

#define DIGRAPH_TYPEDEFS(Digraph)                                       \

  typedef Digraph::Node Node;                                           \

  typedef Digraph::NodeIt NodeIt;                                       \

  typedef Digraph::Arc Arc;                                             \

  typedef Digraph::ArcIt ArcIt;                                         \

  typedef Digraph::InArcIt InArcIt;                                     \

  typedef Digraph::OutArcIt OutArcIt;                                   \

  typedef Digraph::NodeMap<bool> BoolNodeMap;                           \

  typedef Digraph::NodeMap<int> IntNodeMap;                             \

  typedef Digraph::NodeMap<double> DoubleNodeMap;                       \

  typedef Digraph::ArcMap<bool> BoolArcMap;                             \

  typedef Digraph::ArcMap<int> IntArcMap;                               \

  ///\see DIGRAPH_TYPEDEFS

  ///

  ///\note Use this macro, if the graph type is a dependent type,

  ///ie. the graph type depend on a template parameter.

#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \

  typedef typename Digraph::Node Node;                                  \

  typedef typename Digraph::NodeIt NodeIt;                              \

  typedef typename Digraph::Arc Arc;                                    \

  typedef typename Digraph::ArcIt ArcIt;                                \

  typedef typename Digraph::InArcIt InArcIt;                            \

  typedef typename Digraph::OutArcIt OutArcIt;                          \

  typedef typename Digraph::template NodeMap<bool> BoolNodeMap;         \

  typedef typename Digraph::template NodeMap<int> IntNodeMap;           \

  typedef typename Digraph::template NodeMap<double> DoubleNodeMap;     \

  typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \

  typedef typename Digraph::template ArcMap<int> IntArcMap;             \

  ///This \c \#define creates the same convenient type definitions as defined

  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates

  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,

  ///\c DoubleEdgeMap.

  ///

  ///\note If the graph type is a dependent type, ie. the graph type depend

  ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()

  ///macro.

#define GRAPH_TYPEDEFS(Graph)                                           \

  DIGRAPH_TYPEDEFS(Graph);                                              \

  typedef Graph::Edge Edge;                                             \

  typedef Graph::EdgeIt EdgeIt;                                         \

  typedef Graph::IncEdgeIt IncEdgeIt;                                   \

  typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \

  typedef Graph::EdgeMap<int> IntEdgeMap;                               \

  ///\see GRAPH_TYPEDEFS

  ///

  ///\note Use this macro, if the graph type is a dependent type,

  ///ie. the graph type depend on a template parameter.

#define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \

  TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \

  typedef typename Graph::Edge Edge;                                    \

  typedef typename Graph::EdgeIt EdgeIt;                                \

  typedef typename Graph::IncEdgeIt IncEdgeIt;                          \

  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \

  typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \

  /// \brief Function to count the items in a graph.

  ///

  /// This function counts the items (nodes, arcs etc.) in a graph.

  /// The complexity of the function is linear because

  /// it iterates on all of the items.

  template <typename Graph, typename Item>

  inline int countItems(const Graph& g) {

    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;

    int num = 0;

    for (ItemIt it(g); it != INVALID; ++it) {

      ++num;

    }

    return num;

  }

  // Node counting:

  namespace _core_bits {

    template <typename Graph, typename Enable = void>

    struct CountNodesSelector {

      static int count(const Graph &g) {

        return countItems<Graph, typename Graph::Node>(g);