Módulos y funciones

MaxFlow.create_flow_network MaxFlow.edge MaxFlow.vertex

class MaxFlow.create_flow_network

A flow network to which we want to find the maximum flow posible going from one vertex to another. Attributes:

vertices (list): lists all of vertices in the graph network (dictionary): maps every vertex’s name to all of the edges

coming out of the said vertex

MaxFlow()

Follows the path returned by get_path and gets the maximum flow in the network. This function implements the Ford Fulkerson method and calculates the flow while the path is not fully walked. It sums this flow to the fordward edges and substracts it from the reverse edges. Then, another path is calculated and we repeat the process. Returns:

(string): error message when an error in the definition of the

network occurs.

(float): maximum flow through the network

create_edge(start, end, capacity)

Creates and adds a new edge to the flow network with capacity of 0 by first checking the start and end vertices of said edge to verify that the are not the same vertex and that they are both in the network. Args:

start (vertex): start vertex of the new edge end (vertex): end vertex of the new edge capacity (float): capcity of the new edge

Returns:

(string): error message when error arises

create_vertex(name, source=False, sink=False)

Creates and adds a vertex to the network after it checks various error cases to ensure that the vertex can be added. Args:

name (string): name or identifier of vertex_in_network source (bool): whether the vertex to add is source or not sink (bool): whether the vertex to add is sink or not

Returns:

(string): error message when error arises

get_edges()

Takes information from the network vertices and gets a list of all the edges going in and out of this vertices. Returns:

allEdges (list): list of all vertices in the flow network.

get_path(start, end, path)

Recursive function that walks through the network starting at a certain vertex and calculates residual capacity for each edge it passes then uses this residual capacity to define how much flow to send along a given path. Then repeats this process until it reaches the end of the flow network. Args:

start (vertex): start vertex of the new edge end (vertex): end vertex of the new edge path (list): list of vertices in a path

Returns:

path (list): list of vertices in a path

get_sink()

Finds the sink vertex in the list of vertices in the flow network.

get_source()

Finds the source vertex in the list of vertices in the network.

get_vertex(name)

Takes a vertex name finds it in the lists of vertices of the object of class create_flow_network. Args:

name (string): name or identifier of vertex

Returns:

vertex (vertex): object of class vertex corresponding to the

input vertex name.

vertex_in_network(name)

Verifies if a certain vertex is in the list of vertices of the flow network. Args:

name (string): name or identifier of vertex.

Returns:

(bool): if the vertex is in the network or not.

class MaxFlow.edge(start, end, capacity)

An edge in a netwokt, going from one vertex to another Attributes:

start (vertex): the edge comes out of this vertex end (vertex): the edge arrives at this vertex capacity (float): edge’s maximum flow capacity flow (float): current flow in the edge returnEdge (pointer): return edge which is used in the residual graph

class MaxFlow.vertex(name, source=False, sink=False)

A vertex in a network. Attributes:

name (string): name or identifier of vertex source (bool): whether the vertex is a source vertex or not sink (bool): whether the vertex is a sink vertex or not