Python API Reference

This page provides the complete Python API reference for PARAGON.

Core Data Structures

class paragon.core.Graph(vertices: int | List[List[int]], edges: Iterable[Tuple[int, int]] | None = None, directed: bool = False)

Bases: Graph

Unweighted graph data structure.

This class provides a Python interface over a high-performance C++ graph implementation. It supports flexible initialization and efficient graph operations.

Initialization styles

1. Graph(vertices)

2. Graph(adjacency_list)

3. Graph(vertices, edges)

Notes

• Nodes are indexed from 0 to V-1

• Uses adjacency list internally

• Supports both directed and undirected graphs

add_edge(u: int, v: int) → None

Add an edge between two vertices.

Parameters:

• u (int) – Source vertex

• v (int) – Destination vertex

Raises:

• TypeError – If inputs are not integers

• ValueError – If indices are negative

add_edges(edges: Iterable[Tuple[int, int]]) → None

Add multiple edges.

Parameters:

edges (Iterable[Tuple[int, int]]) – Collection of edges (u, v)

add_vertex() → None

Add a new vertex to the graph.

The new vertex will have no edges initially.

build_from_adj_list(adjacency: List[List[int]]) → None

Build graph from adjacency list.

Parameters:

adjacency (List[List[int]]) – adjacency[i] contains neighbors of node i

build_from_adj_matrix(matrix: List[List[int]]) → None

Build graph from adjacency matrix.

Parameters:

matrix (List[List[int]]) – Square matrix where matrix[i][j] = 1 indicates edge

degree(u: int) → int

Get degree of a vertex.

Parameters:

u (int)

Return type:

int

get_adj() → List[List[int]]

Get adjacency list.

Return type:

List[List[int]]

has_edge(u: int, v: int) → bool

Check if edge exists.

Parameters:

• u (int)

• v (int)

Return type:

bool

is_directed() → bool

Check if graph is directed.

Return type:

bool

print_graph() → None

Print graph structure (for debugging).

vertices() → int

Get number of vertices.

Return type:

int

class paragon.core.WeightedGraph(vertices: int, directed: bool = False)

Bases: WeightedGraph

Weighted graph data structure.

This extends the Graph class by associating weights with edges.

Notes

• Edge weights are stored as float

• Supports directed and undirected graphs

add_edge(u: int, v: int, w: float) → None

Add weighted edge.

Parameters:

• u (int)

• v (int)

• w (float) – Edge weight

Raises:

TypeError – If invalid types

add_edges(edges: Iterable[Tuple[int, int, float]]) → None

Add multiple weighted edges.

Parameters:

edges (Iterable[Tuple[int, int, float]])

add_vertex() → None

Add new vertex.

build_from_adj_list(adjacency: List[List[Tuple[int, float]]]) → None

Build graph from weighted adjacency list.

Parameters:

adjacency (List[List[Tuple[int, float]]])

build_from_adj_matrix(matrix: List[List[float]]) → None

Build graph from weighted adjacency matrix.

Parameters:

matrix (List[List[float]])

degree(u: int) → int

Return degree of vertex.

get_adj() → List[List[Tuple[int, float]]]

Get weighted adjacency list.

Return type:

List[List[Tuple[int, float]]]

has_edge(u: int, v: int) → bool

Check if edge exists.

is_directed() → bool

Check if graph is directed.

print_graph() → None

Print weighted graph.

vertices() → int

Return number of vertices.

class paragon.Graph(vertices: int | List[List[int]], edges: Iterable[Tuple[int, int]] | None = None, directed: bool = False)

Bases: Graph

Unweighted graph data structure.

This class provides a Python interface over a high-performance C++ graph implementation. It supports flexible initialization and efficient graph operations.

Initialization styles

1. Graph(vertices)

2. Graph(adjacency_list)

3. Graph(vertices, edges)

Notes

• Nodes are indexed from 0 to V-1

• Uses adjacency list internally

• Supports both directed and undirected graphs

__bool__() → bool

Check if graph is non-empty.

Enables usage like: if graph:

Return type:

bool

