3
\$\begingroup\$

Hi I'm trying to create a c++ code based node editor (GUI versions to be implemented). Here is how it works, each node has ports which can be of INPUT or OUTPUT (they only connect with each other so INPUT->OUTPUT or OUTPUT->INPUT).

Here is the code so far:

main.cpp

#include <iostream>
#include "addition_node.h"
#include "value_node.h"

int main() {
    value_node<double>* number1 = new value_node<double>(new double(8.0));
    value_node<double>* number2 = new value_node<double>(new double(9.0));
    value_node<double>* number3 = new value_node<double>(new double(10.0));
    addition_node<double>* add1 = new addition_node<double>();
    addition_node<double>* add2 = new addition_node<double>();
    addition_node<double>* add3 = new addition_node<double>();
    number1->out->connect_to(add1->in1);
    number2->out->connect_to(add1->in2);
    //std::cout << number1->out->disconnect_from(add1->inputs[0]) << std::endl;
    add1->out->connect_to(add2->in1);
    number2->out->connect_to(add2->in2);
    add2->out->connect_to(add3->in1);
    number3->out->connect_to(add3->in2);
    //number1->out->disconnect_from(add1->in1);
    std::cout << *add3->out->value << std::endl;
    
}

node_editor.h:

#pragma once

#include <iostream>
#include <vector>
#include <memory.h>
#include <typeinfo>

enum iotype {
    INPUT = true,
    OUTPUT = false
};
struct node;
struct port_abstract {
    node* parent = nullptr;
    std::vector<port_abstract*> connections = {};
    iotype io = INPUT;
    virtual bool connect_to(port_abstract* p);
    virtual bool disconnect_from(port_abstract* p);
    virtual void make_empty();
    virtual bool is_empty();
    virtual void give_value_to(port_abstract* p);
};

template <class T>
struct port : port_abstract {
    T* value;
    virtual bool connect_to(port_abstract* p);
    virtual bool disconnect_from(port_abstract* p);
    virtual void make_empty();
    virtual bool is_empty();
    virtual void give_value_to(port_abstract* p);
};

struct node {
    std::vector<port_abstract*> inputs, outputs;
    virtual void compute() {};
};

bool is_valid_port(port_abstract* p) {
    return p != nullptr && p->parent != nullptr;
}

void nested_compute(port_abstract* p) {
    if (is_valid_port(p)) {
        p->parent->compute();
        for (port_abstract* output : p->parent->outputs) {
            for (port_abstract* input : output->connections) {
                if (p->is_empty()) {
                    input->make_empty();
                } else {
                    output->give_value_to(input);
                }
                nested_compute(input);
            }
        }
    }
}

bool connection_check(port_abstract* p1, port_abstract* p2) {
    if (is_valid_port(p1) && is_valid_port(p2)) {
        if (p1->io == (!p2->io)) {
            std::vector<port_abstract*> ports = {};
            (p1->io ? ports = p2->parent->inputs : ports = p2->parent->outputs);
            for (port_abstract* p : ports) {
                for (port_abstract* c : p->connections) {
                    if (c->parent == p1->parent) { return false; }
                    if (!connection_check(p1, c)) { return false; }
                }
            }
            return true;
        }
        return false;
    }
    return false;
}

bool port_abstract::connect_to(port_abstract* p) {
    if (is_valid_port(p)) {
        if (
            p->io == (!io) &&
            (p->connections.size() != (p->io ? 1 : -1)) &&
            (connections.size() != (io ? 1 : -1)) &&
            connection_check(this, p)
            ) {
            connections.push_back(p);
            p->connections.push_back(this);
            (p->io ? nested_compute(p) : nested_compute(this));
            return true;
        }
        return false;
    }
    return false;
}

bool port_abstract::disconnect_from(port_abstract* p) {
    if (is_valid_port(p)) {
        size_t original_length = connections.size();
        connections.erase(std::remove(connections.begin(), connections.end(), p), connections.end());
        size_t new_length = connections.size();
        if (new_length != original_length) {
            p->connections.erase(std::remove(p->connections.begin(), p->connections.end(), this), p->connections.end());
            (p->io ? nested_compute(p) : nested_compute(this));
            return true;
        }
        return false;
    }
    return false;
}

void port_abstract::make_empty() { return; }
bool port_abstract::is_empty() { return false; }
void port_abstract::give_value_to(port_abstract* p) {}

