Graphs#

class data_structures.graphs.graphs.Graph[source]#

Bases: object

Undirected weighted graph backed by an adjacency dictionary of Vertex objects.

__init__()[source]#
classmethod create_example_graph()[source]#

Example graph structure:

   A
 /   \
B --- C
 \   /
   D
 /   \
E --- F
classmethod build_graph(graph_definition: Dict[Any, List])[source]#

Create a Graph

Parameters:

graph_definition – Graph definition

Returns:

The Graph.

>>> str(Graph.create_example_graph())
'{"A": ["B", "C"], "B": ["C", "D"], "C": ["D"], "D": ["E", "F"], "E": ["F"], "F": []}'
add_vertex(key) → Vertex[source]#

Add a vertex for the given key if it does not already exist and return it.

get_vertex(key) → Vertex | None[source]#

Return a vertex by key

get_vertices() → Dict[source]#

Return all vertices

add_edge(key_vertex1, key_vertex2, weight=0)[source]#

Add a directed edge from key_vertex1 to key_vertex2 with an optional weight.

Algorithm used for tree traversal on graphs or tree data structures.

Parameters:

node – Initial node.

Returns:

List of visited nodes.

>>> Graph.create_example_graph().breadth_first_search("A")
['A', 'B', 'C', 'D', 'E', 'F']

Depth First Traversal Algorithm…

Parameters:

  • node_id – Initial node.

  • visited – Set of visited nodes.

Returns:

List of visited nodes.

>>> Graph.create_example_graph().depth_first_search("A")
['A', 'B', 'C', 'D', 'E', 'F']
find_path(start, end, path: List | None = None)[source]#

Determine a path between two nodes…

Parameters:

  • start – Start node.

  • end – End node.

  • path

Returns:

The path.

>>> Graph.create_example_graph().find_path("A", "D")
["A", "B", "C", "D"]
find_all_paths(start, end, path: List | None = None)[source]#

Determine all paths between two nodes…

Parameters:

  • start – Start node.

  • end – End node.

  • path

Returns:

The path.

>>> Graph.create_example_graph().find_all_paths("A", "D")
[["A", "B", "C", "D"], ["A", "B", "D"], ["A", "C", "D"]]
find_shortest_path(start, end)[source]#

Find the shortest path between two nodes…

Parameters:

  • start – Start node.

  • end – End node.

Returns:

Shortest path.

>>> Graph.create_example_graph().find_shortest_path("A", "F")
['A', 'B', 'D', 'F']

>>> Graph.create_example_graph().find_shortest_path("B", "E")
['B', 'D', 'E']
class data_structures.graphs.vertex.Vertex(key)[source]#

Bases: object

Represents a node in a graph with weighted connections to neighbors.

__init__(key)[source]#

Initialize the vertex with a key and no connections.

property id#

The vertex identifier.

get_weight(vertex: Self)[source]#

Retrieve the weight to reach the neighbor

get_connections() → Dict[source]#

Return the connections

get_connections_ids() → List[source]#

Return the connections ids

add_neighbor(vertex: Self, weight=0)[source]#

Add or update a connection