HTTPS SSH
It is an implementation of an algorithm for solving [vertex cover problem](https://en.wikipedia.org/wiki/Vertex_cover). This problem is [np-complete](https://en.wikipedia.org/wiki/NP-complete), so my algorithm is a variation of the brute force. [Threadpool](https://en.wikipedia.org/wiki/Thread_pool_pattern) was used for parallelization. # Presentation (problem, methods and tests) [Pdf file](https://bitbucket.org/RDkL/vertex-cover/downloads/presentation.pdf) ([LaTeX source](https://bitbucket.org/RDkL/vertex-cover/src/7b26d2b5c905c00ba7b572a2f93bad4ee141eafe/doc/presentation/presentation.tex)). # Necessary components [Clang](http://clang.llvm.org/). Plots: [Python](http://www.python.org/), [Matplotlib](http://matplotlib.org/), [NumPy](http://www.numpy.org/). ### Ubuntu / Mint ``` $ sudo apt-get install clang python python-matplotlib python-numpy ``` # How to build ``` $ clang++ -pthread src/*.cpp src/ThreadPool/*.cpp -std=c++0x -o vertex-cover $ ./vertex-cover 4 ``` 4 -- number_of_threads. ### Plots Folder src/plots contains python scripts. They show some plots, related to tests. ### How to run scripts ``` $ python src/plots/full_graphs_plot.py ``` A plot exapmle. ![Plot example](https://bitbucket.org/RDkL/vertex-cover/raw/c500f68800ebb63352cf2fc25e60494c7f34fe38/data/plot_example.png) # License Modified BSD, [license file](https://bitbucket.org/RDkL/vertex-cover/src/7b26d2b5c905c00ba7b572a2f93bad4ee141eafe/license.txt).