BaseGraph#

class BaseGraph(adjacency_list=None)#

Bases: DataStructure, Generic[Node, EdgeData]

Base class for all graphs. Adjacency list representation is assumed for simplicity.

__init__(adjacency_list=None)#

Constructor of the BaseGraph class. Initializes set of edges, adjacency list and adjacency matrix.

Parameters:: adjacency_list (Optional[dict[Node, dict[Node, EdgeData]]] (default None)) – Optional adjacency list from which to build the graph.

Methods

`__init__`([adjacency_list])	Constructor of the BaseGraph class.
`add_edge`(edge)	Add a single edge to the graph.
`add_edges_from`(edges)	Add multiple edges from an iterable.
`add_node`(node)	Add a single node to the graph.
`add_nodes_from`(nodes)	Add multiple nodes from an iterable.
`degree`(node)	Return degree for a given node.
`get_edge_data`(source, target)	rtype: `Union`[`TypeVar`(`EdgeData`), `NoEdge`]
`increment_n_ops`([increment])	Convenience method to increment n_ops count of the given complexity object.
`indegree`(node)	Return indegree for a given node.
`neighbors`(node)	Return a set of adjacent nodes for a given node.
`outdegree`(node)	Return outdegree for a given node.
`remove_edge`(source, target, *data)	Remove an edge between two nodes from the graph.
`remove_edges_from`(edges_to_remove)	Remove a given bunch of edges from the graph.
`remove_node`(node)	Remove given node from the graph along with all its edges.
`remove_nodes_from`(nodes_to_remove)	Remove a given bunch of nodes from the graph.
`reset_n_ops`()	Convenience method to reset n_ops count of the given complexity object.

Attributes

`adjacency_list`	Getter for the adjacency list representation of the graph.
`adjacency_list_transposed`	Getter for transposed adjacency list representation of the graph.
`adjacency_matrix`	Getter for the adjacency matrix of the graph.
`edges`	Retrieve the edges of this graph.
`is_directed`	rtype: `bool`
`is_multigraph`	rtype: `bool`
`n_ops`	rtype: `int`
`name`	rtype: `str`
`nodes`	Retrieve the nodes of this graph.
`number_of_edges`	Retrieve the number of edges of this graph.
`number_of_nodes`	Retrieve the number of nodes of this graph.
`space_complexity`	rtype: `str`

abstract add_edge(edge)#

Add a single edge to the graph. An edge is a tuple of source node, destination node and edge data. In case of an undirected graph, the reverse edge is also added. If an edge is already present in the graph between two nodes and the graph is not a multigraph, edge’s data is rewritten by the input of this method. Both nodes are silently added to the graph in case they are not present in the graph.

Parameters:: edge (Edge) – The edge to add represented as a tuple of (source node, destination node, edge data).
Return type:: None

add_edges_from(edges)#

Add multiple edges from an iterable.

Parameters:: edges (Iterable[Edge]) – Iterable from which to add the edges. Edges are represented as tuples of (source node, destination node, edge data).
Return type:: None

add_node(node)#

Add a single node to the graph. Nothing changes if the node already exists.

Parameters:: node (Node) – Node to add.
Return type:: None

add_nodes_from(nodes)#

Add multiple nodes from an iterable.

Parameters:: nodes (Iterable[Node]) – Iterable from which to add the nodes.
Return type:: None

property adjacency_list: dict[Node, dict[Node, EdgeData]]#

Getter for the adjacency list representation of the graph.

Returns:: adjacency_list – Adjacency list representation of the graph, represented as a dict of node : neighbours pairs with neighbours being a dict of neighbour : edge data or set of edge data in case of a multigraph.
Return type:: dict[Node, dict[Node, EdgeData]]

property adjacency_list_transposed: dict[Node, dict[Node, EdgeData]]#

Getter for transposed adjacency list representation of the graph.

Returns:: adjacency_list_transposed – If the graph is directed, return an adjacency list with all edges having opposite direction. Otherwise, simply return the actual adjacency list.
Return type:: dict[Node, dict[Node, EdgeData]]

property adjacency_matrix: list[list[Union[EdgeData, algpy_src.data_structures.graphs.graph_utils.no_edge_object.NoEdge]]]#

