FlowNetwork#

class FlowNetwork(adjacency_list=None, source=NoNode, sink=NoNode, check_input_flow_validity=False)#

Bases: DiGraph, Generic[Node]

__init__(adjacency_list=None, source=NoNode, sink=NoNode, check_input_flow_validity=False)#

Constructor of the FlowNetwork class.

Parameters:

adjacency_list (adjacency_list: Optional[dict[Node, dict[Node, FlowEdge]]] (default None)) – Optional adjacency list from which to build the flow network. Edge data are named tuples with numeric fields (lower_bound, flow, upper_bound). Flow values between nodes may be None in case Flow has not been assigned yet.
source (Node | NoNode (default NoNode())) – Source of the flow. If not given, an error is raised.
sink (Node | NoNode (default NoNode())) – Sink of the flow. If not given, an error is raised.
check_input_flow_validity (bool (default False)) – Validity of flow given in this constructor may be optionally checked with computation cost of O(n^2).

Methods

`__init__`([adjacency_list, source, sink, ...])	Constructor of the FlowNetwork 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.
`change_flow_between_nodes`(source, target, ...)	Change flow between two nodes to new_flow.
`check_flow_validity`()	rtype: `None`
`degree`(node)	Return degree for a given node.
`get_edge_data`(source, target)	rtype: `Union`[`TypeVar`(`EdgeData`), `NoEdge`]
`get_node_balance`(node)	rtype: `int` \| `float`
`increment_n_ops`([increment])	Convenience method to increment n_ops count of the given complexity object.
`indegree`(node)	Return indegree for a given node.
`is_flow_within_bounds`(edge_data)	rtype: `bool`
`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 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.
`set_sink`(node)	rtype: `None`
`set_source`(node)	rtype: `None`

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.
`current_flow`	rtype: `float`
`edges`	Retrieve the edges of this graph.
`is_directed`	rtype: `bool`
`is_multigraph`	rtype: `bool`
`max_lower_bound`	rtype: `int`
`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.
`sink`	rtype: `TypeVar`(`Node`)
`source`	rtype: `TypeVar`(`Node`)
`space_complexity`	rtype: `str`

add_edge(edge)#

Add a single edge to the graph. An edge is a tuple of source node, destination node and edge data. If an edge is already present in the graph between two nodes, 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]]

change_flow_between_nodes(source, target, new_flow)#

Change flow between two nodes to new_flow. Does not affect anything if edge did not exist before or if the new flow is outside bounds.

Parameters:

source (Node) – Source of the edge with flow to be changed.
target (Node) – Target of the edge with flow to be changed.
new_flow (int | float) – New value of the flow to be assigned to the edge.

Return type:

None

check_flow_validity()#

Return type:: None

property current_flow: float#

Return type:: float

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]

get_node_balance(node)#

Return type:: int | float

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

property is_directed: bool#

Return type:: bool

static is_flow_within_bounds(edge_data)#

Return type:: bool

property is_multigraph: bool#

Return type:: bool

property max_lower_bound: int#

Return type:: int

property n_ops: int#

Return type:: int

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

remove_edge(source, target, *data)#

Remove an edge from the graph. If an edge is not present in the graph, it is silently ignored.

Parameters:

source (Node) – Source node of the edge to remove.
target (Node) – Target node of the edge to remove.
*data (SingleEdgeData) – Data of the edge to be removed. Only one entry has to be given for a simple graph.

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

set_sink(node)#

Return type:: None

set_source(node)#

Return type:: None

property sink: Node#

Return type:: TypeVar(Node)

property source: Node#

Return type:: TypeVar(Node)

property space_complexity: str#

Return type:: str