__contains__(node: int) → bool

Check if a node exists in the graph.

Enables usage like: node in graph

Parameters:

node (int)

Return type:

bool

__copy__()

Create a shallow copy of the graph.

Return type:

Graph

__deepcopy__(memo)

Create a deep copy of the graph.

Parameters:

memo (dict)

Return type:

Graph

__eq__(other) → bool

Compare two graphs for equality.

Two graphs are equal if: - Same number of vertices - Same adjacency list - Same directed property

Parameters:

other (Graph)

Return type:

bool

__getitem__(node: int)

Get neighbors of a node.

Enables usage like: graph[node]

Parameters:

node (int)

Return type:

List[int]

__init__(vertices: int | List[List[int]], edges: Iterable[Tuple[int, int]] | None = None, directed: bool = False) → None

Initialize a graph.

Parameters:

• vertices (int or List[List[int]]) –

  • If int → number of vertices

  • If List → adjacency list

• edges (Iterable[Tuple[int, int]], optional) – List of edges (u, v)

• directed (bool, default=False) – Whether the graph is directed

Raises:

TypeError – If invalid arguments are provided

Examples

>>> g = Graph(5)
>>> g = Graph([[1, 2], [0], [0]])
>>> g = Graph(3, [(0, 1), (1, 2)])

__iter__()

Iterate over graph nodes.

Enables usage like: for node in graph

Return type:

iterator

__len__() → int

Return number of vertices in the graph.

Enables usage of len(graph).

Return type:

int

__ne__(other) → bool

Check if two graphs are not equal.

Parameters:

other (Graph)

Return type:

bool

__repr__() → str

Return developer-friendly string representation of the graph.

Includes number of vertices, edges, and graph type.

Return type:

str

add_edge(u: int, v: int) → None

Add an edge between two vertices.

Parameters:

• u (int) – Source vertex

• v (int) – Destination vertex

Raises:

• TypeError – If inputs are not integers

• ValueError – If indices are negative

add_edges(edges: Iterable[Tuple[int, int]]) → None

Add multiple edges.

Parameters:

edges (Iterable[Tuple[int, int]]) – Collection of edges (u, v)

add_vertex() → None

Add a new vertex to the graph.

The new vertex will have no edges initially.

build_from_adj_list(adjacency: List[List[int]]) → None

Build graph from adjacency list.

Parameters:

adjacency (List[List[int]]) – adjacency[i] contains neighbors of node i

build_from_adj_matrix(matrix: List[List[int]]) → None

Build graph from adjacency matrix.

Parameters:

matrix (List[List[int]]) – Square matrix where matrix[i][j] = 1 indicates edge

degree(u: int) → int

Get degree of a vertex.

Parameters:

u (int)

Return type:

int

get_adj() → List[List[int]]

Get adjacency list.

Return type:

List[List[int]]

has_edge(u: int, v: int) → bool

Check if edge exists.

Parameters:

• u (int)

• v (int)

Return type:

bool

is_directed() → bool

Check if graph is directed.

Return type:

bool

print_graph() → None

Print graph structure (for debugging).

vertices() → int

Get number of vertices.

Return type:

int

class paragon.WeightedGraph(vertices: int, directed: bool = False)

Bases: WeightedGraph

Weighted graph data structure.

This extends the Graph class by associating weights with edges.

Notes

• Edge weights are stored as float

• Supports directed and undirected graphs

__bool__() → bool

Check if graph is non-empty.

Return type:

bool

__contains__(node: int) → bool

Check if node exists.

Parameters:

node (int)

Return type:

bool

__copy__()

Shallow copy.

Return type:

WeightedGraph

__deepcopy__(memo)

Deep copy.

Return type:

WeightedGraph

__eq__(other) → bool

Compare graphs.

Return type:

bool

__getitem__(node: int)

Get neighbors of node.

Parameters:

node (int)

Return type:

List[Tuple[int, float]]

__init__(vertices: int, directed: bool = False) → None

Initialize weighted graph.

Parameters:

• vertices (int) – Number of vertices

• directed (bool, default=False)

