Graph Core Functions

The file forge.relay.graph.graph_core.py houses the core components that enable Forge's graphical support of Relay. Forge 'encodes' and 'decodes' instances of Relay objects into instances of igraph.Graph objects. iGraph is a fast, C-based library for creating and analyzing graphs, offering flexible metadata support and powerful features.

Vertex Attributes

Leveraging the igraph.Vertex API, Forge creates vertex fields/attributes to achieve a 1-to-1 encoding of Relay objects. The attributes can be split into two categories: representation-critical and feature-helpful.

Representation Critical:

• name # MUST be unique
• type # the vertex's Relay expression type
• op_name # operator name
• op_type # operator type
• op_attrs # operator attributes
• activation # activation metadata
• tuple_index # index for tuple access
• const_data # static values
• func_attrs # function attributes

Feature Helpful:

• input_index # positional input index (also used for identifying input nodes)
• layout # tensor layout

Encoding

forge.relay.graph.graph_core.get_call_attributes(name: str, call: Relay.Call.obj) -> Dict[str, Any]

Extracts attributes from a Relay Call object for use in graph construction.

Parameters:

Name	Type	Description	Default
name	str	The name to assign to the call node.	required
call	obj	The Relay Call object to extract attributes from.	required

Returns:

Type	Description
Dict[str, Any]	Dict[str, Any]: A dictionary containing attributes of the Relay Call, including its type, operator type, operator name, operator attributes, and activation metadata.

Raises:

Type	Description
GraphError	If the call.op type is unexpected.

forge.relay.graph.graph_core.get_tuple_attributes(name: str, tup: Relay.Tuple.obj) -> Dict[str, Any]

Extracts attributes from a Relay Tuple object for use in graph construction.

Parameters:

Name	Type	Description	Default
name	str	The name to assign to the tuple node.	required
tup	obj	The Relay Tuple object to extract attributes from.	required

Returns:

Type	Description
Dict[str, Any]	Dict[str, Any]: A dictionary containing attributes of the Relay Tuple, including its type and activation metadata.

forge.relay.graph.graph_core.get_tupleget_attributes(name: str, tupget: Relay.TupleGetItem.obj) -> Dict[str, Any]

Extracts attributes from a Relay TupleGetItem object for use in graph construction.

Parameters:

Name	Type	Description	Default
name	str	The name to assign to the tuple-get-item node.	required
tupget	obj	The Relay TupleGetItem object to extract attributes from.	required

Returns:

Type	Description
Dict[str, Any]	Dict[str, Any]: A dictionary containing attributes of the Relay TupleGetItem, including its type, activation metadata, and the index of the tuple element accessed.

forge.relay.graph.graph_core.get_var_attributes(name: str, var: Relay.Var.obj, input_index: Optional[int]) -> Dict[str, Any]

Extracts attributes from a Relay Var object for use in graph construction.

Parameters:

Name	Type	Description	Default
name	str	The name to assign to the variable node.	required
var	obj	The Relay Var object to extract attributes from.	required
input_index	Optional[int]	The input index of the variable, if applicable.	required

Returns:

Type	Description
Dict[str, Any]	Dict[str, Any]: A dictionary containing attributes of the Relay Var, including its type, activation metadata, and input index.

forge.relay.graph.graph_core.get_constant_attributes(name: str, const: Relay.Constant.obj) -> Dict[str, Any]

Extracts attributes from a Relay Constant object for use in graph construction.

Parameters:

Name	Type	Description	Default
name	str	The name to assign to the constant node.	required
const	obj	The Relay Constant object to extract attributes from.	required

Returns:

Type	Description
Dict[str, Any]	Dict[str, Any]: A dictionary containing attributes of the Relay Constant, including its type, activation metadata, and constant data in a flattened list format.

forge.relay.graph.graph_core.get_function_attributes(name: str, fn: Relay.Function.obj) -> Dict[str, Any]

Extracts attributes from a Relay Function object for use in graph construction.

Parameters:

Name	Type	Description	Default
name	str	The name to assign to the function node.	required
fn	obj	The Relay Function object to extract attributes from.	required

Returns:

Type	Description
Dict[str, Any]	Dict[str, Any]: A dictionary containing attributes of the Relay Function, including its type, activation metadata, and function attributes (if any).

Edge Attribute

In the encoded graph, every edge captures the positional relationship between expressions, reflecting an evaluable Relay expression. For example, in the expression subtract(a, b), the graph encodes the 'Call' to expressions a and b while preserving the order of arguments, which is critical for evaluation.

Since any expression can serve as an argument to another expression, this positional relationship is naturally represented as an edge attribute. Each edge in Forge's encoding includes an argidx attribute, which explicitly denotes the argument's position (e.g., argidx=0 for a and argidx=1 for b).

