GLPK Backend for access to GLPK graph functions#

AUTHORS:

Christian Kuper (2012-11): Initial implementation

Methods index#

Graph creation and modification operations:

`add_vertex()`	Adds an isolated vertex to the graph.
`add_vertices()`	Adds vertices from an iterable container of vertices.
`set_vertex_demand()`	Sets the vertex parameters.
`set_vertices_demand()`	Sets the parameters of selected vertices.
`get_vertex()`	Returns a specific vertex as a `dict` Object.
`get_vertices()`	Returns a dictionary of the dictionaries associated to each vertex.
`vertices()`	Returns a `list` of all vertices.
`delete_vertex()`	Removes a vertex from the graph.
`delete_vertices()`	Removes vertices from the graph.
`add_edge()`	Adds an edge between vertices `u` and `v`.
`add_edges()`	Adds edges to the graph.
`get_edge()`	Returns an edge connecting two vertices.
`edges()`	Returns a `list` of all edges in the graph.
`delete_edge()`	Deletes an edge from the graph.
`delete_edges()`	Deletes edges from the graph.

Graph writing operations:

`write_graph()`	Writes the graph to a plain text file.
`write_ccdata()`	Writes the graph to a text file in DIMACS format.
`write_mincost()`	Writes the mincost flow problem data to a text file in DIMACS format.
`write_maxflow()`	Writes the maximum flow problem data to a text file in DIMACS format.

Network optimization operations:

`mincost_okalg()`	Finds solution to the mincost problem with the out-of-kilter algorithm.
`maxflow_ffalg()`	Finds solution to the maxflow problem with Ford-Fulkerson algorithm.
`cpp()`	Solves the critical path problem of a project network.

Classes and methods#

class sage.numerical.backends.glpk_graph_backend.GLPKGraphBackend#

Bases: object

GLPK Backend for access to GLPK graph functions

The constructor can either be called without arguments (which results in an empty graph) or with arguments to read graph data from a file.

INPUT:

data – a filename or a Graph object.
format – when data is a filename, specifies the format of the data read from a file. The format parameter is a string and can take values as described in the table below.

Format parameters:

`plain`	Read data from a plain text file containing the following information: nv na i[1] j[1] i[2] j[2] … i[na] j[na] where: nv is the number of vertices (nodes); na is the number of arcs; i[k], k = 1, … , na, is the index of tail vertex of arc k; j[k], k = 1, … , na, is the index of head vertex of arc k.
`dimacs`	Read data from a plain ASCII text file in DIMACS format. A description of the DIMACS format can be found at http://dimacs.rutgers.edu/Challenges/.
`mincost`	Reads the mincost flow problem data from a text file in DIMACS format
`maxflow`	Reads the maximum flow problem data from a text file in DIMACS format

Note

When data is a Graph, the following restrictions are applied.

vertices – the value of the demand of each vertex (see set_vertex_demand()) is obtained from the numerical value associated with the key “rhs” if it is a dictionary.

edges – The edge values used in the algorithms are read from the edges labels (and left undefined if the edge labels are equal to None). To be defined, the labels must be dict objects with keys “low”, “cap” and “cost”. See get_edge() for details.

EXAMPLES:

The following example creates an empty graph:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()

The following example creates an empty graph, adds some data, saves the data to a file and loads it:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: gbe.add_vertices([None, None])
['0', '1']
sage: a = gbe.add_edge('0', '1')
sage: import tempfile
sage: with tempfile.NamedTemporaryFile() as f:
....:     _ = gbe.write_graph(f.name)
....:     gbe1 = GLPKGraphBackend(f.name, "plain")
Writing graph to ...
4 lines were written
Reading graph from ...
Graph has 2 vertices and 1 edge
3 lines were read

The following example imports a Sage Graph and then uses it to solve a maxflow problem:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: g = graphs.PappusGraph()
sage: for ed in g.edges(sort=False):
....:     g.set_edge_label(ed[0], ed[1], {"cap":1})
sage: gbe = GLPKGraphBackend(g)
sage: gbe.maxflow_ffalg('1', '2')
3.0