Raises:

ValueError – If vertices is invalid

__iter__()

Iterate over nodes.

Return type:

iterator

__len__() → int

Return number of vertices.

Return type:

int

__ne__(other) → bool

Check inequality.

Return type:

bool

__repr__() → str

Return developer-friendly string representation.

Return type:

str

add_edge(u: int, v: int, w: float) → None

Add weighted edge.

Parameters:

• u (int)

• v (int)

• w (float) – Edge weight

Raises:

TypeError – If invalid types

add_edges(edges: Iterable[Tuple[int, int, float]]) → None

Add multiple weighted edges.

Parameters:

edges (Iterable[Tuple[int, int, float]])

add_vertex() → None

Add new vertex.

build_from_adj_list(adjacency: List[List[Tuple[int, float]]]) → None

Build graph from weighted adjacency list.

Parameters:

adjacency (List[List[Tuple[int, float]]])

build_from_adj_matrix(matrix: List[List[float]]) → None

Build graph from weighted adjacency matrix.

Parameters:

matrix (List[List[float]])

degree(u: int) → int

Return degree of vertex.

get_adj() → List[List[Tuple[int, float]]]

Get weighted adjacency list.

Return type:

List[List[Tuple[int, float]]]

has_edge(u: int, v: int) → bool

Check if edge exists.

is_directed() → bool

Check if graph is directed.

print_graph() → None

Print weighted graph.

vertices() → int

Return number of vertices.

Graph Generators

Graph Generation Utilities

This module provides helper functions to generate sample graphs using probabilistic distributions.

Currently supported: - Normal (Gaussian) distribution based graph generation

paragon.graphs.generate_normal_graph(vertices: int, edges: int, directed: bool = False, mean: float | None = None, std: float | None = None, seed: int | None = None) → Graph

Generate a graph using a normal (Gaussian) distribution.

This function creates a graph with approximately edges edges, where node selection follows a normal distribution.

Parameters:

• vertices (int) – Number of vertices (V)

• edges (int) – Number of edges (E)

• directed (bool, optional (default=False)) – Whether the graph is directed

• mean (float, optional) – Mean of the normal distribution (default = V/2)

• std (float, optional) – Standard deviation (default = V/6)

• seed (int, optional) – Random seed for reproducibility

Returns:

Generated graph instance

Return type:

Graph

Notes

• Nodes near the mean will have higher connectivity

• Useful for testing clustered graph structures

• Does not guarantee exact E edges (approximate)

Example

>>> from paragon.graphs import generate_normal_graph
>>> g = generate_normal_graph(vertices=10, edges=20)
>>> print(g.vertices())
10
>>> print(len(g.get_adj()))
10

paragon.graphs.generate_normal_weighted_graph(vertices: int, edges: int, directed: bool = False, mean: float | None = None, std: float | None = None, weight_range: Tuple[float, float] = (1.0, 10.0), weight_distribution: str = 'uniform', seed: int | None = None) → WeightedGraph

Generate a weighted graph using a normal (Gaussian) distribution.

Parameters:

• vertices (int) – Number of vertices

• edges (int) – Number of edges

• directed (bool, default=False)

• mean (float, optional) – Mean for node sampling (default = V/2)

• std (float, optional) – Standard deviation (default = V/6)

• weight_range (Tuple[float, float], default=(1.0, 10.0)) – Range of edge weights

• weight_distribution (str, default="uniform") – Options: - “uniform” - “normal”

• seed (int, optional)

Return type:

WeightedGraph

Example

>>> from paragon.graphs import generate_normal_weighted_graph
>>> g = generate_normal_weighted_graph(10, 20)
>>> print(g.get_adj()[0])
[(3, 4.2), (5, 7.1)]

paragon.graphs.generate_normal_graph(vertices: int, edges: int, directed: bool = False, mean: float | None = None, std: float | None = None, seed: int | None = None) → Graph

Generate a graph using a normal (Gaussian) distribution.

This function creates a graph with approximately edges edges, where node selection follows a normal distribution.

Parameters:

• vertices (int) – Number of vertices (V)

• edges (int) – Number of edges (E)

• directed (bool, optional (default=False)) – Whether the graph is directed

• mean (float, optional) – Mean of the normal distribution (default = V/2)

• std (float, optional) – Standard deviation (default = V/6)

• seed (int, optional) – Random seed for reproducibility

Returns:

Generated graph instance

Return type:

Graph

Notes

• Nodes near the mean will have higher connectivity

• Useful for testing clustered graph structures

• Does not guarantee exact E edges (approximate)

Example

>>> from paragon.graphs import generate_normal_graph
>>> g = generate_normal_graph(vertices=10, edges=20)
>>> print(g.vertices())
10
>>> print(len(g.get_adj()))
10

paragon.graphs.generate_normal_weighted_graph(vertices: int, edges: int, directed: bool = False, mean: float | None = None, std: float | None = None, weight_range: Tuple[float, float] = (1.0, 10.0), weight_distribution: str = 'uniform', seed: int | None = None) → WeightedGraph

Generate a weighted graph using a normal (Gaussian) distribution.

Parameters:

• vertices (int) – Number of vertices

• edges (int) – Number of edges

• directed (bool, default=False)

• mean (float, optional) – Mean for node sampling (default = V/2)

• std (float, optional) – Standard deviation (default = V/6)

• weight_range (Tuple[float, float], default=(1.0, 10.0)) – Range of edge weights

• weight_distribution (str, default="uniform") – Options: - “uniform” - “normal”

• seed (int, optional)

Return type:

WeightedGraph

Example

>>> from paragon.graphs import generate_normal_weighted_graph
>>> g = generate_normal_weighted_graph(10, 20)
>>> print(g.get_adj()[0])
[(3, 4.2), (5, 7.1)]

Graph Algorithms

paragon.algorithms.parallel_bfs(graph: Graph, source: int, threads: int = -1) → List[int]

Perform parallel breadth-first search (BFS) on a graph.

This function computes the shortest distance from the source node to all other nodes in an unweighted graph using a level-synchronous parallel approach.

Parameters:

• graph (Graph) – Input graph (unweighted).

• source (int) – Starting node for BFS traversal.

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

A list where: - dist[i] = shortest distance from source to node i - dist[i] = -1 if node i is unreachable

Return type:

List[int]

Notes

• Uses level-synchronous traversal (frontier-based).

• Each level is processed in parallel across threads.

• Thread-safe using atomic distance updates and mutex-protected frontier.

Time Complexity

O(V + E) (parallelized)

Example

>>> from paragon import Graph
>>> from paragon.algorithms import parallel_bfs
>>> g = Graph(5)
>>> g.add_edges([(0,1), (1,2), (2,3)])
>>> parallel_bfs(g, 0)
[0, 1, 2, 3, -1]

paragon.algorithms.parallel_connected_components(graph: Graph, threads: int = -1) → List[int]

Compute connected components of a graph in parallel.

This function assigns a component label to each node such that nodes with the same label belong to the same connected component.

Parameters:

• graph (Graph) – Input graph (typically undirected).

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

A list where: - component[i] = component ID of node i - Nodes with the same ID belong to the same component

Return type:

List[int]

Notes

• Based on a parallel Shiloach–Vishkin style algorithm.

• Uses pointer jumping (path compression) for efficiency.

• Iteratively merges components until convergence.

Time Complexity

Approximately O((V + E) log V) in parallel settings.

Example

>>> from paragon import Graph
>>> from paragon.algorithms import connected_components
>>> g = Graph(6)
>>> g.add_edges([(0,1), (1,2), (3,4)])
>>> connected_components(g)
[0, 0, 0, 3, 3, 5]

paragon.algorithms.parallel_dfs(graph: Graph, source: int, threads: int = -1) → List[bool]

Perform parallel depth-first search (DFS) on a graph.

This function explores all nodes reachable from the given source using a parallel, multi-threaded approach.

Parameters:

• graph (Graph) – Input graph (unweighted).

• source (int) – Starting node for DFS traversal.

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

