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.

Topics

• 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)

Agenda

• Welcome Email on 10.7.2021
• Kick-off meeting on 22.7.2021 (Zoom)
• Proposal (PDF slides to info@stce.rwth-aachen.de) 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 git.rwth-aachen.de) by Jan 2, 2022. Presentation on Jan 7, 2022.
• Publication (PDF report) by Jan 23, 2022.
• Final Presentation on Jan 28, 2022.