ksrdp 0.0.2

Protecting graphs under multiple simultaneous attacks: a heuristic approach

General

This repo contains the implementation, instances and results of the paper 'Protecting graphs under multiple simultaneous attacks: a heuristic approach' by Marko Djukanovic, Stefan Kapunac, Aleksandar Kartelj and Dragan Matic.

Original implementation is in C++ and can be compiled using the Makefile. We also created Python bindings using the Pybind11 library. For a quickstart see this Colab notebook.

Installation

pip install ksrdp

Minimal working example

import ksrdp

def test_greedy(in_file_path: str, num_attacks: int) -> None:
    neighbors = ksrdp.read_instance(in_file_path)
    solution, value = ksrdp.greedy_uncovered(neighbors, num_attacks)
    print(f'greedy solution: {solution}, value: {value}')

def test_vns(in_file_path: str, num_attacks: int, vns_params: dict) -> None:
    neighbors = ksrdp.read_instance(in_file_path)
    solution, fitness, iter, end_time, best_found_time = ksrdp.vns(
        neighbors,
        vns_params['comb_take_all_bound'],
        vns_params['comb_intense_max'],
        vns_params['comb_lightweight_max'],
        num_attacks,
        vns_params['time_limit'],
        vns_params['iter_limit'],
        vns_params['k_min'],
        vns_params['k_max'],
        vns_params['move_prob'],
        vns_params['tries'],
        vns_params['num_alternatives_cutoff'],
        # verbose=True,
    )
    print(f'vns solution: {solution}, fitness: {fitness}, iter: {iter}, end_time: {end_time}, best_found_time: {best_found_time}')

def main():
    # help(ksrdp)
    in_file_path = '../instances/random/10_1.txt'
    num_attacks = 2
    test_greedy(in_file_path, num_attacks)
    vns_params = {
        'comb_take_all_bound': 100_000,
        'comb_intense_max': 10_000_000,
        'comb_lightweight_max': 10_000,
        'time_limit': 60,
        'iter_limit': 5000,
        'k_min': 1,
        'k_max': 10,
        'move_prob': 0.5,
        'tries': 10,
        'num_alternatives_cutoff': 100,
    }
    test_vns(in_file_path, num_attacks, vns_params)

if __name__ == '__main__':
    main()

License