dsa.graph module

Module containing graph classes.

class dsa.graph.AdjacencyListGraph(directed=False, vertices=None)

Bases: object

A unweighted adjacency list vertex implementation (allows either directed or undirected representation) vertex labels are string types

add_directed_edge(start_label, end_label)

Add a directed edge to the graph.

Parameters:

start_label (str) – The label of the starting vertex.
end_label (str) – The label of the ending vertex.

add_edge(start_label, end_label, directed=None)

Add an edge to the graph.

Parameters:

start_label (str) – The label of the starting vertex.
end_label (str) – The label of the ending vertex.
directed (bool) – Whether the edge is directed.

add_vertex(label)

Add a vertex to the graph.

Parameters:: label (str) – The vertex label to add.
Raises:: ValueError – If the vertex label already exists.

adjacents(vertex)

Return a list of adjacents of a given vertex

Parameters:: vertex (str) – The label of the vertex.
Return type:: list

delete_edge(start_label, end_label, directed=None)

Delete an edge in the graph.

Parameters:

start_label (str) – Starting vertex label.
end_label (str) – Ending vertex label.
directed (bool) – Whether the edge is directed.

Raises:

KeyError – If the edge does exist.

delete_vertex(label)

Delete a vertex from the graph.

Parameters:: label (str) – The vertex label to delete.

edges()

Return a list of edges in the graph. Each edge is represented by a tuple (start, end)

Return type:: list

classmethod from_dict(data, directed=False)

Create a graph from a dictionary representation.

Parameters:

data (dict) – The dictionary representation of the graph.
directed (bool) – Whether the graph is directed.

Returns:

An instance of the graph class.

has_edge(start_label, end_label)

Return boolean if an edge exists :type start_label: str :param start_label: The starting vertex label. :type start_label: str :type end_label: str :param end_label: The ending vertex label. :type end_label: str

Return type:: bool
Returns:: A boolean of whether there is an edge from start to end
Raises:: KeyError – If either vertex does not exist.

has_vertex(label)

Return boolean if a vertex exists :type label: str :param label: The vertex label. :type label: str

Return type:: bool
Returns:: A boolean of whether the vertex exists in the graph.

order(): Return the number of nodes in the graph. :returns: The number of nodes in the graph. :rtype: int

size(): Return the number of edges in the graph. :returns: The number of edges in the graph. :rtype: int

to_dict()

Return the adjacency list as a dictionary.

For unweighted graphs, returns a dictionary of lists. For weighted graphs, returns a dictionary of dictionaries.

Return type:: dict
Returns:: A dictionary representing the adjacency list of the graph. - Unweighted: {vertex: [neighbor1, neighbor2, …]} - Weighted: {vertex: {neighbor1: weight1, neighbor2: weight2, …}}

undirected_edges()

Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end)

Return type:: list

vertices()

Return a list of vertex labels of the graph

Return type:: list

class dsa.graph.AdjacencyListWeightedGraph(directed=False, vertices=None)

Bases: AdjacencyListGraph

A weighted adjacency list vertex implementation in Python (allows either directed or undirected representation)

add_edge(start_label, end_label, weight, directed=None)

Add an edge to the graph.

Parameters:

start_label (str) – The starting vertex label.
end_label (str) – The ending vertex label.
weight – The edge weight.
directed – Whether the edge is directed.

adjacent_items(vertex)

Return a list of adjacents and weights of a given vertex (adjacent label, weight) pair.

Parameters:: vertex (str) – starting vertex label
Return type:: list

adjacents(vertex)

Return a list of adjacents of a given vertex

Parameters:: vertex (str) – starting vertex label
Return type:: list

delete_edge(start_label, end_label, directed=None)

Delete an edge in the graph.

Parameters:

start_label (str) – Starting vertex label.
end_label (str) – Ending vertex label.
directed (bool) – Whether the edge is directed.

Raises:

KeyError – If the edge does exist.

edges()

Return a list of edges in the graph. Each edge is represented by a tuple (start, end, weight)

Return type:: list

classmethod from_dict(data, directed=False)

Create a weighted graph from a dictionary representation.

Parameters:

data (dict) – The dictionary representation of the graph.
directed (bool) – Whether the graph is directed.

Returns:

An instance of the weighted graph class.

get_weight(start_label, end_label)

Get the weight of an edge.

Parameters:

start_label (str) – The starting vertex label.
end_label (str) – The ending vertex label.

Returns:

The weight of the edge from start to end.

undirected_edges()

Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end, weight)

Return type:: list

class dsa.graph.AdjacencyMatrixGraph(directed=False, weighted=False, vertices=None)

Bases: object

An unweighted adjacency matrix graph implementation.

This class allows either directed or undirected representation of a graph. Vertex labels are string types.

add_edge(start_label, end_label, directed=None)

Add an edge in the graph.

Parameters:

start_label (str) – Starting vertex label.
end_label (str) – Ending vertex label.
directed (bool) – Whether the edge is directed.

add_vertex(label)

Add a vertex to the graph.