Getter for the adjacency matrix of the graph. Note that the graph is internally represented as an adjacency list, thus the adjacency matrix is built in O(n^2) time with O(n^2) space complexity for each call of this method. It is then cached as the graph’s attribute until further change in the graph.

Returns:: adjacency_matrix – Adjacency matrix representation of the graph object represented as a list of lists with edges represented either by the data itself or set of data in case of a multigraph. Symmetrical for undirected graph.
Return type:: list[list[EdgeData | NoEdge]]

degree(node)#

Return degree for a given node.

Parameters:: node (Node) – Node for which to find the degree. If not present in the graph, 0 is returned.
Returns:: degree – Degree of the given node.
Return type:: int

property edges: set[tuple[Node, Node, EdgeData]]#

Retrieve the edges of this graph. Edges are represented as tuples of (source node, destination node, edge data). The order retrieved here corresponds to the order of being added to the graph and there can be multiple edges between two nodes in case of a multigraph. This method retrieves only one direction of each edge even for undirected graph, which is internally represented as a directed graph with edges going both ways.

Returns:: edges – Edges of this graph.
Return type:: set[Edge]

get_edge_data(source, target)#

Return type:: Union[TypeVar(EdgeData), NoEdge]

increment_n_ops(increment=1)#

Convenience method to increment n_ops count of the given complexity object.

Return type:: None

indegree(node)#

Return indegree for a given node.

Parameters:: node (Node) – Node for which to find the indegree. If not present in the graph, 0 is returned.
Returns:: indegree – Indegree of the given node.
Return type:: int

abstract property is_directed: bool#

Return type:: bool

abstract property is_multigraph: bool#

Return type:: bool

property n_ops: int#

Return type:: int

abstract property name: str#

Return type:: str

neighbors(node)#

Return a set of adjacent nodes for a given node.

Parameters:: node (Node) – Node for which to find the neighbours. If not present in the graph, empty set is returned.
Returns:: neighbours – A set of adjacent nodes.
Return type:: set[Node]

property nodes: list[Node]#

Retrieve the nodes of this graph. Nodes can be represented by any Python object and the order retrieved here corresponds to the order of being added to the graph.

Returns:: nodes – Nodes of this graph.
Return type:: list[Node]

property number_of_edges: int#

Retrieve the number of edges of this graph. In case of an undirected graph, each edge is counted only once despite being internally represented as a directed graph.

Returns:: number_of_edges – Number of edges of this graph.
Return type:: int

property number_of_nodes: int#

Retrieve the number of nodes of this graph.

Returns:: number_of_nodes – Number of nodes of this graph.
Return type:: int

outdegree(node)#

Return outdegree for a given node.

Parameters:: node (Node) – Node for which to find the outdegree. If not present in the graph, 0 is returned.
Returns:: outdegree – Outdegree of the given node.
Return type:: int

abstract remove_edge(source, target, *data)#

Remove an edge between two nodes from the graph. If an edge is not present in the graph, it is silently ignored. Either direction can be given for an undirected graph, both respective opposite edges will be removed. If data is given, only the edge with matching EdgeData will be removed (both in case of a multigraph and simple graph). If data is not given for a multigraph, all edges between the two nodes will be removed.

Parameters:

source (Node) – Source node of the edge to remove.
target (Node) – Target node of the edge to remove.
*data (EdgeData) – EdgeData of the edge to be removed.

Return type:

None

remove_edges_from(edges_to_remove)#

Remove a given bunch of edges from the graph.

Parameters:: edges_to_remove (Iterable[Edge | tuple[Node, Node]]) – Edges to be removed from the graph, given either as tuple(s) (source node, destination node, edge data) or just (source node, destination node).
Return type:: None

remove_node(node)#

Remove given node from the graph along with all its edges.

Parameters:: node (Node) – Node to be removed. If not present in the graph, it is silently ignored.
Return type:: None

remove_nodes_from(nodes_to_remove)#

Remove a given bunch of nodes from the graph.

Parameters:: nodes_to_remove (Iterable[Node]) – Nodes to be removed from the graph.
Return type:: None

reset_n_ops()#

Convenience method to reset n_ops count of the given complexity object.

Return type:: None

property space_complexity: str#

Return type:: str