Skip to main content

Graph Class

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

Declaration​

class simaai::neat::graph::Graph { ... }

Included Headers​

#include <Graph.h>

Public Member Typedefs Index​

usingNodePtr = std::shared_ptr< Node >

Public Constructors Index​

Graph ()=default

Public Member Functions Index​

NodeIdadd (NodePtr node)
const NodePtr &node (NodeId id) const
std::size_tnode_count () const noexcept
boolempty () const noexcept
PortIdintern_port (std::string_view name)
const std::string &port_name (PortId id) const
std::size_tport_count () const noexcept
const std::vector< std::string > &port_names () const noexcept
voidconnect (NodeId from, NodeId to, const std::string &from_port="out", const std::string &to_port="in")
const std::vector< Edge > &edges () const noexcept
const Edge &edge (std::size_t idx) const
const std::vector< std::size_t > &out_edges (NodeId id) const
const std::vector< std::size_t > &in_edges (NodeId id) const
std::size_tout_degree (NodeId id) const
std::size_tin_degree (NodeId id) const
std::vector< NodeId >topo_order () const
boolis_dag () const

Private Member Functions Index​

voidvalidate_id_ (NodeId id, const char *where) const
boolhas_edge_ (NodeId from, NodeId to, PortId from_port, PortId to_port) const

Private Member Attributes Index​

std::vector< NodePtr >nodes_
std::vector< Edge >edges_
std::vector< std::vector< std::size_t > >out_edges_
std::vector< std::vector< std::size_t > >in_edges_
std::vector< std::string >port_names_
std::unordered_map< std::string, PortId >port_ids_

Description​

Directed acyclic graph of hybrid nodes with named ports.

Definition at line 26 of file Graph.h.

Public Member Typedefs​

NodePtr​

using simaai::neat::graph::Graph::NodePtr = std::shared_ptr<Node>

Definition at line 28 of file Graph.h.

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

Public Constructors​

Graph()​

simaai::neat::graph::Graph::Graph ()
 default

Definition at line 30 of file Graph.h.

Public Member Functions​

add()​

NodeId simaai::neat::graph::Graph::add (NodePtr node)
 inline

Definition at line 33 of file Graph.h.

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 }

connect()​

void simaai::neat::graph::Graph::connect (NodeId from, NodeId to, const std::string & from_port="out", const std::string & to_port="in")
 inline

Definition at line 87 of file Graph.h.

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 }

edge()​

const Edge& simaai::neat::graph::Graph::edge (std::size_t idx)
 inline

Definition at line 110 of file Graph.h.

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 }

edges()​

const std::vector<Edge>& simaai::neat::graph::Graph::edges ()
 inline noexcept

Definition at line 106 of file Graph.h.

106 const std::vector<Edge>& edges() const noexcept {
107 return edges_;
108 }

empty()​

bool simaai::neat::graph::Graph::empty ()
 inline noexcept

Definition at line 52 of file Graph.h.

52 bool empty() const noexcept {
53 return nodes_.empty();
54 }

in_degree()​

std::size_t simaai::neat::graph::Graph::in_degree (NodeId id)
 inline

Definition at line 132 of file Graph.h.

132 std::size_t in_degree(NodeId id) const {
133 validate_id_(id, "graph::Graph::in_degree");
134 return in_edges_[id].size();
135 }

in_edges()​

const std::vector<std::size_t>& simaai::neat::graph::Graph::in_edges (NodeId id)
 inline

Definition at line 122 of file Graph.h.

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 }

intern_port()​

PortId simaai::neat::graph::Graph::intern_port (std::string_view name)
 inline

Definition at line 57 of file Graph.h.

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 }

is_dag()​

bool simaai::neat::graph::Graph::is_dag ()
 inline

Definition at line 175 of file Graph.h.

175 bool is_dag() const {
176 try {
177 (void)topo_order();
178 return true;
179 } catch (...) {
180 return false;
181 }
182 }

node()​

const NodePtr& simaai::neat::graph::Graph::node (NodeId id)
 inline

Definition at line 44 of file Graph.h.

44 const NodePtr& node(NodeId id) const {
45 validate_id_(id, "graph::Graph::node");
46 return nodes_[id];
47 }

node_count()​

std::size_t simaai::neat::graph::Graph::node_count ()
 inline noexcept

Definition at line 49 of file Graph.h.

49 std::size_t node_count() const noexcept {
50 return nodes_.size();
51 }

out_degree()​

std::size_t simaai::neat::graph::Graph::out_degree (NodeId id)
 inline

Definition at line 127 of file Graph.h.

127 std::size_t out_degree(NodeId id) const {
128 validate_id_(id, "graph::Graph::out_degree");
129 return out_edges_[id].size();
130 }

out_edges()​

const std::vector<std::size_t>& simaai::neat::graph::Graph::out_edges (NodeId id)
 inline

Definition at line 117 of file Graph.h.

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 }

port_count()​

std::size_t simaai::neat::graph::Graph::port_count ()
 inline noexcept

Definition at line 78 of file Graph.h.

78 std::size_t port_count() const noexcept {
79 return port_names_.size();
80 }

port_name()​

const std::string& simaai::neat::graph::Graph::port_name (PortId id)
 inline

Definition at line 71 of file Graph.h.

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 }

port_names()​

const std::vector<std::string>& simaai::neat::graph::Graph::port_names ()
 inline noexcept

Definition at line 82 of file Graph.h.

82 const std::vector<std::string>& port_names() const noexcept {
83 return port_names_;
84 }

topo_order()​

std::vector<NodeId> simaai::neat::graph::Graph::topo_order ()
 inline

Definition at line 138 of file Graph.h.

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 }

Private Member Functions​

has_edge_()​

bool simaai::neat::graph::Graph::has_edge_ (NodeId from, NodeId to, PortId from_port, PortId to_port)
 inline

Definition at line 191 of file Graph.h.

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 }

validate_id_()​

void simaai::neat::graph::Graph::validate_id_ (NodeId id, const char * where)
 inline

Definition at line 185 of file Graph.h.

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 }

Private Member Attributes​

edges_​

std::vector<Edge> simaai::neat::graph::Graph::edges_

Definition at line 202 of file Graph.h.

202 std::vector<Edge> edges_;

in_edges_​

std::vector<std::vector<std::size_t> > simaai::neat::graph::Graph::in_edges_

Definition at line 204 of file Graph.h.

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

nodes_​

std::vector<NodePtr> simaai::neat::graph::Graph::nodes_

Definition at line 201 of file Graph.h.

201 std::vector<NodePtr> nodes_;

out_edges_​

std::vector<std::vector<std::size_t> > simaai::neat::graph::Graph::out_edges_

Definition at line 203 of file Graph.h.

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

port_ids_​

std::unordered_map<std::string, PortId> simaai::neat::graph::Graph::port_ids_

Definition at line 207 of file Graph.h.

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

port_names_​

std::vector<std::string> simaai::neat::graph::Graph::port_names_

Definition at line 206 of file Graph.h.

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

The documentation for this class was generated from the following file:

Generated via doxygen2docusaurus 2.0.0 by Doxygen 1.9.1.