Skip to main content

Graph.h File

Hybrid graph DAG with port interning (STL-only). 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​

namespacesimaai
namespaceneat
namespacegraph

Classes Index​

classGraph

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

Description​

Hybrid graph DAG with port interning (STL-only).

File Listing​

The file content with the documentation metadata removed is:

1
6#pragma once
7
8#include "graph/GraphTypes.h"
9#include "graph/Node.h"
10
11#include <cstddef>
12#include <memory>
13#include <queue>
14#include <stdexcept>
15#include <string>
16#include <string_view>
17#include <unordered_map>
18#include <utility>
19#include <vector>
20
21namespace simaai::neat::graph {
22
26class Graph final {
27public:
28 using NodePtr = std::shared_ptr<Node>;
29
30 Graph() = default;
31
32 // Node management
33 NodeId add(NodePtr node) {
34 if (!node) {
35 throw std::invalid_argument("graph::Graph::add: node is null");
36 }
37 const NodeId id = nodes_.size();
38 nodes_.push_back(std::move(node));
39 out_edges_.emplace_back();
40 in_edges_.emplace_back();
41 return id;
42 }
43
44 const NodePtr& node(NodeId id) const {
45 validate_id_(id, "graph::Graph::node");
46 return nodes_[id];
47 }
48
49 std::size_t node_count() const noexcept {
50 return nodes_.size();
51 }
52 bool empty() const noexcept {
53 return nodes_.empty();
54 }
55
56 // Port interning
57 PortId intern_port(std::string_view name) {
58 const std::string key(name);
59 if (key.empty()) {
60 throw std::invalid_argument("graph::Graph::intern_port: empty port name");
61 }
62 auto it = port_ids_.find(key);
63 if (it != port_ids_.end())
64 return it->second;
65 const PortId id = static_cast<PortId>(port_names_.size());
66 port_names_.push_back(key);
67 port_ids_.emplace(port_names_.back(), id);
68 return id;
69 }
70
71 const std::string& port_name(PortId id) const {
72 if (id >= port_names_.size()) {
73 throw std::out_of_range("graph::Graph::port_name: invalid port id");
74 }
75 return port_names_[id];
76 }
77
78 std::size_t port_count() const noexcept {
79 return port_names_.size();
80 }
81
82 const std::vector<std::string>& port_names() const noexcept {
83 return port_names_;
84 }
85
86 // Edge management
87 void connect(NodeId from, NodeId to, const std::string& from_port = "out",
88 const std::string& to_port = "in") {
89 validate_id_(from, "graph::Graph::connect(from)");
90 validate_id_(to, "graph::Graph::connect(to)");
91 if (from == to) {
92 throw std::invalid_argument("graph::Graph::connect: self-loop is not allowed");
93 }
94 const PortId f = intern_port(from_port);
95 const PortId t = intern_port(to_port);
96
97 if (has_edge_(from, to, f, t))
98 return;
99
100 edges_.push_back({from, f, to, t});
101 const std::size_t idx = edges_.size() - 1;
102 out_edges_[from].push_back(idx);
103 in_edges_[to].push_back(idx);
104 }
105
106 const std::vector<Edge>& edges() const noexcept {
107 return edges_;
108 }
109
110 const Edge& edge(std::size_t idx) const {
111 if (idx >= edges_.size()) {
112 throw std::out_of_range("graph::Graph::edge: invalid index");
113 }
114 return edges_[idx];
115 }
116
117 const std::vector<std::size_t>& out_edges(NodeId id) const {
118 validate_id_(id, "graph::Graph::out_edges");
119 return out_edges_[id];
120 }
121
122 const std::vector<std::size_t>& in_edges(NodeId id) const {
123 validate_id_(id, "graph::Graph::in_edges");
124 return in_edges_[id];
125 }
126
127 std::size_t out_degree(NodeId id) const {
128 validate_id_(id, "graph::Graph::out_degree");
129 return out_edges_[id].size();
130 }
131
132 std::size_t in_degree(NodeId id) const {
133 validate_id_(id, "graph::Graph::in_degree");
134 return in_edges_[id].size();
135 }
136
137 // Topological order
138 std::vector<NodeId> topo_order() const {
139 const std::size_t n = nodes_.size();
140 std::vector<std::size_t> indeg(n, 0);
141 for (NodeId i = 0; i < n; ++i)
142 indeg[i] = in_edges_[i].size();
143
144 std::queue<NodeId> q;
145 for (NodeId i = 0; i < n; ++i) {
146 if (indeg[i] == 0)
147 q.push(i);
148 }
149
150 std::vector<NodeId> order;
151 order.reserve(n);
152
153 while (!q.empty()) {
154 NodeId u = q.front();
155 q.pop();
156 order.push_back(u);
157
158 for (const std::size_t eidx : out_edges_[u]) {
159 const Edge& e = edges_[eidx];
160 if (indeg[e.to] == 0) {
161 continue;
162 }
163 indeg[e.to]--;
164 if (indeg[e.to] == 0)
165 q.push(e.to);
166 }
167 }
168
169 if (order.size() != n) {
170 throw std::runtime_error("graph::Graph::topo_order: cycle detected (graph is not a DAG)");
171 }
172 return order;
173 }
174
175 bool is_dag() const {
176 try {
177 (void)topo_order();
178 return true;
179 } catch (...) {
180 return false;
181 }
182 }
183
184private:
185 void validate_id_(NodeId id, const char* where) const {
186 if (id >= nodes_.size()) {
187 throw std::out_of_range(std::string(where) + ": invalid NodeId");
188 }
189 }
190
191 bool has_edge_(NodeId from, NodeId to, PortId from_port, PortId to_port) const {
192 for (const std::size_t eidx : out_edges_[from]) {
193 const Edge& e = edges_[eidx];
194 if (e.from == from && e.to == to && e.from_port == from_port && e.to_port == to_port) {
195 return true;
196 }
197 }
198 return false;
199 }
200
201 std::vector<NodePtr> nodes_;
202 std::vector<Edge> edges_;
203 std::vector<std::vector<std::size_t>> out_edges_;
204 std::vector<std::vector<std::size_t>> in_edges_;
205
206 std::vector<std::string> port_names_;
207 std::unordered_map<std::string, PortId> port_ids_;
208};
209
210} // namespace simaai::neat::graph

Generated via doxygen2docusaurus 2.0.0 by Doxygen 1.9.1.