tessl/pypi-rustworkx

A high-performance graph library for Python implemented in Rust, providing fast graph algorithms and data structures for computational tasks

—

Pending

Overview

Eval results

Files

Graph Analysis

Name: tessl/pypi-rustworkx
Author: tessl

Comprehensive tools for analyzing graph structure, connectivity, and properties. These functions provide insights into graph topology, component structure, isomorphism relationships, and various graph-theoretic measures.

Capabilities

Connectivity Analysis

Functions for analyzing how nodes and components are connected within graphs.

def strongly_connected_components(graph) -> list:
    """
    Find strongly connected components in directed graph.
    
    A strongly connected component is a maximal set of vertices
    where every vertex is reachable from every other vertex.
    
    Parameters:
    - graph: PyDiGraph input
    
    Returns:
    list: List of components, each component is list of node indices
    """

def connected_components(graph) -> list:
    """
    Find connected components in undirected graph.
    
    Parameters:
    - graph: PyGraph input
    
    Returns:
    list: List of components, each component is list of node indices
    """

def is_strongly_connected(graph) -> bool:
    """
    Test if directed graph is strongly connected.
    
    Parameters:
    - graph: PyDiGraph input
    
    Returns:
    bool: True if strongly connected, False otherwise
    """

def is_connected(graph) -> bool:
    """
    Test if undirected graph is connected.
    
    Parameters:
    - graph: PyGraph input
    
    Returns:
    bool: True if connected, False otherwise
    """

def is_weakly_connected(graph) -> bool:
    """
    Test if directed graph is weakly connected.
    
    A directed graph is weakly connected if replacing all edges
    with undirected edges produces a connected graph.
    
    Parameters:
    - graph: PyDiGraph input
    
    Returns:
    bool: True if weakly connected, False otherwise
    """

Cut Points and Bridges

Functions for identifying critical vertices and edges whose removal would disconnect the graph.

def articulation_points(graph):
    """
    Find articulation points (cut vertices) in undirected graph.
    
    An articulation point is a vertex whose removal increases
    the number of connected components.
    
    Parameters:
    - graph: PyGraph input
    
    Returns:
    NodeIndices: List of articulation point node indices
    """

def bridges(graph):
    """
    Find bridges (cut edges) in undirected graph.
    
    A bridge is an edge whose removal increases the number
    of connected components.
    
    Parameters:
    - graph: PyGraph input
    
    Returns:
    EdgeList: List of bridge edges as (source, target) tuples
    """

def biconnected_components(graph) -> list:
    """
    Find biconnected components in undirected graph.
    
    A biconnected component is a maximal subgraph with no
    articulation points (cannot be disconnected by removing
    a single vertex).
    
    Parameters:
    - graph: PyGraph input
    
    Returns:
    list: List of biconnected components, each is list of node indices
    """

Topological Analysis

Functions for analyzing directed acyclic graphs and topological properties.

def topological_sort(graph):
    """
    Compute topological ordering of directed acyclic graph.
    
    Returns nodes in topological order where for every directed
    edge (u,v), u appears before v in the ordering.
    
    Parameters:
    - graph: PyDiGraph input (must be acyclic)
    
    Returns:
    NodeIndices: List of node indices in topological order
    
    Raises:
    DAGHasCycle: If graph contains cycles
    """

def is_directed_acyclic_graph(graph) -> bool:
    """
    Test if directed graph is acyclic (is a DAG).
    
    Parameters:
    - graph: PyDiGraph input
    
    Returns:
    bool: True if graph is a DAG, False if it contains cycles
    """

def dag_longest_path(graph, weight_fn = None, default_weight: float = 1.0):
    """
    Find longest path in directed acyclic graph.
    
    Parameters:
    - graph: PyDiGraph input (must be acyclic)
    - weight_fn (callable, optional): Function to extract edge weight
    - default_weight (float): Default edge weight
    
    Returns:
    NodeIndices: List of node indices forming longest path
    
    Raises:
    DAGHasCycle: If graph contains cycles
    """