Parameters:: label (str) – The vertex label to add.
Raises:: ValueError – If the vertex label already exists.

adjacents(vertex)

Return a list of adjacents of a given vertex

Parameters:: vertex (str) – The label of the vertex.
Return type:: list

delete_edge(start_label, end_label, directed=None)

Delete an edge in the graph.

Parameters:

start_label (str) – Starting vertex label.
end_label (str) – Ending vertex label.
directed (bool) – Whether the edge is directed.

delete_vertex(label)

Delete a vertex from the graph.

Parameters:: label (str) – The vertex label to delete.

edges()

Return a list of edges in the graph. Each edge is represented by a tuple (start, end)

Return type:: list

classmethod from_dict(data, directed=False)

Create a graph from a dictionary representation.

Parameters:

data (dict) – The dictionary representation of the graph.
directed (bool) – Whether the graph is directed.

Returns:

An instance of the graph class.

has_edge(start_label, end_label)

Return boolean if an edge exists.

Parameters:

start_label (str) – starting vertex label
end_label (str) – starting vertex label

Return type:

bool

Returns:

A boolean of whether there is an edge from start to end.

has_vertex(label)

Return boolean if a vertex exists

Parameters:: label (str) – The vertex label.
Return type:: bool
Returns:: A boolean of whether the vertex exists in the graph.

order(): Return the number of nodes in the graph. :returns: The number of nodes in the graph. :rtype: int

print_graph(): Print the contents of the graph.

size(): Return the number of edges in the graph. :returns: The number of edges in the graph. :rtype: int

to_dict()

Return the adjacency matrix as a dictionary.

For unweighted graphs, returns a dictionary of lists. For weighted graphs, returns a dictionary of dictionaries.

Return type:: dict
Returns:: A dictionary representing the adjacency matrix of the graph. - Unweighted: {vertex: [neighbor1, neighbor2, …]} - Weighted: {vertex: {neighbor1: weight1, neighbor2: weight2, …}}

undirected_edges()

Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end)

Return type:: list

vertices()

Return a list of vertex labels of the graph

Return type:: list

class dsa.graph.AdjacencyMatrixWeightedGraph(directed=False, vertices=None)

Bases: AdjacencyMatrixGraph

A weighted adjacency matrix graph implementation (allows either directed or undirected representation) vertex labels are string types

add_edge(start_label, end_label, weight, directed=None)

Add an edge to the graph.

Parameters:

start_label (str) – The starting vertex label.
end_label (str) – The ending vertex label.
weight – The weight of the vertex.
directed – Whether the edge is directed.

adjacent_items(vertex)

Return a list of adjacents and weights of a given vertex (adjacent label, weight) pair.

Parameters:: vertex (str) – starting vertex label
Return type:: list

edges()

Return a list of edges in the graph. Each edge is represented by a tuple (start, end, weight).

Return type:: list

classmethod from_dict(data, directed=False)

Create a weighted graph from a dictionary representation.

Parameters:

data (dict) – The dictionary representation of the graph.
directed (bool) – Whether the graph is directed.

Returns:

An instance of the weighted graph class.

get_weight(start_label, end_label)

Get the weight of an edge.

Parameters:

start_label (str) – The starting vertex label.
end_label (str) – The ending vertex label.

Returns:

The weight of the edge from start to end.

print_graph(): Print the contents of the graph.

undirected_edges()

Return a list of undirected edges in the graph. Each edge is represented by a tuple (start, end, weight).

Return type:: list

class dsa.graph.Graph

Bases: object

Graph Factory

static create(graph_type, directed=False, weighted=False, vertices=None)

Return a graph object based on the specified parameters.

Parameters:

graph_type (str) – The type of graph (‘adjacency_matrix’ or ‘adjacency_list’).
directed (bool) – Whether the graph is directed.
weighted (bool) – Whether the graph is weighted.
labels (list[str], optional) – List of vertex labels for adjacency matrix graphs. Defaults to [].

Return type:

object

static create_adjacency_list(directed=False, weighted=False, vertices=None)

Return an adjacency list graph object.

Parameters:

directed (bool) – Whether the graph is directed.
weighted (bool) – Whether the graph is weighted.
labels (list[str], optional) – List of vertex labels for adjacency matrix graphs. Defaults to [].

Return type:

object

static create_adjacency_matrix(directed=False, weighted=False, vertices=None)

Return an adjacency matrix graph object.

Parameters:

directed (bool) – Whether the graph is directed.
weighted (bool) – Whether the graph is weighted.
labels (list[str], optional) – List of vertex labels for adjacency matrix graphs. Defaults to [].

Return type:

object

static from_dict(data, graph_type, directed=False, weighted=False)

Create a graph from a dictionary representation using the factory.

Parameters:

data (dict) – The dictionary representation of the graph.
graph_type (str) – The type of graph (‘adjacency_matrix’ or ‘adjacency_list’).
directed (bool) – Whether the graph is directed.
weighted (bool) – Whether the graph is weighted.

Return type:

object

Returns:

An instance of the specified graph class.