14 #ifndef OR_TOOLS_GRAPH_MINIMUM_SPANNING_TREE_H_
15 #define OR_TOOLS_GRAPH_MINIMUM_SPANNING_TREE_H_
20 #include "ortools/base/adjustable_priority_queue-inl.h"
21 #include "ortools/base/adjustable_priority_queue.h"
22 #include "ortools/base/integral_types.h"
24 #include "ortools/util/vector_or_function.h"
48 template <
typename Graph>
49 std::vector<typename Graph::ArcIndex>
52 const std::vector<typename Graph::ArcIndex>& sorted_arcs) {
55 const int num_arcs = graph.num_arcs();
57 std::vector<ArcIndex> tree_arcs;
58 if (graph.num_nodes() == 0) {
61 const int expected_tree_size = graph.num_nodes() - 1;
62 tree_arcs.reserve(expected_tree_size);
64 components.
Init(graph.num_nodes());
65 while (tree_arcs.size() != expected_tree_size && arc_index < num_arcs) {
66 const ArcIndex arc = sorted_arcs[arc_index];
71 if (tail_class != head_class) {
73 tree_arcs.push_back(arc);
90 template <
typename Graph,
typename ArcComparator>
92 const Graph& graph,
const ArcComparator& arc_comparator) {
94 std::vector<ArcIndex> sorted_arcs(graph.num_arcs());
95 for (
const ArcIndex arc : graph.AllForwardArcs()) {
96 sorted_arcs[arc] = arc;
98 std::sort(sorted_arcs.begin(), sorted_arcs.end(), arc_comparator);
116 template <
typename Graph,
typename ArcValue>
118 const Graph& graph,
const ArcValue& arc_value) {
121 using ArcValueType = decltype(arc_value(0));
122 std::vector<ArcIndex> tree_arcs;
123 if (graph.num_nodes() == 0) {
126 const int expected_tree_size = graph.num_nodes() - 1;
127 tree_arcs.reserve(expected_tree_size);
128 std::vector<ArcIndex> node_neighbor(graph.num_nodes(), Graph::kNilArc);
129 std::vector<bool> node_active(graph.num_nodes(),
true);
136 void SetHeapIndex(
int index) { heap_index = index; }
137 int GetHeapIndex()
const {
return heap_index; }
138 bool operator<(
const Entry& other)
const {
return value > other.value; }
145 AdjustablePriorityQueue<Entry> pq;
146 std::vector<Entry> entries;
147 std::vector<bool> touched_entry(graph.num_nodes(),
false);
148 for (
NodeIndex node : graph.AllNodes()) {
149 entries.push_back({node, std::numeric_limits<ArcValueType>::max(), -1});
151 entries[0].value = 0;
153 while (!pq.IsEmpty() && tree_arcs.size() != expected_tree_size) {
154 const Entry* best = pq.Top();
157 node_active[node] =
false;
158 if (node_neighbor[node] != Graph::kNilArc) {
159 tree_arcs.push_back(node_neighbor[node]);
161 for (
const ArcIndex arc : graph.OutgoingArcs(node)) {
162 const NodeIndex neighbor = graph.Head(arc);
163 if (node_active[neighbor]) {
164 const ArcValueType value = arc_value(arc);
165 Entry& entry = entries[neighbor];
166 if (value < entry.value || !touched_entry[neighbor]) {
167 node_neighbor[neighbor] = arc;
169 touched_entry[neighbor] =
true;
170 if (pq.Contains(&entry)) {
171 pq.NoteChangedPriority(&entry);
183 #endif // OR_TOOLS_GRAPH_MINIMUM_SPANNING_TREE_H_