add_edge(u, v, params=None)#

Adds an edge between vertices u and v.

Allows adding an edge and optionally providing parameters used by the algorithms. If a vertex does not exist it is created.

INPUT:

u – The name (as str) of the tail vertex
v – The name (as str) of the head vertex
params – An optional dict containing the edge parameters used for the algorithms. The following keys are used:
- low – The minimum flow through the edge
- cap – The maximum capacity of the edge
- cost – The cost of transporting one unit through the edge

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: gbe.add_edge("A", "B", {"low":0.0, "cap":10.0, "cost":5})
sage: gbe.vertices()
['A', 'B']
sage: for ed in gbe.edges():
....:     print((ed[0], ed[1], ed[2]['cap'], ed[2]['cost'], ed[2]['low']))
('A', 'B', 10.0, 5.0, 0.0)
sage: gbe.add_edge("B", "C", {"low":0.0, "cap":10.0, "cost":'5'})
Traceback (most recent call last):
...
TypeError: Invalid edge parameter.

add_edges(edges)#

Adds edges to the graph.

INPUT:

edges – An iterable container of pairs of the form (u, v), where u is name (as str) of the tail vertex and v is the name (as str) of the head vertex or an iterable container of triples of the form (u, v, params) where params is a dict as described in add_edge.

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: edges = [("A", "B", {"low":0.0, "cap":10.0, "cost":5})]
sage: edges.append(("B", "C"))
sage: gbe.add_edges(edges)
sage: for ed in gbe.edges():
....:     print((ed[0], ed[1], ed[2]['cap'], ed[2]['cost'], ed[2]['low']))
('A', 'B', 10.0, 5.0, 0.0)
('B', 'C', 0.0, 0.0, 0.0)
sage: edges = [("C", "D", {"low":0.0, "cap":10.0, "cost":5})]
sage: edges.append(("C", "E", 5))
sage: gbe.add_edges(edges)
Traceback (most recent call last):
...
TypeError: Argument 'params' has incorrect type ...
sage: for ed in gbe.edges():
....:     print((ed[0], ed[1], ed[2]['cap'], ed[2]['cost'], ed[2]['low']))
('A', 'B', 10.0, 5.0, 0.0)
('B', 'C', 0.0, 0.0, 0.0)
('C', 'D', 10.0, 5.0, 0.0)

add_vertex(name=None)#

Adds an isolated vertex to the graph.

If the vertex already exists, nothing is done.

INPUT:

name – str of max 255 chars length. If no name is
specified, then the vertex will be represented by the string representation of the ID of the vertex or - if this already exists - a string representation of the least integer not already representing a vertex.

OUTPUT:

If no name is passed as an argument, the new vertex name is returned. None otherwise.

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: gbe.add_vertex()
'0'
sage: gbe.add_vertex("2")
sage: gbe.add_vertex()
'1'

add_vertices(vertices)#

Adds vertices from an iterable container of vertices.

Vertices that already exist in the graph will not be added again.

INPUT:

vertices – iterator of vertex labels (str). A label can be None.

OUTPUT:

Generated names of new vertices if there is at least one None value present in vertices. None otherwise.

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: vertices = [None for i in range(3)]
sage: gbe.add_vertices(vertices)
['0', '1', '2']
sage: gbe.add_vertices(['A', 'B', None])
['5']
sage: gbe.add_vertices(['A', 'B', 'C'])
sage: gbe.vertices()
['0', '1', '2', 'A', 'B', '5', 'C']

cpp()#

Solves the critical path problem of a project network.

OUTPUT:

The length of the critical path of the network

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: gbe.add_vertices([None for i in range(3)])
['0', '1', '2']
sage: gbe.set_vertex_demand('0', 3)
sage: gbe.set_vertex_demand('1', 1)
sage: gbe.set_vertex_demand('2', 4)
sage: a = gbe.add_edge('0', '2')
sage: a = gbe.add_edge('1', '2')
sage: gbe.cpp()
7.0
sage: v = gbe.get_vertex('1')
sage: 1, v["rhs"], v["es"], v["ls"] # abs tol 1e-6
(1, 1.0, 0.0, 2.0)

