C++ Reference

C++ Reference: Graph

graphs.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// Temporary utility class needed as long as we have two slightly
15// different graph interface: The one in ebert_graph.h and the one in graph.h
16
17#ifndef OR_TOOLS_GRAPH_GRAPHS_H_
18#define OR_TOOLS_GRAPH_GRAPHS_H_
19
21
22namespace operations_research {
23
24// Since StarGraph does not have exactly the same interface as the other
25// graphs, we define a correspondence there.
26template <typename Graph>
27struct Graphs {
28 typedef typename Graph::ArcIndex ArcIndex;
29 typedef typename Graph::NodeIndex NodeIndex;
30 static ArcIndex OppositeArc(const Graph& graph, ArcIndex arc) {
31 return graph.OppositeArc(arc);
32 }
33 static bool IsArcValid(const Graph& graph, ArcIndex arc) {
34 return graph.IsArcValid(arc);
35 }
36 static NodeIndex NodeReservation(const Graph& graph) {
37 return graph.node_capacity();
38 }
39 static ArcIndex ArcReservation(const Graph& graph) {
40 return graph.arc_capacity();
41 }
42 static void Build(Graph* graph) { graph->Build(); }
43 static void Build(Graph* graph, std::vector<ArcIndex>* permutation) {
44 graph->Build(permutation);
45 }
46};
47
48template <>
51#if defined(_MSC_VER)
54#else
55 typedef typename Graph::ArcIndex ArcIndex;
56 typedef typename Graph::NodeIndex NodeIndex;
57#endif
58 static ArcIndex OppositeArc(const Graph& graph, ArcIndex arc) {
59 return graph.Opposite(arc);
60 }
61 static bool IsArcValid(const Graph& graph, ArcIndex arc) {
62 return graph.CheckArcValidity(arc);
63 }
64 static NodeIndex NodeReservation(const Graph& graph) {
65 return graph.max_num_nodes();
66 }
67 static ArcIndex ArcReservation(const Graph& graph) {
68 return graph.max_num_arcs();
69 }
70 static void Build(Graph* graph) {}
71 static void Build(Graph* graph, std::vector<ArcIndex>* permutation) {
72 permutation->clear();
73 }
74};
75
76} // namespace operations_research
77
78#endif // OR_TOOLS_GRAPH_GRAPHS_H_
bool CheckArcValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:1371
ArcIndexType Opposite(const ArcIndexType arc) const
Definition: ebert_graph.h:1409
NodeIndexType max_num_nodes() const
Definition: ebert_graph.h:255
ArcIndexType max_num_arcs() const
Definition: ebert_graph.h:259
ListGraph Graph
Definition: graph.h:2360
static ArcIndex ArcReservation(const Graph &graph)
Definition: graphs.h:67
static NodeIndex NodeReservation(const Graph &graph)
Definition: graphs.h:64
static void Build(Graph *graph, std::vector< ArcIndex > *permutation)
Definition: graphs.h:71
static bool IsArcValid(const Graph &graph, ArcIndex arc)
Definition: graphs.h:61
static ArcIndex OppositeArc(const Graph &graph, ArcIndex arc)
Definition: graphs.h:58
static void Build(Graph *graph)
Definition: graphs.h:42
static ArcIndex ArcReservation(const Graph &graph)
Definition: graphs.h:39
Graph::ArcIndex ArcIndex
Definition: graphs.h:28
Graph::NodeIndex NodeIndex
Definition: graphs.h:29
static NodeIndex NodeReservation(const Graph &graph)
Definition: graphs.h:36
static void Build(Graph *graph, std::vector< ArcIndex > *permutation)
Definition: graphs.h:43
static bool IsArcValid(const Graph &graph, ArcIndex arc)
Definition: graphs.h:33
static ArcIndex OppositeArc(const Graph &graph, ArcIndex arc)
Definition: graphs.h:30