Node graph implementation for a material system

Question

I'm working on a material/shader graph system. I came up with a simple solution, but nodes that weren't connected were used in some situations. So, I thought of using Kahn's algorithm to execute nodes' tasks. I'm not quite sure if it's a proper implementation.

I've only played with it, so it's a single file to avoid jumping between many files.

https://godbolt.org/z/8hYEWbGsv

includes

#include <iostream>
#include <ranges>
#include <vector>
#include <cinttypes>
#include <memory_resource>

There is a generic DAG class that references Nodes and Edges. It also sorts and executes nodes' code - DAG::Execute() function

struct DAG 
{
    DAG()
    {
        nodes.reserve(16);
        edges.reserve(32);
    }
    ~DAG() = default;
    DAG(const DAG&) = delete;
    DAG& operator=(const DAG&) = delete;

    struct Node 
    {
        Node(DAG& dag)
            : id(dag.AddNode(this))
        {
        }
        virtual ~Node() = default;

        Node(const Node&) = delete;
        Node& operator=(const Node&) = delete;

        virtual void Execute() = 0;

        [[nodiscard]] inline std::size_t getID() const { return id; }
        [[nodiscard]] inline std::uint32_t getRefCount() const { return refCount; }

        inline void MakeTarget() { target = true; }
        [[nodiscard]] inline bool isTarget() const { return target; }

    private:
        friend struct DAG;

        std::uint32_t refCount = 0;
        const std::size_t id = 0;
        bool target = false;
    };

    struct Edge
    {
        Edge(DAG& dag, const std::size_t fromNode, const std::size_t toNode)
            : fromNode(fromNode), toNode(toNode)
        {
            dag.AddEdge(this);
        }

        Edge(const Edge&) = delete;
        Edge& operator=(const Edge& rhs) = delete;

        const std::size_t fromNode = 0;
        const std::size_t toNode = 0;
    };

    [[nodiscard]] inline auto getOutgoingEdges(const Node* const node)
    {
        return edges | std::views::filter([node](const Edge* const edge) { return edge->fromNode == node->getID(); });
    }

    [[nodiscard]] inline auto getIncomingEdges(const Node* const node)
    {
        return edges | std::views::filter([node](const Edge* const edge) { return edge->toNode == node->getID(); });
    }

    void Execute();

private:
    [[nodiscard]] inline std::size_t AddNode(Node* node)
    {
        std::size_t id = nodes.size();
        nodes.push_back(node);
        return id;
    }

    inline void AddEdge(Edge* edge)
    {
        edges.push_back(edge);
    }

    std::vector<Node*> nodes;
    std::vector<Edge*> edges;
};

void DAG::Execute()
{
    //Reset nodes refCount before sorting
    for (Node* const node : nodes) {
        node->refCount = 0;
    }

    for (const Edge* const edge : edges) {
        Node* const node = nodes[edge->fromNode];
        node->refCount++;
    }

    std::vector<Node*> stack;
    for (Node* const node : nodes) {
        if (node->getRefCount() == 0) {
            stack.push_back(node);
        }
    }

    while (!stack.empty()) {
        Node* const node = stack.back();
        stack.pop_back();

        //If the current node is not a target
        //and if it hasn't got out edges
        //don't execute the Node::Execute() function
        //and don't process it's incoming edges
        auto&& outEdges = getOutgoingEdges(node);
        if (outEdges.empty() && !node->isTarget()) {
            continue;
        }

        node->Execute();

        auto&& edges = getIncomingEdges(node);
        for (const Edge* const edge : edges) {
            Node* const linkedNode = nodes[edge->fromNode];
            if (--linkedNode->refCount == 0) {
                stack.push_back(linkedNode);
            }
        }
    }
}

What I'm not sure in DAG::Execute() function is this part:

auto&& outEdges = getOutgoingEdges(node);
if (outEdges.empty() && !node->isTarget()) {
    continue;
}

I don't even know why, but it just feels not right. It's not a standard Kahn algorithm, but I need it to cull not connected nodes. See the results at the end of this question.

The final Node, Edge and Pin look like this:

struct Graph;

struct Node : DAG::Node
{
    Node(Graph& g, const std::string_view name);

    void Execute() override;

    inline void AddInput(const std::size_t pinID) { inputs.push_back(pinID); }
    inline void AddOuput(const std::size_t outputID) { outputs.push_back(outputID); }

    [[nodiscard]] inline const std::string& getName() const { return name; }

    [[nodiscard]] inline const std::vector<size_t>& getInputs() const { return inputs; }
    [[nodiscard]] inline const std::vector<size_t>& getOutputs() const { return outputs; }

    [[nodiscard]] inline bool hasInputs() const { return !inputs.empty(); }
    [[nodiscard]] inline bool hasOutputs() const { return !outputs.empty(); }

private:
    std::vector<std::size_t> inputs;
    std::vector<std::size_t> outputs;

