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/types/span.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, HasReverseArcs >
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, e)
#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, Base::kNilArc)
	ListGraph implementation -------------------------------------------------—.
	util::DEFINE_RANGE_BASED_ARC_ITERATION (StaticGraph, Outgoing, DirectArcLimit(node))
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, Outgoing, Base::kNilArc)
	ReverseArcListGraph implementation ---------------------------------------—.
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, Incoming, Base::kNilArc)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, OutgoingOrOppositeIncoming, Base::kNilArc)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, OppositeIncoming, Base::kNilArc)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, Outgoing, DirectArcLimit(node))
	ReverseArcStaticGraph implementation -------------------------------------—.
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, Incoming, ReverseArcLimit(node))
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, OutgoingOrOppositeIncoming, DirectArcLimit(node))
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, OppositeIncoming, ReverseArcLimit(node))
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, Outgoing, DirectArcLimit(node))
	ReverseArcMixedGraph implementation --------------------------------------—.
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, Incoming, Base::kNilArc)
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, OutgoingOrOppositeIncoming, DirectArcLimit(node))
	util::DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, OppositeIncoming, Base::kNilArc)

Macro Definition Documentation

DEFINE_RANGE_BASED_ARC_ITERATION

#define DEFINE_RANGE_BASED_ARC_ITERATION	(		c,
			t,
			e )

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, e));   \
  }                                                                           \
  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, e));   \
  }

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 1100 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 1117 of file graph.h.