pynetgen 0.1.0

A Python module for generating random network flows problem instances in DIMACS graph format.

PyNETGEN

A Python module for generating random network flows problem instances in DIMACS graph format, including an implementation of the NETGEN algorithm (Klingman et al. 1974).

Introduction

This package defines a variety of scripts for generating random instances of network flows problems subject to tuneable parameters. This can be accomplished within Python by importing pynetgen as a module, or from the command line by calling pynetgen as a shell script.

PyNETGEN began as a Python implementation of NETGEN, a random network flows problem instance generator defined in:

D. Klingman, A. Napier, and J. Stutz. NETGEN: A Program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems. Management Science, 20(5):814-821, 1974. doi:10.1287/mnsc.20.5.814.

This package's implementation of NETGEN is based on a C implementation of NETGEN by Norbert Schlenker (1989). The original implementation was used to generate random minimum-cost flow, maximum flow, and assignment problems, exported in DIMACS graph format.

An alternate network generation algorithm is also included for generating grid-based graphs similar to those described for the test problems of:

S. Sadeghi, A. Seifi, and E. Azizi. Trilevel shortest path network interdiction with partial fortification. Computers & Industrial Engineering, 106:400-411, 2017. doi:10.1016/j.cie.2017.02.006.

Project Status

This is a work in progress. It currently includes only a few necessary submodules and some of the overall framework, and it is not yet release-ready.