Skip to main content

Query a graph

A ModelGraph, traced from your own code or compiled from a model file, answers questions about its own structure: which operators it holds, what feeds what, which orders it can run in, which paths join two nodes, and where it can be split. The answers are views (Node, Value and Edge) that you read, compare and use as keys, and every query reads the graph as it stands. The graph queries are available from C++ and Python.

Get a graph​

A trace records a function once over stand-in tensors and returns the graph as built: every operator stays as written, nothing optimized or finalized, which makes the graph easy to read. The model below has two branches that meet, one tensor read twice and two outputs. Every example on this page uses it, and label names a node by its input name or its operator.

get_a_graph.cpp
#include <cstdio>
#include <string>
#include <vector>

#include <ClikaRT/clika_rt.h>

using ClikaRT::DataType;
using ClikaRT::Tensor;
using ClikaRT::graph::ModelGraph;
using ClikaRT::graph::Node;
using ClikaRT::graph::NodeKind;
using ClikaRT::graph::OpCode;
namespace ops = ClikaRT::ops;

namespace {

// Two branches that meet, one tensor read twice, two outputs.
std::vector<Tensor> model(const std::vector<Tensor>& inputs) {
    const Tensor a = ops::relu(inputs[0]);
    const Tensor b = ops::sigmoid(inputs[0]);
    const Tensor c = ops::add(a, b);
    const Tensor d = ops::mul(c, c);  // c feeds d twice: two edges, on input ports 0 and 1
    const Tensor e = ops::tanh(a);
    return {ops::sub(d, e), b};
}

// A node's label: an input's name, an operator's code.
std::string label(const Node& node) {
    return node.kind() == NodeKind::Input ? node.name() : std::string(ClikaRT::graph::op_code_name(node.op_code()));
}

// The labels of `nodes`, separated by spaces.
std::string labels(const std::vector<Node>& nodes) {
    std::string out;
    for (const Node& node : nodes) out += (out.empty() ? "" : " ") + label(node);
    return out;
}

// The trace returns the graph as recorded: every operator stays as written,
// nothing optimized or finalized.
ModelGraph trace_model() {
    const std::vector<ClikaRT::spec::TensorSpec> signature = {{"x", DataType::Float32, {2, 3}}};
    return ClikaRT::graph::trace(model, signature, "query");
}

}  // namespace

int main() {
    const ModelGraph graph = trace_model();
    std::printf("%s\n", labels(graph.nodes()).c_str());                        // x Relu Sigmoid Add Mul Tanh Sub
    std::printf("%zu\n", graph.find_nodes(OpCode::Mul).front().in_degree());   // 2
    return 0;
}

A compiled model answers the same queries: compile() returns the same ModelGraph type. The program builds a one-operator ONNX file first; any .onnx file works in its place.

compile_a_model.cpp
int main() {
    const ModelGraph graph = OnnxModel::open(relu_model_path()).compile();
    std::printf("%s\n", labels(graph.nodes()).c_str());   // x Relu
    return 0;
}

Each program on this page is complete and runs on its own. From here on, a block shows the part of its program that follows the opening lines the first block shows (the includes or imports, model, label and the trace).

Nodes, values and edges​

A Node is an operator or a graph input. A Value is a tensor that a node produces on one output port, and an Edge is one read of a value, from the producer's output port to the reader's input port. The graph is a multigraph keyed by those ports: d = c * c reads one value over two edges. A node answers its inputs and outputs, input(port), output(port), in_edges() and out_edges(); a value answers producer(), consumers() and uses().

nodes_and_edges.cpp
int main() {
    const ModelGraph graph = trace_model();
    const Node mul = graph.find_nodes(OpCode::Mul).front();
    const std::vector<Edge> reads = mul.in_edges();   // one edge per input port, each keyed by its two ports
    for (const Edge& edge : reads) {
        std::printf("%s %d -> %s %d\n", label(edge.src()).c_str(), edge.src_port(), label(edge.dst()).c_str(),
                    edge.dst_port());
    }
    // Add 0 -> Mul 0
    // Add 0 -> Mul 1
    const Value value = *mul.input(0);   // the tensor both edges carry
    const Node add = *value.producer();
    std::printf("%s %s %s\n", value == *mul.input(1) ? "true" : "false", label(add).c_str(),
                labels(value.consumers()).c_str());                                     // true Add Mul
    std::printf("%zu %zu\n", graph.edges().size(), graph.edges_between(add, mul).size());   // 9 2
    return 0;
}

