Stream Vertex Cover

This project aims to provide implementations for parameterized streaming algorithms for vertex cover as posed in Chitnis, Cormode, Hajiaghayi, & Monemizadeh, 2014 as well as to provide a basis for further work into parameterized streaming algorithms.

Features

• Classical implementations for small graphs using NetworkX
• Stream implementations using Python's io
• Stream implementations using Apache Kafka and Faust
• Tools for visualising the algorithms
• Runtime analysis and memory profiling

Code

All code has been statically type checked using MyPy. View the docs here or using the link above.

Setup

Requirements

• Python 3.8
• GNU Make (for running demos, alternatively run commands from Makefile manually)
• Docker and Docker Compose (for using Kafka and Zookeeper)
• Imagemagick (for creating GIFs)

Installation

1. Clone the repo

$ git clone https://github.com/adamjhc/stream-vertex-cover.git

2. (Optional) Create a python virtual environment
3. Install dependencies

$ pip install -r requirements.txt

Demo

If everything has been setup correctly, you should be able to run the demo using

$ make demo_local_stream
python ./src/local_stream/local_stream.py branching-min ./src/test_sets/labelled_edge_lists/florentine_families_labelled.txt
┌Result────────────┬──────────────────────────────┐
│ Graph Name       │ florentine_families_labelled │
│ Graph Nodes      │ 15                           │
│ Graph Edges      │ 20                           │
│ Min Vertex Cover │ 8                            │
└──────────────────┴──────────────────────────────┘

About

This was my final year project while studying BSc Computer Science at the University of Birmingham.

This project was supervised by Rajesh Chitnis