Software Lab Parallel Graph Algorithms

We run through the main stages of a typical software development process inspired by practically relevant graph algorithms.

General Information

... on the administrative structure of the lab can be found here.


  • Dag Reversal [1]:
    • Design a data structure for storage of directed acyclic graphs (dags) with floating-point labels v(j) and e(i,j) attached to all vertices j and edges (i,j), respectively.
    • implement the generation of random dags of arbitrary size including (block-wise) streaming to hard disc; vertex labels are initially equal to zero; edge labels are nonzeros
    • traverse all edges in reverse order according to the (chain) rule (of differentiation) v(i)+=e(i,j)*v(j) and for given nonzero labels of the maximal (without successors) vertices
    • hide the overhead of writing and reading data to and from hard disc by asynchrony (parallelism) and productive waiting (vertex elimination)
    • a vertex j is eliminated by connecting its predecessors i with its successors k and initializing e(i,k)=0 unless they are connected already and updating edge labels as e(i,k)+=e(i,j)*e(j,k) followed by removing j and all its incident edges
    • test, time, document the software and write a report including user requirements, use cases , system requirements, class model, test results, user guide, developer guide 
  • Coloring [2] (not applicable this year)


  • Welcome Email on 10.7.2021
  • Kick-off meeting on 22.7.2021 (Zoom)
  • Proposal (PDF slides to by Oct 3,2021. Presentation on Oct 7, 2021.
  • Requirements (slides) by Oct 31, 2021. Presentation on Nov 5, 2021.
  • Design (slides) by Nov 28, 2021. Presentation on Dec 3, 2021.
  • Implementation (slides; access to source repository on by Jan 2, 2022. Presentation on Jan 7, 2022.
  • Publication (PDF report) by Jan 23, 2022.
  • Final Presentation on Jan 28, 2022.