Read the views when your own code walks the structure, as an exporter or a quantizer does.

Search by name and by predicate​

find_nodes_by_name matches a regular expression against a node's whole name, or any part of it with the Anywhere name match. find_nodes takes an OpCode or a predicate over a Node, and node(name) looks up one node. Each list comes back in name order. Operator names carry the operator and a number, so match them with a pattern rather than a literal.

search.cpp
int main() {
    const ModelGraph graph = trace_model();
    const Regex relu = Regex::compile("Relu_[0-9]+");
    const Regex sig = Regex::compile("Sig");
    std::printf("%s\n", labels(graph.find_nodes_by_name(relu)).c_str());                        // Relu
    std::printf("%s\n", labels(graph.find_nodes_by_name(sig, NameMatch::Anywhere)).c_str());    // Sigmoid
    std::printf("%s\n", labels(graph.find_nodes([](const Node& node) { return node.in_degree() == 2; })).c_str());
    // Add Mul Sub
    std::printf("%s %s\n", label(*graph.node("x")).c_str(), labels(graph.find_nodes(OpCode::Tanh)).c_str());  // x Tanh
    return 0;
}

Walks, visits, ancestors and descendants​

walk(start) lists the nodes a breadth-first walk reaches, the start first. The options direction, max_depth, max_nodes, stop_at and edge_filter (the fields of WalkOptions in C++, keyword arguments in Python) bound any walk. descendants(node) and ancestors(node) leave the node itself out and list the nearest first. visit(start, visitor) shows a callable each node, and the callable answers the VisitAction Continue, Prune (do not go past this node) or Stop.

walks.cpp
int main() {
    const ModelGraph graph = trace_model();
    const Node x = *graph.node("x");
    const Node relu = graph.find_nodes(OpCode::Relu).front();
    const Node sub = graph.find_nodes(OpCode::Sub).front();
    WalkOptions one_step;
    one_step.max_depth = 1;
    std::printf("%s\n", labels(graph.walk(x, one_step)).c_str());   // x Relu Sigmoid
    std::printf("%s\n", labels(graph.descendants(relu)).c_str());   // Add Tanh Mul Sub
    std::printf("%s\n", labels(graph.ancestors(sub)).c_str());      // Mul Tanh Add Relu Sigmoid x

    std::vector<Node> seen;
    graph.visit(x, [&seen](const Node& node) {
        seen.push_back(node);
        return node.op_code() == OpCode::Add ? VisitAction::Prune : VisitAction::Continue;
    });   // the walk does not go past the Add, so the Mul is never shown
    std::printf("%s\n", labels(seen).c_str());   // x Relu Sigmoid Add Tanh Sub
    return 0;
}

Use a walk to collect everything upstream or downstream of a node, and a visit when the decision to go on depends on the node you are at.

Topological orders, generations and depths​

topological_order() lists every node after the nodes it reads, in the Deterministic order by default (Structural and MinMemory are the other two TopologicalOrder values). topological_generations() groups the nodes by the longest path that ends at them, and depths() gives that length per node. random_topological_order(seed) draws one of the valid orders; the programs check the order they draw instead of printing it, since the order depends on the seed.

orders.cpp
int main() {
    const ModelGraph graph = trace_model();
    std::printf("%s\n", labels(graph.topological_order()).c_str());   // x Relu Sigmoid Add Mul Tanh Sub
    std::string layers;
    for (const std::vector<Node>& layer : graph.topological_generations()) layers += "[" + labels(layer) + "]";
    std::printf("%s\n", layers.c_str());   // [x][Relu Sigmoid][Add Tanh][Mul][Sub]
    std::string depths;
    for (const auto& [node, depth] : graph.depths()) {
        depths += (depths.empty() ? "" : " ") + label(node) + "=" + std::to_string(depth);
    }
    std::printf("%s\n", depths.c_str());   // x=0 Relu=1 Sigmoid=1 Add=2 Mul=3 Tanh=2 Sub=4
    // Any valid order, drawn from the seed: check it rather than print it.
    std::printf("%s\n", graph.is_topological_order(graph.random_topological_order(7)) ? "true" : "false");   // true
    return 0;
}

