Algorithms¶

pydatastructs.breadth_first_search(graph, source_node, operation, *args, **kwargs)¶

Implementation of serial breadth first search(BFS) algorithm.

Parameters

graph (Graph) – The graph on which BFS is to be performed.
source_node (str) – The name of the source node from where the BFS is to be initiated.
operation (function) –
The function which is to be applied on every node when it is visited. The prototype which is to be followed is, `function_name(curr_node, next_node,

arg_1, arg_2, …, arg_n)`.

Here, the first two arguments denote, the current node and the node next to current node. The rest of the arguments are optional and you can provide your own stuff there.

Note

You should pass all the arguments which you are going to use in the prototype of your operation after passing the operation function.

Examples

>>> from pydatastructs import Graph, AdjacencyListGraphNode
>>> V1 = AdjacencyListGraphNode("V1")
>>> V2 = AdjacencyListGraphNode("V2")
>>> V3 = AdjacencyListGraphNode("V3")
>>> G = Graph(V1, V2, V3)
>>> from pydatastructs import breadth_first_search
>>> def f(curr_node, next_node, dest_node):
...     return curr_node != dest_node
...
>>> G.add_edge(V1.name, V2.name)
>>> G.add_edge(V2.name, V3.name)
>>> breadth_first_search(G, V1.name, f, V3.name)

pydatastructs.breadth_first_search_parallel(graph, source_node, num_threads, operation, *args, **kwargs)¶

Parallel implementation of breadth first search on graphs.

Parameters

graph (Graph) – The graph on which BFS is to be performed.
source_node (str) – The name of the source node from where the BFS is to be initiated.
num_threads (int) – Number of threads to be used for computation.
operation (function) –
The function which is to be applied on every node when it is visited. The prototype which is to be followed is, `function_name(curr_node, next_node,

arg_1, arg_2, …, arg_n)`.

Here, the first two arguments denote, the current node and the node next to current node. The rest of the arguments are optional and you can provide your own stuff there.

Note

You should pass all the arguments which you are going to use in the prototype of your operation after passing the operation function.

Examples

>>> from pydatastructs import Graph, AdjacencyListGraphNode
>>> V1 = AdjacencyListGraphNode("V1")
>>> V2 = AdjacencyListGraphNode("V2")
>>> V3 = AdjacencyListGraphNode("V3")
>>> G = Graph(V1, V2, V3)
>>> from pydatastructs import breadth_first_search_parallel
>>> def f(curr_node, next_node, dest_node):
...     return curr_node != dest_node
...
>>> G.add_edge(V1.name, V2.name)
>>> G.add_edge(V2.name, V3.name)
>>> breadth_first_search_parallel(G, V1.name, 3, f, V3.name)

pydatastructs.minimum_spanning_tree(graph, algorithm)¶

Computes a minimum spanning tree for the given graph and algorithm.

Parameters

graph (Graph) – The graph whose minimum spanning tree has to be computed.
algorithm (str) –
The algorithm which should be used for computing a minimum spanning tree. Currently the following algorithms are supported,

’kruskal’ -> Kruskal’s algorithm as given in [1].

’prim’ -> Prim’s algorithm as given in [2].

Returns

mst – A minimum spanning tree using the implementation same as the graph provided in the input.

Return type

Graph

Examples

>>> from pydatastructs import Graph, AdjacencyListGraphNode
>>> from pydatastructs import minimum_spanning_tree
>>> u = AdjacencyListGraphNode('u')
>>> v = AdjacencyListGraphNode('v')
>>> G = Graph(u, v)
>>> G.add_edge(u.name, v.name, 3)
>>> mst = minimum_spanning_tree(G, 'kruskal')
>>> u_n = mst.neighbors(u.name)
>>> mst.get_edge(u.name, u_n[0].name).value
3

References

1: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
2: https://en.wikipedia.org/wiki/Prim%27s_algorithm

Note

The concept of minimum spanning tree is valid only for connected and undirected graphs. So, this function should be used only for such graphs. Using with other types of graphs may lead to unwanted results.

pydatastructs.minimum_spanning_tree_parallel(graph, algorithm, num_threads)¶

Computes a minimum spanning tree for the given graph and algorithm using the given number of threads.

Parameters