    Graph& g;
    const std::string name;
};

struct Pin
{
    Pin(const std::string_view name, const std::size_t id, const std::size_t nodeID)
        : name(name), id(id), nodeID(nodeID)
    {
    }

    [[nodiscard]] inline std::size_t getID() const { return id; }
    [[nodiscard]] inline std::size_t getNodeID() const { return nodeID; }
    [[nodiscard]] inline std::uint32_t getRefCount() const { return refCount; }
    [[nodiscard]] inline bool isCulled() const { return refCount == 0; }

    [[nodiscard]] inline const std::string& getName() const { return name; }

    inline void IncrementRefCount() { refCount++; }
    inline void Reset() { refCount = 0; }

    inline void AddOutputEdge(const std::size_t id) { outputEdges.push_back(id); }
    inline void setInputEdge(const std::size_t id) { inputEdge = id; }

    [[nodiscard]] inline const std::vector<std::size_t>& getOutputEdges() const { return outputEdges; }
    [[nodiscard]] inline const std::optional<std::size_t>& getInputEdge() const { return inputEdge; }

private:
    std::vector<std::size_t> outputEdges;
    std::optional<std::size_t> inputEdge = std::nullopt;

    std::string name;

    std::uint32_t refCount = 0;
    const std::size_t id = 0;
    const std::size_t nodeID = 0;
};

struct Edge : DAG::Edge
{
    Edge(Graph& g, 
        const std::size_t fromPin, 
        const std::size_t toPin, 
        const std::size_t fromNode, 
        const std::size_t toNode);

    const std::size_t fromPin = 0;
    const std::size_t toPin = 0;
};

Note that Pin is not a part of DAG. I wanted to implement some abstraction like

struct PinNode : DAG::Node - holds connections

struct VirtualPin - actual pin type, has a reference/id to PinNode

but after a while it didn't seem like a good idea

Also, I'm not sure how I should return std::optional<std::size_t> inputEdge in getInputEdge() function. const & is ok or should I just return a copy?

Node and Edge constructors will be defined after Graph implementation

Here it is:

struct Graph
{
    Graph(std::pmr::monotonic_buffer_resource& linearArena)
        : linearArena(linearArena)
    {
        nodes.reserve(16);
        edges.reserve(32);
        pins.reserve(64);
    }
    Graph(const Graph&) = delete;
    Graph& operator=(const Graph&) = delete;
    ~Graph() = default;

    [[nodiscard]] Node* AddNode(const std::string_view name);

    [[nodiscard]] Pin* AddInput(const std::string_view name, Node* const owner);
    [[nodiscard]] Pin* AddOutput(const std::string_view name, Node* const owner);

    bool Connect(Pin* const from, Pin* const to);

    void Execute();

    [[nodiscard]] inline const Node* getNode(const std::size_t id) const { return nodes[id]; }
    [[nodiscard]] inline const Pin* getPin(const std::size_t id) const { return pins[id]; }
    [[nodiscard]] inline const DAG& getDag() const { return dag; }
    [[nodiscard]] inline DAG& getDag() { return dag; }

    [[nodiscard]] inline const std::pmr::vector<Pin*>& getPins() const { return pins; }
private:
    [[nodiscard]] Pin* AddPin(const std::string_view name, Node* const owner);

    template<typename T, size_t alignment = alignof(T), typename ... Args>
    [[nodiscard]] T* ArenaAllocate(Args&& ... args)
    {
        void* const p = linearArena.allocate(sizeof(T), alignment);
        return p ? new(p) T(std::forward<Args>(args)...) : nullptr;
    }

    std::pmr::monotonic_buffer_resource& linearArena;

    DAG dag;
    std::pmr::vector<Node*> nodes{&linearArena};
    std::pmr::vector<Edge*> edges{&linearArena};
    std::pmr::vector<Pin*> pins{&linearArena};
};

Node* Graph::AddNode(const std::string_view name) 
{
    auto node = ArenaAllocate<Node>(*this, name);
    nodes.push_back(node); 
    return node;
}

Pin* Graph::AddInput(const std::string_view name, Node* const owner)
{
    auto pin = AddPin(name, owner);
    owner->AddInput(pin->getID());
    return pin;
}

Pin* Graph::AddOutput(const std::string_view name, Node* const owner)
{
    auto pin = AddPin(name, owner);
    owner->AddOuput(pin->getID());
    return pin;
}

Pin* Graph::AddPin(const std::string_view name, Node* const owner)
{
    std::size_t id = pins.size();
    auto pin = ArenaAllocate<Pin>(name, id, owner->getID());
    pins.push_back(pin);
    return pin;
}

