Program Listing for File graph.cc

↰ Return to documentation for file (src/graph.cc)

#include <algorithm>
#include <vector>
#include "nodes-graph/graph.h"
#include "nodes-graph/node_definition.h"
#include "nodes-graph/graph_manager.h"


namespace ng {

Graph::Graph(
    std::string name,
    nodes_t nodes,
    links_t links,
    input_sockets_t input_sockets,
    output_sockets_t output_sockets,
    interface_t parameters,
    interface_t results
): name_(std::move(name)),
   input_sockets_(std::move(input_sockets)),
   output_sockets_(std::move(output_sockets)),
   nodes_(std::move(nodes)),
   links_(std::move(links)),
   parameters_(std::move(parameters)),
   results_(std::move(results))
{}


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// *  Nodes                                                                *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

node_id_t Graph::make_unique_node_id(const qualifier_t& q) const {
    node_id_t node_id;
    do {
        node_id = as_node_id(q, Node::make_random_id());
    } while (has_node(node_id));
    return node_id;
}


node_id_t Graph::instantiate(const NodeDefinition& nd) {
    node_id_t node_id = make_unique_node_id(nd.get_qualifier());
    Node node(nd.get_default_name(), node_id, nd.get_qualifier());

    for (const InputSocket& s : nd.get_input_sockets()) {
        input_sockets_[as_socket_uuid(node_id, s.get_id())] = s;
        node.register_input_socket(s.get_id());
    }

    for (const OutputSocket& s : nd.get_output_sockets()) {
        output_sockets_[as_socket_uuid(node_id, s.get_id())] = s;
        node.register_output_socket(s.get_id());
    }

    nodes_.emplace(node_id, std::move(node));
    return node_id;
}


node_id_t Graph::add_node(const qualifier_t& node_qualifier) {
    const NodesRegistry& registry = NodesRegistry::instance();
    auto it = registry.find(node_qualifier);
    if (it == registry.end()) { return null_node; }
    return instantiate(it->second);
}


node_id_t Graph::add_node(const char* node_qualifier) {
    return add_node(as_qualifier(node_qualifier));
}


Node& Graph::get_node(const node_id_t& node_id) {
    return nodes_.at(node_id);
}


const Node& Graph::get_node(const node_id_t& node_id) const {
    return nodes_.at(node_id);
}


void Graph::rename_node(const node_id_t& node_id, const std::string& name) {
    get_node(node_id).set_name(name);
}


bool Graph::remove_node(const node_id_t& node_id) {
    if (!has_node(node_id)) { return false; }

    disconnect_node(node_id, LinkBreakReason::NodeRemoved);

    auto lo_in = input_sockets_.lower_bound(as_socket_uuid(node_id, null_socket));
    auto hi_in = input_sockets_.upper_bound(as_socket_uuid(node_id, inf_socket));
    for (auto it = lo_in; it != hi_in; ++it) {
        parameters_.erase(it->first);
    }
    input_sockets_.erase(lo_in, hi_in);

    auto lo_out = output_sockets_.lower_bound(as_socket_uuid(node_id, null_socket));
    auto hi_out = output_sockets_.upper_bound(as_socket_uuid(node_id, inf_socket));
    for (auto it = lo_out; it != hi_out; ++it) {
        results_.erase(it->first);
    }
    output_sockets_.erase(lo_out, hi_out);

    nodes_.erase(node_id);
    return true;
}


void Graph::disconnect_node(const node_id_t& node_id, LinkBreakReason reason) {
    // Collected first: callbacks are allowed to modify the links.
    std::vector<link_t> to_break;
    for (const link_t& link : links_) {
        if (link.first.first == node_id || link.second.first == node_id) {
            to_break.push_back(link);
        }
    }
    for (const link_t& link : to_break) {
        break_link(links_.find(link), reason);
    }
}


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// *  Sockets                                                              *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

const InputSocket& Graph::get_input_socket(const socket_uuid_t& suuid) const {
    return input_sockets_.at(suuid);
}


const OutputSocket& Graph::get_output_socket(const socket_uuid_t& suuid) const {
    return output_sockets_.at(suuid);
}


Status Graph::set_socket_value(const socket_uuid_t& suuid, const std::string& value) {
    auto it = input_sockets_.find(suuid);
    if (it == input_sockets_.end()) { return Status::NoInputSocket; }

    InputSocket& socket = it->second;
    if (!socket.is_allowed_value(value)) { return Status::NotAllowedValue; }
    if (!socket.check_validity(value)) { return Status::InvalidValue; }

    std::string old_value = socket.get_value();
    socket.set_value(value);
    socket.trigger_on_value_changed_callbacks(*this, get_node(suuid.first), old_value);
    return Status::Ok;
}


const std::string& Graph::get_socket_value(const socket_uuid_t& suuid) const {
    return input_sockets_.at(suuid).get_value();
}


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// *  Links                                                                *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Graph::links_t::const_iterator Graph::find_link_by_input_socket(const socket_uuid_t& target) const {
    // Links are sorted by destination first, the smallest possible source gives the first candidate.
    link_t lowest = as_link(as_socket_uuid(null_node, null_socket), target);
    auto it = links_.lower_bound(lowest);
    if (it != links_.end() && it->first == target) {
        return it;
    }
    return links_.end();
}


