12 #ifndef NOM_GRAPH_GRAPH_H 13 #define NOM_GRAPH_GRAPH_H 15 #include "nomnigraph/Support/Common.h" 20 #include <unordered_set> 26 #define DEBUG_PRINT(...) ; 30 template <
typename T,
typename U = T>
class Graph;
32 template <
typename T,
typename U = T>
class Node;
39 Edge(NodeRef tail, NodeRef head) : Tail(tail), Head(head) {
40 DEBUG_PRINT(
"Creating instance of Edge: %p\n",
this);
43 Edge(NodeRef tail, NodeRef head, U &&data)
45 DEBUG_PRINT(
"Creating instance of Edge: %p\n",
this);
48 const NodeRef &tail()
const {
return Tail; }
49 const NodeRef &head()
const {
return Head; }
54 friend class Graph<T, U>;
57 template <
typename T,
typename U >
62 DEBUG_PRINT(
"Creating instance of Node: %p\n",
this);
72 void addInEdge(EdgeRef e) { inEdges.emplace_back(e); }
81 auto iter = std::find(inEdges.begin(), inEdges.end(), e);
88 auto iter = std::find(outEdges.begin(), outEdges.end(), e);
92 const std::vector<EdgeRef> &getOutEdges()
const {
return outEdges; }
93 const std::vector<EdgeRef> &getInEdges()
const {
return inEdges; }
96 std::vector<EdgeRef> inEdges;
97 std::vector<EdgeRef> outEdges;
98 friend class Graph<T, U>;
110 template <
typename T,
typename U = T>
class Subgraph {
112 Subgraph() { DEBUG_PRINT(
"Creating instance of Subgraph: %p\n",
this); }
117 void addNode(NodeRef n) { Nodes.insert(n); }
118 bool hasNode(NodeRef n)
const {
return Nodes.count(n) != 0; }
119 void removeNode(NodeRef n) { Nodes.erase(n); }
121 void addEdge(EdgeRef e) { Edges.insert(e); }
122 bool hasEdge(EdgeRef n)
const {
return Edges.count(n) != 0; }
123 void removeEdge(EdgeRef e) { Edges.erase(e); }
125 const std::unordered_set<NodeRef> &getNodes()
const {
return Nodes; }
126 const std::unordered_set<EdgeRef> &getEdges()
const {
return Edges; }
129 for (
const auto &edge : Edges) {
130 printf(
"Edge: %p (%p -> %p)\n", &edge, edge->tail(), edge->head());
134 void printNodes()
const {
135 for (
const auto &node : Nodes) {
136 printf(
"Node: %p\n", node);
140 std::unordered_set<NodeRef> Nodes;
141 std::unordered_set<EdgeRef> Edges;
148 template <
typename T,
typename U >
class Graph {
150 Graph() { DEBUG_PRINT(
"Creating instance of Graph: %p\n",
this); }
165 Nodes.emplace_back(
Node<T, U>(std::move(data)));
166 DEBUG_PRINT(
"Creating node (%p)\n", &Nodes.back());
167 return &Nodes.back();
171 std::list<Node<T, U>> &otherNodes = otherGraph.Nodes;
172 for (
auto it = Nodes.begin(); it != Nodes.end(); ++it) {
173 if (&(*it) == node) {
174 otherNodes.splice(otherNodes.end(), Nodes, it, ++it);
181 std::list<Edge<T, U>> &otherEdges = otherGraph.Edges;
182 for (
auto it = Edges.begin(); it != Edges.end(); ++it) {
183 if (&(*it) == edge) {
184 otherEdges.splice(otherEdges.end(), Edges, it, ++it);
192 DEBUG_PRINT(
"Creating node (%p)\n", &Nodes.back());
193 return &Nodes.back();
204 const NodeRef &newHead_ =
nullptr) {
207 const NodeRef newHead = newHead_ ? newHead_ : newTail;
208 const auto inEdges = old->getInEdges();
209 const auto outEdges = old->getOutEdges();
211 for (
const auto &inEdge : inEdges) {
212 createEdge(inEdge->tail(), newTail);
214 for (
const auto &inEdge : inEdges) {
218 for (
const auto &outEdge : outEdges) {
219 createEdge(newHead, outEdge->head());
221 for (
const auto &outEdge : outEdges) {
231 DEBUG_PRINT(
"Creating edge (%p -> %p)\n", tail, head);
240 DEBUG_PRINT(
"Creating edge (%p -> %p)\n", tail, head);
241 Edges.emplace_back(
Edge<T, U>(tail, head, std::move(data)));
251 for (
auto& inEdge : head->getInEdges()) {
252 if (inEdge->tail() == tail) {
256 assert(0 &&
"Edge doesn't exist.");
266 for (
auto &edge : n->inEdges) {
269 for (
auto &edge : n->outEdges) {
273 for (
auto i = Nodes.begin(); i != Nodes.end(); ++i) {
284 e->Tail->removeOutEdge(e);
285 e->Head->removeInEdge(e);
286 for (
auto i = Edges.begin(); i != Edges.end(); ++i) {
294 const std::vector<NodeRef> getMutableNodes() {
295 std::vector<NodeRef> v;
296 for (
auto &n : Nodes) {
297 DEBUG_PRINT(
"Adding node to mutable output (%p)\n", &n);
303 const std::vector<EdgeRef> getMutableEdges() {
304 std::vector<EdgeRef> v;
305 for (
auto &e : Edges) {
306 DEBUG_PRINT(
"Adding edge to mutable output (%p)\n", &e);
313 for (
const auto &edge : Edges) {
314 printf(
"Edge: %p (%p -> %p)\n", &edge, edge.tail(), edge.head());
318 void printNodes()
const {
319 for (
const auto &node : Nodes) {
320 printf(
"Node: %p\n", &node);
325 std::list<Node<T, U>> Nodes;
326 std::list<Edge<T, U>> Edges;
331 #endif // NOM_GRAPH_GRAPH_H void removeOutEdge(EdgeRef e)
Removes an edge by reference to known out-edges.
Node(T &&data)
Create a node with data.
void addOutEdge(EdgeRef e)
Adds an edge by reference to known out-edges.
Effectively a constant reference to a graph.
NodeRef createNode(T &&data)
Creates a node and retains ownership of it.
This class enables a listener pattern.
EdgeRef getEdge(NodeRef tail, NodeRef head)
Get a reference to the edge between two nodes if it exists.
void deleteNode(NodeRef n, bool deleteEdges=true)
Deletes a node from the graph.
void deleteEdge(EdgeRef e)
Deletes a edge from the graph.
void addInEdge(EdgeRef e)
Adds an edge by reference to known in-edges.
void replaceNode(const NodeRef &old, const NodeRef &newTail, const NodeRef &newHead_=nullptr)
Replace a node in the graph with a generic set of nodes.
A simple graph implementation.
EdgeRef createEdge(NodeRef tail, NodeRef head)
Creates a directed edge and retains ownership of it.
Node()
Create an empty node.
void removeInEdge(EdgeRef e)
Removes an edge by reference to known in-edges.