Struct Graph 

pub struct Graph {
    pub nodes: Arena<NodeId, Node>,
    pub values: Arena<ValueId, Value>,
    pub inputs: Vec<ValueId>,
    pub outputs: Vec<ValueId>,
    pub initializers: HashMap<ValueId, WeightRef>,
    pub symbol_constraints: HashMap<SymbolId, SymbolConstraints>,
    pub opset_imports: HashMap<String, u64>,
    pub subgraphs: HashMap<(NodeId, String), Graph>,
    /* private fields */
}

A computation graph in SSA form.

Nodes and values live in Arenas keyed by NodeId / ValueId. The mutation API keeps producer/consumer edges consistent, so optimization passes can rewrite the graph and then Graph::validate it.

Fields

nodes: Arena<NodeId, Node>

values: Arena<ValueId, Value>

inputs: Vec<ValueId>

Graph inputs, in order. These have no producer.

outputs: Vec<ValueId>

Graph outputs, in order.

initializers: HashMap<ValueId, WeightRef>

Constant initializer weights, keyed by the value they populate.

symbol_constraints: HashMap<SymbolId, SymbolConstraints>

Constraints on symbolic dimensions.

opset_imports: HashMap<String, u64>

Imported opsets: domain → version.

subgraphs: HashMap<(NodeId, String), Graph>

Subgraph bodies for control-flow ops, keyed by (node, attr_name).

Implementations

impl Graph

pub fn new() -> Self

An empty graph.

Examples found in repository

examples/remove_node_bench.rs (line 7)

fn hub_graph(node_count: usize) -> (Graph, Vec<NodeId>) {
    let mut graph = Graph::new();
    let hub = graph.create_value(DataType::Float32, static_shape([1]));
    graph.add_input(hub);
    let mut nodes = Vec::with_capacity(node_count);
    for _ in 0..node_count {
        let output = graph.create_value(DataType::Float32, static_shape([1]));
        nodes.push(graph.insert_node(Node::new(
            NodeId(0),
            "Identity",
            vec![Some(hub)],
            vec![output],
        )));
    }
    (graph, nodes)
}

pub fn node(&self, id: NodeId) -> &Node

Borrow a node. Panics if id is not live; use Graph::try_node for a checked lookup.

pub fn node_mut(&mut self, id: NodeId) -> &mut Node

Mutably borrow a node. Panics if id is not live.

pub fn try_node(&self, id: NodeId) -> Option<&Node>

Checked node lookup.

pub fn value(&self, id: ValueId) -> &Value

Borrow a value. Panics if id is not live; use Graph::try_value for a checked lookup.

pub fn value_mut(&mut self, id: ValueId) -> &mut Value

Mutably borrow a value. Panics if id is not live.

pub fn try_value(&self, id: ValueId) -> Option<&Value>

Checked value lookup.

pub fn uses(&self, value: ValueId) -> Vec<(NodeId, u32)>

Consuming input slots sorted by (NodeId, input_index).

pub fn consumers(&self, value: ValueId) -> Vec<NodeId>

Distinct consumer nodes sorted by ascending NodeId.

pub fn num_uses(&self, value: ValueId) -> usize

Number of consuming input slots.

pub fn has_uses(&self, value: ValueId) -> bool

Whether at least one node input slot consumes value.

pub fn num_nodes(&self) -> usize

Number of live nodes.

pub fn num_values(&self) -> usize

Number of live values.

pub fn value_type_is_known(&self, id: ValueId) -> bool

Whether a value’s element type came from explicit source type information.

pub fn value_shape_is_known(&self, id: ValueId) -> bool

Whether a value’s rank and dimensions came from explicit source shape information.

pub fn mark_value_type_unknown(&mut self, id: ValueId)

Mark a value’s placeholder element type as unknown.

pub fn mark_value_shape_unknown(&mut self, id: ValueId)

Mark a value’s placeholder shape as unknown.

pub fn create_symbol(&mut self, name: Option<String>) -> SymbolId

Allocate a fresh symbolic dimension with an optional name (no dedup).

pub fn intern_symbol(&mut self, name: &str) -> SymbolId

Intern a symbolic dimension by protobuf dim-param name: repeated names resolve to the same SymbolId (graph-construction invariant §3.5.4).

pub fn create_value(&mut self, dtype: DataType, shape: Shape) -> ValueId

Create a new anonymous value with a contiguous default layout.

Examples found in repository

examples/remove_node_bench.rs (line 8)

fn hub_graph(node_count: usize) -> (Graph, Vec<NodeId>) {
    let mut graph = Graph::new();
    let hub = graph.create_value(DataType::Float32, static_shape([1]));
    graph.add_input(hub);
    let mut nodes = Vec::with_capacity(node_count);
    for _ in 0..node_count {
        let output = graph.create_value(DataType::Float32, static_shape([1]));
        nodes.push(graph.insert_node(Node::new(
            NodeId(0),
            "Identity",
            vec![Some(hub)],
            vec![output],
        )));
    }
    (graph, nodes)
}

pub fn create_named_value( &mut self, name: impl Into<String>, dtype: DataType, shape: Shape, ) -> ValueId

Create a new named value.

pub fn add_input(&mut self, value: ValueId)

Register value as a graph input.

Examples found in repository

examples/remove_node_bench.rs (line 9)

fn hub_graph(node_count: usize) -> (Graph, Vec<NodeId>) {
    let mut graph = Graph::new();
    let hub = graph.create_value(DataType::Float32, static_shape([1]));
    graph.add_input(hub);
    let mut nodes = Vec::with_capacity(node_count);
    for _ in 0..node_count {
        let output = graph.create_value(DataType::Float32, static_shape([1]));
        nodes.push(graph.insert_node(Node::new(
            NodeId(0),
            "Identity",
            vec![Some(hub)],
            vec![output],
        )));
    }
    (graph, nodes)
}