A boolean list where: - visited[i] = True → node i is reachable from source - visited[i] = False → node i is not reachable

Return type:

List[bool]

Notes

• Uses a shared work stack across threads.

• Thread-safe via atomic visited array and mutex-protected stack.

• Efficient for large graphs with multiple connected regions.

Time Complexity

O(V + E) (parallelized)

Example

>>> from paragon import Graph
>>> from paragon.algorithms import parallel_dfs
>>> g = Graph(5)
>>> g.add_edges([(0,1), (1,2), (2,3)])
>>> parallel_dfs(g, 0)
[True, True, True, True, False]

paragon.algorithms.parallel_dijkstra(graph: WeightedGraph, source: int, threads: int = -1) → List[float]

Compute shortest paths from a source node in a weighted graph.

This function computes the shortest distance from the source node to all other nodes using a parallel relaxation-based approach.

Parameters:

• graph (WeightedGraph) – Input weighted graph with non-negative edge weights.

• source (int) – Starting node.

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

A list where: - dist[i] = shortest distance from source to node i - dist[i] = large value (INF) if unreachable

Return type:

List[float]

Notes

• Uses parallel edge relaxation (similar to Bellman-Ford).

• Stops early if no updates occur in an iteration.

• Works only for graphs with non-negative weights.

Time Complexity

O(V × E) worst case, with early stopping in practice.

Example

>>> from paragon import WeightedGraph
>>> from paragon.algorithms import parallel_dijkstra
>>> g = WeightedGraph(4)
>>> g.add_edges([(0,1,1.0), (1,2,2.0), (0,3,4.0)])
>>> parallel_dijkstra(g, 0)
[0.0, 1.0, 3.0, 4.0]

paragon.algorithms.parallel_pagerank(graph: Graph, iterations: int = 20, damping: float = 0.85, threads: int = -1) → List[float]

Compute PageRank scores using a parallel pull-based approach.

This method updates each node’s rank by aggregating contributions from incoming neighbors (reverse adjacency).

Parameters:

• graph (Graph) – Input graph (typically directed).

• iterations (int, optional (default = 20)) – Number of PageRank iterations.

• damping (float, optional (default = 0.85)) – Damping factor (probability of following links).

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

PageRank score for each node.

Return type:

List[float]

Notes

• Pull-based computation using incoming edges.

• Stable and widely used formulation.

• Parallelized across nodes.

Time Complexity

O(iterations × (V + E))

Example

>>> from paragon import Graph
>>> from paragon.algorithms import pagerank
>>> g = Graph(4, directed=True)
>>> g.add_edges([(0,1), (1,2), (2,0), (2,3)])
>>> parallel_pagerank(g)
[0.25, 0.25, 0.25, 0.25]

paragon.algorithms.parallel_pagerank_bfs(graph: Graph, iterations: int = 20, damping: float = 0.85, threads: int = -1) → List[float]

Compute PageRank using a push-based (BFS-style) parallel approach.

Each node distributes its rank to its outgoing neighbors, similar to a frontier expansion strategy.

Parameters:

• graph (Graph) – Input graph (typically directed).

• iterations (int, optional (default = 20)) – Number of PageRank iterations.

• damping (float, optional (default = 0.85)) – Damping factor.

• threads (int, optional (default = -1)) – Number of threads to use.

Returns:

PageRank score for each node.

Return type:

List[float]

Notes

• Push-based computation (each node distributes rank).

• Uses per-thread local buffers to avoid contention.

• Efficient for sparse graphs.

Time Complexity

O(iterations × (V + E))

Example

>>> from paragon.algorithms import parallel_pagerank_bfs
>>> parallel_pagerank_bfs(g)
[0.25, 0.25, 0.25, 0.25]

paragon.algorithms.parallel_triangle_count(graph: Graph, threads: int = -1) → int

Count the number of triangles in an undirected graph.

A triangle is a set of three nodes (u, v, w) such that all three edges exist between them.

Parameters:

• graph (Graph) – Input graph (must be undirected).

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

Total number of triangles in the graph.

Return type:

int

