Purpose

The program finds maximal clique of each input graph, plus a maximal common induced subgraph of all input graphs. More information available in the report.

How to compile

Adjacency matrix variant

gcc main.c -o main

Adjacency list variant DEPRECATED!

gcc adjlist.c -o main

How to run with example file

./main input/example.txt

main.exe input/example.txt

If You want to see debug information

Add #define dbg to the start of the main.c

If You want to print the results of the program to the console.

Add #define PRINTTOCMD to the beginning of the main.c. Regardless of that, program saves the output to output.txt file.

TODO

• Write data parsing from file in agreed format.
• Implement the representation of graphs in a form of adjacency list.
• Write a function to find a modular product of matrices.
• Write a function to find maximal cliques of matrices (Bronn Kerbosch probably).
• Write a function to find maximum common induced subgraph.
• Add time measurments inside the program.
• Support for multiple input files.
• Fix GH leak, and improper node removal.
• Switch Bron Kerbosch to iterative approach instead (recursion causes stack overflow for large graphs).
• OPTIONAL: Test the product function against some example online.
• OPTIONAL: Implement Adjacency Matrix implementation to improve time complexity at the cost of space complexity.
• OPTIONAL: Add pivoting to iterative Bron Kerbosch.
• It was also said that if the algorithm used is exponential then we should find a polynomial approximation algorithm also. It should be checked if the results are isomoprhpic to subgraphs in original graphs.
• The result of maximum common subgraph is not entirely correct I think. It whould be mapped to vertices of original graphs and for multigraphs it should be somehow checked if weights are the same.
• Add backtracking to current search for maximum common subgraph.
• Add isomorphism check for multigraphs.
• Modify approximating. It might happen that no maximum subgraph will be found, even tho there is one. To fix it, if none found from current maximum clique, find another maximum clique. To do that: remove found clique from target graphs, and find a maximum clique again.
• Optimise the code, for example when mapping a maximum clique onto one of the graphs, could we just choose the smaller one?
• Handle isomorphism during approximation? But then the approximation might quite often fail.
• OPTIONAL: Do the above three steps for adjacency list also.
• Prepare some example data (reasonable amount). Preferably with known answers to cross-check.
• Run tests, time it to put something to docs.
• OPTIONAL: Check and prepare for edge cases, such as empty graph description, vertex with no edges.
• OPTIONAL: Find a way to measure maximal memory usage.

Possible improvements

• Add a progress bar in a form of a list.
• If let's say graphs can have the edge weight of no more than 256 then instead of using int we could use int8_t to cut down memory usage by around 40%.
• Improve size data type, size_t instead of int should be used and proper casting should be added.