Adjacency Matrix Graph

AdjacencyMatrixGraph (Graph)

An adjacency matrix graph is a graph implemented based on a 2-dimensional array-like structure with the vertices of the graph aligned to both axes. The intersection of both axes marks that the corresponding vertices are connected with an edge, with the value contained at the intersection denoting the weight of the edge. An empty intersection denotes that the corresponding vertices are not connected.

Instantiate an adjacency matrix graph object

>>> directed_graph = AdjacencyMatrixGraph(directed=True)
>>> undirected_graph = AdjacencyMatrixGraph(directed=False)

Check if a graph is directed

>>> directed_graph.is_directed()
True
>>> undirected_graph.is_directed()
False

Add a vertex to a graph

>>> directed_graph.add_vertex(1, 1000)
>>> directed_graph.add_vertex(2, 2000)
>>> directed_graph.add_vertex(3, 3000)
>>> directed_graph.add_vertex(4, 4000)
>>> directed_graph.add_vertex(5, 5000)

>>> undirected_graph.add_vertex(1, 1000)
>>> undirected_graph.add_vertex(2, 2000)
>>> undirected_graph.add_vertex(3, 3000)
>>> undirected_graph.add_vertex(4, 4000)
>>> undirected_graph.add_vertex(5, 5000)

Add an edge to a graph

>>> directed_graph.add_edge(1, 2, 100)
>>> directed_graph.add_edge(1, 3, 200)
>>> directed_graph.add_edge(1, 4, 300)
>>> directed_graph.add_edge(2, 3, 400)
>>> directed_graph.add_edge(2, 5, 500)
>>> directed_graph.add_edge(3, 5, 600)
>>> directed_graph.add_edge(4, 5, 700)

>>> undirected_graph.add_edge(1, 2, 100)
>>> undirected_graph.add_edge(1, 3, 200)
>>> undirected_graph.add_edge(1, 4, 300)
>>> undirected_graph.add_edge(2, 3, 400)
>>> undirected_graph.add_edge(2, 5, 500)
>>> undirected_graph.add_edge(3, 5, 600)
>>> undirected_graph.add_edge(4, 5, 700)

Get keys of all the vertices in a graph

>>> directed_graph.get_vertices()
[1, 2, 3, 4, 5]
>>> undirected_graph.get_vertices()
[1, 2, 3, 4, 5]

Get all the edges in a graph

>>> directed_graph.get_edges()
[(1, 2, 100), (1, 3, 200), (1, 4, 300), (2, 3, 400), (2, 5, 500), (3, 5, 600), (4, 5, 700)]
>>> undirected_graph.get_edges()
[(1, 2, 100), (1, 3, 200), (1, 4, 300), (2, 1, 100), (2, 3, 400), (2, 5, 500), (3, 1, 200), (3, 2, 400), (3, 5, 600), (4, 1, 300), (4, 5, 700), (5, 2, 500), (5, 3, 600), (5, 4, 700)]

Check if a pair of vertices form an edge

>>> directed_graph.is_edge(1, 2)
True
>>> directed_graph.is_edge(2, 1)
False
>>> directed_graph.is_edge(1, 5)
False

>>> undirected_graph.is_edge(1, 2)
True
>>> undirected_graph.is_edge(2, 1)
True
>>> undirected_graph.is_edge(1, 5)
False

Get incoming edges of a vertex

>>> directed_graph.get_incoming_edges(3)
[(1, 3, 200), (2, 3, 400)]

>>> undirected_graph.get_incoming_edges(3)
[(1, 3, 200), (2, 3, 400), (5, 3, 600)]

Get outgoing edges of a vertex

>>> directed_graph.get_outgoing_edges(3)
[(3, 5, 600)]

>>> undirected_graph.get_outgoing_edges(3)
[(3, 1, 200), (3, 2, 400), (3, 5, 600)]

Get the weight of some edge

>>> directed_graph.get_edge_weight(1, 2)
100

>>> undirected_graph.get_edge_weight(1, 2)
100

Get adjacent vertices relative to some vertex

>>> directed_graph.get_adjacent_vertices(2)
[(1, 100), (3, 400), (5, 500)]

>>> undirected_graph.get_adjacent_vertices(2)
[(1, 100), (3, 400), (5, 500)]

Get adjacent incoming vertices relative to some vertex

>>> directed_graph.get_incoming_adjacent_vertices(2)
[(1, 100)]

>>> undirected_graph.get_incoming_adjacent_vertices(2)
[(1, 100), (3, 400), (5, 500)]

Get adjacent outgoing vertices relative to some vertex

>>> directed_graph.get_outgoing_adjacent_vertices(2)
[(3, 400), (5, 500)]

>>> undirected_graph.get_outgoing_adjacent_vertices(2)
[(1, 100), (3, 400), (5, 500)]

Get value stored in a vertex

>>> directed_graph.get_vertex_value(1)
1000

>>> undirected_graph.get_vertex_value(1)
1000

String representation of a graph

>>> str(directed_graph)
'[-, 100, 200, 300, -]\n[-, -, 400, -, 500]\n[-, -, -, -, 600]\n[-, -, -, -, 700]\n[-, -, -, -, -]'

>>> str(undirected_graph).strip()
'[-, 100, 200, 300, -]\n[-, -, 400, -, 500]\n[-, -, -, -, 600]\n[-, -, -, -, 700]\n[-, -, -, -, -]'

Check if a vertex corresponding to some key is contained in the graph

>>> 1 in directed_graph
True
>>> 100 in directed_graph
False

>>> 1 in undirected_graph
True
>>> 100 in undirected_graph
False

Depth-first traversal of a graph

>>> [i for i in directed_graph.depth_first_traversal(1)]
[(1, 1), (2, 2), (3, 3), (5, 4), (4, 8)]

>>> [i for i in undirected_graph.depth_first_traversal(1)]
[(1, 1), (2, 2), (3, 3), (5, 4), (4, 8)]

Breadth-first traversal of a graph

>>> [i for i in directed_graph.breadth_first_traversal(1)]
[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]

>>> [i for i in undirected_graph.breadth_first_traversal(1)]
[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]

Delete an edge

>>> directed_graph.remove_edge(1, 2)

>>> undirected_graph.remove_edge(1, 2)

Delete a vertex

>>> directed_graph.remove_vertex(1)

>>> undirected_graph.remove_vertex(1)

add_edge(self, key1, key2, weight=None)

Connect the vertices associated to the passed keys with a new edge

Parameters:

Name	Type	Description	Default
key1	Any	the key associated to the first vertex in the pair	required
key2	Any	the key associated to the second vertex in the pair	required
weight	float	the cost of traversing the newly formed edge	None

Source code in graphs/adjacency_matrix_graph.py

def add_edge(self, key1: Any, key2: Any, weight: float = None) -> None:
    super().add_edge(key1, key2, weight)

    idx1 = self._keys.index(key1)
    idx2 = self._keys.index(key2)

    self.__adjacency_matrix[idx1][idx2] = weight

add_vertex(self, key, value=None)

Add a new vertex to the graph

Parameters:

Name	Type	Description	Default
key	Any	the key to associate to the new vertex	required
value	Any	the value to be stored in the new vertex	None

Source code in graphs/adjacency_matrix_graph.py

def add_vertex(self, key: Any, value: Any = None) -> None:
    super().add_vertex(key, value)
    self.__adjacency_matrix.append(
        [AdjacencyMatrixGraph._Empty() for _ in range(len(self._keys) - 1)]
    )

    for row in self.__adjacency_matrix:
        row.append(AdjacencyMatrixGraph._Empty())

breadth_first_traversal(self, key)

Return a generator that yields keys of vertices of the graph when traversed breadth first from some vertex

Parameters:

Name	Type	Description	Default
key	Any	the key where the traversal begins from	required

Returns:

Type	Description
Generator	a generator of vertex keys

Source code in graphs/adjacency_matrix_graph.py

def breadth_first_traversal(self, key: Any) -> Generator:
    yield from super().breadth_first_traversal(key)

depth_first_traversal(self, key)

Return a generator that yields keys of vertices of the graph when traversed depth first from some vertex

Parameters:

Name	Type	Description	Default
key	Any	the key where the traversal begins from	required

Returns:

Type	Description
Generator	a generator of vertex keys

Source code in graphs/adjacency_matrix_graph.py

def depth_first_traversal(self, key: Any) -> Generator:
    yield from super().depth_first_traversal(key)

get_adjacent_vertices(self, key)

Return a list of keys of all the vertices connected to the vertex associated with the passed key

Parameters:

Name	Type	Description	Default
key	Any	the key whose vertex all adjacent vertices' keys are being sought	required

Returns:

Type	Description
list	a list of vertex keys

Source code in graphs/adjacency_matrix_graph.py

def get_adjacent_vertices(self, key: Any) -> list:
    super().get_adjacent_vertices(key)

    idx = self._keys.index(key)
    vertices = []

    for i, row in enumerate(self.__adjacency_matrix):
        if i != idx:
            for j, weight in enumerate(row):
                if j == idx and not isinstance(weight, AdjacencyMatrixGraph._Empty):
                    vertices.append((self._keys[i], weight))
        else:
            vertices.extend(
                [
                    (self._keys[j], weight)
                    for j, weight in enumerate(row)
                    if not isinstance(weight, AdjacencyMatrixGraph._Empty)
                ]
            )

    return vertices

get_edge_weight(self, key1, key2)

Return the weight associated with the edge connecting the vertices associated with the vertices of the passed keys

Parameters:

Name	Type	Description	Default
key1	Any	the key of the first vertex in the edge pair	required
key2	Any	the key of the second vertex in the edge pair	required

Returns:

Type	Description
float	weight of the edge

Source code in graphs/adjacency_matrix_graph.py

def get_edge_weight(self, key1: Any, key2: Any) -> float:
    return super().get_edge_weight(key1, key2)

get_edges(self)

Return a list of all the edges in the graph

Returns:

Type	Description
list	a list of all the edges

Source code in graphs/adjacency_matrix_graph.py

def get_edges(self) -> list:
    return super().get_edges()

get_incoming_adjacent_vertices(self, key)

Return a list of keys of all the vertices incoming to the vertex associated with the passed key

Parameters:

Name	Type	Description	Default
key	Any	the key whose vertex all incoming vertices' keys are being sought	required

Returns:

Type	Description
list	a list of vertex keys

Source code in graphs/adjacency_matrix_graph.py

def get_incoming_adjacent_vertices(self, key: Any) -> list:
    super().get_incoming_adjacent_vertices(key)

    idx = self._keys.index(key)
    vertices = []

    for i, row in enumerate(self.__adjacency_matrix):
        if i != idx:
            for j, weight in enumerate(row):
                if j == idx and not isinstance(weight, AdjacencyMatrixGraph._Empty):
                    vertices.append((self._keys[i], weight))
        else:
            if not self.is_directed():
                vertices.extend(
                    [
                        (self._keys[j], weight)
                        for j, weight in enumerate(row)
                        if not isinstance(weight, AdjacencyMatrixGraph._Empty)
                    ]
                )

    return vertices

get_incoming_edges(self, key)

Return a list of incoming edges corresponding to the vertex associated with the passed key

Parameters:

Name	Type	Description	Default
key	Any	the key whose vertex a list of incoming edges is being sought	required

Returns:

Type	Description
list	a list of edges

Source code in graphs/adjacency_matrix_graph.py

def get_incoming_edges(self, key: Any) -> list:
    return super().get_incoming_edges(key)

get_outgoing_adjacent_vertices(self, key)

Return a list of keys of all the vertices outgoing from the vertex associated with the passed key

Parameters:

Name	Type	Description	Default
key	Any	the key whose vertex all outgoing vertices' keys are being sought	required

Returns:

Type	Description
list	a list of vertex keys

Source code in graphs/adjacency_matrix_graph.py

def get_outgoing_adjacent_vertices(self, key: Any) -> list:
    super().get_outgoing_adjacent_vertices(key)

    idx = self._keys.index(key)
    vertices = []

    for i, row in enumerate(self.__adjacency_matrix):
        if i != idx:
            if not self.is_directed():
                for j, weight in enumerate(row):
                    if j == idx and not isinstance(
                        weight, AdjacencyMatrixGraph._Empty
                    ):
                        vertices.append((self._keys[i], weight))
        else:
            vertices.extend(
                [
                    (self._keys[j], weight)
                    for j, weight in enumerate(row)
                    if not isinstance(weight, AdjacencyMatrixGraph._Empty)
                ]
            )

    return vertices

get_outgoing_edges(self, key)

Return a list of outgoing edges corresponding to the vertex associated with the passed key

Parameters:

Name	Type	Description	Default
key	Any	the key whose vertex a list of outgoing edges is being sought	required

Returns:

Type	Description
list	a list of edges

Source code in graphs/adjacency_matrix_graph.py

def get_outgoing_edges(self, key: Any) -> list:
    return super().get_outgoing_edges(key)

is_edge(self, key1, key2)

Check if a pair of vertices form an edge

Parameters:

Name	Type	Description	Default
key1	Any	the key of the first vertex in the edge pair	required
key2	Any	the key of the second vertex in the edge pair	required

Returns:

Type	Description
bool	True if the passed pair form an edge, else False

Source code in graphs/adjacency_matrix_graph.py

def is_edge(self, key1: Any, key2: Any) -> bool:
    return super().is_edge(key1, key2)

remove_edge(self, key1, key2)

Delete the edge connecting the vertices associated with the passed keys

Parameters:

Name	Type	Description	Default
key1	Any	the key associated with the first vertex of the edge pair	required
key2	Any	the key associated with the second vertex of the edge pair	required

Source code in graphs/adjacency_matrix_graph.py

def remove_edge(self, key1: Any, key2: Any) -> None:
    super().remove_edge(key1, key2)

    for i in self.get_adjacent_vertices(key1):
        if key2 == i[0]:
            idx1 = self._keys.index(key1)
            idx2 = self._keys.index(key2)
            self.__adjacency_matrix[idx1][idx2] = AdjacencyMatrixGraph._Empty()
            return

    if not self.is_directed():
        for i in self.get_adjacent_vertices(key2):
            if key1 == i[0]:
                idx1 = self._keys.index(key1)
                idx2 = self._keys.index(key2)
                self.__adjacency_matrix[idx2][idx1] = AdjacencyMatrixGraph._Empty()
                return

    raise ValueError(f"Edge ({key1}, {key2}) is absent from the graph")

remove_vertex(self, key)

Delete the vertex associated to the passed key

Parameters:

Name	Type	Description	Default
key	Any	the key whose vertex id to be deleted	required

Source code in graphs/adjacency_matrix_graph.py

def remove_vertex(self, key: Any) -> None:
    idx = None
    if key in self:
        idx = self._keys.index(key)

    super().remove_vertex(key)
    del self.__adjacency_matrix[idx]

    for i in range(len(self.__adjacency_matrix)):
        del self.__adjacency_matrix[i][idx]