{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP2 (Student version)\n"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"import sys"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Consider the following test graphs:\n",
"- http://snap.stanford.edu/data/email-Eu-core.html\n",
"- http://snap.stanford.edu/data/com-Amazon.html\n",
"- http://snap.stanford.edu/data/com-LiveJournal.html\n",
"- http://snap.stanford.edu/data/com-Orkut.html\n",
"- (https://snap.stanford.edu/data/com-Friendster.html)\n",
"\n",
"It can also be usefull to consider some toy graphs (e.g. manually created graphs with a dozen nodes) to test your programs."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 1: BFS\n",
"\n",
"Implement an efficient BFS algorithm and test it on the four graphs. \n",
"Use your BFS implementation to compute a good lower (and upper) bound to the diameter of a graph.\n",
"Test your program on the 4 downloaded graphs and for each one of them report the lower bound you have found as well as the running time of your program."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 2: Triangles\n",
"\n",
"Implement an efficient algorithm for counting triangles. Test your program on the 4 downloaded graphs and report the number of triangles as well as the running time of your program.\n",
"\n",
"Generalize your program to compute the transitivity ratio and the clustering of the graph. Test your program on the 4 downloaded graphs and report the two values as well as the running time of your program."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 3 (bonus): Bron-Kerbosch\n",
"\n",
"Implement an efficient Bron-Kerbosch algorithm following the wikipedia pseudocode: https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm. Test your program on the 4 graphs.\n",
"Report the number of maximal cliques for each graphs as well as the running time of your program."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Plot the number of maximal cliques of size k (for k from 1 to the size of a maximum clique) as a function of k for each graph."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}