1495 lines
37 KiB
Plaintext
1495 lines
37 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "code",
|
|
"id": "initial_id",
|
|
"metadata": {
|
|
"collapsed": true,
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:34:20.291013Z",
|
|
"start_time": "2024-12-15T13:34:20.279729Z"
|
|
}
|
|
},
|
|
"source": [
|
|
"import queue\n",
|
|
"from readline import get_current_history_length\n",
|
|
"from urllib.response import addinfourl\n",
|
|
"\n",
|
|
"# -*- coding: utf-8 -*-\n",
|
|
"\"\"\"Graph module.\n",
|
|
"\n",
|
|
"Provide an implementation of graphs with adjacency lists.\n",
|
|
"\n",
|
|
"In a graph, vertices are considered numbered from 0 to the order of the graph\n",
|
|
"minus one. The vertex key can then be used to access its\n",
|
|
"adjacency list.\n",
|
|
"\n",
|
|
"\"\"\"\n",
|
|
"\n",
|
|
"\n",
|
|
"class Graph:\n",
|
|
" \"\"\" Simple class for graph: adjacency lists\n",
|
|
"\n",
|
|
" Attributes:\n",
|
|
" order (int): Number of vertices.\n",
|
|
" directed (bool): True if the graph is directed. False otherwise.\n",
|
|
" adjlists (List[List[int]]): Lists of connected vertices for each vertex.\n",
|
|
"\n",
|
|
" \"\"\"\n",
|
|
"\n",
|
|
" def __init__(self, order, directed, labels=None):\n",
|
|
" \"\"\"Init graph, allocate adjacency lists\n",
|
|
"\n",
|
|
" Args:\n",
|
|
" order (int): Number of nodes.\n",
|
|
" directed (bool): True if the graph is directed. False otherwise.\n",
|
|
" labels (list[str]): optionnal vector of vertex labels\n",
|
|
" \"\"\"\n",
|
|
"\n",
|
|
" self.order = order\n",
|
|
" self.directed = directed\n",
|
|
" self.adjlists = []\n",
|
|
" for _ in range(order):\n",
|
|
" self.adjlists.append([])\n",
|
|
" self.labels = labels\n",
|
|
"\n",
|
|
" def addedge(self, src, dst):\n",
|
|
" \"\"\"Add egde to graph.\n",
|
|
"\n",
|
|
" Args:\n",
|
|
" src (int): Source vertex.\n",
|
|
" dst (int): Destination vertex.\n",
|
|
"\n",
|
|
" Raises:\n",
|
|
" IndexError: If any vertex index is invalid.\n",
|
|
"\n",
|
|
" \"\"\"\n",
|
|
" if src >= self.order or src < 0:\n",
|
|
" raise IndexError(\"Invalid src index\")\n",
|
|
" if dst >= self.order or dst < 0:\n",
|
|
" raise IndexError(\"Invalid dst index\")\n",
|
|
"\n",
|
|
" self.adjlists[src].append(dst)\n",
|
|
" if not self.directed and dst != src:\n",
|
|
" self.adjlists[dst].append(src)\n",
|
|
"\n",
|
|
"\n",
|
|
" def addvertex(self, number=1, labels=None):\n",
|
|
" \"\"\"Add number vertices to graph.\n",
|
|
"\n",
|
|
" Args:\n",
|
|
" ref (Graph).\n",
|
|
" number (int): Number of vertices to add.\n",
|
|
"\n",
|
|
" \"\"\"\n",
|
|
"\n",
|
|
" # Increment order and extend adjacency list\n",
|
|
" self.order += number\n",
|
|
" for _ in range(number):\n",
|
|
" self.adjlists.append([])\n",
|
|
" if labels:\n",
|
|
" self.labels += labels\n",
|
|
"\n",
|
|
" def removeedge(self, src, dst):\n",
|
|
" \"\"\"Remove egde from the graph.\n",
|
|
"\n",
|
|
" Args:\n",
|
|
" src (int): Source vertex.\n",
|
|
" dst (int): Destination vertex.\n",
|
|
"\n",
|
|
" Raises:\n",
|
|
" IndexError: If any vertex index is invalid.\n",
|
|
"\n",
|
|
" \"\"\"\n",
|
|
"\n",
|
|
" if src >= self.order or src < 0:\n",
|
|
" raise IndexError(\"Invalid src index\")\n",
|
|
" if dst >= self.order or dst < 0:\n",
|
|
" raise IndexError(\"Invalid dst index\")\n",
|
|
" if dst in self.adjlists[src]:\n",
|
|
" self.adjlists[src].remove(dst)\n",
|
|
" if not self.directed and dst != src:\n",
|
|
" self.adjlists[dst].remove(src)\n",
|
|
"\n",
|
|
"def sortgraph(G):\n",
|
|
" \"\"\"\n",
|
|
" sorts adjacency lists -> to have same results as those asked in tutorials/exams\n",
|
|
" \"\"\"\n",
|
|
" for i in range(G.order):\n",
|
|
" G.adjlists[i].sort()\n",
|
|
"\n",
|
|
"def dot(G):\n",
|
|
" \"\"\"Dot format of graph.\n",
|
|
"\n",
|
|
" Args:\n",
|
|
" Graph\n",
|
|
"\n",
|
|
" Returns:\n",
|
|
" str: String storing dot format of graph.\n",
|
|
"\n",
|
|
" \"\"\"\n",
|
|
"\n",
|
|
" if G.directed:\n",
|
|
" s = \"digraph {\\n\"\n",
|
|
" for x in range(G.order):\n",
|
|
" if G.labels:\n",
|
|
" s += \" \" + str(x) + '[label = \"' + G.labels[x] + '\"]\\n'\n",
|
|
" else:\n",
|
|
" s += \" \" + str(x) + '\\n'\n",
|
|
" for y in G.adjlists[x]:\n",
|
|
" s += str(x) + \" -> \" + str(y) + '\\n'\n",
|
|
" else:\n",
|
|
" s = \"graph {\\n\"\n",
|
|
" for x in range(G.order):\n",
|
|
" if G.labels:\n",
|
|
" s += \" \" + str(x) + '[label = \"' + G.labels[x] + '\"]\\n'\n",
|
|
" else:\n",
|
|
" s += \" \" + str(x) + '\\n'\n",
|
|
" for y in G.adjlists[x]:\n",
|
|
" if x <= y:\n",
|
|
" s += str(x) + \" -- \" + str(y) + '\\n'\n",
|
|
" return s + '}'\n",
|
|
"\n",
|
|
"def display(G, eng=None):\n",
|
|
" \"\"\"\n",
|
|
" *Warning:* Made for use within IPython/Jupyter only.\n",
|
|
" eng: graphivz.Source \"engine\" optional argument (try \"neato\", \"fdp\", \"sfdp\", \"circo\")\n",
|
|
"\n",
|
|
" \"\"\"\n",
|
|
"\n",
|
|
" try:\n",
|
|
" from graphviz import Source\n",
|
|
" from IPython.display import display\n",
|
|
" except:\n",
|
|
" raise Exception(\"Missing module: graphviz and/or IPython.\")\n",
|
|
" display(Source(dot(G), engine = eng))\n",
|
|
"\n",
|
|
"\n",
|
|
"# load / save gra format\n",
|
|
"\n",
|
|
"def load(filename):\n",
|
|
" \"\"\"Build a new graph from a GRA file.\n",
|
|
"\n",
|
|
" Args:\n",
|
|
" filename (str): File to load.\n",
|
|
"\n",
|
|
" Returns:\n",
|
|
" Graph: New graph.\n",
|
|
"\n",
|
|
" Raises:\n",
|
|
" FileNotFoundError: If file does not exist.\n",
|
|
"\n",
|
|
" \"\"\"\n",
|
|
"\n",
|
|
" f = open(filename)\n",
|
|
" lines = f.readlines()\n",
|
|
" f.close()\n",
|
|
"\n",
|
|
" infos = {}\n",
|
|
" i = 0\n",
|
|
" while '#' in lines[i]:\n",
|
|
" (key, val) = lines[i][1:].strip().split(\": \")\n",
|
|
" infos[key] = val\n",
|
|
" i += 1\n",
|
|
"\n",
|
|
" directed = bool(int(lines[i]))\n",
|
|
" order = int(lines[i+1])\n",
|
|
"\n",
|
|
" if infos and \"labels\" in infos:\n",
|
|
" labels = infos[\"labels\"].split(',') #labels is a list of str\n",
|
|
" G = Graph(order, directed, labels) # a graph with labels\n",
|
|
" else:\n",
|
|
" G = Graph(order, directed) # a graph without labels\n",
|
|
" if infos:\n",
|
|
" G.infos = infos\n",
|
|
"\n",
|
|
" for line in lines[i+2:]:\n",
|
|
" edge = line.strip().split(' ')\n",
|
|
" (src, dst) = (int(edge[0]), int(edge[1]))\n",
|
|
" G.addedge(src, dst)\n",
|
|
" return G\n",
|
|
"\n",
|
|
"\n",
|
|
"def save(G, fileOut):\n",
|
|
" gra = \"\"\n",
|
|
" if G.labels:\n",
|
|
" lab = \"#labels: \"\n",
|
|
" for i in range(G.order - 1):\n",
|
|
" lab += G.labels[i] + ','\n",
|
|
" lab += G.labels[-1]\n",
|
|
" gra += lab + '\\n'\n",
|
|
" gra += str(int(G.directed)) + '\\n'\n",
|
|
" gra += str(G.order) + '\\n'\n",
|
|
" for x in range(G.order):\n",
|
|
" for y in G.adjlists[x]:\n",
|
|
" if G.directed or x >= y:\n",
|
|
" gra += str(x) + \" \" + str(y) + '\\n'\n",
|
|
" fout = open(fileOut, mode='w')\n",
|
|
" fout.write(gra)\n",
|
|
" fout.close()\n"
|
|
],
|
|
"outputs": [],
|
|
"execution_count": 2
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:34:20.415273Z",
|
|
"start_time": "2024-12-15T13:34:20.413571Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": "",
|
|
"id": "e12f5903c5348752",
|
|
"outputs": [],
|
|
"execution_count": null
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:34:20.550666Z",
|
|
"start_time": "2024-12-15T13:34:20.548054Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"# -*- coding: utf-8 -*-\n",
|
|
"\"\"\"Queue module.\"\"\"\n",
|
|
"\n",
|
|
"from collections import deque\n",
|
|
"\n",
|
|
"class Queue:\n",
|
|
" \"\"\"Simple class for FIFO (first-in-first-out) container.\"\"\"\n",
|
|
"\n",
|
|
" def __init__(self):\n",
|
|
" \"\"\"Init queue.\"\"\"\n",
|
|
"\n",
|
|
" self.elements = deque()\n",
|
|
"\n",
|
|
" def enqueue(self, elt):\n",
|
|
" \"\"\"Add an element to the queue.\n",
|
|
"\n",
|
|
" Args:\n",
|
|
" elt (Any): Element to enqueue.\n",
|
|
"\n",
|
|
" \"\"\"\n",
|
|
"\n",
|
|
" self.elements.append(elt)\n",
|
|
"\n",
|
|
" def dequeue(self):\n",
|
|
" \"\"\"Remove and return next element from the queue.\n",
|
|
"\n",
|
|
" Returns:\n",
|
|
" Any: Element from the queue.\n",
|
|
"\n",
|
|
" Raises:\n",
|
|
" IndexError: If queue is empty.\n",
|
|
"\n",
|
|
" \"\"\"\n",
|
|
"\n",
|
|
" return self.elements.popleft()\n",
|
|
"\n",
|
|
" def isempty(self):\n",
|
|
" \"\"\"Check whether queue is empty.\n",
|
|
"\n",
|
|
" Returns:\n",
|
|
" bool: True if queue is empty, False otherwise.\n",
|
|
"\n",
|
|
" \"\"\"\n",
|
|
"\n",
|
|
" return len(self.elements) == 0\n"
|
|
],
|
|
"id": "663b49e4f6763d11",
|
|
"outputs": [],
|
|
"execution_count": 3
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# Graph figure 2",
|
|
"id": "52a4e079fe9cea35"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:34:20.816394Z",
|
|
"start_time": "2024-12-15T13:34:20.814063Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"G = Graph(10, False)\n",
|
|
"G.adjlists = [[4, 4, 1, 3],\n",
|
|
" [0],\n",
|
|
" [6, 6, 6, 5, 7],\n",
|
|
" [0],\n",
|
|
" [0, 0, 9],\n",
|
|
" [2, 7, 8],\n",
|
|
" [2, 2, 2, 7],\n",
|
|
" [2, 6, 5, 8],\n",
|
|
" [7, 5, 8],\n",
|
|
" [4]]\n",
|
|
"\n"
|
|
],
|
|
"id": "ca54f5a3f1a225b",
|
|
"outputs": [],
|
|
"execution_count": 4
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:34:20.992097Z",
|
|
"start_time": "2024-12-15T13:34:20.988967Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"print(G.order)\n",
|
|
"print(G.adjlists)\n",
|
|
"print(G.adjlists[1])\n"
|
|
],
|
|
"id": "45b4722e0e0844c6",
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"10\n",
|
|
"[[4, 4, 1, 3], [0], [6, 6, 6, 5, 7], [0], [0, 0, 9], [2, 7, 8], [2, 2, 2, 7], [2, 6, 5, 8], [7, 5, 8], [4]]\n",
|
|
"[0]\n"
|
|
]
|
|
}
|
|
],
|
|
"execution_count": 5
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# Graph Figure 1",
|
|
"id": "7b374e3cdb9f773c"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:34:21.765995Z",
|
|
"start_time": "2024-12-15T13:34:21.763776Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"G1 = Graph(9, True)\n",
|
|
"G1.adjlists = [[4, 1, 1, 1, 5, 3],\n",
|
|
" [4],\n",
|
|
" [3],\n",
|
|
" [6, 6],\n",
|
|
" [],\n",
|
|
" [4, 2, 0],\n",
|
|
" [0, 5],\n",
|
|
" [8, 1, 0],\n",
|
|
" [6, 8]]\n"
|
|
],
|
|
"id": "6920c423c0bdfc24",
|
|
"outputs": [],
|
|
"execution_count": 6
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# Exercise 1.3",
|
|
"id": "313f1375b01bcce1"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:34:22.368505Z",
|
|
"start_time": "2024-12-15T13:34:22.363049Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def degrees(G):\n",
|
|
" final = []\n",
|
|
" for element in G.adjlists:\n",
|
|
" final.append(len(element))\n",
|
|
" return final\n",
|
|
"\n",
|
|
"degrees(G)"
|
|
],
|
|
"id": "55ba6e30c008762e",
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"[4, 1, 5, 1, 3, 3, 4, 4, 3, 1]"
|
|
]
|
|
},
|
|
"execution_count": 7,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"execution_count": 7
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-14T12:23:31.946802Z",
|
|
"start_time": "2024-12-14T12:23:31.943693Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def in_out_degrees(G):\n",
|
|
" In = [0] * G.order\n",
|
|
" Out = [0] * G.order\n",
|
|
" for i in range(G.order):\n",
|
|
" for element in G.adjlists[i]:\n",
|
|
" In[element] += 1\n",
|
|
" Out[i] += 1\n",
|
|
" return [In, Out]\n",
|
|
"\n",
|
|
"in_out_degrees(G1)"
|
|
],
|
|
"id": "1b1a1615d90dc209",
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"[[3, 4, 1, 2, 3, 2, 3, 0, 2], [6, 1, 1, 2, 0, 3, 2, 3, 2]]"
|
|
]
|
|
},
|
|
"execution_count": 7,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"execution_count": 7
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# Exercise 1.4",
|
|
"id": "4bd26fbd65135589"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-14T12:23:32.018541Z",
|
|
"start_time": "2024-12-14T12:23:32.015799Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def dot(G):\n",
|
|
" string = \"digraph {\\n\"\n",
|
|
" if G.directed:\n",
|
|
" for i in range(G.order):\n",
|
|
" for element in G.adjlists[i]:\n",
|
|
" string += f\"{i} --> {element}\\n\"\n",
|
|
" elif not G.directed:\n",
|
|
" for i in range(G.order):\n",
|
|
" for element in G.adjlists[i]:\n",
|
|
" string += f\"{i} -- {element}\\n\"\n",
|
|
" string += \"}\"\n",
|
|
" return string\n",
|
|
"\n",
|
|
"print(dot(G1))\n",
|
|
"print(dot(G))"
|
|
],
|
|
"id": "f7602fcf61e82a17",
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"digraph {\n",
|
|
"0 --> 4\n",
|
|
"0 --> 1\n",
|
|
"0 --> 1\n",
|
|
"0 --> 1\n",
|
|
"0 --> 5\n",
|
|
"0 --> 3\n",
|
|
"1 --> 4\n",
|
|
"2 --> 3\n",
|
|
"3 --> 6\n",
|
|
"3 --> 6\n",
|
|
"5 --> 4\n",
|
|
"5 --> 2\n",
|
|
"5 --> 0\n",
|
|
"6 --> 0\n",
|
|
"6 --> 5\n",
|
|
"7 --> 8\n",
|
|
"7 --> 1\n",
|
|
"7 --> 0\n",
|
|
"8 --> 6\n",
|
|
"8 --> 8\n",
|
|
"}\n",
|
|
"digraph {\n",
|
|
"0 -- 4\n",
|
|
"0 -- 4\n",
|
|
"0 -- 1\n",
|
|
"0 -- 3\n",
|
|
"1 -- 0\n",
|
|
"2 -- 6\n",
|
|
"2 -- 6\n",
|
|
"2 -- 6\n",
|
|
"2 -- 5\n",
|
|
"2 -- 7\n",
|
|
"3 -- 0\n",
|
|
"4 -- 0\n",
|
|
"4 -- 0\n",
|
|
"4 -- 9\n",
|
|
"5 -- 2\n",
|
|
"5 -- 7\n",
|
|
"5 -- 8\n",
|
|
"6 -- 2\n",
|
|
"6 -- 2\n",
|
|
"6 -- 2\n",
|
|
"6 -- 7\n",
|
|
"7 -- 2\n",
|
|
"7 -- 6\n",
|
|
"7 -- 5\n",
|
|
"7 -- 8\n",
|
|
"8 -- 7\n",
|
|
"8 -- 5\n",
|
|
"8 -- 8\n",
|
|
"9 -- 4\n",
|
|
"}\n"
|
|
]
|
|
}
|
|
],
|
|
"execution_count": 8
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# Exercise 2.1 (BFS)\n",
|
|
"id": "ebfdd54aefc25650"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-14T10:59:44.343779Z",
|
|
"start_time": "2024-12-14T10:59:44.337510Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def aux(G, M, src):\n",
|
|
" cur = Queue()\n",
|
|
" cur.enqueue(src)\n",
|
|
" M[src] = True\n",
|
|
" while not cur.isempty():\n",
|
|
" x = cur.dequeue()\n",
|
|
" print(x, end=\" \")\n",
|
|
" for adj in G.adjlists[x]:\n",
|
|
" if not M[adj]:\n",
|
|
" M[adj] = True\n",
|
|
" cur.enqueue(adj)\n",
|
|
"\n",
|
|
"\n",
|
|
"def dfs(G):\n",
|
|
" M = [False]*G.order\n",
|
|
" for src in range(G.order):\n",
|
|
" if not M[src]:\n",
|
|
" aux(G, M, src)\n",
|
|
" print()\n",
|
|
"BFS(G)"
|
|
],
|
|
"id": "b8bf6413a1d63515",
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"0 4 1 3 9 \n",
|
|
"2 6 5 7 8 \n"
|
|
]
|
|
}
|
|
],
|
|
"execution_count": 20
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# Exercise 2.2 (DFS)",
|
|
"id": "55b1247fe428aa0d"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-14T11:01:46.103932Z",
|
|
"start_time": "2024-12-14T11:01:46.101045Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def auxDFS(G, M, src):\n",
|
|
" M[src] = True\n",
|
|
" print(src, end=\" \")\n",
|
|
" for adj in G.adjlists[src]:\n",
|
|
" if not M[adj]:\n",
|
|
" auxDFS(G, M, adj)\n",
|
|
"\n",
|
|
"def DFS(G):\n",
|
|
" M = [False] * G.order\n",
|
|
" for src in range(G.order):\n",
|
|
" if not M[src]:\n",
|
|
" aux(G, M, src)\n",
|
|
" print()\n",
|
|
"DFS(G)"
|
|
],
|
|
"id": "507b403020a6f941",
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"0 4 1 3 9 \n",
|
|
"2 6 5 7 8 \n"
|
|
]
|
|
}
|
|
],
|
|
"execution_count": 23
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# Exercise 3.1 (Connect)",
|
|
"id": "a30c671c43131bb2"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-09T15:03:14.627181Z",
|
|
"start_time": "2024-12-09T15:03:14.622512Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def __components(G, M, src, nbComponents):\n",
|
|
" M[src] = nbComponents\n",
|
|
" for adj in G.adjlists[src]:\n",
|
|
" if not M[adj]:\n",
|
|
" M[adj] = nbComponents\n",
|
|
" __components(G, M, adj, nbComponents)\n",
|
|
"\n",
|
|
"def components(G):\n",
|
|
" M = [False] * G.order\n",
|
|
" nbComponents = 0\n",
|
|
" for src in range(G.order):\n",
|
|
" if not M[src]:\n",
|
|
" nbComponents += 1\n",
|
|
" __components(G, M, src, nbComponents)\n",
|
|
" return (nbComponents, M)\n",
|
|
"\n",
|
|
"components(G)\n"
|
|
],
|
|
"id": "b8b8a6ec16fc88a5",
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"(2, [1, 1, 2, 1, 1, 2, 2, 2, 2, 1])"
|
|
]
|
|
},
|
|
"execution_count": 16,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"execution_count": 16
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# Exercise 3.2 (That's the way)",
|
|
"id": "dae9cdccb36ac9d5"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-09T15:09:02.024738Z",
|
|
"start_time": "2024-12-09T15:09:02.020400Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def __path(G, src, dst, M, path):\n",
|
|
" M[src] = True\n",
|
|
" for adj in G.adjlists[src]:\n",
|
|
" if not M[src]:\n",
|
|
" if adj == dst or __path(G, src, dst, M, path):\n",
|
|
" path.append(adj)\n",
|
|
" return True\n",
|
|
" return False\n",
|
|
"\n",
|
|
"def path(G, src, dst):\n",
|
|
" M = [False] * G.order\n",
|
|
" path = []\n",
|
|
" if __path(G, src, dst, M, path):\n",
|
|
" path.append(src)\n",
|
|
" path.reverse()\n",
|
|
" return path\n",
|
|
"\n",
|
|
"path(G, 0, 9)"
|
|
],
|
|
"id": "67b1808a9c9996e1",
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"[]"
|
|
]
|
|
},
|
|
"execution_count": 26,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"execution_count": 26
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "",
|
|
"id": "9b679ab534f329fb"
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "code",
|
|
"outputs": [],
|
|
"execution_count": null,
|
|
"source": "",
|
|
"id": "71f4c39123fe94c1"
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# 2025 - Exercise 1",
|
|
"id": "b67ef07f6d7c99b0"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-14T12:50:54.278706Z",
|
|
"start_time": "2024-12-14T12:50:54.271435Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def aux_colors(G, M, src):\n",
|
|
" new_color = not M[src]\n",
|
|
" for adj in G.adjlists[src]:\n",
|
|
" if M[adj] == None:\n",
|
|
" M[adj] = new_color\n",
|
|
" if not aux_colors(G, M, adj):\n",
|
|
" return False\n",
|
|
" else:\n",
|
|
" if M[adj] != new_color:\n",
|
|
" return False\n",
|
|
" return True\n",
|
|
"\n",
|
|
"\n",
|
|
"def two_coloring(G):\n",
|
|
" M = [None] * G.order\n",
|
|
" for src in range(G.order):\n",
|
|
" if M[src] == None:\n",
|
|
" M[src] = True\n",
|
|
" if not aux_colors(G, M, src):\n",
|
|
" return False\n",
|
|
" return True\n",
|
|
"\n",
|
|
"two_coloring(G1)"
|
|
],
|
|
"id": "9ed534351df71362",
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"False"
|
|
]
|
|
},
|
|
"execution_count": 26,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"execution_count": 26
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# 2025 - Exercise 2",
|
|
"id": "38c3d4e952147c50"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-09T16:08:14.367172Z",
|
|
"start_time": "2024-12-09T16:08:14.361769Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def __fakenews(G, M, src, fake):\n",
|
|
" q = Queue()\n",
|
|
" q.enqueue(src)\n",
|
|
" stop = False\n",
|
|
" while not q.isempty() and not stop:\n",
|
|
" x = q.dequeue()\n",
|
|
" if M[x] > fake:\n",
|
|
" for adj in G.adjlists[x]:\n",
|
|
" if M[adj] == None:\n",
|
|
" M[adj] = M[x] - 1\n",
|
|
" q.enqueue(adj)\n",
|
|
" else:\n",
|
|
" stop = True\n",
|
|
"\n",
|
|
"def fakenews(G, src, truth):\n",
|
|
" M = [None] * G.order\n",
|
|
" M[src] = truth\n",
|
|
" __fakenews(G, M, src, truth//2)\n",
|
|
" L = []\n",
|
|
" for s in range(G.order):\n",
|
|
" if M[s] == None:\n",
|
|
" L.append(s)\n",
|
|
" return L"
|
|
],
|
|
"id": "c66ac4688a6975c9",
|
|
"outputs": [],
|
|
"execution_count": 34
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# 2027 - Exercice 2",
|
|
"id": "b8fa23568b4bd3df"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-14T12:27:17.971319Z",
|
|
"start_time": "2024-12-14T12:27:17.967991Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"# Reconstitution du graph du partiel\n",
|
|
"# Initialisation d'un graphe non orienté avec 10 sommets\n",
|
|
"G = Graph(order=10, directed=False)\n",
|
|
"\n",
|
|
"# Ajout des arêtes selon l'image fournie\n",
|
|
"G.addedge(0, 1)\n",
|
|
"G.addedge(0, 2)\n",
|
|
"G.addedge(0, 8)\n",
|
|
"G.addedge(0, 6)\n",
|
|
"G.addedge(1, 2)\n",
|
|
"G.addedge(1, 3)\n",
|
|
"G.addedge(2, 3)\n",
|
|
"G.addedge(2, 8)\n",
|
|
"G.addedge(3, 5)\n",
|
|
"G.addedge(3, 6)\n",
|
|
"G.addedge(4, 5)\n",
|
|
"G.addedge(5, 7)\n",
|
|
"G.addedge(6, 9)\n",
|
|
"G.addedge(7, 9)\n",
|
|
"G.addedge(8, 9)\n",
|
|
"\n",
|
|
"# Tri des listes d'adjacence pour une sortie cohérente\n",
|
|
"sortgraph(G)\n",
|
|
"\n",
|
|
"# Affichage du graphe au format DOT (si tu as graphviz configuré)\n",
|
|
"print(dot(G))\n",
|
|
"\n",
|
|
"# Affichage visuel dans Jupyter Notebook (optionnel)\n",
|
|
"# display(G, eng=\"neato\") # Utilise l'option \"neato\" pour une disposition automatique"
|
|
],
|
|
"id": "f3f003f5ecd72f9e",
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"digraph {\n",
|
|
"0 -- 1\n",
|
|
"0 -- 2\n",
|
|
"0 -- 6\n",
|
|
"0 -- 8\n",
|
|
"1 -- 0\n",
|
|
"1 -- 2\n",
|
|
"1 -- 3\n",
|
|
"2 -- 0\n",
|
|
"2 -- 1\n",
|
|
"2 -- 3\n",
|
|
"2 -- 8\n",
|
|
"3 -- 1\n",
|
|
"3 -- 2\n",
|
|
"3 -- 5\n",
|
|
"3 -- 6\n",
|
|
"4 -- 5\n",
|
|
"5 -- 3\n",
|
|
"5 -- 4\n",
|
|
"5 -- 7\n",
|
|
"6 -- 0\n",
|
|
"6 -- 3\n",
|
|
"6 -- 9\n",
|
|
"7 -- 5\n",
|
|
"7 -- 9\n",
|
|
"8 -- 0\n",
|
|
"8 -- 2\n",
|
|
"8 -- 9\n",
|
|
"9 -- 6\n",
|
|
"9 -- 7\n",
|
|
"9 -- 8\n",
|
|
"}\n"
|
|
]
|
|
}
|
|
],
|
|
"execution_count": 15
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-14T12:42:59.642392Z",
|
|
"start_time": "2024-12-14T12:42:59.636696Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"\"\"\"\n",
|
|
"def __smallest_level(G, M, src, perLevel):\n",
|
|
" cur = Queue()\n",
|
|
" cur.enqueue(src)\n",
|
|
" cur.enqueue(None)\n",
|
|
" M[src] = True\n",
|
|
" temp = []\n",
|
|
" while not cur.isempty():\n",
|
|
" x = cur.dequeue()\n",
|
|
" if x is None:\n",
|
|
" if (len(temp) != 0 and temp != [src]):\n",
|
|
" perLevel.append(temp)\n",
|
|
" temp = []\n",
|
|
" else:\n",
|
|
" temp.append(x)\n",
|
|
" for adj in G.adjlists[x]:\n",
|
|
" if not M[adj]:\n",
|
|
" M[adj] = True\n",
|
|
" cur.enqueue(adj)\n",
|
|
" cur.enqueue(None)\n",
|
|
"\n",
|
|
"def smallest_level(G, src):\n",
|
|
" M = [False] * G.order\n",
|
|
" perLevel = []\n",
|
|
" __smallest_level(G, M, src, perLevel)\n",
|
|
" min = perLevel[0]\n",
|
|
" for element in perLevel:\n",
|
|
" if len(element) < len(min):\n",
|
|
" min = element\n",
|
|
" return min\n",
|
|
"\"\"\"\n",
|
|
"\n",
|
|
"def smallest(G, src):\n",
|
|
" dist = [None] * G.order\n",
|
|
" q = Queue()\n",
|
|
" q.enqueue(src)\n",
|
|
" dist[src] = 0\n",
|
|
" small = G.order\n",
|
|
" d = 0\n",
|
|
" L = []\n",
|
|
" while not q.isempty():\n",
|
|
" x = q.dequeue()\n",
|
|
" if dist[x] > d:\n",
|
|
" if len(L) < small:\n",
|
|
" small = len(L)\n",
|
|
" Res = L\n",
|
|
" d += 1\n",
|
|
" L = []\n",
|
|
" for y in G.adjlists[x]:\n",
|
|
" if dist[y] == None:\n",
|
|
" dist[y] = dist[x] + 1\n",
|
|
" q.enqueue(y)\n",
|
|
" L.append(y)\n",
|
|
" return Res"
|
|
],
|
|
"id": "9a3a85d15dccbb97",
|
|
"outputs": [],
|
|
"execution_count": 23
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-14T12:43:03.858284Z",
|
|
"start_time": "2024-12-14T12:43:03.855864Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"for s in range(10):\n",
|
|
" print(s, \"=>\", smallest(G, s))"
|
|
],
|
|
"id": "5be240ac4da2b002",
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"0 => [4]\n",
|
|
"1 => [0, 2, 3]\n",
|
|
"2 => [4, 7]\n",
|
|
"3 => [1, 2, 5, 6]\n",
|
|
"4 => [5]\n",
|
|
"5 => [0, 8]\n",
|
|
"6 => [4]\n",
|
|
"7 => [5, 9]\n",
|
|
"8 => [5]\n",
|
|
"9 => [1, 4]\n"
|
|
]
|
|
}
|
|
],
|
|
"execution_count": 24
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# 2024 - Exercise 3",
|
|
"id": "fc95daf0e8cb39e6"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:34:27.890752Z",
|
|
"start_time": "2024-12-15T13:34:27.886850Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"# Reconstitution du graph du partiel\n",
|
|
"# Initialisation d'un graphe non orienté avec 10 sommets\n",
|
|
"G = Graph(order=12, directed=True)\n",
|
|
"\n",
|
|
"# Ajout des arêtes selon l'image fournie\n",
|
|
"G.addedge(0, 1)\n",
|
|
"G.addedge(0, 2)\n",
|
|
"G.addedge(0, 3)\n",
|
|
"G.addedge(0, 6)\n",
|
|
"G.addedge(1, 4)\n",
|
|
"G.addedge(2,4)\n",
|
|
"G.addedge(2, 5)\n",
|
|
"G.addedge(11, 5)\n",
|
|
"G.addedge(3, 6)\n",
|
|
"G.addedge(4, 7)\n",
|
|
"G.addedge(5, 8)\n",
|
|
"G.addedge(6, 9)\n",
|
|
"G.addedge(7, 10)\n",
|
|
"G.addedge(8, 7)\n",
|
|
"G.addedge(8,10)\n",
|
|
"G.addedge(9, 8)\n",
|
|
"G.addedge(9, 10)\n",
|
|
"\n",
|
|
"# Tri des listes d'adjacence pour une sortie cohérente\n",
|
|
"sortgraph(G)\n",
|
|
"\n",
|
|
"# Affichage du graphe au format DOT (si tu as graphviz configuré)\n",
|
|
"print(dot(G))\n",
|
|
"\n",
|
|
"# Affichage visuel dans Jupyter Notebook (optionnel)\n",
|
|
"# display(G, eng=\"neato\") # Utilise l'option \"neato\" pour une disposition automatique"
|
|
],
|
|
"id": "9fa8bd36f36fbdde",
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"digraph {\n",
|
|
" 0\n",
|
|
"0 -> 1\n",
|
|
"0 -> 2\n",
|
|
"0 -> 3\n",
|
|
"0 -> 6\n",
|
|
" 1\n",
|
|
"1 -> 4\n",
|
|
" 2\n",
|
|
"2 -> 4\n",
|
|
"2 -> 5\n",
|
|
" 3\n",
|
|
"3 -> 6\n",
|
|
" 4\n",
|
|
"4 -> 7\n",
|
|
" 5\n",
|
|
"5 -> 8\n",
|
|
" 6\n",
|
|
"6 -> 9\n",
|
|
" 7\n",
|
|
"7 -> 10\n",
|
|
" 8\n",
|
|
"8 -> 7\n",
|
|
"8 -> 10\n",
|
|
" 9\n",
|
|
"9 -> 8\n",
|
|
"9 -> 10\n",
|
|
" 10\n",
|
|
" 11\n",
|
|
"11 -> 5\n",
|
|
"}\n"
|
|
]
|
|
}
|
|
],
|
|
"execution_count": 8
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:49:16.391524Z",
|
|
"start_time": "2024-12-15T13:49:16.385573Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def __dist_range(G, M, src):\n",
|
|
" cur = Queue()\n",
|
|
" cur.enqueue(src)\n",
|
|
" d = 0\n",
|
|
" while not cur.isempty():\n",
|
|
" x = cur.dequeue()\n",
|
|
" if M[x] > d:\n",
|
|
" d += 1\n",
|
|
" for adj in G.adjlists[x]:\n",
|
|
" if M[adj] == None:\n",
|
|
" M[adj] = M[x] + 1\n",
|
|
" cur.enqueue(adj)\n",
|
|
"def dist_ragen(G, src, dmin, dmax):\n",
|
|
" M = [None] * G.order\n",
|
|
" result = []\n",
|
|
" M[src] = 0\n",
|
|
" __dist_range(G, M, src)\n",
|
|
" for i in range(len(M)):\n",
|
|
" if (M[i] != None) and dmin <= M[i] <= dmax:\n",
|
|
" result.append(i)\n",
|
|
" return result\n",
|
|
"\n",
|
|
"dist_ragen(G, 0, 2, 3)"
|
|
],
|
|
"id": "40afbf22ad096b78",
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"[4, 5, 7, 8, 9, 10]"
|
|
]
|
|
},
|
|
"execution_count": 28,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"execution_count": 28
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:47:27.002306Z",
|
|
"start_time": "2024-12-15T13:47:26.997672Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def amaurypasbo(G, src, dmin, dmax):\n",
|
|
" q = Queue()\n",
|
|
" q.enqueue(src)\n",
|
|
" L = []\n",
|
|
" dist = [None] * G.order\n",
|
|
" dist[src] = 0\n",
|
|
" while not q.isempty():\n",
|
|
" x = q.dequeue()\n",
|
|
" if dist[x] >= dmin:\n",
|
|
" L.append(x)\n",
|
|
" if dist[x] < dmax:\n",
|
|
" for y in G.adjlists[x]:\n",
|
|
" if dist[y] is None:\n",
|
|
" dist[y] = dist[x] + 1\n",
|
|
" q.enqueue(y)\n",
|
|
" return L\n",
|
|
"amaurypasbo(G, 0, 2, 3)"
|
|
],
|
|
"id": "6d6b88841d1c89e",
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"[4, 5, 9, 7, 8, 10]"
|
|
]
|
|
},
|
|
"execution_count": 27,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"execution_count": 27
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T13:50:09.757608Z",
|
|
"start_time": "2024-12-15T13:50:09.754120Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"import time\n",
|
|
"start = time.time()\n",
|
|
"dist_ragen(G, 0, 2, 3)\n",
|
|
"end = time.time()\n",
|
|
"print(f\"Elapsed time for Louis: {end-start}ms\")\n",
|
|
"\n",
|
|
"start = time.time()\n",
|
|
"amaurypasbo(G, 0, 2, 3)\n",
|
|
"end = time.time()\n",
|
|
"print(f\"Elapsed time for Amaury pas bô: {end-start}ms\")"
|
|
],
|
|
"id": "29ee33a593dd1896",
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"Elapsed time for Louis: 5.5789947509765625e-05ms\n",
|
|
"Elapsed time for Amaury pas bô: 4.100799560546875e-05ms\n"
|
|
]
|
|
}
|
|
],
|
|
"execution_count": 29
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "markdown",
|
|
"source": "# 2024 - Exercise 4",
|
|
"id": "5c9033d8eb1154a5"
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T14:03:30.413537Z",
|
|
"start_time": "2024-12-15T14:03:30.410183Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"# Reconstitution du graph du partiel\n",
|
|
"# Initialisation d'un graphe non orienté avec 10 sommets\n",
|
|
"G = Graph(order=10, directed=False)\n",
|
|
"\n",
|
|
"# Ajout des arêtes selon l'image fournie\n",
|
|
"G.addedge(0, 1)\n",
|
|
"G.addedge(0, 8)\n",
|
|
"G.addedge(1,3)\n",
|
|
"G.addedge(1,2)\n",
|
|
"G.addedge(2,3)\n",
|
|
"G.addedge(2,8)\n",
|
|
"G.addedge(8,6)\n",
|
|
"G.addedge(8,9)\n",
|
|
"G.addedge(3,4)\n",
|
|
"G.addedge(3,5)\n",
|
|
"G.addedge(3,6)\n",
|
|
"G.addedge(6,9)\n",
|
|
"G.addedge(9,7)\n",
|
|
"G.addedge(4,5)\n",
|
|
"G.addedge(5,7)\n",
|
|
"\n",
|
|
"# Tri des listes d'adjacence pour une sortie cohérente\n",
|
|
"sortgraph(G)\n",
|
|
"\n",
|
|
"# Affichage du graphe au format DOT (si tu as graphviz configuré)\n",
|
|
"print(dot(G))\n",
|
|
"\n",
|
|
"# Affichage visuel dans Jupyter Notebook (optionnel)\n",
|
|
"# display(G, eng=\"neato\") # Utilise l'option \"neato\" pour une disposition automatique"
|
|
],
|
|
"id": "5cb5a950e355b0e2",
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"graph {\n",
|
|
" 0\n",
|
|
"0 -- 1\n",
|
|
"0 -- 8\n",
|
|
" 1\n",
|
|
"1 -- 2\n",
|
|
"1 -- 3\n",
|
|
" 2\n",
|
|
"2 -- 3\n",
|
|
"2 -- 8\n",
|
|
" 3\n",
|
|
"3 -- 4\n",
|
|
"3 -- 5\n",
|
|
"3 -- 6\n",
|
|
" 4\n",
|
|
"4 -- 5\n",
|
|
" 5\n",
|
|
"5 -- 7\n",
|
|
" 6\n",
|
|
"6 -- 8\n",
|
|
"6 -- 9\n",
|
|
" 7\n",
|
|
"7 -- 9\n",
|
|
" 8\n",
|
|
"8 -- 9\n",
|
|
" 9\n",
|
|
"}\n"
|
|
]
|
|
}
|
|
],
|
|
"execution_count": 30
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T14:36:40.935741Z",
|
|
"start_time": "2024-12-15T14:36:40.929196Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def __get_cycle(G, x, parent):\n",
|
|
" for y in G.adjlists [x]:\n",
|
|
" if parent[y] == None:\n",
|
|
" parent [y] = x\n",
|
|
" get = __get_cycle(G, y, parent)\n",
|
|
" if get != None:\n",
|
|
" return get\n",
|
|
" else:\n",
|
|
" if y != parent [x]:\n",
|
|
" return (x, y)\n",
|
|
" return None\n",
|
|
"\n",
|
|
"def get_cycle(G):\n",
|
|
" parent = [None] * G. order\n",
|
|
" s = 0\n",
|
|
" get = None\n",
|
|
" while s < G.order and get == None:\n",
|
|
" if parent[s] == None:\n",
|
|
" parent[s] = -1\n",
|
|
" get = __get_cycle(G, s, parent)\n",
|
|
" s += 1\n",
|
|
" L = []\n",
|
|
" if get != None:\n",
|
|
" (x, y) = get\n",
|
|
" L = [x]\n",
|
|
" while x != y:\n",
|
|
" x = parent[x]\n",
|
|
" L.append(x)\n",
|
|
" L.append(L[0])\n",
|
|
" return L\n",
|
|
"\n",
|
|
"get_cycle(G)"
|
|
],
|
|
"id": "d1736b826cb4a92",
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"[3, 2, 1, 3]"
|
|
]
|
|
},
|
|
"execution_count": 53,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"execution_count": 53
|
|
},
|
|
{
|
|
"metadata": {
|
|
"ExecuteTime": {
|
|
"end_time": "2024-12-15T14:14:21.270509Z",
|
|
"start_time": "2024-12-15T14:14:21.263983Z"
|
|
}
|
|
},
|
|
"cell_type": "code",
|
|
"source": [
|
|
"def __amaurycycle(G, src, M, L, P):\n",
|
|
" for y in G.adjlists[src]:\n",
|
|
" if M[y] == True and P[y] != src:\n",
|
|
" L.append(y)\n",
|
|
" return True\n",
|
|
" else:\n",
|
|
" L.append(y)\n",
|
|
" M[y] = True\n",
|
|
" P[y] = src\n",
|
|
" if __amaurycycle(G, y, M, L, P):\n",
|
|
" return True\n",
|
|
" return False\n",
|
|
"\n",
|
|
"def amaurycycle(G):\n",
|
|
" M = [False] * G.order\n",
|
|
" P = [None] * G.order\n",
|
|
" L = []\n",
|
|
" for x in range(G.order):\n",
|
|
" print(x)\n",
|
|
" if not M[x]:\n",
|
|
" M[x] = True\n",
|
|
"\n",
|
|
" if __amaurycycle(G, x, M, L, P):\n",
|
|
" return L\n",
|
|
" L = []\n",
|
|
" return L\n",
|
|
"\n",
|
|
"amaurycycle(G)\n"
|
|
],
|
|
"id": "1ba0708151f432e2",
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"0\n"
|
|
]
|
|
},
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"[1, 0]"
|
|
]
|
|
},
|
|
"execution_count": 47,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"execution_count": 47
|
|
},
|
|
{
|
|
"metadata": {},
|
|
"cell_type": "code",
|
|
"outputs": [],
|
|
"execution_count": null,
|
|
"source": "",
|
|
"id": "d17cd6bd32656bbd"
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "Python 3",
|
|
"language": "python",
|
|
"name": "python3"
|
|
},
|
|
"language_info": {
|
|
"codemirror_mode": {
|
|
"name": "ipython",
|
|
"version": 2
|
|
},
|
|
"file_extension": ".py",
|
|
"mimetype": "text/x-python",
|
|
"name": "python",
|
|
"nbconvert_exporter": "python",
|
|
"pygments_lexer": "ipython2",
|
|
"version": "2.7.6"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|