graph.h File Reference

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iterator>
#include <limits>
#include <type_traits>
#include <vector>
#include "absl/base/attributes.h"
#include "absl/debugging/leak_check.h"
#include "absl/log/check.h"
#include "absl/types/span.h"
#include "ortools/base/constant_divisor.h"
#include "ortools/base/logging.h"
#include "ortools/graph/iterators.h"

Go to the source code of this file.

Classes
class	util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >
class	util::ArcPropertyIterator< Graph, ArcIterator, PropertyT, property >
class	util::internal::Vector< IndexT, T >
	Allows indexing into a vector with an edge or node index. More...
class	util::internal::SVector< IndexT, T >
struct	util::GraphTraits< Graph >
class	util::ListGraph< NodeIndexType, ArcIndexType >
struct	util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingArcIteratorTag
	Do not use directly. More...
class	util::StaticGraph< NodeIndexType, ArcIndexType >
class	util::ReverseArcListGraph< NodeIndexType, ArcIndexType >
struct	util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingArcIteratorTag
	Do not use directly. See instead the arc iteration functions below. More...
struct	util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcIteratorTag
class	util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >
class	util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingOrOppositeIncomingArcIterator
class	util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OutgoingOrOppositeIncomingArcIterator
class	util::CompleteGraph< NodeIndexType, ArcIndexType >
class	util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >

Namespaces
namespace	util
	A collections of i/o utilities for the Graph classes in ./graph.h.
namespace	util::internal

Macros
#define	DEFINE_RANGE_BASED_ARC_ITERATION(c, t)
#define	DEFINE_STL_ITERATOR_FUNCTIONS(iterator_class_name)

Typedefs
template<typename Graph, typename ArcIterator>
using	util::ArcHeadIterator
	An iterator that iterates on the heads of the arcs of another iterator.
template<typename Graph, typename ArcIterator>
using	util::ArcOppositeArcIterator
	An iterator that iterates on the opposite arcs of another iterator.
typedef ListGraph	util::Graph
	Defining the simplest Graph interface as Graph for convenience.

Functions
template<typename ArcIndexType>
constexpr bool	util::internal::IsSigned ()
template<class IntVector, class Array>
void	util::Permute (const IntVector &permutation, Array *array_to_permute)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, OutgoingOrOppositeIncoming)
	ReverseArcListGraph implementation ---------------------------------------—.
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, OutgoingOrOppositeIncoming)
	ReverseArcStaticGraph implementation -------------------------------------—.

Macro Definition Documentation

DEFINE_RANGE_BASED_ARC_ITERATION

#define DEFINE_RANGE_BASED_ARC_ITERATION	(		c,
			t )

Value:

  template <typename NodeIndexType, typename ArcIndexType>                 \
  BeginEndWrapper<typename c<NodeIndexType, ArcIndexType>::t##ArcIterator> \
      c<NodeIndexType, ArcIndexType>::t##Arcs(NodeIndexType node) const {  \
    return BeginEndWrapper<t##ArcIterator>(                                \
        t##ArcIterator(*this, node),                                       \
        t##ArcIterator(*this, node, Base::kNilArc));                       \
  }                                                                        \
  template <typename NodeIndexType, typename ArcIndexType>                 \
  BeginEndWrapper<typename c<NodeIndexType, ArcIndexType>::t##ArcIterator> \
      c<NodeIndexType, ArcIndexType>::t##ArcsStartingFrom(                 \
          NodeIndexType node, ArcIndexType from) const {                   \
    return BeginEndWrapper<t##ArcIterator>(                                \
        t##ArcIterator(*this, node, from),                                 \
        t##ArcIterator(*this, node, Base::kNilArc));                       \
  }

Macros to wrap old style iteration into the new range-based for loop style. The parameters are:

• c: the class name.
• t: the iteration type (Outgoing, Incoming, OutgoingOrOppositeIncoming or OppositeIncoming).
• e: the "end" ArcIndexType.

Definition at line 1259 of file graph.h.

DEFINE_STL_ITERATOR_FUNCTIONS

#define DEFINE_STL_ITERATOR_FUNCTIONS

(

iterator_class_name

)

Value:

  using iterator_category = std::input_iterator_tag;        \
  using difference_type = ptrdiff_t;                        \
  using pointer = const ArcIndexType*;                      \
  using value_type = ArcIndexType;                          \
  using reference = value_type;                             \
  bool operator!=(const iterator_class_name& other) const { \
    return this->index_ != other.index_;                    \
  }                                                         \
  bool operator==(const iterator_class_name& other) const { \
    return this->index_ == other.index_;                    \
  }                                                         \
  ArcIndexType operator*() const { return this->Index(); }  \
  iterator_class_name& operator++() {                       \
    this->Next();                                           \
    return *this;                                           \
  }                                                         \
  iterator_class_name operator++(int) {                     \
    auto tmp = *this;                                       \
    this->Next();                                           \
    return tmp;                                             \
  }

Adapt our old iteration style to support range-based for loops. Add typedefs required by std::iterator_traits.

Definition at line 1278 of file graph.h.