Graphs

class ecyglpki.Graph

A GLPK graph

a_size

size of data associated with each arc, an int

add_arc(tail, head)

Add new arc to graph

add_named_vertices(*names)

Add new vertices to graph

Parameters:names (tuple of str) – the names of the vertices to add, none may exceed 255 bytes encoded as UTF-8

add_vertices(int vertices)

Add new vertices to graph

asnprob_hall(int v_set, int a_x)

Find bipartite matching of maximum cardinality

asnprob_lp(str asnform, bool copy_names, int v_set, int a_cost)

Convert assignment problem to LP

asnprob_okalg(str asnform, int v_set, int a_cost, int a_x)

Solve assignment problem with out-of-kilter algorithm

check_asnprob(int v_set)

Check correctness of assignment problem data

cpp(int v_t, int v_es, int v_ls)

Solve critical path problem

del_arc(Arc arc)

Delete arc from graph

del_vertices(*vertices)

Delete vertices from graph

erase_graph(int vertex_data_size, int arc_data_size)

Erase graph content

find_vertex(str name)

Find vertex by its name

Parameters:name (str) – the name of the vertex

find_vertex_as_needed(vertex)

get_vertex_object(vertex)

Return Vertex object

gridgen(int vertex_data_size, int arc_data_size, int v_rhs, int a_cap, int a_cost, **parameters)

Grid-like network problem generator

maxflow_ffalg(source, sink, int a_cap, int a_x, int v_cut)

Find maximal flow with Ford-Fulkerson algorithm

maxflow_lp(bool copy_names, source, sink, int a_cap)

Convert maximum flow problem to LP

mincost_lp(bool copy_names, int v_rhs, int a_low, int a_cap, int a_cost)

Convert minimum cost flow problem to LP

mincost_okalg(int v_rhs, int a_low, int a_cap, int a_cost, int a_x, int v_pi)

Find minimum-cost flow with out-of-kilter algorithm

mincost_relax4(int v_rhs, int a_low, int a_cap, int a_cost, int crash, int a_x, int a_rc)

Find minimum-cost flow with Bertsekas-Tseng relaxation method

na

The number of arcs in the graph, an int

netgen(int vertex_data_size, int arc_data_size, int v_rhs, int a_cap, int a_cost, **parameters)

Klingman’s network problem generator

nv

The number of vertices in the graph, an int

read_asnprob(int vertex_data_size, int arc_data_size, int v_set, int a_cost, str fname)

Read assignment problem data in DIMACS format

read_ccdata(int vertex_data_size, int arc_data_size, int v_wgt, str fname)

Read graph in DIMACS clique/coloring format

read_graph(int vertex_data_size, int arc_data_size, str fname)

Read graph from plain text file

read_maxflow(int vertex_data_size, int arc_data_size, int a_cap, str fname)

Read maximum flow problem data in DIMACS format

read_mincost(int vertex_data_size, int arc_data_size, int v_rhs, int a_low, int a_cap, int a_cost, str fname)

Read min-cost flow problem data in DIMACS format

rmfgen(int vertex_data_size, int arc_data_size, int a_cap, parameters)

Goldfarb’s maximum flow problem generator

set_graph_name(str name)

Assign (change) graph name

Parameters:name (str) – the name of the graph, it may not exceed 255 bytes encoded as UTF-8

set_vertex_name(vertex, str name)

Assign (change) vertex name

Parameters:name (str) – the name of the vertex, it may not exceed 255 bytes encoded as UTF-8

strong_comp(int v_num)

Find all strongly connected components of graph

top_sort(int v_num)

Topological sorting of acyclic digraph

v_size

Size of data associated with each vertex, an int

wclique_exact(int v_wgt, int v_set)

Find maximum weight clique with exact algorithm

weak_comp(int v_num)

Find all weakly connected components of graph

write_asnprob(int v_set, int a_cost, str fname)

Write assignment problem data in DIMACS format

write_ccdata(int v_wgt, str fname)

Write graph in DIMACS clique/coloring format

write_graph(str fname)

Write graph to plain text file

write_maxflow(source, sink, int a_cap, str fname)

Write maximum flow problem data in DIMACS format

write_mincost(int v_rhs, int a_low, int a_cap, int a_cost, str fname)

Write min-cost flow problem data in DIMACS format

Vertices

class ecyglpki.Vertex

A GLPK graph vertex

i

Vertex ordinal number, an int

inc

First incoming arc, an Arc

name

Vertex name, a str

out

First outgoing arc, an Arc

Arcs

class ecyglpki.Arc

A GLPK graph arc

h_next

Next arc having the same head endpoint, an Arc

h_prev

Previous arc having the same head endpoint, an Arc

head

Head vertex, a Vertex

t_next

Next arc having the same tail endpoint, an Arc

t_prev

Previous arc having the same tail endpoint, an Arc

tail

Tail vertex, a Vertex