template <class T>
bool port<T>::connect_to(port_abstract* p) {
    port<T>* p1 = dynamic_cast<port<T>*>(p);
    if (is_valid_port(p)) {
        if (
            p1 != 0 &&
            p->io == (!io) &&
            (p->connections.size() != (p->io ? 1 : -1)) &&
            (connections.size() != (io ? 1 : -1)) &&
            connection_check(this, p)
            ) {
            connections.push_back(p);
            p->connections.push_back(this);

            (p->io ? ((port<T>*)p)->value = value : value = ((port<T>*)p)->value);

            (p->io ? nested_compute(p) : nested_compute(this));
            return true;
        }
        return false;
    }
    return false;
}

template <class T>
bool port<T>::disconnect_from(port_abstract* p) {
    if (is_valid_port(p)) {
        size_t original_length = connections.size();
        connections.erase(std::remove(connections.begin(), connections.end(), p), connections.end());
        size_t new_length = connections.size();
        if (new_length != original_length) {
            p->connections.erase(std::remove(p->connections.begin(), p->connections.end(), this), p->connections.end());

            (p->io ? ((port<T>*)p)->value = nullptr : value = nullptr);

            (p->io ? nested_compute(p) : nested_compute(this));

            return true;
        }
        return false;
    }
    return false;
}

template <class T>
void port<T>::make_empty() {
    if (value) {
        value = nullptr;
        return;
    }
    return;
}
template <class T>
bool port<T>::is_empty() {
    return value == nullptr;
}

template <class T>
void port<T>::give_value_to(port_abstract* p) {
    if (is_valid_port(p)) {
        port<T>* p1 = dynamic_cast<port<T>*>(p);
        if (p1 != 0) {
            ((port<T>*)p)->value = value;
        }
    }
}

value_node.h:

#pragma once
#include "node_editor.h"
template <class T>
struct value_node : node {
    port<T>* out = nullptr;
    value_node();
    value_node(T* value);
    virtual void compute();
};

template<class T>
value_node<T>::value_node() {
    out = new port<T>();
    out->io = OUTPUT;
    out->parent = this;
    *out->value = 0;
    this->outputs.push_back(out);
}
template<class T>
value_node<T>::value_node(T* value) {
    out = new port<T>();
    out->io = OUTPUT;
    out->parent = this;
    out->value = value;
    this->outputs.push_back(out);
}
template<class T>
void value_node<T>::compute() {}

addition_node.h:

#pragma once
#include "node_editor.h"
template<class T>
struct addition_node : node {
    port<T>* in1;
    port<T>* in2;
    port<T>* out;
    addition_node();
    virtual void compute();
};

template<class T>
addition_node<T>::addition_node() {
    in1 = new port<T>();
    in2 = new port<T>();
    out = new port<T>();
    out->io = OUTPUT;
    in1->parent = this;
    in2->parent = this;
    out->parent = this;
    this->inputs.push_back(in1);
    this->inputs.push_back(in2);
    this->outputs.push_back(out);
}
template<class T>
void addition_node<T>::compute() {
    std::cout << "compute" << std::endl;
    if (in1 && in2) {
        if (in1->value && in2->value) {
            out->value = new T;
            *out->value = *in1->value + *in2->value;
            return;
        }
    }
    //std::cout << '0' << std::endl;
    out->value = nullptr;
}

Any advice is greatly appreciated!

\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

I just recently wrote a similar bit of code, and I put it through half a dozen iterations before I was finally happy with it. Along the way, I ran into several issues you're probably encountering with this system. I'll talk through some of the pitfalls I ran into and how I dealt with them. Before that, here are some more general modifications I'd suggest...

Physical State vs. Logical State

Don't expose implementation -- C++ allows for access modifiers for exactly this purpose. For logical abstractions like this, favor classes and keep internal implementation (like pointers to parent and child nodes/ports) private. PHYSICAL state shouldn't matter to the user -- the values of your class's internal members. LOGICAL state should be accessible and (where applicable) mutable to the user. A connection is a logical abstraction from a set of child-to-parent pointers -- let the user think about the connection, you mess with the pointers.

Along the same vein, the current design has too much latitude -- writing a check to ensure that two output ports aren't connected should hint to you that you are exposing too much functionality to the client code. If output ports shouldn't be connected together, your code should never allow it to happen.

As for the node system and its implementation, there are several design choices to be made. First is your choice to tackle this problem with polymorphism -- a natural place to go given that every type of node is-a node. Each node contains a list of inputs and outputs. A drawback to this design choice is that the evaluation algorithm is tightly coupled to the hierarchy itself. A potential alternative would be to have a free function to traverse the hierarchy and evaluate it:

    template <typename T> T evaluate(port<T> port) {
        // ...
    }