pub fn add_output(&mut self, value: ValueId)

Register value as a graph output.

pub fn insert_output(&mut self, index: usize, value: ValueId)

Insert value into the ordered graph outputs.

pub fn remove_input(&mut self, index: usize) -> ValueId

Remove one ordered graph input.

pub fn remove_output(&mut self, index: usize) -> ValueId

Remove one ordered graph output.

pub fn set_inputs(&mut self, inputs: Vec<ValueId>)

Replace the complete ordered graph-input list.

pub fn set_outputs(&mut self, outputs: Vec<ValueId>)

Replace the complete ordered graph-output list.

pub fn set_initializer(&mut self, value: ValueId, weight: WeightRef)

Attach initializer weights to value.

pub fn predecessors(&self, node: NodeId) -> Vec<NodeId>

Direct predecessors: nodes that produce this node’s inputs.

pub fn successors(&self, node: NodeId) -> Vec<NodeId>

Direct successors: nodes that consume this node’s outputs.

pub fn nodes_between( &self, inputs: &[ValueId], outputs: &[ValueId], ) -> Vec<NodeId>

All nodes that lie on a path between inputs and outputs.

Walks backwards from outputs via producer edges, stopping at any value in inputs. Used to extract subgraphs for EP capability claims (§3.4).

pub fn topological_order(&self) -> Result<Vec<NodeId>, GraphError>

Topological order of nodes via Kahn’s algorithm.

Ties are broken by ascending NodeId for deterministic output. Returns GraphError::CycleDetected if the graph has a cycle.

pub fn insert_node(&mut self, node: Node) -> NodeId

Insert a node, wiring its producer/consumer edges. The node’s id field is overwritten with the freshly allocated NodeId.

Examples found in repository

examples/remove_node_bench.rs (lines 13-18)

fn hub_graph(node_count: usize) -> (Graph, Vec<NodeId>) {
    let mut graph = Graph::new();
    let hub = graph.create_value(DataType::Float32, static_shape([1]));
    graph.add_input(hub);
    let mut nodes = Vec::with_capacity(node_count);
    for _ in 0..node_count {
        let output = graph.create_value(DataType::Float32, static_shape([1]));
        nodes.push(graph.insert_node(Node::new(
            NodeId(0),
            "Identity",
            vec![Some(hub)],
            vec![output],
        )));
    }
    (graph, nodes)
}

pub fn remove_node(&mut self, id: NodeId)

Remove a node, disconnecting its edges. Output values left with no consumers (and not graph I/O or initializers) are deleted.

Examples found in repository

examples/remove_node_bench.rs (line 27)

fn sequential_remove(node_count: usize) -> Duration {
    let (mut graph, nodes) = hub_graph(node_count);
    let start = Instant::now();
    for node in nodes {
        graph.remove_node(node);
    }
    let elapsed = start.elapsed();
    black_box(graph);
    elapsed
}

fn single_hub_disconnect(node_count: usize, repeats: usize) -> Duration {
    let (base, nodes) = hub_graph(node_count);
    let target = nodes[0];
    let mut elapsed = Duration::ZERO;
    for _ in 0..repeats {
        let mut graph = base.clone();
        let start = Instant::now();
        graph.remove_node(target);
        elapsed += start.elapsed();
        black_box(graph);
    }
    elapsed / repeats as u32
}

pub fn remove_nodes(&mut self, ids: &[NodeId])

Remove nodes in slice order.

Each input edge is removed directly by (NodeId, input_index), so this remains linear in the number of removed edges even for a high-fanout shared value.

pub fn replace_node_groups( &mut self, groups: Vec<(Vec<NodeId>, Node)>, graph_outputs: &HashSet<ValueId>, ) -> Vec<NodeId>

Replace disjoint node groups with one node each while updating shared producer/consumer metadata in a batch.

Each group is semantically equivalent to calling Graph::remove_node for its IDs in slice order and then Graph::insert_node for the replacement. In particular, replacement IDs and orphan-value collection match that sequential operation. graph_outputs is retained for API compatibility and checked against the per-value membership invariant in debug builds.

pub fn replace_node(&mut self, old: NodeId, new: Node) -> NodeId

Replace node old in place with new, preserving the NodeId.

The old node’s edges are disconnected and the new node’s edges are connected. Values that were outputs of old but not of new are left in place (producer cleared); the caller may prune them.

pub fn insert_on_edge(&mut self, value: ValueId, new_node: Node) -> NodeId

Splice new_node onto the edge feeding out of value: producer(value) → [new_node] → consumers(value).

new_node’s single input becomes value, and it produces a fresh value that replaces value in all of value’s original consumers.

pub fn replace_input( &mut self, node: NodeId, input_index: usize, new_value: Option<ValueId>, ) -> Option<ValueId>

Replace one node input and update both values’ consumer sets.

This is constant-time on average for edge metadata. None disconnects the slot and is used by node removal.

pub fn replace_all_uses(&mut self, old_value: ValueId, new_value: ValueId)

Replace every use of old_value with new_value in consumer nodes and in the graph output list, moving consumer edges accordingly.

pub fn validate(&self) -> Result<(), Vec<GraphError>>

Verify structural invariants (§3.3). Returns every defect found.

Trait Implementations

impl Clone for Graph

fn clone(&self) -> Graph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Graph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Graph

fn default() -> Graph

Returns the “default value” for a type.