def condensation(graph, sccs = None):
    """
    Return condensation of directed graph.
    
    The condensation is a DAG where each node represents a
    strongly connected component of the original graph.
    
    Parameters:
    - graph: PyDiGraph input
    - sccs (list, optional): Pre-computed strongly connected components
    
    Returns:
    PyDiGraph: Condensation graph with SCC nodes
    """

Reachability Analysis

Functions for analyzing which nodes can reach which other nodes in directed graphs.

def ancestors(graph, node: int) -> set:
    """
    Find all ancestors of a node in directed graph.
    
    Ancestors are all nodes from which the given node is reachable.
    
    Parameters:
    - graph: PyDiGraph input
    - node (int): Target node index
    
    Returns:
    set: Set of ancestor node indices
    """

def descendants(graph, node: int) -> set:
    """
    Find all descendants of a node in directed graph.
    
    Descendants are all nodes reachable from the given node.
    
    Parameters:
    - graph: PyDiGraph input  
    - node (int): Source node index
    
    Returns:
    set: Set of descendant node indices
    """

Isomorphism Testing

Functions for testing structural equivalence between graphs.

def is_isomorphic(first, second, node_matcher = None, edge_matcher = None, id_order: bool = True, call_limit: int = None) -> bool:
    """
    Test if two graphs are isomorphic using VF2 algorithm.
    
    Parameters:
    - first: First graph (PyGraph or PyDiGraph)
    - second: Second graph (same type as first)
    - node_matcher (callable, optional): Function to compare node data
    - edge_matcher (callable, optional): Function to compare edge data
    - id_order (bool): Use ID-based ordering for better performance on large graphs
    - call_limit (int, optional): Limit on VF2 algorithm iterations
    
    Returns:
    bool: True if graphs are isomorphic, False otherwise
    """

def is_isomorphic_node_match(first, second, matcher, id_order: bool = True) -> bool:
    """
    Test isomorphism with node data matching only.
    
    Parameters:
    - first: First graph
    - second: Second graph  
    - matcher (callable): Function to compare node data
    - id_order (bool): Use ID-based ordering
    
    Returns:
    bool: True if graphs are isomorphic with matching nodes
    """

def is_subgraph_isomorphic(first, second, node_matcher = None, edge_matcher = None, id_order: bool = False, induced: bool = True, call_limit: int = None) -> bool:
    """
    Test if second graph is isomorphic to subgraph of first.
    
    Parameters:
    - first: Host graph
    - second: Pattern graph
    - node_matcher (callable, optional): Function to compare node data
    - edge_matcher (callable, optional): Function to compare edge data
    - id_order (bool): Use ID-based ordering
    - induced (bool): Check for induced subgraph if True
    - call_limit (int, optional): Limit on VF2 algorithm iterations
    
    Returns:
    bool: True if subgraph isomorphism exists
    """

def vf2_mapping(first, second, node_matcher = None, edge_matcher = None, id_order: bool = True, subgraph: bool = False, induced: bool = True, call_limit: int = None):
    """
    Generate all VF2 mappings between graphs.
    
    Returns iterator over all possible isomorphic mappings.
    
    Parameters:
    - first: First graph
    - second: Second graph
    - node_matcher (callable, optional): Function to compare node data
    - edge_matcher (callable, optional): Function to compare edge data
    - id_order (bool): Use ID-based ordering
    - subgraph (bool): Find subgraph isomorphisms if True
    - induced (bool): Check induced subgraphs if True
    - call_limit (int, optional): Limit on VF2 algorithm iterations
    
    Returns:
    Iterable[NodeMap]: Iterator over node index mappings
    """

Graph Properties

Functions for computing various graph-theoretic properties and measures.

def transitivity(graph) -> float:
    """
    Compute transitivity (global clustering coefficient) of graph.
    
    Transitivity is the fraction of triangles to connected triples,
    measuring the tendency of nodes to cluster together.
    
    Parameters:
    - graph: Input graph (PyGraph or PyDiGraph)
    
    Returns:
    float: Transitivity coefficient (0.0 to 1.0)
    
    Note: Assumes no parallel edges or self-loops for accurate results.
    """

