maximum cliques using sql
Budget: $250 – $750 USD
program to generate SQL queries to analyze any input graph given in a table. Detecting top (maximal) cliques embedded in the graph. Assume there is a maximum clique size treshold k. Assume the graph is undirected. you are expected to solve them the best way you can, documenting your programming decisions and theory assumptions. You will soon realize you need recursion depth or maximum clique size.
A graph is defined as G = {V, E} where V is a set of vertices or nodes and E is a set of edges between the
nodes. G can be undirected. Each edge has a distance v (weight/cost) associated with it. The graph will be stored in edge list form in a table E(i, j, v), where each row is a triple. Therefore, it is necessary to insert the ”back” edge, in the opposite direction. Keep in mind different tables may be have different vertex column names (not necessarily i, j, v). and more columns than needed.
clique: a table listing maximal cliques, numbered as they are detected (and filtered).
For clique detection you should display the table name where you store all cliques in a vertical layout.
Alternatively, you can store cliques in multiple tables of cliques of different size (size 3,4 .. k).
Verification: you should verify your results are correct with small graphs (say n ≤ 10). You can optionally
use some graph library (C++, Python) to verify SQL results are correct.
• Both graph problems are related to the Transitive Closure of the graph G*, i.e. iteratively calculate an
adjacency matrix multiplication as explained in [1, 2].
• Assume there is a maximum path length up to k ≤ 10 edges (max. recursion depth) as a parameter. This
parameter is necessary to make the problem tractable.
• The program should not halt when encountering errors. It should just send a message to the log file and
continue with the next line. The only error that is unrecoverable is a missing input table, bad column
names.
A graph is defined as G = {V, E} where V is a set of vertices or nodes and E is a set of edges between the
nodes. G can be undirected. Each edge has a distance v (weight/cost) associated with it. The graph will be stored in edge list form in a table E(i, j, v), where each row is a triple. Therefore, it is necessary to insert the ”back” edge, in the opposite direction. Keep in mind different tables may be have different vertex column names (not necessarily i, j, v). and more columns than needed.
clique: a table listing maximal cliques, numbered as they are detected (and filtered).
For clique detection you should display the table name where you store all cliques in a vertical layout.
Alternatively, you can store cliques in multiple tables of cliques of different size (size 3,4 .. k).
Verification: you should verify your results are correct with small graphs (say n ≤ 10). You can optionally
use some graph library (C++, Python) to verify SQL results are correct.
• Both graph problems are related to the Transitive Closure of the graph G*, i.e. iteratively calculate an
adjacency matrix multiplication as explained in [1, 2].
• Assume there is a maximum path length up to k ≤ 10 edges (max. recursion depth) as a parameter. This
parameter is necessary to make the problem tractable.
• The program should not halt when encountering errors. It should just send a message to the log file and
continue with the next line. The only error that is unrecoverable is a missing input table, bad column
names.