graph.h File Reference

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <iterator>
#include <limits>
#include <new>
#include <type_traits>
#include <vector>
#include "absl/base/port.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/base/macros.h"
#include "ortools/base/types.h"
#include "ortools/graph/iterators.h"

Go to the source code of this file.

Classes
class	util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >
class	util::ListGraph< NodeIndexType, ArcIndexType >
class	util::StaticGraph< NodeIndexType, ArcIndexType >
class	util::ReverseArcListGraph< NodeIndexType, ArcIndexType >
class	util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >
class	util::ReverseArcMixedGraph< NodeIndexType, ArcIndexType >
class	util::SVector< T >
	Forward declaration. More...
class	util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator
class	util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator
class	util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator
class	util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator
class	util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcIterator
class	util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::IncomingArcIterator
class	util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingOrOppositeIncomingArcIterator
class	util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator
class	util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator
class	util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcIterator
class	util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::IncomingArcIterator
class	util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OutgoingOrOppositeIncomingArcIterator
class	util::ReverseArcMixedGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator
class	util::ReverseArcMixedGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcIterator
class	util::ReverseArcMixedGraph< NodeIndexType, ArcIndexType >::IncomingArcIterator
class	util::ReverseArcMixedGraph< NodeIndexType, ArcIndexType >::OutgoingOrOppositeIncomingArcIterator
class	util::CompleteGraph< NodeIndexType, ArcIndexType >
class	util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >
class	util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator

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

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

Typedefs
typedef ListGraph	util::Graph
	Defining the simplest Graph interface as Graph for convenience.

Functions
template<class IntVector, class Array, class ElementType>
void	util::PermuteWithExplicitElementType (const IntVector &permutation, Array *array_to_permute, ElementType unused)
template<class IntVector, class Array>
void	util::Permute (const IntVector &permutation, Array *array_to_permute)
template<class IntVector>
void	util::Permute (const IntVector &permutation, std::vector< bool > *array_to_permute)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ListGraph, Outgoing)
	ListGraph implementation -------------------------------------------------—.
	util::DEFINE_RANGE_BASED_ARC_ITERATION (StaticGraph, Outgoing)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, Outgoing)
	ReverseArcListGraph implementation ---------------------------------------—.
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, Incoming)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, OutgoingOrOppositeIncoming)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, OppositeIncoming)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, Outgoing)
	ReverseArcStaticGraph implementation -------------------------------------—.
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, Incoming)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, OutgoingOrOppositeIncoming)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, OppositeIncoming)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, Outgoing)
	ReverseArcMixedGraph implementation --------------------------------------—.
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, Incoming)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, OutgoingOrOppositeIncoming)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, OppositeIncoming)

Variables
template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
const NodeIndexType	util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::kNilNode
template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
const ArcIndexType	util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::kNilArc

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 1108 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(); }  \
  void operator++() { this->Next(); }

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

Definition at line 1127 of file graph.h.