50 const Graph& graph,

51 absl::Span<const typename Graph::ArcIndex> sorted_arcs) {

53 const int num_arcs = graph.num_arcs();

54 int arc_index = 0;

55 std::vector<ArcIndex> tree_arcs;

57 return tree_arcs;

58 }

59 const int expected_tree_size = graph.num_nodes() - 1;

60 tree_arcs.reserve(expected_tree_size);

63 while (tree_arcs.size() != expected_tree_size && arc_index < num_arcs) {

64 const ArcIndex arc = sorted_arcs[arc_index];

65 const auto tail = graph.Tail(arc);

66 const auto head = graph.Head(arc);

67 if (!components.Connected(tail, head)) {

68 components.AddEdge(tail, head);

69 tree_arcs.push_back(arc);

70 }

71 ++arc_index;

72 }

73 return tree_arcs;

74}

88 const Graph& graph, const ArcComparator& arc_comparator) {

90 std::vector<ArcIndex> sorted_arcs(graph.num_arcs());

92 sorted_arcs[arc] = arc;

93 }

94 std::sort(sorted_arcs.begin(), sorted_arcs.end(), arc_comparator);

96}

114 const Graph& graph, const ArcValue& arc_value) {

117 using ArcValueType = decltype(arc_value(0));

118 std::vector<ArcIndex> tree_arcs;

120 return tree_arcs;

121 }

122 const int expected_tree_size = graph.num_nodes() - 1;

123 tree_arcs.reserve(expected_tree_size);

125 std::vector<bool> node_active(graph.num_nodes(), true);

126

127

128

129

130

131 struct Entry {

132 void SetHeapIndex(int index) { heap_index = index; }

133 int GetHeapIndex() const { return heap_index; }

134 bool operator<(const Entry& other) const { return value > other.value; }

135

136

137

138

139 ArcValueType value;

141 int heap_index;

142 };

143

145 std::vector<Entry> entries;

146 std::vector<bool> touched_entry(graph.num_nodes(), false);

148 entries.push_back({.value = std::numeric_limits<ArcValueType>::max(),

149 .node = node,

150 .heap_index = -1});

151 }

152 entries[0].value = 0;

153 pq.Add(&entries[0]);

154 while (!pq.IsEmpty() && tree_arcs.size() != expected_tree_size) {

155 const Entry* best = pq.Top();

156 const NodeIndex node = best->node;

157 pq.Pop();

158 node_active[node] = false;

160 tree_arcs.push_back(node_neighbor[node]);

161 }

162 for (const ArcIndex arc : graph.OutgoingArcs(node)) {

164 if (node_active[neighbor]) {

165 const ArcValueType value = arc_value(arc);

166 Entry& entry = entries[neighbor];

167 if (value < entry.value || !touched_entry[neighbor]) {

168 node_neighbor[neighbor] = arc;

169 entry.value = value;

170 touched_entry[neighbor] = true;

173 } else {

174 pq.Add(&entry);

175 }

176 }

177 }

178 }

179 }

180 return tree_arcs;

181}

bool Contains(const T *val) const

void NoteChangedPriority(T *val)

bool Connected(int node1, int node2)

bool AddEdge(int node1, int node2)

void SetNumberOfNodes(int num_nodes)

IntegerRange< ArcIndex > AllForwardArcs() const

NodeIndexType num_nodes() const

ArcIndexType num_arcs() const

static constexpr int32_t kNilArc

IntegerRange< NodeIndex > AllNodes() const

NodeIndexType Tail(ArcIndexType arc) const

IntegerRange< ArcIndexType > OutgoingArcs(NodeIndexType node) const

NodeIndexType Head(ArcIndexType arc) const

BlossomGraph::NodeIndex NodeIndex

std::vector< typename Graph::ArcIndex > BuildPrimMinimumSpanningTree(const Graph &graph, const ArcValue &arc_value)

Definition minimum_spanning_tree.h:113

std::vector< typename Graph::ArcIndex > BuildKruskalMinimumSpanningTreeFromSortedArcs(const Graph &graph, absl::Span< const typename Graph::ArcIndex > sorted_arcs)

Definition minimum_spanning_tree.h:49

util::ReverseArcStaticGraph Graph

std::vector< typename Graph::ArcIndex > BuildKruskalMinimumSpanningTree(const Graph &graph, const ArcComparator &arc_comparator)

Definition minimum_spanning_tree.h:87