delete_edge(u, v, params=None)#

Deletes an edge from the graph.

If an edge does not exist it is ignored.

INPUT:

u – The name (as str) of the tail vertex of the edge
v – The name (as str) of the tail vertex of the edge
params – params – An optional dict containing the edge parameters (see add_edge()). If this parameter is not provided, all edges connecting u and v are deleted. Otherwise only edges with matching parameters are deleted.

See also

delete_edge()

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: edges = [("A", "B", {"low":0.0, "cap":10.0, "cost":5})]
sage: edges.append(("A", "B", {"low":0.0, "cap":15.0, "cost":10}))
sage: edges.append(("B", "C", {"low":0.0, "cap":20.0, "cost":1}))
sage: edges.append(("B", "C", {"low":0.0, "cap":10.0, "cost":20}))
sage: gbe.add_edges(edges)
sage: gbe.delete_edges(edges[1:])
sage: len(gbe.edges())
1
sage: gbe.edges()[0][0], gbe.edges()[0][1], gbe.edges()[0][2]['cap']
('A', 'B', 10.0)

delete_vertex(vert)#

Removes a vertex from the graph.

Trying to delete a non existing vertex will raise an exception.

INPUT:

vert – The name (as str) of the vertex to delete.

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: verts = ["A", "D"]
sage: gbe.add_vertices(verts)
sage: gbe.delete_vertex("A")
sage: gbe.vertices()
['D']
sage: gbe.delete_vertex("A")
Traceback (most recent call last):
...
RuntimeError: Vertex A does not exist.

delete_vertices(verts)#

Removes vertices from the graph.

Trying to delete a non existing vertex will raise an exception.

INPUT:

verts – iterable container containing names (as str) of the vertices to delete

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: verts = ["A", "B", "C", "D"]
sage: gbe.add_vertices(verts)
sage: v_d = ["A", "B"]
sage: gbe.delete_vertices(v_d)
sage: gbe.vertices()
['C', 'D']
sage: gbe.delete_vertices(["C", "A"])
Traceback (most recent call last):
...
RuntimeError: Vertex A does not exist.
sage: gbe.vertices()
['C', 'D']

edges()#

Returns a list of all edges in the graph

OUTPUT:

A list of triples representing the edges of the graph.

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: edges = [("A", "B", {"low":0.0, "cap":10.0, "cost":5})]
sage: edges.append(("B", "C"))
sage: gbe.add_edges(edges)
sage: for ed in gbe.edges():
....:     print((ed[0], ed[1], ed[2]['cost']))
('A', 'B', 5.0)
('B', 'C', 0.0)

get_edge(u, v)#

Returns an edge connecting two vertices.

Note

If multiple edges connect the two vertices only the first edge found is returned.

INPUT:

u – Name (as str) of the tail vertex
v – Name (as str) of the head vertex

OUTPUT:

A triple describing if edge was found or None if not. The third value of the triple is a dict containing the following edge parameters:

low – The minimum flow through the edge

cap – The maximum capacity of the edge

cost – The cost of transporting one unit through the edge

x – The actual flow through the edge after solving

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: edges = [("A", "B"), ("A", "C"), ("B", "C")]
sage: gbe.add_edges(edges)
sage: ed = gbe.get_edge("A", "B")
sage: ed[0], ed[1], ed[2]['x']
('A', 'B', 0.0)
sage: gbe.get_edge("A", "F") is None
True

get_vertex(vertex)#

Returns a specific vertex as a dict Object.

INPUT:

vertex – The vertex label as str.

OUTPUT:

The vertex as a dict object or None if the vertex does not exist. The dict contains the values used or created by the different algorithms. The values associated with the keys following keys contain:

“rhs” – The supply / demand value the vertex (mincost alg)

“pi” – The node potential (mincost alg)