This allows slightly more latitude, as the internal node implementation no longer matters as long as the interface the function used to traverse the node graph doesn't change. The decreased coupling means that you could do something like this if you ever needed to:

    template <typename T> std::string asExpression(port<T> port) {
        // Returns the string "(2 * 3) + 2"
    }
    
    template <typename T> T evaluate(port<T> port) {
        // Returns the number 8
    }

Memory Management

Another drawback of using polymorphism is copy semantics. Consider the factory method:

    node<float> getSomeUsefulFunction() {
        // ...
    }

How is this function implemented? If we create several node instances on the stack, point them at each other and return the root, its parent nodes go out of scope and we get an access violation trying to evaluate the result. Do we allocate heap memory for those nodes? Who deletes them? How do you decide which ones to delete? If a node has the same parent for two inputs, a naive algorithm could accidentally delete an object twice. Even if you decide who owns what and who deletes what, you'd still have problems if you ever wanted to copy-construct the whole hierarchy. You don't know the type of each node, so you can't simply copy-construct them. The typical solution to this dilemma is often known as the prototype pattern -- each node must implement a virtual clone method returning a node instance of the same type and with identical fields. Here again you run into memory management issues -- how do you allocate and manage memory you create within clone()?

You could try to use shared memory by only using shared pointers to these structures, or specifically enforcing it by making node structures work like shared pointers to an internal implementation. However, with this method, we no longer have a zero-cost abstraction -- we're using garbage collection. More importantly, though, does this choice properly reflect the intent of your program -- are the nodes supposed to have shared ownership? It might be a better idea to create a class to represent a node graph and force nodes to be created as part of a node graph. This way ownership is clear and undisputed. This means that the factory from earlier could be modified like this:

    node_graph<float> getSomeUsefulFunction() {
        node_graph<float> graph;
        node<float>& n = // note the return by reference -- the memory is acquired
                         // and initialized by the node_graph and you get a handle
            graph.add_node();
        // ...
        return graph; // Copy constructor implementation here is critical
    }

At this point, you could even reference input/output nodes simply by their index within the node_graph's internal node container (although this quickly creates a problem for insertion or removal of nodes -- but it makes copying the structure much easier).

This brings me to the non-polymorphic node class. Instead of making a subclass for every different function, you could add a separate field, possibly an enum, to track the node's function. In other words, replace addition_node, multiplication_node, etc. with node(func::add), node(func::multiply), etc. It might look like this:

    enum class node_func { add, subtract, value };
    
    template <typename T> class node {
    public:
        node_func func;
        T value;
    }

    template <typename T> T evaluate(node<T> n) {
        switch (n.func) {
        case node_func::value:
            return n.value;
        case node_func::add:
            return evaluate(*n.input[0]) + evaluate(*n.input[1]);
        // etc.
        }
    }

As long as your node_graph's copy and move constructors are properly implemented, you won't have problems with access violations because all the nodes used in the graph come with it in the copy/move. You won't have problems with deleting because the graph can simply delete all of its nodes when it goes out of scope with the assurance that nothing else should be referencing the nodes within that system.

The biggest drawback for this design lies within the copy/move functionality. Because the nodes would all contain pointers to nodes memory-managed by their parent node_graph, the node_graph would need to take special care to make sure all of these pointers are valid. A possible algorithm might look something like this:

    node_graph::node_graph(const node_graph& other) {
        m_nodes = other.m_nodes;
        for (node& n : m_nodes) {
            // for each pointer, get the index in 'other' of the node it points to
            // set that pointer to point at our own node at that index
        }
    }

Recursion

One final consideration is recursion -- what happens when you connect a node's output to a node that eventually drives it? Your evaluation code will go on forever. Note that with the free-function design I proposed earlier, your code wouldn't necessarily ever encounter a problem with recursion -- for example, if you used the system to represent a set of logic gates and you wanted to simulate signals propagating through, recursion would be a common occurrence. Your evaluation function could then simply use only the current input values to advance the simulation instead of recursing all the way down the hierarchy into an infinite loop. Thus, recursion within a node graph system is not inherently evil. That said, you're still best off adding a function to traverse the hierarchy and detect loops. That way, when a recursive setup would result in an infinite evaluation, you can handle the case before you attempt to evaluate.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Welcome to Code Review. Very nice in depth review. \$\endgroup\$
    – pacmaninbw
    Aug 3, 2020 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.