Skip to content

Latest commit

 

History

History
60 lines (41 loc) · 2.27 KB

README.md

File metadata and controls

60 lines (41 loc) · 2.27 KB
Raw

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
  1. (Optional) Create a python virtual environment
  2. 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