This piece of code is heavily modified from
https://github.com/fraenkel-lab/pcst_fast
We owe special thanks to the authors who make the above code available
Please also consider citing authors' work as related work
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

To run this code, 
in main.cc 
the required input files are:
(1)A weighted(weight is not necessary) edgeList file
(2)An attribute file starting with each node id and its attributes
(3)A penalty file starting with each node id and its penalty value in the graph
(4)An ordered given node indexing, the algorithm will reindex the node id from 0


Cite
If you use this code in a scientific publication, we would appreciate citations to the following paper:

@inproceedings{guan2019attribute,
  title={Attribute-Driven Backbone Discovery},
  author={Guan, Sheng and Ma, Hanchao and Wu, Yinghui},
  booktitle={Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery \& Data Mining},
  pages={187--195},
  year={2019},
  organization={ACM}
}