Skip to main content

A fast implementation of the Goemans-Williamson scheme for the prize-collecting Steiner tree / forest problem.

Project description

Build Status

pcst_fast

A library for solving the prize-collecting Steiner forest (PCSF) problem on graphs. The underlying algorithm is based on the classical Goemans-Williamson approximation scheme. Our variant provably runs in nearly-linear time and has a factor-2 approximation guarantee. The following paper contains details about the algorithm:

A Nearly-Linear Time Framework for Graph-Structured Sparsity Chinmay Hegde, Piotr Indyk, Ludwig Schmidt ICML 2015

Installation

  • Option 1: pip

      pip install pcst_fast
    

    This may not work for some versions of python on some operating systems.

  • Option 2: manual

    The core C++ library has no dependencies besides a basic build system for C++11. Both g++ and clang are currently supported. The Python wrapper requires a functioning Python build system.

    Clone the repository and compile the python wrapper with the supplied makefile:

      make pcst_fast_py
    

    You can then import the package via import pcst_fast.

Usage

The pcst_fast package contains the following function:

vertices, edges = pcst_fast(edges, prizes, costs, root, num_clusters, pruning, verbosity_level)

The parameters are:

  • edges: a 2D int64 array. Each row (of length 2) specifies an undirected edge in the input graph. The nodes are labeled 0 to n-1, where n is the number of nodes.
  • prizes: the node prizes as a 1D float64 array.
  • costs: the edge costs as a 1D float64 array.
  • root: the root note for rooted PCST. For the unrooted variant, this parameter should be -1.
  • num_clusters: the number of connected components in the output.
  • pruning: a string value indicating the pruning method. Possible values are 'none', 'simple', 'gw', and 'strong' (all literals are case-insensitive). 'none' and 'simple' return intermediate stages of the algorithm and do not have approximation guarantees. They are only intended for development. The standard GW pruning method is 'gw', which is also the default. 'strong' uses "strong pruning", which was introduced in [JMP00]. It has the same theoretical guarantees as GW pruning but better empirical performance in some cases. For the PCSF problem, the output of strong pruning is at least as good as the output of GW pruning.
  • verbosity_level: an integer indicating how much debug output the function should produce.

The output variables are:

  • vertices: the vertices in the solution as a 1D int64 array.
  • edges: the edges in the output as a 1D int64 array. The list contains indices into the list of edges passed into the function.

Performance

The following paper contains many results on standard PCST benchmark instances:

A Fast, Adaptive Variant of the Goemans-Williamson Scheme for the Prize-Collecting Steiner Tree Problem Chinmay Hegde, Piotr Indyk, Ludwig Schmidt Workshop of the 11th DIMACS Implementation Challenge: Steiner Tree Problems, 2014

On instances with up to 350,000 edges, the algorithm typically runs in under 2 seconds on a standard laptop computer from 2010.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pcst_fast-1.0.10.tar.gz (1.7 MB view hashes)

Uploaded Source

Built Distributions

