--- title: Query a graph description: "Read a ModelGraph as data: its nodes, values and edges, search by name or predicate, walks and topological orders, paths and the critical path, dominance, regions, cones and the cheapest cut, views across edits, and networkx." --- {/* Every block is a program under examples//howto/query_a_graph/: the first block of each tab is get_a_graph whole, and every later block is its program's docs region. tools/tutorial_check.py runs each program against its recorded output. */} 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. ```cpp title="get_a_graph.cpp" #include #include #include #include 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 model(const std::vector& 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& 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 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; } ``` ```python title="get_a_graph.py" import clika_runtime as crt from clika_runtime.graph import NodeKind, OpCode def model(inputs: list[crt.Tensor]) -> list[crt.Tensor]: x = inputs[0] a, b = crt.relu(x), crt.sigmoid(x) c = a + b d = c * c # c feeds d twice: two edges, on input ports 0 and 1 e = crt.tanh(a) return [d - e, b] def label(node: crt.graph.Node) -> str: return node.name if node.kind == NodeKind.Input else node.op_code.name # The trace returns the graph as recorded: every operator stays as written, # nothing optimized or finalized. graph = crt.trace(model, [crt.TensorSpec("x", crt.float32, [2, 3])]).graph print([label(node) for node in graph.nodes()]) # ['x', 'Relu', 'Sigmoid', 'Add', 'Mul', 'Tanh', 'Sub'] print(graph.find_nodes(OpCode.Mul)[0].in_degree()) # 2 ``` 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. ```cpp title="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; } ``` ```python title="compile_a_model.py" graph = crt.io.OnnxModel.open(path).compile() print([label(node) for node in graph.nodes()]) # ['x', 'Relu'] ``` 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()`. ```cpp title="nodes_and_edges.cpp" int main() { const ModelGraph graph = trace_model(); const Node mul = graph.find_nodes(OpCode::Mul).front(); const std::vector 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; } ``` ```python title="nodes_and_edges.py" (mul,) = graph.find_nodes(OpCode.Mul) for edge in mul.in_edges(): # one edge per input port, each keyed by its two ports print(label(edge.src()), edge.src_port(), "->", label(edge.dst()), edge.dst_port()) # Add 0 -> Mul 0 # Add 0 -> Mul 1 value = mul.input(0) # the tensor both edges carry print(value == mul.input(1), label(value.producer()), [label(node) for node in value.consumers()]) # True Add ['Mul'] print(len(graph.edges()), len(graph.edges_between(value.producer(), mul))) # 9 2 ``` 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. ```cpp title="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; } ``` ```python title="search.py" print([label(node) for node in graph.find_nodes_by_name("Relu_[0-9]+")]) # ['Relu'] print([label(node) for node in graph.find_nodes_by_name("Sig", crt.graph.NameMatch.Anywhere)]) # ['Sigmoid'] print([label(node) for node in graph.find_nodes(lambda node: node.in_degree() == 2)]) # ['Add', 'Mul', 'Sub'] print(label(graph.node("x")), [label(node) for node in graph.find_nodes(OpCode.Tanh)]) # x ['Tanh'] ``` ## 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`. ```cpp title="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 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; } ``` ```python title="walks.py" x = graph.node("x") (relu,) = graph.find_nodes(OpCode.Relu) (sub,) = graph.find_nodes(OpCode.Sub) print([label(node) for node in graph.walk(x, max_depth=1)]) # ['x', 'Relu', 'Sigmoid'] print([label(node) for node in graph.descendants(relu)]) # ['Add', 'Tanh', 'Mul', 'Sub'] print([label(node) for node in graph.ancestors(sub)]) # ['Mul', 'Tanh', 'Add', 'Relu', 'Sigmoid', 'x'] seen: list[str] = [] def look(node: crt.graph.Node) -> crt.graph.VisitAction: seen.append(label(node)) return crt.graph.VisitAction.Prune if node.op_code == OpCode.Add else crt.graph.VisitAction.Continue graph.visit(x, look) # the walk does not go past the Add, so the Mul is never shown print(seen) # ['x', 'Relu', 'Sigmoid', 'Add', 'Tanh', 'Sub'] ``` 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. ```cpp title="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& 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; } ``` ```python title="orders.py" print([label(node) for node in graph.topological_order()]) # ['x', 'Relu', 'Sigmoid', 'Add', 'Mul', 'Tanh', 'Sub'] print([[label(node) for node in layer] for layer in graph.topological_generations()]) # [['x'], ['Relu', 'Sigmoid'], ['Add', 'Tanh'], ['Mul'], ['Sub']] print({label(node): depth for node, depth in graph.depths().items()}) # {'x': 0, 'Relu': 1, 'Sigmoid': 1, 'Add': 2, 'Mul': 3, 'Tanh': 2, 'Sub': 4} print(graph.is_topological_order(graph.random_topological_order(7))) # True: any valid order, drawn from the seed ``` 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. ```cpp title="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> paths = graph.all_simple_paths(x, sub); for (const std::vector& 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(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; } ``` ```python title="paths.py" x = graph.node("x") (sub,) = graph.find_nodes(OpCode.Sub) for path in graph.all_simple_paths(x, sub): # the two edges into the Mul give one path print([label(node) for node in path]) # ['x', 'Relu', 'Add', 'Mul', 'Sub'] # ['x', 'Relu', 'Tanh', 'Sub'] # ['x', 'Sigmoid', 'Add', 'Mul', 'Sub'] print(graph.count_paths(x, sub), len(list(graph.all_simple_edge_paths(x, sub)))) # 3 5 print([label(node) for node in graph.shortest_path(x, sub)], graph.has_path(sub, x)) # ['x', 'Relu', 'Tanh', 'Sub'] False print(len(list(graph.all_simple_paths(x, sub, limit=1))), crt.graph.MAX_PATHS_WITHOUT_LIMIT) # 1 10000 ``` ## 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. ```cpp title="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; } ``` ```python title="critical_path.py" # A cost per node (and optionally per edge): here the Sigmoid costs 2, every other node 1. path = graph.critical_path(lambda node: 2.0 if node.op_code == OpCode.Sigmoid else 1.0) print([label(node) for node in path.nodes], path.cost) # ['x', 'Sigmoid', 'Add', 'Mul', 'Sub'] 6.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. ```cpp title="structure.cpp" int main() { const ModelGraph graph = trace_model(); std::map 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; } ``` ```python title="structure.py" node = {label(n): n for n in graph.nodes()} print(graph.find_cycle(), graph.would_create_cycle(node["Sub"], node["x"])) # [] True print(len(graph.weakly_connected_components())) # 1 print({label(n): label(dominator) for n, dominator in graph.dominators().items()}) # {'x': 'x', 'Relu': 'x', 'Sigmoid': 'x', 'Add': 'x', 'Mul': 'Add', 'Tanh': 'Relu', 'Sub': 'x'} print([label(n) for n in graph.split_points()], label(graph.merge_point([node["Add"], node["Tanh"]]))) # ['x'] Sub print([label(n) for n in graph.region(node["Add"], node["Mul"])]) # ['Add', 'Mul'] print([label(n) for n in graph.producer_cone([node["Mul"]])]) # ['x', 'Relu', 'Sigmoid', 'Add'] print(graph.is_convex([node["Add"], node["Mul"]]), graph.is_convex([node["Relu"], node["Mul"]])) # True False ``` ## 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. ```cpp title="value_cut.cpp" int main() { const ModelGraph graph = trace_model(); std::map 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(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; } ``` ```python title="value_cut.py" node = {label(n): n for n in graph.nodes()} cut = graph.min_value_cut() # every float32 [2, 3] value holds 24 bytes print([label(value.producer()) for value in cut.values], cut.bytes) # ['x'] 24 pinned = graph.min_value_cut(before=[node["Add"]], after=[node["Sub"]]) print([label(value.producer()) for value in pinned.values], pinned.bytes) # ['Relu', 'Sigmoid', 'Add'] 72 ``` ## 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. ```cpp title="edits.cpp" int main() { const std::vector signature = {{"x", DataType::Float32, {2, 3}}}; ModelGraph twice = ClikaRT::graph::trace( [](const std::vector& inputs) -> std::vector { 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 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; } ``` ```python title="edits.py" twice = crt.trace(lambda inputs: [crt.relu(crt.relu(inputs[0]))], [crt.TensorSpec("x", crt.float32, [2, 3])]).graph (inner,) = twice.node("x").successors() (outer,) = inner.successors() index = {inner: "inner", outer: "outer"} # views key a dict across edits twice.optimize() # Relu(Relu(x)) is Relu(x): the optimizer removes the outer Relu print(inner.check(), label(inner), inner.output(0).is_graph_output()) # None Relu True try: outer.check() # so does every other read of the view, and any query given it except crt.InvalidArgumentError: print("the outer Relu is gone") # the outer Relu is gone print(index[outer], repr(outer).startswith("Node(gone: ")) # outer True ``` ## 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. ```python title="to_networkx.py" nx_graph = graph.to_networkx() # a networkx.MultiDiGraph whose nodes are the Node views print(nx_graph.number_of_nodes(), nx_graph.number_of_edges()) # 7 9 print(nx.dag_longest_path_length(nx_graph)) # 4 print(sorted(label(node) for node in nx_graph.successors(graph.node("x")))) # ['Relu', 'Sigmoid'] ```