# Roadmap

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 straightforward^{1} |

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 |

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