Notes

• Uses parallel intersection-based counting.

• Avoids duplicate counting using node ordering (u < v < w).

• Efficient for large sparse graphs.

Time Complexity

Depends on graph density; typically near O(E * sqrt(E)).

Example

>>> from paragon import Graph
>>> from paragon.algorithms import parallel_triangle_count
>>> g = Graph(4)
>>> g.add_edges([(0,1), (1,2), (2,0), (2,3)])
>>> parallel_triangle_count(g)
1

Traversal Algorithms

paragon.algorithms.parallel_bfs(graph: Graph, source: int, threads: int = -1) → List[int]

Perform parallel breadth-first search (BFS) on a graph.

This function computes the shortest distance from the source node to all other nodes in an unweighted graph using a level-synchronous parallel approach.

Parameters:

• graph (Graph) – Input graph (unweighted).

• source (int) – Starting node for BFS traversal.

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

A list where: - dist[i] = shortest distance from source to node i - dist[i] = -1 if node i is unreachable

Return type:

List[int]

Notes

• Uses level-synchronous traversal (frontier-based).

• Each level is processed in parallel across threads.

• Thread-safe using atomic distance updates and mutex-protected frontier.

Time Complexity

O(V + E) (parallelized)

Example

>>> from paragon import Graph
>>> from paragon.algorithms import parallel_bfs
>>> g = Graph(5)
>>> g.add_edges([(0,1), (1,2), (2,3)])
>>> parallel_bfs(g, 0)
[0, 1, 2, 3, -1]

paragon.algorithms.parallel_dfs(graph: Graph, source: int, threads: int = -1) → List[bool]

Perform parallel depth-first search (DFS) on a graph.

This function explores all nodes reachable from the given source using a parallel, multi-threaded approach.

Parameters:

• graph (Graph) – Input graph (unweighted).

• source (int) – Starting node for DFS traversal.

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

A boolean list where: - visited[i] = True → node i is reachable from source - visited[i] = False → node i is not reachable

Return type:

List[bool]

Notes

• Uses a shared work stack across threads.

• Thread-safe via atomic visited array and mutex-protected stack.

• Efficient for large graphs with multiple connected regions.

Time Complexity

O(V + E) (parallelized)

Example

>>> from paragon import Graph
>>> from paragon.algorithms import parallel_dfs
>>> g = Graph(5)
>>> g.add_edges([(0,1), (1,2), (2,3)])
>>> parallel_dfs(g, 0)
[True, True, True, True, False]

Connectivity Algorithms

paragon.algorithms.parallel_connected_components(graph: Graph, threads: int = -1) → List[int]

Compute connected components of a graph in parallel.

This function assigns a component label to each node such that nodes with the same label belong to the same connected component.

Parameters:

• graph (Graph) – Input graph (typically undirected).

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

A list where: - component[i] = component ID of node i - Nodes with the same ID belong to the same component

Return type:

List[int]

Notes

• Based on a parallel Shiloach–Vishkin style algorithm.

• Uses pointer jumping (path compression) for efficiency.

• Iteratively merges components until convergence.

Time Complexity

Approximately O((V + E) log V) in parallel settings.

Example

>>> from paragon import Graph
>>> from paragon.algorithms import connected_components
>>> g = Graph(6)
>>> g.add_edges([(0,1), (1,2), (3,4)])
>>> connected_components(g)
[0, 0, 0, 3, 3, 5]

Shortest Path Algorithms

paragon.algorithms.parallel_dijkstra(graph: WeightedGraph, source: int, threads: int = -1) → List[float]

Compute shortest paths from a source node in a weighted graph.

This function computes the shortest distance from the source node to all other nodes using a parallel relaxation-based approach.

Parameters:

• graph (WeightedGraph) – Input weighted graph with non-negative edge weights.

• source (int) – Starting node.

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

A list where: - dist[i] = shortest distance from source to node i - dist[i] = large value (INF) if unreachable

Return type:

List[float]

Notes

• Uses parallel edge relaxation (similar to Bellman-Ford).

• Stops early if no updates occur in an iteration.

