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

Detailed Description

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
class util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >

CompleteBipartiteGraph implementation ------------------------------------— Nodes and arcs are implicit and not stored.

Definition at line 1936 of file graph.h.

#include <graph.h>

Inheritance diagram for util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >:
util::BaseGraph< int32_t, int32_t, false >

Public Member Functions

 CompleteBipartiteGraph (NodeIndexType left_nodes, NodeIndexType right_nodes)
ArcIndexType GetArc (NodeIndexType left_node, NodeIndexType right_node) const
NodeIndexType Head (ArcIndexType arc) const
NodeIndexType Tail (ArcIndexType arc) const
ArcIndexType OutDegree (NodeIndexType node) const
IntegerRange< ArcIndexType > OutgoingArcs (NodeIndexType node) const
IntegerRange< ArcIndexType > OutgoingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
IntegerRange< NodeIndexType > operator[] (NodeIndexType node) const
Public Member Functions inherited from util::BaseGraph< int32_t, int32_t, false >
 BaseGraph ()
BaseGraphoperator= (const BaseGraph &)=default
virtual ~BaseGraph ()=default
int32_t num_nodes () const
int32_t size () const
int32_t num_arcs () const
 Returns the number of valid arcs in the graph.
IntegerRange< NodeIndexAllNodes () const
 BaseGraph implementation -------------------------------------------------—.
IntegerRange< ArcIndexAllForwardArcs () const
bool IsNodeValid (int32_t node) const
 Returns true if the given node is a valid node of the graph.
bool IsArcValid (int32_t arc) const
int32_t node_capacity () const
 Capacity reserved for future nodes, always >= num_nodes_.
int32_t arc_capacity () const
 Capacity reserved for future arcs, always >= num_arcs_.
virtual void ReserveNodes (int32_t bound)
virtual void ReserveArcs (int32_t bound)
void Reserve (int32_t node_capacity, int32_t arc_capacity)
void FreezeCapacities ()

Additional Inherited Members

Public Types inherited from util::BaseGraph< int32_t, int32_t, false >
typedef int32_t NodeIndex
typedef int32_t ArcIndex
Static Public Attributes inherited from util::BaseGraph< int32_t, int32_t, false >
static constexpr bool kHasNegativeReverseArcs
static constexpr int32_t kNilNode
static constexpr int32_t kNilArc
Protected Member Functions inherited from util::BaseGraph< int32_t, int32_t, false >
void ComputeCumulativeSum (internal::Vector< int32_t, int32_t > *v)
 Functions commented when defined because they are implementation details.
void BuildStartAndForwardHead (internal::SVector< int32_t, int32_t > *head, internal::Vector< int32_t, int32_t > *start, std::vector< int32_t > *permutation)
Protected Attributes inherited from util::BaseGraph< int32_t, int32_t, false >
int32_t num_nodes_
int32_t node_capacity_
int32_t num_arcs_
int32_t arc_capacity_
bool const_capacities_

Constructor & Destructor Documentation

◆ CompleteBipartiteGraph()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >::CompleteBipartiteGraph ( NodeIndexType left_nodes,
NodeIndexType right_nodes )
inline

Builds a complete bipartite graph from a set of left nodes to a set of right nodes. Indices of left nodes of the bipartite graph range from 0 to left_nodes-1; indices of right nodes range from left_nodes to left_nodes+right_nodes-1. If there are no right nodes, the divisor is arbitrary. We pick 2 as 0 and 1 are not supported by ConstantDivisor. We handle the case where right_nodes is 1 explicitly when dividing.

Definition at line 1950 of file graph.h.

Member Function Documentation

◆ GetArc()

template<typename NodeIndexType, typename ArcIndexType>
ArcIndexType util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >::GetArc ( NodeIndexType left_node,
NodeIndexType right_node ) const

Returns the arc index for the arc from left to right, where left is in [0, left_nodes) and right is in [left_nodes, left_nodes + right_nodes).

Definition at line 1985 of file graph.h.

◆ Head()

template<typename NodeIndexType, typename ArcIndexType>
NodeIndexType util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >::Head ( ArcIndexType arc) const

See comment on divisor_ in the constructor.

Definition at line 1995 of file graph.h.

◆ operator[]()

template<typename NodeIndexType, typename ArcIndexType>
IntegerRange< NodeIndexType > util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >::operator[] ( NodeIndexType node) const

Definition at line 2043 of file graph.h.

◆ OutDegree()

template<typename NodeIndexType, typename ArcIndexType>
ArcIndexType util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >::OutDegree ( NodeIndexType node) const

Definition at line 2011 of file graph.h.

◆ OutgoingArcs()

template<typename NodeIndexType, typename ArcIndexType>
IntegerRange< ArcIndexType > util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >::OutgoingArcs ( NodeIndexType node) const

Definition at line 2018 of file graph.h.

◆ OutgoingArcsStartingFrom()

template<typename NodeIndexType, typename ArcIndexType>
IntegerRange< ArcIndexType > util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >::OutgoingArcsStartingFrom ( NodeIndexType node,
ArcIndexType from ) const

Definition at line 2031 of file graph.h.

◆ Tail()

template<typename NodeIndexType, typename ArcIndexType>
NodeIndexType util::CompleteBipartiteGraph< NodeIndexType, ArcIndexType >::Tail ( ArcIndexType arc) const

See comment on divisor_ in the constructor.

Definition at line 2003 of file graph.h.


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