“cut” – The cut flag of the vertex (maxflow alg)

“es” – The earliest start of task (cpp alg)

“ls” – The latest start of task (cpp alg)

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: verts = ["A", "B", "C", "D"]
sage: gbe.add_vertices(verts)
sage: sorted(gbe.get_vertex("A").items())
[('cut', 0), ('es', 0.0), ('ls', 0.0), ('pi', 0.0), ('rhs', 0.0)]
sage: gbe.get_vertex("F") is None
True

get_vertices(verts)#

Returns a dictionary of the dictionaries associated to each vertex.

INPUT:

verts – iterable container of vertices

OUTPUT:

A list of pairs (vertex, properties) where properties is a dictionary containing the numerical values associated with a vertex. For more information, see the documentation of GLPKGraphBackend.get_vertex().

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: verts = ['A', 'B']
sage: gbe.add_vertices(verts)
sage: sorted(gbe.get_vertices(verts)['B'].items())
[('cut', 0), ('es', 0.0), ('ls', 0.0), ('pi', 0.0), ('rhs', 0.0)]
sage: gbe.get_vertices(["C", "D"])
{}

maxflow_ffalg(u=None, v=None)#

Finds solution to the maxflow problem with Ford-Fulkerson algorithm.

INPUT:

u – Name (as str) of the tail vertex. Default is None.
v – Name (as str) of the head vertex. Default is None.

If u or v are None, the currently stored values for the head or tail vertex are used. This behavior is useful when reading maxflow data from a file. When calling this function with values for u and v, the head and tail vertex are stored for later use.

OUTPUT:

The solution to the maxflow problem, i.e. the maximum flow.

Note

If the source or sink vertex does not exist, an IndexError is raised.
If the source and sink are identical, a ValueError is raised.
This method raises MIPSolverException exceptions when the solution cannot be computed for any reason (none exists, or the LP solver was not able to find it, etc…)

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: v = gbe.add_vertices([None for i in range(5)])
sage: edges = ((0, 1, 2), (0, 2, 3), (1, 2, 3), (1, 3, 4),
....:         (3, 4, 1), (2, 4, 2))
sage: for a in edges:
....:     edge = gbe.add_edge(str(a[0]), str(a[1]), {"cap":a[2]})
sage: gbe.maxflow_ffalg('0', '4')
3.0
sage: gbe.maxflow_ffalg()
3.0
sage: gbe.maxflow_ffalg('0', '8')
Traceback (most recent call last):
...
IndexError: Source or sink vertex does not exist

mincost_okalg()#

Finds solution to the mincost problem with the out-of-kilter algorithm.

The out-of-kilter algorithm requires all problem data to be integer valued.

OUTPUT:

The solution to the mincost problem, i.e. the total cost, if operation was successful.

Note

This method raises MIPSolverException exceptions when the solution cannot be computed for any reason (none exists, or the LP solver was not able to find it, etc…)

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: vertices = (35, 50, 40, -45, -20, -30, -30)
sage: vs = gbe.add_vertices([None for i in range(len(vertices))])
sage: v_dict = {}
sage: for i, v in enumerate(vs):
....:     v_dict[v] = vertices[i]
sage: gbe.set_vertices_demand(list(v_dict.items()))
sage: cost = ((8, 6, 10, 9), (9, 12, 13, 7), (14, 9, 16, 5))

sage: for i in range(len(cost)):
....:     for j in range(len(cost[0])):
....:         gbe.add_edge(str(i), str(j + len(cost)), {"cost":cost[i][j], "cap":100})
sage: gbe.mincost_okalg()
1020.0
sage: for ed in gbe.edges():
....:     print("{} -> {} {}".format(ed[0], ed[1], ed[2]["x"]))
0 -> 6 0.0
0 -> 5 25.0
0 -> 4 10.0
0 -> 3 0.0
1 -> 6 0.0
1 -> 5 5.0
1 -> 4 0.0
1 -> 3 45.0
2 -> 6 30.0
2 -> 5 0.0
2 -> 4 10.0
2 -> 3 0.0