graph (Graph) – The graph whose minimum spanning tree has to be computed.
algorithm (str) –
The algorithm which should be used for computing a minimum spanning tree. Currently the following algorithms are supported,

’kruskal’ -> Kruskal’s algorithm as given in [1].

’prim’ -> Prim’s algorithm as given in [2].
num_threads (int) – The number of threads to be used.

Returns

mst – A minimum spanning tree using the implementation same as the graph provided in the input.

Return type

Graph

Examples

>>> from pydatastructs import Graph, AdjacencyListGraphNode
>>> from pydatastructs import minimum_spanning_tree_parallel
>>> u = AdjacencyListGraphNode('u')
>>> v = AdjacencyListGraphNode('v')
>>> G = Graph(u, v)
>>> G.add_edge(u.name, v.name, 3)
>>> mst = minimum_spanning_tree_parallel(G, 'kruskal', 3)
>>> u_n = mst.neighbors(u.name)
>>> mst.get_edge(u.name, u_n[0].name).value
3

References

1: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm#Parallel_algorithm
2: https://en.wikipedia.org/wiki/Prim%27s_algorithm#Parallel_algorithm

Note

The concept of minimum spanning tree is valid only for connected and undirected graphs. So, this function should be used only for such graphs. Using with other types of graphs will lead to unwanted results.

pydatastructs.strongly_connected_components(graph, algorithm)¶

Computes strongly connected components for the given graph and algorithm.

Parameters

graph (Graph) – The graph whose minimum spanning tree has to be computed.
algorithm (str) –
The algorithm which should be used for computing strongly connected components. Currently the following algorithms are supported,

’kosaraju’ -> Kosaraju’s algorithm as given in [1].

Returns

components – Python list with each element as set of vertices.

Return type

list

Examples

>>> from pydatastructs import Graph, AdjacencyListGraphNode
>>> from pydatastructs import strongly_connected_components
>>> v1, v2, v3 = [AdjacencyListGraphNode(i) for i in range(3)]
>>> g = Graph(v1, v2, v3)
>>> g.add_edge(v1.name, v2.name)
>>> g.add_edge(v2.name, v3.name)
>>> g.add_edge(v3.name, v1.name)
>>> scc = strongly_connected_components(g, 'kosaraju')
>>> scc == [{'2', '0', '1'}]
True

References

1: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

pydatastructs.depth_first_search(graph, source_node, operation, *args, **kwargs)¶

Implementation of depth first search (DFS) algorithm.

Parameters

graph (Graph) – The graph on which DFS is to be performed.
source_node (str) – The name of the source node from where the DFS is to be initiated.
operation (function) –
The function which is to be applied on every node when it is visited. The prototype which is to be followed is, `function_name(curr_node, next_node,

arg_1, arg_2, …, arg_n)`.

Here, the first two arguments denote, the current node and the node next to current node. The rest of the arguments are optional and you can provide your own stuff there.

Note

You should pass all the arguments which you are going to use in the prototype of your operation after passing the operation function.

Examples

>>> from pydatastructs import Graph, AdjacencyListGraphNode
>>> V1 = AdjacencyListGraphNode("V1")
>>> V2 = AdjacencyListGraphNode("V2")
>>> V3 = AdjacencyListGraphNode("V3")
>>> G = Graph(V1, V2, V3)
>>> from pydatastructs import depth_first_search
>>> def f(curr_node, next_node, dest_node):
...     return curr_node != dest_node
...
>>> G.add_edge(V1.name, V2.name)
>>> G.add_edge(V2.name, V3.name)
>>> depth_first_search(G, V1.name, f, V3.name)

References

1: https://en.wikipedia.org/wiki/Depth-first_search

pydatastructs.shortest_paths(graph: pydatastructs.graphs.graph.Graph, algorithm: str, source: str, target: str = '') → tuple¶

Finds shortest paths in the given graph from a given source.

Parameters

graph (Graph) – The graph under consideration.
algorithm (str) –
The algorithm to be used. Currently, the following algorithms are implemented,

’bellman_ford’ -> Bellman-Ford algorithm as given in [1].

’dijkstra’ -> Dijkstra algorithm as given in [2].
source (str) – The name of the source the node.
target (str) – The name of the target node. Optional, by default, all pair shortest paths are returned.

Returns

