|
| Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
#include <ebert_graph.h>
Public Member Functions | |
| bool | Reserve (NodeIndexType new_max_num_nodes, ArcIndexType new_max_num_arcs) |
| Reserves memory needed for max_num_nodes nodes and max_num_arcs arcs. | |
| NodeIndexType | num_nodes () const |
| Returns the number of nodes in the graph. | |
| ArcIndexType | num_arcs () const |
| Returns the number of original arcs in the graph (The ones with positive indices. | |
| NodeIndexType | end_node_index () const |
| Returns one more than the largest index of an extant node. | |
| ArcIndexType | end_arc_index () const |
| Returns one more than the largest index of an extant direct arc. | |
| NodeIndexType | max_num_nodes () const |
| Returns the maximum possible number of nodes in the graph. | |
| ArcIndexType | max_num_arcs () const |
| Returns the maximum possible number of original arcs in the graph. | |
| NodeIndexType | max_end_node_index () const |
| Returns one more than the largest valid index of a node. | |
| ArcIndexType | max_end_arc_index () const |
| Returns one more than the largest valid index of a direct arc. | |
| bool | IsNodeValid (NodeIndexType node) const |
| Utility function to check that a node index is within the bounds AND different from kNilNode. | |
| ArcIndexType | AddArc (NodeIndexType tail, NodeIndexType head) |
| Adds an arc to the graph and returns its index. | |
| template<typename ArcIndexTypeStrictWeakOrderingFunctor> | |
| void | GroupForwardArcsByFunctor (const ArcIndexTypeStrictWeakOrderingFunctor &compare, PermutationCycleHandler< ArcIndexType > *annotation_handler) |
| ArcIndexType | LookUpArc (const NodeIndexType tail, const NodeIndexType head) const |
| Returns the first arc going from tail to head, if it exists, or kNilArc if such an arc does not exist. | |
| NodeIndexType | Head (const ArcIndexType arc) const |
| Returns the head or end-node of arc. | |
| string | NodeDebugString (const NodeIndexType node) const |
| string | ArcDebugString (const ArcIndexType arc) const |
Static Public Attributes | |
| static const NodeIndexType | kNilNode = -1 |
| The index of the 'nil' node in the graph. | |
| static const ArcIndexType | kNilArc |
| The index of the 'nil' arc in the graph. | |
| static const NodeIndexType | kFirstNode = 0 |
| The index of the first node in the graph. | |
| static const ArcIndexType | kFirstArc = 0 |
| The index of the first arc in the graph. | |
| static const NodeIndexType | kMaxNumNodes |
| The maximum possible number of nodes in the graph. | |
| static const ArcIndexType | kMaxNumArcs |
| The maximum possible number of arcs in the graph. | |
Protected Member Functions | |
| EbertGraphCore () | |
| ~EbertGraphCore () | |
| void | Initialize (NodeIndexType max_num_nodes, ArcIndexType max_num_arcs) |
| NodeIndexType | StartNode (NodeIndexType node) const |
| Returns kNilNode if the graph has no nodes or node if it has at least one node. | |
| ArcIndexType | StartArc (ArcIndexType arc) const |
| Returns kNilArc if the graph has no arcs arc if it has at least one arc. | |
| ArcIndexType | FirstIncidentArc (const NodeIndexType node) const |
| Returns the first arc in node's incidence list. | |
| ArcIndexType | NextAdjacentArc (const ArcIndexType arc) const |
| Returns the next arc following the passed argument in its adjacency list. | |
| NodeIndexType | NextNode (const NodeIndexType node) const |
| Returns the node following the argument in the graph. | |
| ArcIndexType | NextArc (const ArcIndexType arc) const |
| Returns the arc following the argument in the graph. | |
| ArcIndexType | FirstOutgoingArc (const NodeIndexType node) const |
| Returns the first outgoing arc for node. | |
Protected Attributes | |
| NodeIndexType | max_num_nodes_ |
| The maximum number of nodes that the graph can hold. | |
| ArcIndexType | max_num_arcs_ |
| The maximum number of arcs that the graph can hold. | |
| NodeIndexType | num_nodes_ |
| The maximum index of the node currently held by the graph. | |
| ArcIndexType | num_arcs_ |
| The current number of arcs held by the graph. | |
| ZVector< NodeIndexType > | head_ |
| Array of node indices. head_[i] contains the head node of arc i. | |
| ZVector< ArcIndexType > | next_adjacent_arc_ |
| Array of next indices. | |
| ZVector< ArcIndexType > | first_incident_arc_ |
| Array of arc indices. | |
| bool | representation_clean_ |
| Flag to indicate that BuildRepresentation() needs to be called before the adjacency lists are examined. | |
Classes | |
| class | ArcIterator |
| Iterator class for traversing the arcs in the graph. More... | |
| class | CycleHandlerForAnnotatedArcs |
| class | NodeIterator |
| Iterator class for traversing all the nodes in the graph. More... | |
This template is for internal use only, and this is enforced by making all constructors for this class template protected. Clients should use one of the two derived-class templates. Most clients will not even use those directly, but will use the StarGraph and ForwardStarGraph typenames declared above.
The DerivedGraph template argument must be the type of the class (typically itself built from a template) that: 1. implements the full interface expected for either ForwardEbertGraph or EbertGraph, and 2. inherits from an instance of this template. The base class needs access to some members of the derived class such as, for example, NextOutgoingArc(), and it gets this access via the DerivedGraph template argument.
Definition at line 167 of file ebert_graph.h.
| operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::EbertGraphCore | ( | ) | [inline, protected] |
Definition at line 462 of file ebert_graph.h.
| operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::~EbertGraphCore | ( | ) | [inline, protected] |
Definition at line 472 of file ebert_graph.h.
| bool operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::Reserve | ( | NodeIndexType | new_max_num_nodes, | |
| ArcIndexType | new_max_num_arcs | |||
| ) | [inline] |
Reserves memory needed for max_num_nodes nodes and max_num_arcs arcs.
Returns false if the parameters passed are not OK. It can be used to enlarge the graph, but does not shrink memory if called with smaller values.
Definition at line 195 of file ebert_graph.h.
| NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::num_nodes | ( | ) | const [inline] |
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::num_arcs | ( | ) | const [inline] |
Returns the number of original arcs in the graph (The ones with positive indices.
)
Definition at line 222 of file ebert_graph.h.
| NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::end_node_index | ( | ) | const [inline] |
Returns one more than the largest index of an extant node.
To be used as a helper when clients need to dimension or iterate over arrays of node annotation information.
Definition at line 227 of file ebert_graph.h.
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::end_arc_index | ( | ) | const [inline] |
Returns one more than the largest index of an extant direct arc.
To be used as a helper when clients need to dimension or iterate over arrays of arc annotation information.
Definition at line 234 of file ebert_graph.h.
| NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::max_num_nodes | ( | ) | const [inline] |
Returns the maximum possible number of nodes in the graph.
Definition at line 239 of file ebert_graph.h.
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::max_num_arcs | ( | ) | const [inline] |
Returns the maximum possible number of original arcs in the graph.
(The ones with positive indices.)
Definition at line 243 of file ebert_graph.h.
| NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::max_end_node_index | ( | ) | const [inline] |
Returns one more than the largest valid index of a node.
To be used as a helper when clients need to dimension or iterate over arrays of node annotation information.
Definition at line 248 of file ebert_graph.h.
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::max_end_arc_index | ( | ) | const [inline] |
Returns one more than the largest valid index of a direct arc.
To be used as a helper when clients need to dimension or iterate over arrays of arc annotation information.
Definition at line 255 of file ebert_graph.h.
| bool operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::IsNodeValid | ( | NodeIndexType | node | ) | const [inline] |
Utility function to check that a node index is within the bounds AND different from kNilNode.
Returns true if node is in the range [kFirstNode .. max_num_nodes_). It is exported so that users of the DerivedGraph class can use it. To be used in a DCHECK; also used internally to validate arguments passed to our methods from clients (e.g., AddArc()).
Reimplemented in operations_research::ForwardEbertGraph< NodeIndexType, ArcIndexType >.
Definition at line 265 of file ebert_graph.h.
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::AddArc | ( | NodeIndexType | tail, | |
| NodeIndexType | head | |||
| ) | [inline] |
Adds an arc to the graph and returns its index.
Returns kNilArc if the arc could not be added. Note that for a given pair (tail, head) AddArc does not overwrite an already-existing arc between tail and head: Another arc is created instead. This makes it possible to handle multi-graphs.
Definition at line 274 of file ebert_graph.h.
| void operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::GroupForwardArcsByFunctor | ( | const ArcIndexTypeStrictWeakOrderingFunctor & | compare, | |
| PermutationCycleHandler< ArcIndexType > * | annotation_handler | |||
| ) | [inline] |
Definition at line 295 of file ebert_graph.h.
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::LookUpArc | ( | const NodeIndexType | tail, | |
| const NodeIndexType | head | |||
| ) | const [inline] |
Returns the first arc going from tail to head, if it exists, or kNilArc if such an arc does not exist.
Definition at line 427 of file ebert_graph.h.
| NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::Head | ( | const ArcIndexType | arc | ) | const [inline] |
| string operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::NodeDebugString | ( | const NodeIndexType | node | ) | const [inline] |
Definition at line 445 of file ebert_graph.h.
| string operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::ArcDebugString | ( | const ArcIndexType | arc | ) | const [inline] |
Definition at line 453 of file ebert_graph.h.
| void operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::Initialize | ( | NodeIndexType | max_num_nodes, | |
| ArcIndexType | max_num_arcs | |||
| ) | [inline, protected] |
Definition at line 474 of file ebert_graph.h.
| NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::StartNode | ( | NodeIndexType | node | ) | const [inline, protected] |
Returns kNilNode if the graph has no nodes or node if it has at least one node.
Useful for initializing iterators correctly in the case of empty graphs.
Definition at line 489 of file ebert_graph.h.
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::StartArc | ( | ArcIndexType | arc | ) | const [inline, protected] |
Returns kNilArc if the graph has no arcs arc if it has at least one arc.
Useful for initializing iterators correctly in the case of empty graphs.
Definition at line 495 of file ebert_graph.h.
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::FirstIncidentArc | ( | const NodeIndexType | node | ) | const [inline, protected] |
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::NextAdjacentArc | ( | const ArcIndexType | arc | ) | const [inline, protected] |
Returns the next arc following the passed argument in its adjacency list.
Definition at line 507 of file ebert_graph.h.
| NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::NextNode | ( | const NodeIndexType | node | ) | const [inline, protected] |
Returns the node following the argument in the graph.
Returns kNilNode (= end) if the range of nodes has been exhausted. It is called by NodeIterator::Next() and as such does not expect to be passed an argument equal to kNilNode. This is why the return line is simplified from return (node == kNilNode || next_node >= num_nodes_) ? kNilNode : next_node; to return next_node < num_nodes_ ? next_node : kNilNode;
Definition at line 522 of file ebert_graph.h.
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::NextArc | ( | const ArcIndexType | arc | ) | const [inline, protected] |
Returns the arc following the argument in the graph.
Returns kNilArc (= end) if the range of arcs has been exhausted. It is called by ArcIterator::Next() and as such does not expect to be passed an argument equal to kNilArc. This is why the return line is simplified from return ( arc == kNilArc || next_arc >= num_arcs_) ? kNilArc : next_arc; to return next_arc < num_arcs_ ? next_arc : kNilArc;
Definition at line 536 of file ebert_graph.h.
| ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::FirstOutgoingArc | ( | const NodeIndexType | node | ) | const [inline, protected] |
const NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::kNilNode = -1 [inline, static] |
const ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::kNilArc [inline, static] |
Initial value:
std::numeric_limits<ArcIndexType>::min()
Definition at line 173 of file ebert_graph.h.
const NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::kFirstNode = 0 [inline, static] |
const ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::kFirstArc = 0 [inline, static] |
const NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::kMaxNumNodes [inline, static] |
Initial value:
std::numeric_limits<NodeIndexType>::max()
The maximum possible node index in the graph.
(The maximum index is kMaxNumNodes-1, since indices start at 0. Unfortunately we waste a value representing this and the max_num_nodes_ member.)
Definition at line 184 of file ebert_graph.h.
const ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::kMaxNumArcs [inline, static] |
Initial value:
std::numeric_limits<ArcIndexType>::max()
(The maximum index is kMaxNumArcs-1, since indices start at 0. Unfortunately we waste a value representing this and the max_num_arcs_ member.)
(The maximum index is kMaxNumArcs-1, since indices start at 0.)
Definition at line 189 of file ebert_graph.h.
NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::max_num_nodes_ [protected] |
ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::max_num_arcs_ [protected] |
NodeIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::num_nodes_ [protected] |
The maximum index of the node currently held by the graph.
Definition at line 555 of file ebert_graph.h.
ArcIndexType operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::num_arcs_ [protected] |
ZVector<NodeIndexType> operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::head_ [protected] |
Array of node indices. head_[i] contains the head node of arc i.
Definition at line 561 of file ebert_graph.h.
ZVector<ArcIndexType> operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::next_adjacent_arc_ [protected] |
Array of next indices.
next_adjacent_arc_[i] contains the next arc in the adjacency list of arc i.
Definition at line 565 of file ebert_graph.h.
ZVector<ArcIndexType> operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::first_incident_arc_ [protected] |
Array of arc indices.
first_incident_arc_[i] contains the first arc incident to node i.
Definition at line 569 of file ebert_graph.h.
bool operations_research::EbertGraphCore< NodeIndexType, ArcIndexType, DerivedGraph >::representation_clean_ [protected] |
Flag to indicate that BuildRepresentation() needs to be called before the adjacency lists are examined.
Only for DCHECK in debug builds.
Definition at line 574 of file ebert_graph.h.