Status Graph::add_link(const socket_uuid_t& from, const socket_uuid_t& to) {
    return add_link(as_link(from, to));
}


Status Graph::add_link(const link_t& link) {
    if (links_.count(link) > 0) { return Status::Ok; }

    auto it_from = output_sockets_.find(link.second);
    if (it_from == output_sockets_.end()) { return Status::NoOutputSocket; }

    auto it_to = input_sockets_.find(link.first);
    if (it_to == input_sockets_.end()) { return Status::NoInputSocket; }

    if (!it_from->second.accepts_type(it_to->second.get_type())) { return Status::IncompatibleTypes; }

    if (!it_to->second.is_linkable()) { return Status::NotLinkable; }

    // Checked before replacing the existing link, so a refused link leaves the graph untouched.
    // Keeping the replaced link in the check can't create a false positive: a simple cycle enters a socket only once.
    if (causes_cycle(link)) { return Status::CausesCycle; }

    break_link(find_link_by_input_socket(link.first), LinkBreakReason::Replaced);
    parameters_.erase(link.first);
    links_.insert(link);

    Node& node_from = get_node(link.second.first);
    Node& node_to = get_node(link.first.first);
    it_from->second.trigger_on_added_link_callbacks(*this, node_from, node_to, it_to->second);
    it_to->second.trigger_on_added_link_callbacks(*this, node_from, it_from->second, node_to);
    return Status::Ok;
}


bool Graph::break_link(links_t::const_iterator link_it, LinkBreakReason reason) {
    if (link_it == links_.end()) { return false; }

    link_t link = *link_it;
    links_.erase(link_it);

    InputSocket& socket_to = input_sockets_.at(link.first);
    OutputSocket& socket_from = output_sockets_.at(link.second);
    Node& node_from = get_node(link.second.first);
    Node& node_to = get_node(link.first.first);

    socket_from.trigger_on_broken_link_callbacks(*this, node_from, node_to, socket_to, reason);
    socket_to.trigger_on_broken_link_callbacks(*this, node_from, socket_from, node_to, reason);
    return true;
}


bool Graph::break_link(const link_t& link) {
    return break_link(links_.find(link), LinkBreakReason::Manual);
}


Graph::links_t Graph::get_input_links(const node_id_t& node_id) const {
    links_t result;
    for (const link_t& link : links_) {
        if (link.first.first == node_id) {
            result.insert(link);
        }
    }
    return result;
}


Graph::links_t Graph::get_output_links(const node_id_t& node_id) const {
    links_t result;
    for (const link_t& link : links_) {
        if (link.second.first == node_id) {
            result.insert(link);
        }
    }
    return result;
}


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// *  Interface                                                            *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

bool Graph::is_alias_available(const interface_t& interface, const socket_uuid_t& suuid, const socket_id_t& alias) {
    for (const auto& [other, ppts] : interface) {
        if (other != suuid && ppts.socket_id == alias) {
            return false;
        }
    }
    return true;
}