• Works only for graphs with non-negative weights.

Time Complexity

O(V × E) worst case, with early stopping in practice.

Example

>>> from paragon import WeightedGraph
>>> from paragon.algorithms import parallel_dijkstra
>>> g = WeightedGraph(4)
>>> g.add_edges([(0,1,1.0), (1,2,2.0), (0,3,4.0)])
>>> parallel_dijkstra(g, 0)
[0.0, 1.0, 3.0, 4.0]

Ranking Algorithms

paragon.algorithms.parallel_pagerank(graph: Graph, iterations: int = 20, damping: float = 0.85, threads: int = -1) → List[float]

Compute PageRank scores using a parallel pull-based approach.

This method updates each node’s rank by aggregating contributions from incoming neighbors (reverse adjacency).

Parameters:

• graph (Graph) – Input graph (typically directed).

• iterations (int, optional (default = 20)) – Number of PageRank iterations.

• damping (float, optional (default = 0.85)) – Damping factor (probability of following links).

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

PageRank score for each node.

Return type:

List[float]

Notes

• Pull-based computation using incoming edges.

• Stable and widely used formulation.

• Parallelized across nodes.

Time Complexity

O(iterations × (V + E))

Example

>>> from paragon import Graph
>>> from paragon.algorithms import pagerank
>>> g = Graph(4, directed=True)
>>> g.add_edges([(0,1), (1,2), (2,0), (2,3)])
>>> parallel_pagerank(g)
[0.25, 0.25, 0.25, 0.25]

paragon.algorithms.parallel_pagerank_bfs(graph: Graph, iterations: int = 20, damping: float = 0.85, threads: int = -1) → List[float]

Compute PageRank using a push-based (BFS-style) parallel approach.

Each node distributes its rank to its outgoing neighbors, similar to a frontier expansion strategy.

Parameters:

• graph (Graph) – Input graph (typically directed).

• iterations (int, optional (default = 20)) – Number of PageRank iterations.

• damping (float, optional (default = 0.85)) – Damping factor.

• threads (int, optional (default = -1)) – Number of threads to use.

Returns:

PageRank score for each node.

Return type:

List[float]

Notes

• Push-based computation (each node distributes rank).

• Uses per-thread local buffers to avoid contention.

• Efficient for sparse graphs.

Time Complexity

O(iterations × (V + E))

Example

>>> from paragon.algorithms import parallel_pagerank_bfs
>>> parallel_pagerank_bfs(g)
[0.25, 0.25, 0.25, 0.25]

Subgraph Algorithms

paragon.algorithms.parallel_triangle_count(graph: Graph, threads: int = -1) → int

Count the number of triangles in an undirected graph.

A triangle is a set of three nodes (u, v, w) such that all three edges exist between them.

Parameters:

• graph (Graph) – Input graph (must be undirected).

• threads (int, optional (default = -1)) – Number of threads to use. -1 means automatically use hardware concurrency.

Returns:

Total number of triangles in the graph.

Return type:

int

Notes

• Uses parallel intersection-based counting.

• Avoids duplicate counting using node ordering (u < v < w).

• Efficient for large sparse graphs.

Time Complexity

Depends on graph density; typically near O(E * sqrt(E)).

Example

>>> from paragon import Graph
>>> from paragon.algorithms import parallel_triangle_count
>>> g = Graph(4)
>>> g.add_edges([(0,1), (1,2), (2,0), (2,3)])
>>> parallel_triangle_count(g)
1

Utilities

Note

All algorithms support thread-level parallelism.

from paragon.graphs import generate_normal_graph
from paragon.algorithms import parallel_bfs

NUM_THREADS = 4
g = generate_normal_graph(vertices=10, edges=50)

dist = parallel_bfs(graph=g, source=0, threads=NUM_THREADS)
print(dist)

Tip

Use higher thread counts for better performance on multicore systems.

Warning

• Invalid inputs will raise Python exceptions

• Ensure correct graph type (Graph vs WeightedGraph)

• Some algorithms require specific constraints (e.g., non-negative weights)