A generation's nodes read only earlier generations, so they are the nodes that can run at the same time.

Paths and path counts​

A path never repeats a node. all_simple_paths(src, dst) lists the paths as nodes, where parallel edges give one path, and all_simple_edge_paths lists them as edges, where each parallel edge gives its own. Both search at the call, and Python hands the paths back through an iterator. Without a limit, a search that finds more than kMaxPathsWithoutLimit paths (MAX_PATHS_WITHOUT_LIMIT in Python) fails with an invalid-argument error instead of returning part of the list; count_paths counts without listing and has no such cap. shortest_path gives the path with the fewest edges and has_path answers reachability. The options cutoff, avoid and edge_filter (the fields of PathOptions in C++, keyword arguments in Python) bound every path query.

paths.cpp
int main() {
    const ModelGraph graph = trace_model();
    const Node x = *graph.node("x");
    const Node sub = graph.find_nodes(OpCode::Sub).front();
    // The two edges into the Mul give one path.
    const std::vector<std::vector<Node>> paths = graph.all_simple_paths(x, sub);
    for (const std::vector<Node>& path : paths) std::printf("%s\n", labels(path).c_str());
    // x Relu Add Mul Sub
    // x Relu Tanh Sub
    // x Sigmoid Add Mul Sub
    std::printf("%llu %zu\n", static_cast<unsigned long long>(graph.count_paths(x, sub)),
                graph.all_simple_edge_paths(x, sub).size());   // 3 5
    std::printf("%s %s\n", labels(graph.shortest_path(x, sub)).c_str(),
                graph.has_path(sub, x) ? "true" : "false");   // x Relu Tanh Sub false
    PathOptions first;
    first.limit = 1;
    std::printf("%zu %zu\n", graph.all_simple_paths(x, sub, first).size(),
                ClikaRT::graph::kMaxPathsWithoutLimit);   // 1 10000
    return 0;
}

The critical path​

critical_path(node_cost, edge_cost) returns the costliest path as a WeightedPath carrying its nodes, its edges and its summed cost: the longest chain of work when each node costs its run time. Given an edge_cost, shortest_path returns the cheapest path in the same form.

critical_path.cpp
int main() {
    const ModelGraph graph = trace_model();
    // A cost per node (and optionally per edge): here the Sigmoid costs 2, every other node 1.
    const WeightedPath path =
        graph.critical_path([](const Node& node) { return node.op_code() == OpCode::Sigmoid ? 2.0 : 1.0; });
    std::printf("%s %g\n", labels(path.nodes).c_str(), path.cost);   // x Sigmoid Add Mul Sub 6
    return 0;
}

Structure: cycles, dominance, regions and cones​

find_cycle() is empty for every traced or compiled graph, and would_create_cycle(src, dst) checks an edge before an edit adds it. weakly_connected_components() groups the nodes that edges join in either direction. dominators() maps each node to the last node that every path from the inputs to it crosses, split_points() lists the nodes that every path from the inputs to the outputs crosses, and merge_point(nodes) finds where the paths from several nodes meet. region(entry, exit) is the single-entry, single-exit block between two nodes, producer_cone and consumer_cone are everything a set of nodes reads or feeds, and is_convex tells whether a set can be cut out and replaced as one piece.