Graph Functions

Graphically encoded Relay expressions will have the following properties:

• Directed edges
• No cycles (DAG)
• No multi-edges
• Single artificial sink vertex (tree-like)

Encoding & Decoding

forge.relay.graph.graph_core.from_relay(relay_expr: Relay.Node.obj, sink_name: str = 'Sink', input_names: Optional[Iterable[str]] = None) -> igraph.Graph

Encodes a Relay expression into an igraph.Graph.

This function acts as a "frontend" to encode Relay expressions into an igraph.Graph object. It does not support Relay IRModule objects, as these are treated as "non-graphical" objects. However, any Relay expression that can be expressed as a Relay Function or the body of a Relay Function will be encoded as a directed acyclic graph (DAG) with an artificial sink node that serves as the "root" for the "DAG-tree".

Parameters:

Name	Type	Description	Default
relay_expr	obj	A valid Relay expression.	required
sink_name	str	Optional name for the artificial sink node.	'Sink'
input_names	Sequence[str]	A set of input names that will be mapped as Input nodes instead of Var nodes.	None

Examples:

Invalid usage on a Relay IRModule:

mod = ...  # Relay IRModule
from_relay(mod)  # Raises an error

Valid usage on a Relay Function:

from_relay(mod.functions["main"])

Valid usage on a Relay expression:

from_relay(mod.functions["main"].body)  # e.g., Call/Var/Tuple/etc.

Notes

All vertices are initialized with the fields keyed in GRAPH_VERTEX_ATTRIBUTES.

forge.relay.graph.graph_core.to_relay(g: igraph.Graph, root_vertex: Optional[igraph.Vertex] = None, global_vars: Optional[Dict[str, Relay.GlobalVar.obj]] = None) -> Relay.Node.obj

Decodes an igraph.Graph representation back into a Relay object.

Parameters:

Name	Type	Description	Default
g	Graph	A valid graph encoding.	required
root_vertex	Optional[Vertex]	The root vertex for decoding a portion of the graph. If specified, the function returns a Relay expression object for the graph-tree rooted at root_vertex. Defaults to decoding the entire graph rooted at its artificial sink.	None

Helper Functions

Collection of procedures that provide the foundational and core features of a graphically encoded Relay expression using iGraph.

forge.relay.graph.graph_core.sanitize_graph(g: igraph.Graph) -> None

Removes any vertices in the graph that do not have a simple path to the artificial sink node.

Parameters:

Name	Type	Description	Default
g	Graph	The graph from which disconnected vertices are removed. The artificial sink node is assumed to have the attribute type="Sink".	required

forge.relay.graph.graph_core.iter_vertex_args(vertex: igraph.Vertex) -> Iterator[igraph.Vertex]

Iterates over the input vertices of a vertex, ordered by the expression's argument index.

Parameters:

Name	Type	Description	Default
vertex	Vertex	The vertex whose input vertices are to be iterated.	required

Yields:

Type	Description
Vertex	igraph.Vertex: Input vertices in the order specified by the argidx attribute of the edges.

forge.relay.graph.graph_core.list_vertex_args(vertex: igraph.Vertex) -> List[igraph.Vertex]

Returns a list of the input vertices of a vertex, ordered by the expression's argument index.

Parameters:

Name	Type	Description	Default
vertex	Vertex	The vertex whose input vertices are to be listed.	required

Returns:

Type	Description
List[Vertex]	List[igraph.Vertex]: Input vertices in the order specified by the argidx attribute of the edges.

forge.relay.graph.graph_core.iter_predecessors(vertex: igraph.Vertex, in_order: bool = True) -> Iterator[igraph.Vertex]

Iterates over the ancestors of a vertex in a depth-first pre-order traversal.

Parameters:

Name	Type	Description	Default
vertex	Vertex	The vertex whose ancestors are to be iterated.	required
in_order	bool	Whether to traverse in pre-order DFS. If False, traversal order is arbitrary but faster. Defaults to True.	True

Yields:

Type	Description
Vertex	igraph.Vertex: Ancestor vertices in the traversal order.

forge.relay.graph.graph_core.iter_successors(vertex: igraph.Vertex) -> Iterator[igraph.Vertex]

Iterates over the successors (children) of a vertex in a depth-first traversal. There is no "order" in this iteration.

Parameters:

Name	Type	Description	Default
vertex	Vertex	The vertex whose successors are to be iterated.	required

Yields:

Type	Description
Vertex	igraph.Vertex: Successor vertices in traversal order.

forge.relay.graph.graph_core.add_vertex(g: igraph.Graph, vertex_attributes: Dict[str, Any]) -> igraph.Vertex

