graphs.basic_graphs

Attributes

graph_choice

Functions

_input(message)
adjm()	Reading an Adjacency matrix
bfs(→ None)
dfs(→ None)
dijk(→ None)
edglist()	Get the edges and number of edges from the user
find_isolated_nodes(graph)	Find the isolated node in the graph
floyd_warshall(→ None)	Floyd-Warshall algorithm to compute all-pairs shortest paths.
initialize_unweighted_directed_graph(→ dict[int, ...)
initialize_unweighted_undirected_graph(→ dict[int, ...)
initialize_weighted_undirected_graph(→ dict[int, ...)
krusk(→ None)	Sort edges on the basis of distance
prim(g, s)
topo(→ None)	Perform a topological sort on a directed acyclic graph.

Module Contents

graphs.basic_graphs._input(message)

graphs.basic_graphs.adjm()

Reading an Adjacency matrix

Parameters:

None

Returns:

tuple: A tuple containing a list of edges and number of edges

Example: >>> # Simulate user input for 3 nodes >>> input_data = “4n0 1 0 1n1 0 1 0n0 1 0 1n1 0 1 0n” >>> import sys,io >>> original_input = sys.stdin >>> sys.stdin = io.StringIO(input_data) # Redirect stdin for testing >>> adjm() ([(0, 1, 0, 1), (1, 0, 1, 0), (0, 1, 0, 1), (1, 0, 1, 0)], 4) >>> sys.stdin = original_input # Restore original stdin

graphs.basic_graphs.bfs(g, s) → None

>>> bfs({1: [2, 3], 2: [4, 5], 3: [6, 7], 4: [], 5: [8], 6: [], 7: [], 8: []}, 1)
1
2
3
4
5
6
7
8

graphs.basic_graphs.dfs(g, s) → None

>>> dfs({1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}, 1)
1
2
4
5
3

graphs.basic_graphs.dijk(g, s) → None

>>> dijk({
...     1: [(2, 7), (3, 9), (6, 14)],
...     2: [(1, 7), (3, 10), (4, 15)],
...     3: [(1, 9), (2, 10), (4, 11), (6, 2)],
...     4: [(2, 15), (3, 11), (5, 6)],
...     5: [(4, 6), (6, 9)],
...     6: [(1, 14), (3, 2), (5, 9)]
... }, 1)
7
9
11
20
20

graphs.basic_graphs.edglist()

Get the edges and number of edges from the user

Parameters:

None

Returns:

tuple: A tuple containing a list of edges and number of edges

Example: >>> # Simulate user input for 3 edges and 4 vertices: (1, 2), (2, 3), (3, 4) >>> input_data = “4 3n1 2n2 3n3 4n” >>> import sys,io >>> original_input = sys.stdin >>> sys.stdin = io.StringIO(input_data) # Redirect stdin for testing >>> edglist() ([(1, 2), (2, 3), (3, 4)], 4) >>> sys.stdin = original_input # Restore original stdin

graphs.basic_graphs.find_isolated_nodes(graph)

Find the isolated node in the graph

Parameters: graph (dict): A dictionary representing a graph.

Returns: list: A list of isolated nodes.

Examples: >>> graph1 = {1: [2, 3], 2: [1, 3], 3: [1, 2], 4: []} >>> find_isolated_nodes(graph1) [4]

>>> graph2 = {'A': ['B', 'C'], 'B': ['A'], 'C': ['A'], 'D': []}
>>> find_isolated_nodes(graph2)
['D']

>>> graph3 = {'X': [], 'Y': [], 'Z': []}
>>> find_isolated_nodes(graph3)
['X', 'Y', 'Z']

>>> graph4 = {1: [2, 3], 2: [1, 3], 3: [1, 2]}
>>> find_isolated_nodes(graph4)
[]

>>> graph5 = {}
>>> find_isolated_nodes(graph5)
[]

graphs.basic_graphs.floyd_warshall(a_and_n) → None

Floyd-Warshall algorithm to compute all-pairs shortest paths.

Parameters:

a_and_n (tuple): A tuple (a, n) where

a is an N x N adjacency matrix (list of lists), n is the number of nodes.

Example: >>> floyd_warshall(([ … [0, 5, float(‘inf’)], … [50, 0, 10], … [float(‘inf’), float(‘inf’), 0] … ], 3)) [[0, 5, 15], [50, 0, 10], [inf, inf, 0]]

graphs.basic_graphs.initialize_unweighted_directed_graph(node_count: int, edge_count: int) → dict[int, list[int]]

graphs.basic_graphs.initialize_unweighted_undirected_graph(node_count: int, edge_count: int) → dict[int, list[int]]

graphs.basic_graphs.initialize_weighted_undirected_graph(node_count: int, edge_count: int) → dict[int, list[tuple[int, int]]]

graphs.basic_graphs.krusk(e_and_n) → None

Sort edges on the basis of distance

graphs.basic_graphs.prim(g, s)

graphs.basic_graphs.topo(g, ind=None, q=None) → None

Perform a topological sort on a directed acyclic graph.

>>> topo({1: [2, 3], 2: [4], 3: [4], 4: []})
1
2
3
4

graphs.basic_graphs.graph_choice