Imports¶

Internally, GraphILP wraps the NetworkX classes to represent graphs. This makes it particularly easy to import graphs through the functionality provided by this package. There are, however, a number of file formats specific to the types of optimisation problems covered by GraphILP. This module therefore offers import filters for such file formats.

ILPGraph¶

The ILPGraph class takes care of both the graph instance used in an optimisation problem and the variables of the integer linear program used to solve it.

`ILPGraph`	Wrapper class for graph instances and variables of a related integer linear program
`ILPGraph.set_nx_graph`	Set the underlying NetworkX graph
`ILPGraph.set_edge_vars`	Set the dictionary of edge variables
`ILPGraph.set_node_vars`	Set the dictionary of node variables
`ILPGraph.set_label_vars`	Set the dictionary of node label variables

NetworkX¶

NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks. GraphILP is using NetworkX objects both to represent graphs internally and as an interface to provide problem instances.

read

Wrap a NetworkX graph class by an ILPGraph class

Graph file formats¶

Many useful benchmark instances for optimisation problems on graphs are available from a variety of sources. In this section, we provide import filters to create NetworkX Graph objects from various specialised file formats.

`edges_to_networkx`	Creates a NetworkX Graph from an .edges file (Network Repository format).
`stp_to_networkx`	Creates a NetworkX Graph from an .stp file (SteinLib format).
`mis_to_networkx`	Creates a NetworkX Graph from a .mis file (ASCII DIMACS graph format).

ILPSetSystem¶

The ILPSetSystem class takes care of both the set system instance used in an optimisation problem and the variables of the integer linear program used to solve it.

A set system (or undirected hypergraph) consists of a universe \(U\) generalising the vertex set of a graph and a generalised edge set called the system of the graph. Each element of the system is a subset of the universe and hence generalises the notion of an edge which is a two element subset of the universe.

`ILPSetSystem`	Wrapper class for set systems (undirected hyper graphs)
`ILPSetSystem.set_universe`	Set the universe of the set system
`ILPSetSystem.set_system`	Set the names of the sets in the system
`ILPSetSystem.set_inc_matrix`	Set the incidence matrix of the system
`ILPSetSystem.set_system_vars`	Set the dictionary of indicator variables for the elements of the system
`ILPSetSystem.set_universe_vars`	Set the dictionary of indicator variables for elements of the universe

Details¶

class graphilp.imports.ilpgraph.ILPGraph¶

Wrapper class for graph instances and variables of a related integer linear program

set_edge_vars(variables)¶

Set the dictionary of edge variables

Parameters: variables – a dictionary with variable names as keys and gurobipy variables as values

set_label_vars(variables)¶

Set the dictionary of node label variables

Parameters: variables – a dictionary with variable names as keys and gurobipy variables as values

set_node_vars(variables)¶

Set the dictionary of node variables

Parameters: variables – a dictionary with variable names as keys and gurobipy variables as values

set_nx_graph(G)¶

Set the underlying NetworkX graph

Parameters: G – a NetworkX graph

class graphilp.imports.ilpsetsystem.ILPSetSystem¶

Wrapper class for set systems (undirected hyper graphs)

Joint representation of set system instances and variables of a related integer linear program

set_inc_matrix(M)¶

Set the incidence matrix of the system

The incidence matrix indicates which element of the universe is contained in which set of the system.

Parameters: M – the incidence matrix of the set system

set_system(S)¶

Set the names of the sets in the system

Parameters: S – the system of the set system

set_system_vars(variables)¶

Set the dictionary of indicator variables for the elements of the system

Parameters: variables – a dictionary with variable names as keys and gurobipy variables as values

set_universe(U)¶

Set the universe of the set system

Parameters: U – the universe of the set system

set_universe_vars(variables)¶

Set the dictionary of indicator variables for elements of the universe

Parameters: variables – a dictionary with variable names as keys and gurobipy variables as values

graphilp.imports.networkx.read(G)¶

Wrap a NetworkX graph class by an ILPGraph class

The wrapper class is used store the graph and the related variables of an optimisation problem in a single entity.

Parameters: G – a NetworkX graph
Returns: an ILPGraph

graphilp.imports.graph_formats.edges_to_networkx(path)¶

Creates a NetworkX Graph from an .edges file (Network Repository format).

Network Repository is a large collection of network graph data for research and benchmarking.

Parameters: path (str) – path to .edges file
Returns: a NetworkX Graph

graphilp.imports.graph_formats.mis_to_networkx(path)¶

Creates a NetworkX Graph from a .mis file (ASCII DIMACS graph format).

This is used for maximum independet set benchmarking data from BHOSLIB.

Parameters: path (str) – path to .edges file
Returns: a NetworkX Graph

graphilp.imports.graph_formats.stp_to_networkx(path)¶

Creates a NetworkX Graph from an .stp file (SteinLib format).

SteinLib is a collection of Steiner tree problems in graphs and variants.

The format description can be found here on the SteinLib pages.

Parameters: path (str) – path to .stp file
Returns: a NetworkX Graph and a list of terminals

Example:: G, terminals = stp_to_networkx(“steinlib_instance.stp”)