bool Graph::Connect(Pin* const from, Pin* const to)
{
    if (to->getInputEdge().has_value()) {
        return false;
    }

    const std::size_t id = edges.size();

    auto edge = ArenaAllocate<Edge>(
        *this, 
        from->getID(), 
        to->getID(), 
        from->getNodeID(), 
        to->getNodeID()
    );
    edges.push_back(edge);
    from->AddOutputEdge(id);
    to->setInputEdge(id);

    return true;
}

void Graph::Execute()
{
    //Reset pins refCount before each DAG::Execute() call
    for(auto pin : pins) {
        pin->Reset();
    }
    //Calculate pins refCount
    for (const Edge* const edge : edges) {
        Pin& pin = *pins[edge->fromPin];
        pin.IncrementRefCount();
    }
    dag.Execute();
}

Node::Node(Graph& g, const std::string_view name)
    : DAG::Node(g.getDag()), g(g), name(name)
{
}

Edge::Edge(Graph& g, 
    const std::size_t fromPin, 
    const std::size_t toPin, 
    const std::size_t fromNode, 
    const std::size_t toNode)
        : DAG::Edge(g.getDag(), fromNode, toNode), fromPin(fromPin), toPin(toPin)
{
}

right now Node::Execute() simply prints inputs and outputs

void Node::Execute()
{
    std::cout << "\nNode: " << name << "\n";
    std::cout << "  Inputs:\n";
    
    if(inputs.empty()) {
        std::cout << "   empty   \n";
    } else {
        for (auto inputID : inputs) {
            auto input = g.getPin(inputID);
            std::cout << "   " << input->getName() << "\n";
        }
    }

    std::cout << "  Outputs:\n";
    auto unculledOutputs = getOutputs() | std::views::filter([&pins = g.getPins()](auto pinID) { return !pins[pinID]->isCulled(); });
    for (auto outputID : unculledOutputs) {
        auto output = g.getPin(outputID);
        std::cout << "   " << output->getName() << "\n";
    }
}

but in a future it'll convert outputs into some variables. I haven't fully written it yet.

main function:

int main()
{
    std::pmr::monotonic_buffer_resource arena{1024 * 1024};
    Graph sg{arena};

    auto lit = sg.AddNode("Lit");
    [[maybe_unused]] auto basePin = sg.AddInput("material.baseColor", lit);
    [[maybe_unused]] auto normalPin = sg.AddInput("material.normal", lit);
    [[maybe_unused]] auto materialAlphaPin = sg.AddInput("material.alpha", lit);
    [[maybe_unused]] auto metallicPin = sg.AddInput("material.metallic", lit);
    [[maybe_unused]] auto roughnessPin = sg.AddInput("material.roughness", lit);
    lit->MakeTarget();

    auto alphaNode = sg.AddNode("Alpha");
    auto alphaPin = sg.AddOutput("alpha", alphaNode);

    auto multiplierNode = sg.AddNode("Multiplier");
    auto multiplierPin = sg.AddOutput("multiplier", multiplierNode);

    auto addNode = sg.AddNode("AddNode");
    auto a = sg.AddInput("a", addNode);
    auto b = sg.AddInput("b", addNode);
    auto out = sg.AddOutput("out", addNode);

    sg.Connect(alphaPin, a);
    sg.Connect(multiplierPin, b);
    sg.Connect(out, materialAlphaPin);

    sg.Execute();

    return 0;
}

Output of this program:

Node: Lit
  Inputs:
   material.baseColor
   material.normal
   material.alpha
   material.metallic
   material.roughness
  Outputs:

Node: AddNode
  Inputs:
   a
   b
  Outputs:
   out

Node: Multiplier
  Inputs:
   empty   
  Outputs:
   multiplier

Node: Alpha
  Inputs:
   empty   
  Outputs:
   alpha

It looks good. Now let's disconnect alphaPin from a pin, just comment out this line in the main function: sg.Connect(alphaPin, a); and run again:

Node: Lit
  Inputs:
   material.baseColor
   material.normal
   material.alpha
   material.metallic
   material.roughness
  Outputs:

Node: AddNode
  Inputs:
   a
   b
  Outputs:
   out

Node: Multiplier
  Inputs:
   empty   
  Outputs:
   multiplier

Also looks good. Alpha Node hasn't been printed since its pin is not connected.

If DAG::Execute wouldn't have:

auto&& outEdges = getOutgoingEdges(node);
if (outEdges.empty() && !node->isTarget()) {
    continue;
}

the it would look like this:

Node: Alpha
  Inputs:
   empty   
  Outputs:

Node: Lit
  Inputs:
   material.baseColor
   material.normal
   material.alpha
   material.metallic
   material.roughness
  Outputs:

Node: AddNode
  Inputs:
   a
   b
  Outputs:
   out

Node: Multiplier
  Inputs:
   empty   
  Outputs:
   multiplier