Status Graph::expose_parameter(const socket_uuid_t& suuid, const socket_id_t& alias, std::string show_as) {
    auto it = input_sockets_.find(suuid);
    if (it == input_sockets_.end()) { return Status::NoInputSocket; }
    if (!is_alias_available(parameters_, suuid, alias)) { return Status::DuplicateAlias; }

    if (show_as.empty()) {
        show_as = it->second.get_name();
    }

    break_link(find_link_by_input_socket(suuid), LinkBreakReason::Replaced);
    parameters_[suuid] = InterfaceProperties{std::move(show_as), alias};
    return Status::Ok;
}


bool Graph::remove_parameter(const socket_uuid_t& suuid) {
    return parameters_.erase(suuid) > 0;
}


Status Graph::expose_result(const socket_uuid_t& suuid, const socket_id_t& alias, std::string show_as) {
    auto it = output_sockets_.find(suuid);
    if (it == output_sockets_.end()) { return Status::NoOutputSocket; }
    if (!is_alias_available(results_, suuid, alias)) { return Status::DuplicateAlias; }

    if (show_as.empty()) {
        show_as = it->second.get_name();
    }

    results_[suuid] = InterfaceProperties{std::move(show_as), alias};
    return Status::Ok;
}


bool Graph::remove_result(const socket_uuid_t& suuid) {
    return results_.erase(suuid) > 0;
}


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// *  Proxies                                                              *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

node_id_t Graph::add_proxy_node(const qualifier_t& graph_qualifier) {
    if (qualifier_.has_value() && qualifier_.value() == graph_qualifier) { return null_node; }

    const Graph g = GraphManager::instance().raw_read(graph_qualifier);

    node_id_t node_id = make_unique_node_id(graph_qualifier);
    Node proxy(g.get_name(), node_id, graph_qualifier);
    proxy.set_proxy(true);

    for (const auto& [suuid, ppts] : g.get_parameters()) {
        InputSocket s = g.get_input_socket(suuid);
        s.set_alias(ppts.show_as, ppts.socket_id);
        input_sockets_[as_socket_uuid(node_id, s.get_id())] = s;
        proxy.register_input_socket(s.get_id());
    }

    for (const auto& [suuid, ppts] : g.get_results()) {
        OutputSocket s = g.get_output_socket(suuid);
        s.set_alias(ppts.show_as, ppts.socket_id);
        output_sockets_[as_socket_uuid(node_id, s.get_id())] = s;
        proxy.register_output_socket(s.get_id());
    }

    nodes_.emplace(node_id, std::move(proxy));
    return node_id;
}


node_id_t Graph::add_proxy_node(const char* graph_qualifier) {
    return add_proxy_node(as_qualifier(graph_qualifier));
}


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// *  Topology                                                             *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

std::set<node_id_t> Graph::get_source_nodes() const {
    return get_source_nodes(links_);
}


std::set<node_id_t> Graph::get_source_nodes(const links_t& links) const {
    std::set<node_id_t> source_nodes;
    for (const auto& [node_id, _] : nodes_) {
        source_nodes.insert(node_id);
    }
    for (const link_t& link : links) {
        source_nodes.erase(link.first.first);
    }
    return source_nodes;
}


bool Graph::causes_cycle(const link_t& link) const {
    links_t candidate_links = links_;
    candidate_links.insert(link);
    return get_depth_properties(candidate_links).has_cycle;
}


Graph::DepthProperties Graph::get_depth_properties() const {
    return get_depth_properties(links_);
}


