GLPK Backend for access to GLPK graph functions
AUTHORS:
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 dictonaries 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. |
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:
Format parameters:
plain | Read data from a plain text file containing the following information:
where:
|
dimacs | Read data from a plain ASCII text file in DIMACS format. A discription 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: gbe.write_graph(SAGE_TMP+"/graph.txt")
Writing graph to ...
2 lines were written
0
sage: gbe1 = GLPKGraphBackend(SAGE_TMP+"/graph.txt", "plain")
Reading graph from ...
Graph has 2 vertices and 1 arc
2 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
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
EXAMPLE:
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.
Adds edges to the graph.
INPUT:
EXAMPLE:
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
Adds an isolated vertex to the graph.
If the vertex already exists, nothing is done.
INPUT:
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.
EXAMPLE:
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'
Adds vertices from an iterable container of vertices.
Vertices that already exist in the graph will not be added again.
INPUT:
OUTPUT:
Generated names of new vertices if there is at least one None value present in vertices. None otherwise.
EXAMPLE:
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']
TESTS:
sage: from sage.numerical.backends.glpk_graph_backend import GLPKGraphBackend
sage: gbe = GLPKGraphBackend()
sage: gbe.add_vertices([None, None, None, '1'])
['0', '2', '3']
Solves the critical path problem of a project network.
OUTPUT:
The length of the critical path of the network
EXAMPLE:
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: print 1, v["rhs"], v["es"], v["ls"] # abs tol 1e-6
1 1.0 0.0 2.0
Deletes an edge from the graph.
If an edge does not exist it is ignored.
INPUT:
See also
EXAMPLE:
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: print gbe.edges()[0][0], gbe.edges()[0][1], gbe.edges()[0][2]['cost']
B C 1.0
Deletes edges from the graph.
Non existing edges are ignored.
INPUT:
See also
EXAMPLE:
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: print gbe.edges()[0][0], gbe.edges()[0][1], gbe.edges()[0][2]['cap']
A B 10.0
Removes a vertex from the graph.
Trying to delete a non existing vertex will raise an exception.
INPUT:
EXAMPLE:
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.
Removes vertices from the graph.
Trying to delete a non existing vertex will raise an exception.
INPUT:
EXAMPLE:
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']
Returns a list of all edges in the graph
OUTPUT:
A list of triples representing the edges of the graph.
EXAMPLE:
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
Returns an edge connecting two vertices.
Note
If multiple edges connect the two vertices only the first edge found is returned.
INPUT:
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
EXAMPLE:
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: print ed[0], ed[1], ed[2]['x']
A B 0.0
sage: gbe.get_edge("A", "F") is None
True
Returns a specific vertex as a dict Object.
INPUT:
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)
EXAMPLE:
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
Returns a dictionary of the dictonaries associated to each vertex.
INPUT:
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().
EXAMPLE:
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"])
{}
Finds solution to the maxflow problem with Ford-Fulkerson algorithm.
INPUT:
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
EXAMPLE:
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
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 can not be computed for any reason (none exists, or the LP solver was not able to find it, etc...)
EXAMPLE:
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(v_dict.items())
sage: cost = ((8, 6, 10, 9), (9, 12, 13, 7), (14, 9, 16, 5))
sage: lcost = range(len(cost))
sage: lcost_0 = range(len(cost[0]))
sage: for i in lcost:
... for j in lcost_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 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
Sets the demand of the vertex in a mincost flow algorithm.
INPUT:
EXAMPLE:
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.'
Sets the parameters of selected vertices.
INPUT:
EXAMPLE:
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)]
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.
EXAMPLE:
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']
Writes the graph to a text file in DIMACS format.
Writes the data to plain ASCII text file in DIMACS format. A discription of the DIMACS format can be found at http://dimacs.rutgers.edu/Challenges/.
INPUT:
OUTPUT:
Zero if the operations was successful otherwise nonzero
EXAMPLE:
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
Writes the graph to a plain text file
INPUT:
OUTPUT:
Zero if the operations was successful otherwise nonzero
EXAMPLE:
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 ...
2 lines were written
0
Writes the maximum flow problem data to a text file in DIMACS format.
INPUT:
OUTPUT:
Zero if successful, otherwise non-zero
EXAMPLE:
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
Writes the mincost flow problem data to a text file in DIMACS format
INPUT:
OUTPUT:
Zero if successful, otherwise nonzero
EXAMPLE:
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 min-cost flow problem data to ...
4 lines were written
0