Protecting graphs under multiple simultaneous attacks: a heuristic approach
Project description
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
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
ksrdp-0.0.2.tar.gz
(9.6 kB
view hashes)
Built Distribution
Close
Hashes for ksrdp-0.0.2-cp38-cp38-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1ea01da0a6e6487edebfe36b1898057e66c6f420ed68a284fd33e8493ace7102 |
|
MD5 | efee2f15f5038716e394873b0a08ae8c |
|
BLAKE2b-256 | b695345d84183665c07eaebd294f66c4e13c5ff87c615d4465e518b078fcfc8e |