`Graph.h` File

Runtime graph::Graph — actor-style DAG with named ports for the runtime. More...

Included Headers

#include "graph/GraphTypes.h" #include "graph/Node.h" #include <cstddef> #include <memory> #include <queue> #include <stdexcept> #include <string> #include <string_view> #include <unordered_map> #include <utility> #include <vector>

Namespaces Index

namespace	simaai


namespace	neat


namespace	graph

Classes Index

class	Graph
	Directed acyclic graph of hybrid nodes with named ports. More...

Description

Runtime graph::Graph — actor-style DAG with named ports for the runtime.

This is the framework's runtime graph — a different type from the builder-side simaai::neat::Graph. The runtime graph carries named ports (e.g., "out", "in"), interned to compact PortIds, so a node can have multiple distinct inputs and outputs that the executor can route between. It's the substrate the actor-style runtime uses for stage scheduling and mailbox-based message passing.

Use the builder Graph (in include/builder/Graph.h) when you're authoring a pipeline shape; use this runtime Graph only if you're building a runtime-graph-driven Session via GraphSession.

See Also: GraphSession, GraphRun, StageExecutor

See Also: "The two graph systems" (§0.14 / §73 of the design deep dive)

File Listing

The file content with the documentation metadata removed is:

19#pragma once

21#include "graph/GraphTypes.h"

22#include "graph/Node.h"

24#include <cstddef>

25#include <memory>

26#include <queue>

27#include <stdexcept>

28#include <string>

29#include <string_view>

30#include <unordered_map>

31#include <utility>

32#include <vector>

34namespace simaai::neat::graph {

50class Graph final {

51public:

53 using NodePtr = std::shared_ptr<Node>;

56 Graph() = default;

58 // ---------------------------

59 // Node management

60 // ---------------------------

67 NodeId add(NodePtr node) {

68 if (!node) {

69 throw std::invalid_argument("graph::Graph::add: node is null");

70 }

71 const NodeId id = nodes_.size();

72 nodes_.push_back(std::move(node));

73 out_edges_.emplace_back();

74 in_edges_.emplace_back();

75 return id;

76 }

79 const NodePtr& node(NodeId id) const {

80 validate_id_(id, "graph::Graph::node");

81 return nodes_[id];

82 }

85 std::size_t node_count() const noexcept {

86 return nodes_.size();

87 }

89 bool empty() const noexcept {

90 return nodes_.empty();

91 }

93 // ---------------------------

94 // Port interning

95 // ---------------------------

105 PortId intern_port(std::string_view name) {

106 const std::string key(name);

107 if (key.empty()) {

108 throw std::invalid_argument("graph::Graph::intern_port: empty port name");

109 }

110 auto it = port_ids_.find(key);

111 if (it != port_ids_.end())

112 return it->second;

113 const PortId id = static_cast<PortId>(port_names_.size());

114 port_names_.push_back(key);

115 port_ids_.emplace(port_names_.back(), id);

116 return id;

117 }

118

120 const std::string& port_name(PortId id) const {

121 if (id >= port_names_.size()) {

122 throw std::out_of_range("graph::Graph::port_name: invalid port id");

123 }

124 return port_names_[id];

125 }

126

128 std::size_t port_count() const noexcept {

129 return port_names_.size();

130 }

131

133 const std::vector<std::string>& port_names() const noexcept {

134 return port_names_;

135 }

136

137 // ---------------------------

138 // Edge management

139 // ---------------------------

140

153 void connect(NodeId from, NodeId to, const std::string& from_port = "out",

154 const std::string& to_port = "in") {

155 validate_id_(from, "graph::Graph::connect(from)");

156 validate_id_(to, "graph::Graph::connect(to)");

157 if (from == to) {

158 throw std::invalid_argument("graph::Graph::connect: self-loop is not allowed");

159 }

160 const PortId f = intern_port(from_port);

161 const PortId t = intern_port(to_port);

162

163 if (has_edge_(from, to, f, t))

164 return;

165

166 edges_.push_back({from, f, to, t});

167 const std::size_t idx = edges_.size() - 1;

168 out_edges_[from].push_back(idx);

169 in_edges_[to].push_back(idx);

170 }

171

173 const std::vector<Edge>& edges() const noexcept {

174 return edges_;

175 }

176

178 const Edge& edge(std::size_t idx) const {

179 if (idx >= edges_.size()) {

180 throw std::out_of_range("graph::Graph::edge: invalid index");

181 }

182 return edges_[idx];

183 }

184

186 const std::vector<std::size_t>& out_edges(NodeId id) const {

187 validate_id_(id, "graph::Graph::out_edges");

188 return out_edges_[id];

189 }

190

192 const std::vector<std::size_t>& in_edges(NodeId id) const {

193 validate_id_(id, "graph::Graph::in_edges");

194 return in_edges_[id];

195 }

196

198 std::size_t out_degree(NodeId id) const {

199 validate_id_(id, "graph::Graph::out_degree");

200 return out_edges_[id].size();

201 }

202

204 std::size_t in_degree(NodeId id) const {

205 validate_id_(id, "graph::Graph::in_degree");

206 return in_edges_[id].size();

207 }

208

209 // ---------------------------

210 // Topological order

211 // ---------------------------

212

217 std::vector<NodeId> topo_order() const {

218 const std::size_t n = nodes_.size();

219 std::vector<std::size_t> indeg(n, 0);

220 for (NodeId i = 0; i < n; ++i)

221 indeg[i] = in_edges_[i].size();

222

223 std::queue<NodeId> q;

224 for (NodeId i = 0; i < n; ++i) {

225 if (indeg[i] == 0)

226 q.push(i);

227 }

228

229 std::vector<NodeId> order;

230 order.reserve(n);

231

232 while (!q.empty()) {

233 NodeId u = q.front();

234 q.pop();

235 order.push_back(u);

236

237 for (const std::size_t eidx : out_edges_[u]) {

238 const Edge& e = edges_[eidx];

239 if (indeg[e.to] == 0) {

240 continue;

241 }

242 indeg[e.to]--;

243 if (indeg[e.to] == 0)

244 q.push(e.to);

245 }

246 }

247

248 if (order.size() != n) {

249 throw std::runtime_error("graph::Graph::topo_order: cycle detected (graph is not a DAG)");

250 }

251 return order;

252 }

253

255 bool is_dag() const {

256 try {

257 (void)topo_order();

258 return true;

259 } catch (...) {

260 return false;

261 }

262 }

263

264private:

265 void validate_id_(NodeId id, const char* where) const {

266 if (id >= nodes_.size()) {

267 throw std::out_of_range(std::string(where) + ": invalid NodeId");

268 }

269 }

270

271 bool has_edge_(NodeId from, NodeId to, PortId from_port, PortId to_port) const {

272 for (const std::size_t eidx : out_edges_[from]) {

273 const Edge& e = edges_[eidx];

274 if (e.from == from && e.to == to && e.from_port == from_port && e.to_port == to_port) {

275 return true;

276 }

277 }

278 return false;

279 }

280

281 std::vector<NodePtr> nodes_;

282 std::vector<Edge> edges_;

283 std::vector<std::vector<std::size_t>> out_edges_;

284 std::vector<std::vector<std::size_t>> in_edges_;

285

286 std::vector<std::string> port_names_;

287 std::unordered_map<std::string, PortId> port_ids_;

288};

289

290} // namespace simaai::neat::graph

Generated via doxygen2docusaurus 2.0.0 by Doxygen 1.9.8.

Included Headers​

Namespaces Index​

Classes Index​

Description​

File Listing​

Included Headers

Namespaces Index

Classes Index

Description

File Listing