which is not correct, because Alpha node is processed.

Could you do a review of this code and say if this code in DAG::Execute():

auto&& outEdges = getOutgoingEdges(node);
if (outEdges.empty() && !node->isTarget()) {
    continue;
}

is corrected and I'm just freaking out?

I haven't meant that the output is wrong. I've asked for a general code review + modification I did with Kahn's algorithm and if(outEdges.empty() ... thing — Edziju, Commented Dec 10, 2022 at 0:48

G. Sliepen · Accepted Answer · 2022-12-10 16:23:53Z

Make better use of polymorphic allocators

The whole point of polymorphic allocators is so that containers that use those can transparently use that allocator to allocate memory for the objects they store. Of course, if you want stable pointers to elements stored in a container, you cannot use std::vector, however you can use std::deque or std::list instead. So instead of doing:

std::pmr::vector<Node*> nodes{&linearArena};
…
auto node = ArenaAllocate<Node>(*this, name);
nodes.push_back(node);
return node;

You want to do this:

std::pmr::deque<Node> nodes{&linearArena};
…
return &nodes.emplace_back(name);

Once you store everything by value, copying graphs also becomes safe, and you no longer need to delete the copy constructors.

Prefer passing references where appropriate

You pass pointers everywhere, but especially if you store items in PMR containers by value, then it makes sense to pass references instead, so for example:

Pin& Graph::AddPin(std::string_view name, Node& owner)
{
    std::size_t id = pins.size();
    return pins.emplace_back(name, id, owner.getID());
}

References must always be non-null, so the compiler and/or static analyzers could spot bugs more easily, they also cannot be changed to point to another object, so const is not necessary anymore.

Note that whereever you used auto variables to hold a pointer, now you should use auto& to hold a reference, otherwise a copy will be made.

Avoid double bookkeeping

There seems to be some double bookkeeping going on. Graph owns the nodes, edges and pins, but then in also has a DAG that stores pointers to exactly the same nodes and edges. This is all done seemingly to make Execute() a bit simpler to implement.

I see two ways around this. One is to make DAG a base class of Graph, and add virtual functions to DAG that allow Execute access to the nodes and edges without having to store pointers to them itself.

Another way is to do away with DAG entirely, and instead make a templated free function that can work on any kind of graph. For example:

template<typename Nodes, typename Edges, typename Executor>
void execute_dag(Nodes& nodes, Edges& edges, Executor&& executor)
{
    for (auto& node: nodes) {
         node.refCount = 0;
    }
    …
    std::stack<Nodes::pointer> stack;
    for (auto& node: nodes) {
        if (node.getRefCount() == 0) {
            stack.push(&node);
        }
    }
    
    while (!stack.empty()) {
        auto& node = *stack.back();
        stack.pop();
        …
        std::invoke(std::forward<Executor>(executor), node);
        …
    }
}

The above function takes a reference to the lists of nodes and edges, so that these can stay private inside Graph. And Graph::Execute() just becomes:

void Graph::Execute()
{
    for (auto& pin : pins) {
        pin.Reset();
    }

    for (auto Edge& edge : edges) {
         pins[edge->fromPin].IncrementRefCount();
    }

    execute_dag(nodes, edges, [](Node& node){ node.Execute(); });
}

The above assumes that Node still has a refCount and isTarget(). Since refCount is only needed during the DAG traversal, you could instead create a temporary vector holding the reference counts inside execute_dag(). For isTarget(), you could consider having the executor return a bool to indicate whether to process the incoming edges or not, so the executor can return false if node.isTarget() == false. This decouples knowledge of isTarget() from the DAG algorithm. Finally, getOutgoingEdges() and getIncomingEdges() are quite simple and can be inlined into execute_dag().

Thanks for your answer. Let me double-check your first statement because I believe it was my first idea and it didn't work as intended. — Edziju, Commented Dec 10, 2022 at 14:28
Alright, so I remembered why I used pointers and ArenaAllocate. See, nodes, pins and edges capacity is reserved in a Graph constructor, but what if somehow there'll be more than 16 nodes? In that case, the program won't work well, because at some point, let's say auto& lit = sg.AddNode("lit") will be pointing to an invalid memory address. — Edziju, Commented Dec 10, 2022 at 15:40
Good point, I forgot to address that. The solution is to use a std::deque or std::list instead of a std::vector then, as the former two have stable pointers. — G. Sliepen, Commented Dec 10, 2022 at 16:22

Stack Exchange Network

Node graph implementation for a material system

1 Answer 1

Make better use of polymorphic allocators

Prefer passing references where appropriate

Avoid double bookkeeping

Your Answer

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

Hot Network Questions

Node graph implementation for a material system

1 Answer 1

Make better use of polymorphic allocators

Prefer passing references where appropriate

Avoid double bookkeeping

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

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