structure.cpp
int main() {
    const ModelGraph graph = trace_model();
    std::map<std::string, Node> node;
    for (const Node& n : graph.nodes()) node.emplace(label(n), n);
    std::printf("%zu %s\n", graph.find_cycle().size(),
                graph.would_create_cycle(node.at("Sub"), node.at("x")) ? "true" : "false");   // 0 true
    std::printf("%zu\n", graph.weakly_connected_components().size());                      // 1
    std::string dominators;
    for (const auto& [n, dominator] : graph.dominators()) {
        dominators += (dominators.empty() ? "" : " ") + label(n) + ":" + label(dominator);
    }
    std::printf("%s\n", dominators.c_str());   // x:x Relu:x Sigmoid:x Add:x Mul:Add Tanh:Relu Sub:x
    std::printf("%s %s\n", labels(graph.split_points()).c_str(),
                label(*graph.merge_point({node.at("Add"), node.at("Tanh")})).c_str());   // x Sub
    std::printf("%s\n", labels(graph.region(node.at("Add"), node.at("Mul"))).c_str());   // Add Mul
    std::printf("%s\n", labels(graph.producer_cone({node.at("Mul")})).c_str());           // x Relu Sigmoid Add
    std::printf("%s %s\n", graph.is_convex({node.at("Add"), node.at("Mul")}) ? "true" : "false",
                graph.is_convex({node.at("Relu"), node.at("Mul")}) ? "true" : "false");   // true false
    return 0;
}

The cheapest cut​

min_value_cut(before, after) finds the split of the nodes into two parts that hands the fewest bytes from the first part to the second, and returns a ValueCut of the values that cross and their bytes. before and after pin nodes to either part. Of the cheapest cuts it returns the one nearest the inputs; networkx's minimum_cut returns the one nearest the sink instead. Use it to decide where to split a model across two devices or two processes.

value_cut.cpp
int main() {
    const ModelGraph graph = trace_model();
    std::map<std::string, Node> node;
    for (const Node& n : graph.nodes()) node.emplace(label(n), n);
    // The producers of the values that cross the cut, and their bytes.
    const auto show = [](const ValueCut& cut) {
        std::string crossing;
        for (const Value& value : cut.values) crossing += (crossing.empty() ? "" : " ") + label(*value.producer());
        std::printf("%s %llu\n", crossing.c_str(), static_cast<unsigned long long>(cut.bytes));
    };
    show(graph.min_value_cut());   // x 24: every float32 [2, 3] value holds 24 bytes
    show(graph.min_value_cut({node.at("Add")}, {node.at("Sub")}));   // Relu Sigmoid Add 72
    return 0;
}

Views across edits​

An edit such as optimize() changes the graph under the views you hold. A view finds its node, value or edge again by its key (a node's name, a value's producer and port, an edge's two ends and ports) and keeps answering. Once the key is gone, check() refuses, naming the key, and so does a query given the view. In C++ the view's other reads answer empty; in Python they raise the same InvalidArgumentError as check(). Equality and hashing keep working in both, so a map or dictionary keyed by views still finds its entries.

edits.cpp
int main() {
    const std::vector<ClikaRT::spec::TensorSpec> signature = {{"x", DataType::Float32, {2, 3}}};
    ModelGraph twice = ClikaRT::graph::trace(
        [](const std::vector<Tensor>& inputs) -> std::vector<Tensor> { return {ops::relu(ops::relu(inputs[0]))}; },
        signature, "twice");
    const Node inner = twice.node("x")->successors().front();
    const Node outer = inner.successors().front();
    // Views key a map across edits.
    const std::unordered_map<Node, std::string> index = {{inner, "inner"}, {outer, "outer"}};

    twice.optimize();   // Relu(Relu(x)) is Relu(x): the optimizer removes the outer Relu
    inner.check();      // the kept Relu still answers
    std::printf("%s %s\n", label(inner).c_str(), inner.output(0)->is_graph_output() ? "true" : "false");   // Relu true
    try {
        outer.check();   // refuses, naming the node, and so does a query given the view
    } catch (const Error& error) {
        std::printf("%s\n", error.code_name().c_str());   // INVALID_ARGUMENT
    }
    // Every other read of the gone view answers empty.
    std::printf("%s '%s'\n", index.at(outer).c_str(), outer.name().c_str());   // outer ''
    return 0;
}

Hand the graph to networkx​

to_networkx() returns the graph as a networkx.MultiDiGraph, for the algorithms networkx provides. Its nodes are the Node views, which keep the graph alive, and each edge is keyed (src_port, dst_port). It needs the networkx package, which the program imports as nx.

networkx is a Python library, so this section has a Python program only. From C++, edges() and the node views carry the same structure to any graph library.