14#ifndef OR_TOOLS_GRAPH_MINIMUM_SPANNING_TREE_H_
15#define OR_TOOLS_GRAPH_MINIMUM_SPANNING_TREE_H_
48template <
typename Graph>
49std::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);
65 while (tree_arcs.size() != expected_tree_size && arc_index < num_arcs) {
66 const ArcIndex arc = sorted_arcs[arc_index];
67 const auto tail = graph.Tail(arc);
68 const auto head = graph.Head(arc);
71 tree_arcs.push_back(arc);
88template <
typename Graph,
typename ArcComparator>
90 const Graph& graph,
const ArcComparator& arc_comparator) {
92 std::vector<ArcIndex> sorted_arcs(graph.num_arcs());
93 for (
const ArcIndex arc : graph.AllForwardArcs()) {
94 sorted_arcs[arc] = arc;
96 std::sort(sorted_arcs.begin(), sorted_arcs.end(), arc_comparator);
114template <
typename Graph,
typename ArcValue>
116 const Graph& graph,
const ArcValue& arc_value) {
119 using ArcValueType =
decltype(arc_value(0));
120 std::vector<ArcIndex> tree_arcs;
121 if (graph.num_nodes() == 0) {
124 const int expected_tree_size = graph.num_nodes() - 1;
125 tree_arcs.reserve(expected_tree_size);
126 std::vector<ArcIndex> node_neighbor(graph.num_nodes(), Graph::kNilArc);
127 std::vector<bool> node_active(graph.num_nodes(),
true);
134 void SetHeapIndex(
int index) { heap_index =
index; }
135 int GetHeapIndex()
const {
return heap_index; }
136 bool operator<(
const Entry& other)
const {
return value > other.value; }
144 std::vector<Entry> entries;
145 std::vector<bool> touched_entry(graph.num_nodes(),
false);
146 for (
NodeIndex node : graph.AllNodes()) {
149 entries[0].value = 0;
151 while (!pq.
IsEmpty() && tree_arcs.size() != expected_tree_size) {
152 const Entry* best = pq.
Top();
155 node_active[node] =
false;
156 if (node_neighbor[node] != Graph::kNilArc) {
157 tree_arcs.push_back(node_neighbor[node]);
159 for (
const ArcIndex arc : graph.OutgoingArcs(node)) {
160 const NodeIndex neighbor = graph.Head(arc);
161 if (node_active[neighbor]) {
162 const ArcValueType
value = arc_value(arc);
163 Entry& entry = entries[neighbor];
164 if (
value < entry.value || !touched_entry[neighbor]) {
165 node_neighbor[neighbor] = arc;
167 touched_entry[neighbor] =
true;
void NoteChangedPriority(T *val)
bool Contains(const T *val) const
void AddEdge(int node1, int node2)
bool Connected(int node1, int node2)
void SetNumberOfNodes(int num_nodes)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::vector< typename Graph::ArcIndex > BuildPrimMinimumSpanningTree(const Graph &graph, const ArcValue &arc_value)
std::vector< typename Graph::ArcIndex > BuildKruskalMinimumSpanningTreeFromSortedArcs(const Graph &graph, const std::vector< typename Graph::ArcIndex > &sorted_arcs)
std::vector< typename Graph::ArcIndex > BuildKruskalMinimumSpanningTree(const Graph &graph, const ArcComparator &arc_comparator)