pcst_fast-1.0.10-pp310-pypy310_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (113.2 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

pcst_fast-1.0.10-pp310-pypy310_pp73-manylinux_2_17_i686.manylinux2014_i686.whl (121.5 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686

pcst_fast-1.0.10-pp310-pypy310_pp73-macosx_10_9_x86_64.whl (87.5 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

pcst_fast-1.0.10-pp39-pypy39_pp73-win_amd64.whl (80.5 kB view hashes)

Uploaded PyPy Windows x86-64

pcst_fast-1.0.10-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (113.2 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

pcst_fast-1.0.10-pp39-pypy39_pp73-manylinux_2_17_i686.manylinux2014_i686.whl (121.5 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686

pcst_fast-1.0.10-pp39-pypy39_pp73-macosx_10_9_x86_64.whl (87.5 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

pcst_fast-1.0.10-pp38-pypy38_pp73-win_amd64.whl (80.5 kB view hashes)

Uploaded PyPy Windows x86-64

pcst_fast-1.0.10-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (113.6 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

pcst_fast-1.0.10-pp38-pypy38_pp73-manylinux_2_17_i686.manylinux2014_i686.whl (121.4 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686

pcst_fast-1.0.10-pp38-pypy38_pp73-macosx_10_9_x86_64.whl (87.5 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

pcst_fast-1.0.10-cp312-cp312-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.12 musllinux: musl 1.1+ x86-64

pcst_fast-1.0.10-cp312-cp312-musllinux_1_1_i686.whl (1.8 MB view hashes)

Uploaded CPython 3.12 musllinux: musl 1.1+ i686

pcst_fast-1.0.10-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.3 MB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ x86-64

pcst_fast-1.0.10-cp312-cp312-manylinux_2_17_i686.manylinux2014_i686.whl (1.2 MB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ i686

pcst_fast-1.0.10-cp312-cp312-macosx_10_9_x86_64.whl (96.5 kB view hashes)

Uploaded CPython 3.12 macOS 10.9+ x86-64

pcst_fast-1.0.10-cp311-cp311-win_amd64.whl (81.4 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

pcst_fast-1.0.10-cp311-cp311-win32.whl (71.2 kB view hashes)

Uploaded CPython 3.11 Windows x86

pcst_fast-1.0.10-cp311-cp311-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ x86-64

pcst_fast-1.0.10-cp311-cp311-musllinux_1_1_i686.whl (1.8 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ i686

pcst_fast-1.0.10-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

pcst_fast-1.0.10-cp311-cp311-manylinux_2_17_i686.manylinux2014_i686.whl (1.2 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ i686

pcst_fast-1.0.10-cp311-cp311-macosx_10_9_x86_64.whl (100.1 kB view hashes)

Uploaded CPython 3.11 macOS 10.9+ x86-64

pcst_fast-1.0.10-cp310-cp310-win_amd64.whl (80.5 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

pcst_fast-1.0.10-cp310-cp310-win32.whl (70.4 kB view hashes)

Uploaded CPython 3.10 Windows x86

pcst_fast-1.0.10-cp310-cp310-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ x86-64

pcst_fast-1.0.10-cp310-cp310-musllinux_1_1_i686.whl (1.8 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ i686

pcst_fast-1.0.10-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

pcst_fast-1.0.10-cp310-cp310-manylinux_2_17_i686.manylinux2014_i686.whl (1.2 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ i686

pcst_fast-1.0.10-cp310-cp310-macosx_10_9_x86_64.whl (98.8 kB view hashes)

Uploaded CPython 3.10 macOS 10.9+ x86-64

pcst_fast-1.0.10-cp39-cp39-win_amd64.whl (80.3 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

pcst_fast-1.0.10-cp39-cp39-win32.whl (70.4 kB view hashes)

Uploaded CPython 3.9 Windows x86

pcst_fast-1.0.10-cp39-cp39-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ x86-64

pcst_fast-1.0.10-cp39-cp39-musllinux_1_1_i686.whl (1.8 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ i686

pcst_fast-1.0.10-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

pcst_fast-1.0.10-cp39-cp39-manylinux_2_17_i686.manylinux2014_i686.whl (1.2 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ i686

pcst_fast-1.0.10-cp39-cp39-macosx_10_9_x86_64.whl (98.9 kB view hashes)

Uploaded CPython 3.9 macOS 10.9+ x86-64

pcst_fast-1.0.10-cp38-cp38-win_amd64.whl (80.5 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

pcst_fast-1.0.10-cp38-cp38-win32.whl (70.3 kB view hashes)

Uploaded CPython 3.8 Windows x86

pcst_fast-1.0.10-cp38-cp38-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ x86-64

pcst_fast-1.0.10-cp38-cp38-musllinux_1_1_i686.whl (1.8 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ i686

pcst_fast-1.0.10-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

pcst_fast-1.0.10-cp38-cp38-manylinux_2_17_i686.manylinux2014_i686.whl (1.2 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ i686

pcst_fast-1.0.10-cp38-cp38-macosx_10_9_x86_64.whl (98.7 kB view hashes)

Uploaded CPython 3.8 macOS 10.9+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page