Adds a new vertex to the graph with specified attributes.

Parameters:

Name	Type	Description	Default
g	Graph	The graph to which the vertex will be added.	required
vertex_attributes	Dict[str, Any]	A dictionary of attributes for the new vertex. Must include a name key.	required

Returns:

Type	Description
Vertex	igraph.Vertex: The newly added vertex.

Raises:

Type	Description
GraphError	If a vertex with the same name already exists in the graph.

forge.relay.graph.graph_core.add_vertices(g: igraph.Graph, vertex_attributes: Dict[str, List[Any]]) -> None

Adds multiple vertices to the graph with specified attributes.

Parameters:

Name	Type	Description	Default
g	Graph	The graph to which the vertices will be added.	required
vertex_attributes	Dict[str, List[Any]]	A dictionary where keys are attribute names and values are lists of attribute values for each new vertex.	required

Raises:

Type	Description
GraphError	If any of the specified vertex names already exist in the graph.

forge.relay.graph.graph_core.add_edge(g: igraph.Graph, source: Union[igraph.Vertex, str], target: Union[igraph.Vertex, str], argidx: int) -> igraph.Edge

Adds a directed edge between two vertices in the graph.

Parameters:

Name	Type	Description	Default
g	Graph	The graph to which the edge will be added.	required
source	Union[Vertex, str]	The source vertex or its name.	required
target	Union[Vertex, str]	The target vertex or its name.	required
argidx	int	The argument index describing the positional relationship of the source vertex to the target vertex.	required

Returns:

Type	Description
Edge	igraph.Edge: The newly added edge.

Raises:

Type	Description
GraphError	If an edge with the specified argument index already exists between the source and target vertices.

forge.relay.graph.graph_core.add_edges(g: igraph.Graph, edges: List[Tuple[Union[igraph.Vertex, str], Union[igraph.Vertex, str]]], argidxs: List[int]) -> None

Adds multiple directed edges to the graph.

Parameters:

Name	Type	Description	Default
g	Graph	The graph to which the edges will be added.	required
edges	List[Tuple[Union[Vertex, str], Union[Vertex, str]]]	A list of tuples specifying source and target vertices or their names.	required
argidxs	List[int]	A list of argument indices describing positional relationships of source vertices to target vertices.	required

Note

This function does not check for duplicate edges.

forge.relay.graph.graph_core.delete_subdag(vertex: igraph.Vertex) -> None

Deletes the subgraph rooted at a specified vertex.

Parameters:

Name	Type	Description	Default
vertex	Vertex	The root vertex of the subgraph to be deleted.	required

forge.relay.graph.graph_core.delete_unary_vertex(vertex: igraph.Vertex) -> None

Deletes a unary vertex (a vertex with one in-edge and one or more out-edges) and stitches its predecessor to its successors.

Parameters:

Name	Type	Description	Default
vertex	Vertex	The unary vertex to be deleted.	required

Raises:

Type	Description
AssertionError	If the vertex does not have exactly one in-edge and at least one out-edge.

forge.relay.graph.graph_core.get_input_names(g: igraph.Graph) -> List[str]

Returns a list of input vertex names in evaluation order.

Parameters:

Name	Type	Description	Default
g	Graph	The graph from which input names are retrieved.	required

Returns:

Type	Description
List[str]	List[str]: A list of names of input vertices, ordered by their evaluation sequence.

Embed Function

The singular graph manipulation function to rule them all.

forge.relay.graph.graph_core.embed_graph(g: igraph.Graph, graft: igraph.Graph, target_names: List[str], target_argidxs: List[int]) -> str

Embeds a subgraph (graft) into a target graph (g) by connecting the graft's sink to specified target vertices.

The grafted subgraph retains its structure and becomes part of the original graph. Connections are made using the provided target names and argument indices, and existing edges to the targets are replaced with edges from the graft.

Parameters:

Name	Type	Description	Default
g	Graph	The target graph where the graft will be embedded.	required
graft	Graph	The subgraph to embed. Its root must be connected to a Sink vertex.	required
target_names	List[str]	The names of the vertices in the target graph to which the graft's root will be connected.	required
target_argidxs	List[int]	Argument indices corresponding to the positional connections for the target vertices.	required

Returns:

Name	Type	Description
str	str	The name of the graft's root vertex, now part of the target graph.

Raises:

Type	Description
AssertionError	If target_names or target_argidxs are empty, their lengths do not match, or if a target name does not exist in the target graph.
GraphError	If the embedding process results in a corrupted graph that is no longer a DAG.

Note

• The grafted subgraph's vertices and edges are added to the target graph while ensuring that existing edges to the target vertices are correctly replaced.

• The function uses sanitize_graph to clean up and validate the graph after embedding.