def core_number(graph) -> dict:
    """
    Compute k-core decomposition of graph.
    
    The k-core is the maximal subgraph where each vertex has
    degree at least k. Core number is the highest k for which
    a vertex belongs to the k-core.
    
    Parameters:
    - graph: Input graph (PyGraph or PyDiGraph)
    
    Returns:
    dict: Mapping of node indices to core numbers
    
    Note: Assumes no parallel edges or self-loops.
    """

def complement(graph):
    """
    Compute complement of graph.
    
    The complement has the same vertices but complementary edges:
    edges present in original are absent in complement and vice versa.
    
    Parameters:
    - graph: Input graph (PyGraph or PyDiGraph)
    
    Returns:
    Same type as input: Complement graph
    
    Note: Never creates parallel edges or self-loops.
    """

def isolates(graph):
    """
    Find isolated nodes (degree 0) in graph.
    
    Parameters:
    - graph: Input graph
    
    Returns:
    NodeIndices: List of isolated node indices
    """

Bipartite Analysis

Functions for analyzing and testing bipartite graph properties.

def is_bipartite(graph) -> bool:
    """
    Test if graph is bipartite.
    
    A graph is bipartite if its vertices can be colored with
    two colors such that no adjacent vertices have the same color.
    
    Parameters:
    - graph: Input graph
    
    Returns:
    bool: True if graph is bipartite, False otherwise
    """

def two_color(graph) -> dict:
    """
    Compute two-coloring of bipartite graph.
    
    Parameters:
    - graph: Input graph
    
    Returns:
    dict or None: Mapping of node indices to colors (0 or 1),
                  or None if graph is not bipartite
    """

Spanning Trees

Functions for finding spanning trees in undirected graphs.

def minimum_spanning_tree(graph, weight_fn = None, default_weight: float = 1.0):
    """
    Find minimum spanning tree using Prim's algorithm.
    
    Parameters:
    - graph: PyGraph input
    - weight_fn (callable, optional): Function to extract edge weight
    - default_weight (float): Default edge weight
    
    Returns:
    EdgeList: List of edges forming minimum spanning tree
    """

Usage Examples

Connectivity Analysis

import rustworkx as rx

# Create directed graph with multiple components
digraph = rx.PyDiGraph()
nodes = digraph.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
digraph.add_edges_from([
    (nodes[0], nodes[1], None),  # A -> B
    (nodes[1], nodes[2], None),  # B -> C
    (nodes[2], nodes[0], None),  # C -> A (creates SCC)
    (nodes[3], nodes[4], None),  # D -> E (separate component)
])

# Analyze connectivity
sccs = rx.strongly_connected_components(digraph)
print(f"Strongly connected components: {sccs}")

is_strong = rx.is_strongly_connected(digraph)
is_weak = rx.is_weakly_connected(digraph)
print(f"Strongly connected: {is_strong}")
print(f"Weakly connected: {is_weak}")

Cut Points and Bridges Analysis

# Create graph with articulation points
graph = rx.PyGraph()
nodes = graph.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
graph.add_edges_from([
    (nodes[0], nodes[1], None),  # A-B
    (nodes[1], nodes[2], None),  # B-C (B is articulation point)
    (nodes[2], nodes[3], None),  # C-D
    (nodes[3], nodes[4], None),  # D-E
])

# Find critical vertices and edges
articulation_pts = rx.articulation_points(graph)
bridge_edges = rx.bridges(graph)
biconnected = rx.biconnected_components(graph)

print(f"Articulation points: {articulation_pts}")
print(f"Bridges: {bridge_edges}")
print(f"Biconnected components: {biconnected}")

Topological Analysis

# Create DAG for topological analysis
dag = rx.PyDiGraph()
tasks = dag.add_nodes_from(['Start', 'Task1', 'Task2', 'Task3', 'End'])
dag.add_edges_from([
    (tasks[0], tasks[1], None),  # Start -> Task1
    (tasks[0], tasks[2], None),  # Start -> Task2
    (tasks[1], tasks[3], None),  # Task1 -> Task3
    (tasks[2], tasks[3], None),  # Task2 -> Task3
    (tasks[3], tasks[4], None),  # Task3 -> End
])

