GLPK Backend for access to GLPK graph functions¶
AUTHORS:
Christian Kuper (201211): Initial implementation
Methods index¶
Graph creation and modification operations:
Adds an isolated vertex to the graph. 

Adds vertices from an iterable container of vertices. 

Sets the vertex parameters. 

Sets the parameters of selected vertices. 

Returns a specific vertex as a 

Returns a dictionary of the dictionaries associated to each vertex. 

Returns a 

Removes a vertex from the graph. 

Removes vertices from the graph. 

Adds an edge between vertices 

Adds edges to the graph. 

Returns an edge connecting two vertices. 

Returns a 

Deletes an edge from the graph. 

Deletes edges from the graph. 
Graph writing operations:
Writes the graph to a plain text file. 

Writes the graph to a text file in DIMACS format. 

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

Writes the maximum flow problem data to a text file in DIMACS format. 
Network optimization operations:
Finds solution to the mincost problem with the outofkilter algorithm. 

Finds solution to the maxflow problem with FordFulkerson algorithm. 

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 aGraph
object.format
– whendata
is a filename, specifies the format of the data read from a file. Theformat
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 nai[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 aGraph
, 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 bedict
objects with keys “low”, “cap” and “cost”. Seeget_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: gbe.write_graph(SAGE_TMP+"/graph.txt") Writing graph to ... 4 lines were written 0 sage: gbe1 = GLPKGraphBackend(SAGE_TMP+"/graph.txt", "plain") 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(): ....: 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
andv
.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 (asstr
) of the tail vertexv
– The name (asstr
) of the head vertexparams
– An optionaldict
containing the edge parameters used for the algorithms. The following keys are used:low
– The minimum flow through the edgecap
– The maximum capacity of the edgecost
– 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)
, whereu
is name (asstr
) of the tail vertex andv
is the name (asstr
) of the head vertex or an iterable container of triples of the form(u, v, params)
where params is adict
as described inadd_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 isspecified, 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 beNone
.
OUTPUT:
Generated names of new vertices if there is at least one
None
value present invertices
.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 1e6 (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 (asstr
) of the tail vertex of the edgev
– The name (asstr
) of the tail vertex of the edgeparams
–params
– An optionaldict
containing the edge parameters (seeadd_edge()
). If this parameter is not provided, all edges connectingu
andv
are deleted. Otherwise only edges with matching parameters are deleted.
See also
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_edge("A", "B") sage: gbe.delete_edge("B", "C", {"low":0.0, "cap":10.0, "cost":20}) sage: gbe.edges()[0][0], gbe.edges()[0][1], gbe.edges()[0][2]['cost'] ('B', 'C', 1.0)
 delete_edges(edges)¶
Deletes edges from the graph.
Non existing edges are ignored.
INPUT:
edges
– An iterable container of edges.
See also
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 (asstr
) 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 (asstr
) 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 graphOUTPUT:
A
list
oftriples
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 (asstr
) of the tail vertexv
– Name (asstr
) of the head vertex
OUTPUT:
A
triple
describing if edge was found orNone
if not. The third value of the triple is adict
containing the following edge parameters:low
– The minimum flow through the edgecap
– The maximum capacity of the edgecost
– The cost of transporting one unit through the edgex
– 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 asstr
.
OUTPUT:
The vertex as a
dict
object orNone
if the vertex does not exist. Thedict
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)
whereproperties
is a dictionary containing the numerical values associated with a vertex. For more information, see the documentation ofGLPKGraphBackend.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 FordFulkerson algorithm.
INPUT:
u
– Name (asstr
) of the tail vertex. Default isNone
.v
– Name (asstr
) of the head vertex. Default isNone
.
If
u
orv
areNone
, 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 foru
andv
, 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 outofkilter algorithm.
The outofkilter 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 vertexdemand
– 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 anint
orfloat
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 ofset_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 resultinglist
.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: gbe.write_ccdata(SAGE_TMP+"/graph.dat") 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: gbe.write_graph(SAGE_TMP+"/graph.txt") 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, otherwisenonzero
EXAMPLES:
sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend sage: gbe = GLPKGraphBackend() 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: gbe.write_maxflow(SAGE_TMP+"/graph.max") Writing maximum flow problem data to ... 6 lines were written 0 sage: gbe = GLPKGraphBackend() sage: gbe.write_maxflow(SAGE_TMP+"/graph.max") Traceback (most recent call last): ... IOError: Cannot write empty graph
 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: gbe.write_mincost(SAGE_TMP+"/graph.min") Writing mincost flow problem data to ... 4 lines were written 0