set_vertex_demand(vertex, demand)#

Sets the demand of the vertex in a mincost flow algorithm.

INPUT:

vertex – Name of the vertex
demand – the numerical value representing demand of the vertex in a mincost flow algorithm (it could be for instance \(-1\) to represent a sink, or \(1\) to represent a source and \(0\) for a neutral vertex). This can either be an int or float value.

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: vertices = [None for i in range(3)]
sage: gbe.add_vertices(vertices)
['0', '1', '2']
sage: gbe.set_vertex_demand('0', 2)
sage: gbe.get_vertex('0')['rhs']
2.0
sage: gbe.set_vertex_demand('3', 2)
Traceback (most recent call last):
...
KeyError: 'Vertex 3 does not exist.'

set_vertices_demand(pairs)#

Sets the parameters of selected vertices.

INPUT:

pairs – A list of pairs (vertex, demand) associating a demand to each vertex. For more information, see the documentation of set_vertex_demand().

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: vertices = [None for i in range(3)]
sage: gbe.add_vertices(vertices)
['0', '1', '2']
sage: gbe.set_vertices_demand([('0', 2), ('1', 3), ('3', 4)])
sage: sorted(gbe.get_vertex('1').items())
[('cut', 0), ('es', 0.0), ('ls', 0.0), ('pi', 0.0), ('rhs', 3.0)]

vertices()#

Returns the list of all vertices

Note

Changing elements of the list will not change anything in the the graph.

Note

If a vertex in the graph does not have a name / label it will appear as None in the resulting list.

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: verts = ["A", "B", "C"]
sage: gbe.add_vertices(verts)
sage: a = gbe.vertices(); a
['A', 'B', 'C']
sage: a.pop(0)
'A'
sage: gbe.vertices()
['A', 'B', 'C']

write_ccdata(fname)#

Writes the graph to a text file in DIMACS format.

Writes the data to plain ASCII text file in DIMACS format. A description of the DIMACS format can be found at http://dimacs.rutgers.edu/Challenges/.

INPUT:

fname – full name of the file

OUTPUT:

Zero if the operations was successful otherwise nonzero

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: a = gbe.add_edge("0", "1")
sage: import tempfile
sage: with tempfile.NamedTemporaryFile() as f:
....:     gbe.write_ccdata(f.name)
Writing graph to ...
6 lines were written
0

write_graph(fname)#

Writes the graph to a plain text file

INPUT:

fname – full name of the file

OUTPUT:

Zero if the operations was successful otherwise nonzero

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: a = gbe.add_edge("0", "1")
sage: import tempfile
sage: with tempfile.NamedTemporaryFile() as f:
....:     gbe.write_graph(f.name)
Writing graph to ...
4 lines were written
0

write_maxflow(fname)#

Writes the maximum flow problem data to a text file in DIMACS format.

INPUT:

fname – Full name of file

OUTPUT:

Zero if successful, otherwise non-zero

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: import tempfile
sage: with tempfile.NamedTemporaryFile() as f:
....:     gbe.write_maxflow(f.name)
Traceback (most recent call last):
...
OSError: Cannot write empty graph
sage: gbe.add_vertices([None for i in range(2)])
['0', '1']
sage: a = gbe.add_edge('0', '1')
sage: gbe.maxflow_ffalg('0', '1')
0.0
sage: with tempfile.NamedTemporaryFile() as f:
....:     gbe.write_maxflow(f.name)
Writing maximum flow problem data to ...
6 lines were written
0

write_mincost(fname)#

Writes the mincost flow problem data to a text file in DIMACS format

INPUT:

fname – Full name of file

OUTPUT:

Zero if successful, otherwise nonzero

EXAMPLES:

sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: a = gbe.add_edge("0", "1")
sage: import tempfile
sage: with tempfile.NamedTemporaryFile() as f:
....:     gbe.write_mincost(f.name)
Writing min-cost flow problem data to ...
4 lines were written
0