Google OR-Tools v9.15
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs > Class Template Reference

Detailed Description

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
class util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >

Definition at line 206 of file graph.h.

#include <graph.h>

Inheritance diagram for util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >:
util::ReverseArcStaticGraph< NodeIndex, ArcIndex >

Public Types

typedef NodeIndexType NodeIndex
typedef ArcIndexType ArcIndex

Public Member Functions

 BaseGraph ()
 BaseGraph (const BaseGraph &)=default
BaseGraph & operator= (const BaseGraph &)=default
virtual ~BaseGraph ()=default
NodeIndexType num_nodes () const
NodeIndexType size () const
ArcIndexType num_arcs () const
IntegerRange< NodeIndex > AllNodes () const
IntegerRange< ArcIndex > AllForwardArcs () const
bool IsNodeValid (NodeIndexType node) const
bool IsArcValid (ArcIndexType arc) const
NodeIndexType node_capacity () const
ArcIndexType arc_capacity () const
virtual void ReserveNodes (NodeIndexType bound)
virtual void ReserveArcs (ArcIndexType bound)
void Reserve (NodeIndexType node_capacity, ArcIndexType arc_capacity)
void FreezeCapacities ()
virtual void Build (std::vector< ArcIndexType > *permutation)
void Build ()
virtual bool IsBuilt () const

Static Public Attributes

static constexpr bool kHasNegativeReverseArcs = HasNegativeReverseArcs
static constexpr NodeIndexType kNilNode
static constexpr ArcIndexType kNilArc

Protected Member Functions

void ComputeCumulativeSum (internal::Vector< NodeIndexType, ArcIndexType > *v)
void BuildStartAndForwardHead (internal::SVector< ArcIndexType, NodeIndexType > *head, internal::Vector< NodeIndexType, ArcIndexType > *start, std::vector< ArcIndexType > *permutation)

Protected Attributes

NodeIndexType num_nodes_
NodeIndexType node_capacity_
ArcIndexType num_arcs_
ArcIndexType arc_capacity_
bool const_capacities_

Member Typedef Documentation

◆ ArcIndex

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
typedef ArcIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::ArcIndex

Definition at line 213 of file graph.h.

◆ NodeIndex

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
typedef NodeIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::NodeIndex

Definition at line 212 of file graph.h.

Constructor & Destructor Documentation

◆ BaseGraph() [1/2]

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::BaseGraph ( )
inline

Definition at line 216 of file graph.h.

◆ BaseGraph() [2/2]

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::BaseGraph ( const BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs > & )
default

◆ ~BaseGraph()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
virtual util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::~BaseGraph ( )
virtualdefault

Member Function Documentation

◆ AllForwardArcs()

template<typename Impl, typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
IntegerRange< ArcIndexType > util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::AllForwardArcs ( ) const

Definition at line 1154 of file graph.h.

◆ AllNodes()

template<typename Impl, typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
IntegerRange< NodeIndexType > util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::AllNodes ( ) const

Definition at line 1146 of file graph.h.

◆ arc_capacity()

template<typename Impl, typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
ArcIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::arc_capacity ( ) const

Definition at line 1171 of file graph.h.

◆ Build() [1/2]

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
void util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::Build ( )
inline

Definition at line 307 of file graph.h.

◆ Build() [2/2]

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
virtual void util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::Build ( std::vector< ArcIndexType > * permutation)
inlinevirtual

Reimplemented in util::ReverseArcStaticGraph< NodeIndex, ArcIndex >.

Definition at line 304 of file graph.h.

◆ BuildStartAndForwardHead()

template<typename Impl, typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
void util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::BuildStartAndForwardHead ( internal::SVector< ArcIndexType, NodeIndexType > * head,
internal::Vector< NodeIndexType, ArcIndexType > * start,
std::vector< ArcIndexType > * permutation )
protected

Definition at line 1211 of file graph.h.

◆ ComputeCumulativeSum()

template<typename Impl, typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
void util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::ComputeCumulativeSum ( internal::Vector< NodeIndexType, ArcIndexType > * v)
protected

Definition at line 1191 of file graph.h.

◆ FreezeCapacities()

template<typename Impl, typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
void util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::FreezeCapacities ( )

Definition at line 1179 of file graph.h.

◆ IsArcValid()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
bool util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::IsArcValid ( ArcIndexType arc) const
inline

Definition at line 248 of file graph.h.

◆ IsBuilt()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
virtual bool util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::IsBuilt ( ) const
inlinevirtual

Reimplemented in util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >, util::ReverseArcStaticGraph< NodeIndex, ArcIndex >, and util::StaticGraph< NodeIndexType, ArcIndexType >.

Definition at line 308 of file graph.h.

◆ IsNodeValid()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
bool util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::IsNodeValid ( NodeIndexType node) const
inline

Definition at line 242 of file graph.h.

◆ node_capacity()

template<typename Impl, typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>
NodeIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::node_capacity ( ) const

Definition at line 1162 of file graph.h.

◆ num_arcs()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
ArcIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::num_arcs ( ) const
inline

Definition at line 233 of file graph.h.

◆ num_nodes()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
NodeIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::num_nodes ( ) const
inline

Definition at line 229 of file graph.h.

◆ operator=()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
BaseGraph & util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::operator= ( const BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs > & )
default

◆ Reserve()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
void util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::Reserve ( NodeIndexType node_capacity,
ArcIndexType arc_capacity )
inline

Definition at line 277 of file graph.h.

◆ ReserveArcs()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
virtual void util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::ReserveArcs ( ArcIndexType bound)
inlinevirtual

Reimplemented in util::ReverseArcListGraph< int, int >, and util::ReverseArcStaticGraph< NodeIndex, ArcIndex >.

Definition at line 271 of file graph.h.

◆ ReserveNodes()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
virtual void util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::ReserveNodes ( NodeIndexType bound)
inlinevirtual

Reimplemented in util::ReverseArcListGraph< int, int >.

Definition at line 265 of file graph.h.

◆ size()

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
NodeIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::size ( ) const
inline

Definition at line 230 of file graph.h.

Member Data Documentation

◆ arc_capacity_

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
ArcIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::arc_capacity_
protected

Definition at line 321 of file graph.h.

◆ const_capacities_

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
bool util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::const_capacities_
protected

Definition at line 322 of file graph.h.

◆ kHasNegativeReverseArcs

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
bool util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::kHasNegativeReverseArcs = HasNegativeReverseArcs
staticconstexpr

Definition at line 214 of file graph.h.

◆ kNilArc

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
ArcIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::kNilArc
staticconstexpr
Initial value:
=
std::numeric_limits<ArcIndexType>::max()

Definition at line 292 of file graph.h.

◆ kNilNode

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
NodeIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::kNilNode
staticconstexpr
Initial value:
=
std::numeric_limits<NodeIndexType>::max()

Definition at line 289 of file graph.h.

◆ node_capacity_

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
NodeIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::node_capacity_
protected

Definition at line 319 of file graph.h.

◆ num_arcs_

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
ArcIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::num_arcs_
protected

Definition at line 320 of file graph.h.

◆ num_nodes_

template<typename Impl, typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
NodeIndexType util::BaseGraph< Impl, NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::num_nodes_
protected

Definition at line 318 of file graph.h.

The documentation for this class was generated from the following file: