Graph ADT

`Graph (ABC)`

A graph is a set of vertices and the edges that connect these vertices together in pairs. The graph abstract data type can be implemented based on various structures, but the most common are:

adjacency matrix
adjacency list

Graph vocabularies include, but are not limited to:

Directed graph: a graph whose edges have an order, such that one of the vertices in each edge precedes the other. It's also called a digraph.
Undirected graph: a graph whose edges have no order, such that each vertex has no precedence over any other vertex.
Multi-graph: a graph that contains at least one pair of vertices joined by multiple edges.
Complete graph: a graph whose vertices are each connected to every other vertex within the graph.
Degree of a vertex: the number of edges connected to the vertex.
Weight of an edge: the cost of traversing the edge.
Path: a complete route from some vertex to some other vertex within the graph.
Circuit: a path that begins and ends at the same vertex without traversing any edge more than once.

`contains(self, key)` `special`

Check if a graph contains a vertex with the passed key

Parameters:

Name	Type	Description	Default
`key`	`Any`	the key to check	required

Returns:

Type	Description
`bool`	True if the key is contained in some vertex of the graph, else False

Source code in graphs/graph.py

def __contains__(self, key: Any) -> bool:
    """Check if a graph contains a vertex with the passed key

    :param key: the key to check
    :returns: True if the key is contained in some vertex of the graph, else False
    """
    return key in self._keys

`repr(self)` `special`

Return a string representation of the graph

Returns:

Type	Description
`str`	the string representation of the graph

Source code in graphs/graph.py

@abstractmethod
def __repr__(self) -> str:
    """Return a string representation of the graph

    :returns: the string representation of the graph
    """
    pass

`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/graph.py

@abstractmethod
def add_edge(self, key1: Any, key2: Any, weight: float = None) -> None:
    """Connect the vertices associated to the passed keys with a new edge

    :param key1: the key associated to the first vertex in the pair
    :param key2: the key associated to the second vertex in the pair
    :param weight: the cost of traversing the newly formed edge
    """
    if key1 not in self:
        raise KeyError(f"{key1} is absent from the graph")
    if key2 not in self:
        raise KeyError(f"{key2} is absent from the graph")

`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/graph.py

@abstractmethod
def add_vertex(self, key: Any, value: Any = None) -> None:
    """Add a new vertex to the graph

    :param key: the key to associate to the new vertex
    :param value: the value to be stored in the new vertex
    """
    if key in self:
        raise KeyError(f"{key} already exists in the graph")

    self._keys.append(key)
    self._vertices.append(Graph._Vertex(key, value))

`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/graph.py

@abstractmethod
def breadth_first_traversal(self, key: Any) -> Generator:
    """Return a generator that yields keys of vertices of the graph when traversed breadth first from some vertex

    :param key: the key where the traversal begins from
    :returns: a generator of vertex keys
    """
    visited = {"__steps": 1, key: {"visit": 1}}
    helper_queue = [key]

    while len(helper_queue) > 0:
        current_key = helper_queue.pop(0)

        yield current_key, visited[current_key]["visit"]

        for k, _ in self._get_next_vertices(current_key):
            if k not in visited.keys():
                visited["__steps"] += 1
                visited[k] = {"visit": visited["__steps"]}
                helper_queue.append(k)

`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/graph.py

@abstractmethod
def depth_first_traversal(self, key: Any) -> Generator:
    """Return a generator that yields keys of vertices of the graph when traversed depth first from some vertex

    :param key: the key where the traversal begins from
    :returns: a generator of vertex keys
    """
    visited = {"__steps": 0}

    def helper(vertex_key):
        visited["__steps"] += 1
        visited[vertex_key] = {"first_visit": visited["__steps"]}

        yield vertex_key, visited["__steps"]

        for k, _ in self._get_next_vertices(vertex_key):
            if k not in visited.keys():
                yield from helper(k)

        visited["__steps"] += 1
        visited[vertex_key] = {"last_visit": visited["__steps"]}

    yield from helper(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/graph.py

@abstractmethod
def get_adjacent_vertices(self, key: Any) -> list:
    """Return a list of keys of all the vertices connected to the vertex associated with the passed key

    :param key: the key whose vertex all adjacent vertices' keys are being sought
    :returns: a list of vertex keys
    """
    if key not in self:
        raise KeyError(f"{key} is absent from the graph")

`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/graph.py

@abstractmethod
def get_edge_weight(self, key1: Any, key2: Any) -> float:
    """Return the weight associated with the edge connecting the vertices associated with the vertices of the
    passed keys

    :param key1: the key of the first vertex in the edge pair
    :param key2: the key of the second vertex in the edge pair
    :returns: weight of the edge
    """
    if key1 not in self:
        raise KeyError(f"{key1} is absent from the graph")
    if key2 not in self:
        raise KeyError(f"{key2} is absent from the graph")

    for i in self.get_adjacent_vertices(key1):
        if key2 == i[0]:
            return i[1]

    if not self.is_directed():
        for i in self.get_adjacent_vertices(key2):
            if key1 == i[0]:
                return i[1]

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

`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/graph.py

@abstractmethod
def get_edges(self) -> list:
    """Return a list of all the edges in the graph

    :returns: a list of all the edges
    """
    edges = []

    for i in self.get_vertices():
        for j in self.get_outgoing_adjacent_vertices(i):
            edges.append((i, j[0], j[1]))

    return 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/graph.py

@abstractmethod
def get_incoming_adjacent_vertices(self, key: Any) -> list:
    """Return a list of keys of all the vertices incoming to the vertex associated with the passed key

    :param key: the key whose vertex all incoming vertices' keys are being sought
    :returns: a list of vertex keys
    """
    if key not in self:
        raise KeyError(f"{key} is absent from the graph")

`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/graph.py

@abstractmethod
def get_incoming_edges(self, key: Any) -> list:
    """Return a list of incoming edges corresponding to the vertex associated with the passed key

    :param key: the key whose vertex a list of incoming edges is being sought
    :returns: a list of edges
    """
    if key not in self:
        raise KeyError(f"{key} is absent from the graph")

    return [(i[0], key, i[1]) for i in self.get_incoming_adjacent_vertices(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/graph.py

@abstractmethod
def get_outgoing_adjacent_vertices(self, key: Any) -> list:
    """Return a list of keys of all the vertices outgoing from the vertex associated with the passed key

    :param key: the key whose vertex all outgoing vertices' keys are being sought
    :returns: a list of vertex keys
    """
    if key not in self:
        raise KeyError(f"{key} is absent from the graph")

`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/graph.py

@abstractmethod
def get_outgoing_edges(self, key: Any) -> list:
    """Return a list of outgoing edges corresponding to the vertex associated with the passed key

    :param key: the key whose vertex a list of outgoing edges is being sought
    :returns: a list of edges
    """
    if key not in self:
        raise KeyError(f"{key} is absent from the graph")

    return [(key, *i) for i in self.get_outgoing_adjacent_vertices(key)]

`get_vertex_value(self, key)`

Return the value stored in the vertex corresponding to the passed key

Parameters:

Name	Type	Description	Default
`key`	`Any`	the key whose corresponding vertex's value is being sought	required

Returns:

Type	Description
`Any`	the value associated to vertex of the passed key

Source code in graphs/graph.py

def get_vertex_value(self, key: Any) -> Any:
    """Return the value stored in the vertex corresponding to the passed key

    :param key: the key whose corresponding vertex's value is being sought
    :returns: the value associated to vertex of the passed key
    """
    if key not in self:
        raise KeyError(f"{key} is absent from the graph")

    idx = self._keys.index(key)
    return self._vertices[idx].value

`get_vertices(self)`

Return a list of the keys of all vertices contained within the graph

Returns:

Type	Description
`list`	a list of all the vertices' keys

Source code in graphs/graph.py

def get_vertices(self) -> list:
    """Return a list of the keys of all vertices contained within the graph

    :returns: a list of all the vertices' keys
    """
    return self._keys

`is_directed(self)`

Check if the graph is directed

Returns:

Type	Description
`bool`	True if the graph is directed, else False

Source code in graphs/graph.py

def is_directed(self) -> bool:
    """Check if the graph is directed

    :returns: True if the graph is directed, else False
    """
    return self._directed

`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/graph.py

@abstractmethod
def is_edge(self, key1: Any, key2: Any) -> bool:
    """Check if a pair of vertices form an edge

    :param key1: the key of the first vertex in the edge pair
    :param key2: the key of the second vertex in the edge pair
    :returns: True if the passed pair form an edge, else False
    """
    if key1 not in self:
        raise KeyError(f"{key1} is absent from the graph")
    if key2 not in self:
        raise KeyError(f"{key2} is absent from the graph")

    for i in self.get_outgoing_adjacent_vertices(key1):
        if key2 == i[0]:
            return True

    return False

`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/graph.py

@abstractmethod
def remove_edge(self, key1: Any, key2: Any) -> None:
    """Delete the edge connecting the vertices associated with the passed keys

    :param key1: the key associated with the first vertex of the edge pair
    :param key2: the key associated with the second vertex of the edge pair
    """
    if key1 not in self:
        raise KeyError(f"{key1} is absent from the graph")
    if key2 not in self:
        raise KeyError(f"{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/graph.py

@abstractmethod
def remove_vertex(self, key: Any) -> None:
    """Delete the vertex associated to the passed key

    :param key: the key whose vertex id to be deleted
    """
    if key not in self:
        raise KeyError(f"{key} is absent from the graph")

    idx = self._keys.index(key)

    del self._keys[idx]
    del self._vertices[idx]

Graph ADT

Graph (ABC)

__contains__(self, key) special

__repr__(self) special

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

add_vertex(self, key, value=None)

breadth_first_traversal(self, key)

depth_first_traversal(self, key)

get_adjacent_vertices(self, key)

get_edge_weight(self, key1, key2)

get_edges(self)

get_incoming_adjacent_vertices(self, key)

get_incoming_edges(self, key)

get_outgoing_adjacent_vertices(self, key)

get_outgoing_edges(self, key)

get_vertex_value(self, key)

get_vertices(self)

is_directed(self)

is_edge(self, key1, key2)

remove_edge(self, key1, key2)

remove_vertex(self, key)

`Graph (ABC)`

`contains(self, key)` `special`

`repr(self)` `special`

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

`add_vertex(self, key, value=None)`

`breadth_first_traversal(self, key)`

`depth_first_traversal(self, key)`

`get_adjacent_vertices(self, key)`

`get_edge_weight(self, key1, key2)`

`get_edges(self)`

`get_incoming_adjacent_vertices(self, key)`

`get_incoming_edges(self, key)`

`get_outgoing_adjacent_vertices(self, key)`

`get_outgoing_edges(self, key)`

`get_vertex_value(self, key)`

`get_vertices(self)`

`is_directed(self)`

`is_edge(self, key1, key2)`

`remove_edge(self, key1, key2)`

`remove_vertex(self, key)`