# Check if DAG and get topological order
is_dag = rx.is_directed_acyclic_graph(dag)
if is_dag:
    topo_order = rx.topological_sort(dag)
    longest_path = rx.dag_longest_path(dag)
    print(f"Topological order: {topo_order}")
    print(f"Longest path: {longest_path}")
else:
    print("Graph contains cycles!")

Isomorphism Testing

# Create two structurally identical graphs
graph1 = rx.PyGraph()
nodes1 = graph1.add_nodes_from(['X', 'Y', 'Z'])
graph1.add_edges_from([(nodes1[0], nodes1[1], 1), (nodes1[1], nodes1[2], 2)])

graph2 = rx.PyGraph()  
nodes2 = graph2.add_nodes_from(['A', 'B', 'C'])
graph2.add_edges_from([(nodes2[0], nodes2[1], 1), (nodes2[1], nodes2[2], 2)])

# Test structural isomorphism
is_iso = rx.is_isomorphic(graph1, graph2)
print(f"Structurally isomorphic: {is_iso}")

# Test with node data matching
is_iso_nodes = rx.is_isomorphic_node_match(
    graph1, graph2, 
    matcher=lambda x, y: True  # Ignore node data differences
)
print(f"Isomorphic ignoring node data: {is_iso_nodes}")

# Generate all mappings
mappings = list(rx.vf2_mapping(graph1, graph2))
print(f"All isomorphic mappings: {mappings}")

Graph Property Analysis

# Compute various graph properties
properties_graph = rx.generators.erdos_renyi_gnp_random_graph(20, 0.3)

# Structural properties
transitivity = rx.transitivity(properties_graph)
core_nums = rx.core_number(properties_graph)
isolated_nodes = rx.isolates(properties_graph)
is_bip = rx.is_bipartite(properties_graph)

print(f"Transitivity: {transitivity:.3f}")
print(f"Max core number: {max(core_nums.values()) if core_nums else 0}")
print(f"Isolated nodes: {len(isolated_nodes)}")
print(f"Is bipartite: {is_bip}")

# Two-coloring if bipartite
if is_bip:
    coloring = rx.two_color(properties_graph)
    print(f"Two-coloring: {coloring}")

Reachability Analysis

# Analyze reachability in directed graph
hierarchy = rx.PyDiGraph()
levels = hierarchy.add_nodes_from(['Root', 'Level1A', 'Level1B', 'Level2A', 'Level2B'])
hierarchy.add_edges_from([
    (levels[0], levels[1], None),  # Root -> Level1A
    (levels[0], levels[2], None),  # Root -> Level1B
    (levels[1], levels[3], None),  # Level1A -> Level2A
    (levels[2], levels[4], None),  # Level1B -> Level2B
])

# Find ancestors and descendants
root_descendants = rx.descendants(hierarchy, levels[0])
leaf_ancestors = rx.ancestors(hierarchy, levels[3])

print(f"Descendants of root: {root_descendants}")
print(f"Ancestors of Level2A: {leaf_ancestors}")

Minimum Spanning Tree

# Find MST in weighted graph
weighted_graph = rx.PyGraph()
cities = weighted_graph.add_nodes_from(['A', 'B', 'C', 'D'])
weighted_graph.add_edges_from([
    (cities[0], cities[1], 5),   # A-B: distance 5
    (cities[0], cities[2], 3),   # A-C: distance 3  
    (cities[1], cities[2], 2),   # B-C: distance 2
    (cities[1], cities[3], 4),   # B-D: distance 4
    (cities[2], cities[3], 6),   # C-D: distance 6
])

mst_edges = rx.minimum_spanning_tree(
    weighted_graph,
    weight_fn=lambda x: x
)

print(f"MST edges: {mst_edges}")
total_weight = sum(weighted_graph.edges()[i] for _, _, i in mst_edges)
print(f"Total MST weight: {total_weight}")

Install with Tessl CLI