102 NodeIndex num_nodes,

103 NodeIndex source) {

104 if (source < 0 || source >= num_nodes) {

105 return absl::InvalidArgumentError(

106 absl::StrFormat("Invalid graph: source=%d is not in [0, num_nodes=%d)",

107 source, num_nodes));

108 }

109

110

111

112 constexpr NodeIndex kNone = -1;

113 std::vector<NodeIndex> bfs_tree(num_nodes, kNone);

114 bfs_tree[source] = source;

115 std::vector<NodeIndex> bfs_queue = {source};

116 size_t num_visited = 0;

117 while (num_visited < bfs_queue.size()) {

118 const NodeIndex node = bfs_queue[num_visited++];

119 for (const NodeIndex child : graph[node]) {

120 if (child < 0 || child >= num_nodes) {

121 return absl::InvalidArgumentError(

122 absl::StrFormat("Invalid graph: graph[%d] contains %d, which is "

123 "not a valid node index in [0, num_nodes=%d)",

124 node, child, num_nodes));

125 }

126 if (bfs_tree[child] != kNone) continue;

127 bfs_tree[child] = node;

128 bfs_queue.push_back(child);

129 }

130 }

131 return bfs_tree;

132}

136 const std::vector<NodeIndex>& bfs_tree) {

137 const NodeIndex n = bfs_tree.size();

138 constexpr NodeIndex kNone = -1;

139

140

141 constexpr NodeIndex kMaxNodeIndex = std::numeric_limits<NodeIndex>::max();

142 if (bfs_tree.size() > kMaxNodeIndex) {

143 return absl::InvalidArgumentError(absl::StrFormat(

144 "bfs_tree.size()=%d is too large for its integer node type (max=%d)",

145 bfs_tree.size(), kMaxNodeIndex));

146 }

147 for (NodeIndex i = 0; i < n; ++i) {

148 const NodeIndex parent = bfs_tree[i];

149 if (parent != kNone && (parent < 0 || parent >= n)) {

150 return absl::InvalidArgumentError(absl::StrFormat(

151 "bfs_tree[%d]=%d is outside [0, bfs_tree.size()=%d)", i, parent, n));

152 }

153 }

154

155

156 std::vector<NodeIndex> distance(n, kNone);

157 for (NodeIndex i = 0; i < n; ++i) {

158 if (bfs_tree[i] == kNone) continue;

159

160

161 NodeIndex p = i;

162 NodeIndex dist = 0;

163 while (bfs_tree[p] != p && distance[p] == kNone) {

164 p = bfs_tree[p];

165 ++dist;

166 if (dist >= n) {

167 return absl::InvalidArgumentError(

168 absl::StrFormat("bfs_tree isn't a BFS tree: detected a cycle in"

169 " the ascendance of node %d",

170 i));

171 }

172 if (p == kNone) {

173 return absl::InvalidArgumentError(

174 absl::StrFormat("bfs_tree isn't a BFS tree: detected an"

175 " interrupted ascendance from %d",

176 i));

177 }

178 }

179

180 if (bfs_tree[p] == p) distance[p] = 0;

181 dist += distance[p];

182

183

184 const NodeIndex known_node = p;

185 p = i;

186 while (p != known_node) {

187 distance[p] = dist;

188 --dist;

189 p = bfs_tree[p];

190 }

191 }

192 return distance;

193}

197 const std::vector<NodeIndex>& bfs_tree, NodeIndex target) {

198 const NodeIndex n = bfs_tree.size();

199 if (target < 0 || target >= n) {

200 return absl::InvalidArgumentError(absl::StrFormat(

201 "target=%d is outside [0, bfs_tree.size()=%d)", target, n));

202 }

203

204 std::vector<NodeIndex> path;

205 constexpr NodeIndex kNone = -1;

206 if (bfs_tree[target] == kNone) return path;

207 while (true) {

208 if (path.size() >= bfs_tree.size()) {

209 return absl::InvalidArgumentError(

210 absl::StrFormat("bfs_tree isn't a BFS tree: detected a cycle in"

211 " the ascendance of node %d",

212 target));

213 }

214 path.push_back(target);

215 const NodeIndex new_target = bfs_tree[target];

216 if (new_target == target) break;

217 if (new_target < 0 || new_target >= n) {

218 return absl::InvalidArgumentError(

219 absl::StrFormat("bfs_tree[%d]=%d is outside [0, bfs_tree.size()=%d)",

220 target, new_target, n));

221 }

222 target = new_target;

223 }

224 std::reverse(path.begin(), path.end());

225 return path;

226}