(distances, predecessors) ((dict, dict)) – If target is not provided and algorithm used is ‘bellman_ford’/’dijkstra’.
(distances[target], predecessors) ((float, dict)) – If target is provided and algorithm used is ‘bellman_ford’/’dijkstra’.

Examples

>>> from pydatastructs import Graph, AdjacencyListGraphNode
>>> from pydatastructs import shortest_paths
>>> V1 = AdjacencyListGraphNode("V1")
>>> V2 = AdjacencyListGraphNode("V2")
>>> V3 = AdjacencyListGraphNode("V3")
>>> G = Graph(V1, V2, V3)
>>> G.add_edge('V2', 'V3', 10)
>>> G.add_edge('V1', 'V2', 11)
>>> shortest_paths(G, 'bellman_ford', 'V1')
({'V1': 0, 'V2': 11, 'V3': 21}, {'V1': None, 'V2': 'V1', 'V3': 'V2'})
>>> shortest_paths(G, 'dijkstra', 'V1')
({'V2': 11, 'V3': 21, 'V1': 0}, {'V1': None, 'V2': 'V1', 'V3': 'V2'})

References

1: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
2: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

pydatastructs.all_pair_shortest_paths(graph: pydatastructs.graphs.graph.Graph, algorithm: str) → tuple¶

Finds shortest paths between all pairs of vertices in the given graph.

Parameters

graph (Graph) – The graph under consideration.
algorithm (str) –
The algorithm to be used. Currently, the following algorithms are implemented,

’floyd_warshall’ -> Floyd Warshall algorithm as given in [1].

Returns

(distances, predecessors)

Return type

(dict, dict)

Examples

>>> from pydatastructs import Graph, AdjacencyListGraphNode
>>> from pydatastructs import all_pair_shortest_paths
>>> V1 = AdjacencyListGraphNode("V1")
>>> V2 = AdjacencyListGraphNode("V2")
>>> V3 = AdjacencyListGraphNode("V3")
>>> G = Graph(V1, V2, V3)
>>> G.add_edge('V2', 'V3', 10)
>>> G.add_edge('V1', 'V2', 11)
>>> G.add_edge('V3', 'V1', 5)
>>> dist, _ = all_pair_shortest_paths(G, 'floyd_warshall')
>>> dist['V1']['V3']
21
>>> dist['V3']['V1']
5

References

1: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

pydatastructs.topological_sort(graph: pydatastructs.graphs.graph.Graph, algorithm: str) → list¶

Performs topological sort on the given graph using given algorithm.

Parameters

graph (Graph) – The graph under consideration.
algorithm (str) –
The algorithm to be used. Currently, following are supported,

’kahn’ -> Kahn’s algorithm as given in [1].

Returns

The list of topologically sorted vertices.

Return type

list

Examples

>>> from pydatastructs import Graph, AdjacencyListGraphNode, topological_sort
>>> v_1 = AdjacencyListGraphNode('v_1')
>>> v_2 = AdjacencyListGraphNode('v_2')
>>> graph = Graph(v_1, v_2)
>>> graph.add_edge('v_1', 'v_2')
>>> topological_sort(graph, 'kahn')
['v_1', 'v_2']

References

1: https://en.wikipedia.org/wiki/Topological_sorting#Kahn’s_algorithm

pydatastructs.topological_sort_parallel(graph: pydatastructs.graphs.graph.Graph, algorithm: str, num_threads: int) → list¶

Performs topological sort on the given graph using given algorithm using given number of threads.

Parameters

graph (Graph) – The graph under consideration.
algorithm (str) –
The algorithm to be used. Currently, following are supported,

’kahn’ -> Kahn’s algorithm as given in [1].
num_threads (int) – The maximum number of threads to be used.

Returns

The list of topologically sorted vertices.

Return type

list

Examples

>>> from pydatastructs import Graph, AdjacencyListGraphNode, topological_sort_parallel
>>> v_1 = AdjacencyListGraphNode('v_1')
>>> v_2 = AdjacencyListGraphNode('v_2')
>>> graph = Graph(v_1, v_2)
>>> graph.add_edge('v_1', 'v_2')
>>> topological_sort_parallel(graph, 'kahn', 1)
['v_1', 'v_2']

References

1: https://en.wikipedia.org/wiki/Topological_sorting#Kahn’s_algorithm

Algorithms¶

Related Topics

This Page