utils
AdjacencyMatrix
Bases: NKAlgorithm
An algorithm to calculate the adjacency matrix of a graph using networkit.
The adjacency matrix is a square 2D NumPy array of shape (nodes_number, nodes_number) that
represents the connections between nodes in a graph. Each entry (i, j) in the matrix is a
boolean value:
- 1 indicates there is an edge from node i to node j.
- 0 indicates no edge exists from node i to node j.
For example
If there are 3 nodes and edges connecting: - Node 0 to Node 1, with weight 1 - Node 1 to Node 2, with weight 5 - Node 2 to Node 0, with weight 3
The adjacency matrix would look like this
[[0, 1, 0] [0, 0, 5] [3, 0, 0]]
run()
Compute the adjacency matrix of the graph.
Returns:
| Type | Description |
|---|---|
ndarray
|
np.ndarray[N, N]: Adjacency matrix of the graph. |
BreadthFirstSearch
Bases: NKAlgorithm
An algorithm using the networkit implementation of Breadth-First Search. This algorithm finds a path between the source and target node.
source = source
instance-attribute
target = target
instance-attribute
__init__(graph, source, target)
run()
Compute the path between the source and target node of the given graph.
Returns:
| Type | Description |
|---|---|
ndarray
|
np.ndarray[path_length]: Nodes of the shortest path between the source and target. |
DijkstraShortestPath
Bases: NKAlgorithm
An algorithm using the networkit implementation of Dijkstra's algorithm to find the shortest path between two nodes.
source = source
instance-attribute
target = target
instance-attribute
__init__(graph, source, target)
run()
Compute the shortest path between the source and target node of the given graph.
Returns:
| Type | Description |
|---|---|
ndarray
|
np.ndarray[path_length]: Nodes of the shortest path between the source and target. |
ShortestDistanceMatrix
Bases: NKAlgorithm
An algorithm to compute a matrix of the shortest distance between all nodes (if a path exists between the nodes). The algorithm uses networkit's APSP algorithm.
run()
Build distance matrix for all nodes in the graph.
Returns:
| Type | Description |
|---|---|
ndarray
|
np.ndarray[N, N]: Shortest distance matrix between all [N] nodes in the graph. |
Note
APSP returns np max float64 value if there is no path to the node.
This value is replaced by np.inf.
This method uses OpenMP and parallelizes the computation.
You can restrict the number of threads by calling set_number_of_threads method.
SpanningForest
Bases: NKAlgorithm
start_node = None
instance-attribute
__init__(graph)
run()
Builds a Spanning Forest of the graph starting from a given node using Breadth-First- Search (BFS).
Returns:
| Type | Description |
|---|---|
Graph
|
networkit.Graph: Spanning Forest. |