Graph::DepthProperties Graph::get_depth_properties(const links_t& links) const {
    DepthProperties props;

    // Number of incoming links not processed yet, for each node.
    SmallMap<node_id_t, std::size_t> in_degree;
    in_degree.reserve(nodes_.size());
    for (const auto& [node_id, _] : nodes_) {
        in_degree[node_id] = 0;
    }

    // Successors of each node (links are stored as {to, from}).
    std::map<node_id_t, std::vector<node_id_t>> successors;
    for (const link_t& link : links) {
        in_degree[link.first.first]++;
        successors[link.second.first].push_back(link.first.first);
    }

    std::vector<node_id_t> stack;
    stack.reserve(nodes_.size());
    props.depth.reserve(nodes_.size());
    for (const auto& [node_id, count] : in_degree) {
        if (count == 0) {
            stack.push_back(node_id);
            props.depth[node_id] = 0;
        }
    }

    std::size_t processed = 0;
    while (!stack.empty()) {
        node_id_t current = stack.back();
        stack.pop_back();
        processed++;
        std::size_t current_depth = props.depth[current];
        props.max_depth = std::max(props.max_depth, current_depth);

        auto it = successors.find(current);
        if (it == successors.end()) { continue; }
        for (const node_id_t& next : it->second) {
            std::size_t& d = props.depth[next];
            d = std::max(d, current_depth + 1);
            if (--in_degree[next] == 0) {
                stack.push_back(next);
            }
        }
    }

    props.has_cycle = processed < in_degree.size();
    return props;
}


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// *  Deep comparison                                                      *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

namespace {

    // Compares two maps sharing the same key ordering: keys must be equal and values equal according to `eq`.
    template <typename Map, typename Eq>
    bool same_maps(const Map& a, const Map& b, Eq eq) {
        if (a.size() != b.size()) { return false; }
        auto it_b = b.begin();
        for (const auto& [key, value] : a) {
            if (key != it_b->first || !eq(value, it_b->second)) { return false; }
            ++it_b;
        }
        return true;
    }

} // namespace


bool CmpGraph::same_socket(const Socket& a, const Socket& b) const {
    return a.get_name() == b.get_name()
        && a.get_id() == b.get_id()
        && a.get_type() == b.get_type()
        && a.is_active() == b.is_active()
        && a.get_on_added_link_callbacks() == b.get_on_added_link_callbacks()
        && a.get_on_broken_link_callbacks() == b.get_on_broken_link_callbacks();
}


bool CmpGraph::same_input_socket(const InputSocket& a, const InputSocket& b) const {
    return same_socket(a, b)
        && a.get_value() == b.get_value()
        && a.is_linkable() == b.is_linkable()
        && a.get_allowed_values() == b.get_allowed_values()
        && a.get_on_value_changed_callbacks() == b.get_on_value_changed_callbacks();
}


bool CmpGraph::same_output_socket(const OutputSocket& a, const OutputSocket& b) const {
    return same_socket(a, b);
}


bool CmpGraph::same_node(const Node& a, const Node& b) const {
    return a.get_name() == b.get_name()
        && a.get_id() == b.get_id()
        && a.get_qualifier() == b.get_qualifier()
        && a.is_proxy() == b.is_proxy()
        && a.get_input_sockets() == b.get_input_sockets()
        && a.get_output_sockets() == b.get_output_sockets();
}


bool CmpGraph::same_interface(const Graph::InterfaceProperties& a, const Graph::InterfaceProperties& b) const {
    return a.show_as == b.show_as && a.socket_id == b.socket_id;
}


bool CmpGraph::equal(const Graph& a, const Graph& b) const {
    if (&a == &b) { return true; }

    return a.get_name() == b.get_name()
        && a.get_qualifier() == b.get_qualifier()
        && a.get_links() == b.get_links()
        && same_maps(a.get_nodes(), b.get_nodes(),
            [this](const Node& x, const Node& y) { return same_node(x, y); })
        && same_maps(a.get_input_sockets(), b.get_input_sockets(),
            [this](const InputSocket& x, const InputSocket& y) { return same_input_socket(x, y); })
        && same_maps(a.get_output_sockets(), b.get_output_sockets(),
            [this](const OutputSocket& x, const OutputSocket& y) { return same_output_socket(x, y); })
        && same_maps(a.get_parameters(), b.get_parameters(),
            [this](const Graph::InterfaceProperties& x, const Graph::InterfaceProperties& y) { return same_interface(x, y); })
        && same_maps(a.get_results(), b.get_results(),
            [this](const Graph::InterfaceProperties& x, const Graph::InterfaceProperties& y) { return same_interface(x, y); });
}

} // namespace ng