General outline of the work done and remaining to be done during the project.

1. Literature

  • Find relevant algorithms
  • Look into graph transformations to make it easier to use existing algorithms

2. Framework implementation

  • Generate test CPQs (gMark)
  • Compute the query graph of CPQs
  • Compute the core of the query graphs (technically not strictly required)
  • Transform the query graphs to a suitable input for each algorithm
    • Algorithm(s) for digraph -> graph
    • Algorithm(s) for edge labelled -> edge unlabelled
    • Possibly others for parallel edges, self loops

3. Algorithm implementation

Only listing canonization algorithms for now:

Done Algorithm Info Form Difficulty
Yes Scott Good Codebase No major issues expected
Yes nauty Very good Codebase Possibly linking difficulties
Yes traces Very good Codebase Possibly linking difficulties
Yes bliss Fine Codebase Limited documentation
Skip Arnborg et al. Very good Textual description Seems straightforward1
Skip Grohe et al. Limited High level proof Very difficult
Skip Arvind et al. Okay Proof sketch Maybe okay
Skip Wiebking Complex Proofs & math Extremely difficult
Yes nishe Little Codebase Probably fine
  1. If we try to extend or make a second version of this algorithm that natively handles directed edge labelled graphs, more time is probably required.

4. Reporting

  • Evaluate the algorithms (focus on determining the most suitable candidate for CPQ keys)
  • Write the final report

Timeline

Times are in hours, internship target is 15 ECTS or 420 hours.

Week Days Target Spent Comment
2022-04-25 2 16 15.3 Planning & literature research
2022-05-02 3 40 54.1 Literature research, finding existing canonization algorithms, Seiji’s notes, treewidth terms
2022-05-09 5 80 93.8 Graph transform research, investigate existing algorithms
2022-05-16 5 120 136.0 Literature research, investigating existing algorithms, implementation (query graph)
2022-05-23 3 144 168.3 Implementation of graph transforms and algorithms (nauty, traces, nishe)
2022-05-30 5 184 206.8 Implementation of graph transforms and algorithms (nauty, traces, nishe, unlabelled transform)
2022-06-06 4 216 245.3 Implementation of graph transforms and algorithms (nauty, traces, nishe, bliss, scott, core logic)
2022-06-13 5 256 286.3 Finish the implementation
2022-06-20 5 296 325.2 Report
2022-06-27 5 336 368.6 Report & data collection
2022-07-04 5 376 414.1 Report
2022-07-11 5 416 462.4 Finish
2022-07-18 5 456 - Reserve