489 lines
14 KiB
Plaintext
489 lines
14 KiB
Plaintext
{
|
||
"cells": [
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 78,
|
||
"metadata": {},
|
||
"outputs": [],
|
||
"source": [
|
||
"# matrices from the document\n",
|
||
"R1 = [[1,0,1],[0,1,0],[1,0,0]]\n",
|
||
"R2 = [[1,1,0],[0,0,1],[1,0,1]]\n",
|
||
"R3 = [[1, 1, 1], [0, 0, 1], [0, 0, 1]]\n",
|
||
"R4 = [[1, 1, 0, 1], [1, 1, 0, 1], [0, 0, 1, 0], [1, 1, 0, 1]]\n",
|
||
"R5 = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]\n",
|
||
"R6 = [[1, 1, 1], [0, 0, 1], [1, 0, 0]]\n",
|
||
"\n",
|
||
"tests = [R1, R2, R3, R4, R5, R6]\n",
|
||
"\n",
|
||
"CHAMPIONS = [[1,1,0,1,1],\n",
|
||
" [0,1,0,0,0],\n",
|
||
" [1,1,1,1,1],\n",
|
||
" [1,1,0,1,1],\n",
|
||
" [0,1,0,0,1]]"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 79,
|
||
"metadata": {},
|
||
"outputs": [],
|
||
"source": [
|
||
"# Check if a matrix is reflexive\n",
|
||
"def reflexive(R):\n",
|
||
" for i in range(len(R)):\n",
|
||
" if R[i][i] != 1:\n",
|
||
" return False\n",
|
||
" return True\n",
|
||
"\n",
|
||
"# Check if a matrix is symmetric\n",
|
||
"def symmetrical(R):\n",
|
||
" for i in range(len(R)):\n",
|
||
" for j in range(len(R)):\n",
|
||
" if R[i][j] != R[j][i]:\n",
|
||
" return False\n",
|
||
" return True\n",
|
||
"\n",
|
||
"# Check if a matrix is anti-symmetric\n",
|
||
"def anti_symmetrical(R):\n",
|
||
" for i in range(len(R)):\n",
|
||
" for j in range(len(R)):\n",
|
||
" if R[i][j] > 0 and R[j][i] > 0 and i != j:\n",
|
||
" return False\n",
|
||
" return True\n",
|
||
"\n",
|
||
"# Check if a matrix is asymmetrical\n",
|
||
"def asymmetrical(R):\n",
|
||
" for i in range(len(R)):\n",
|
||
" for j in range(len(R)):\n",
|
||
" if R[i][j] > 0 and R[j][i] > 0:\n",
|
||
" return False\n",
|
||
" return True\n",
|
||
"\n",
|
||
"# Check if a matrix is irreflexive\n",
|
||
"def irreflexive(R):\n",
|
||
" for i in range(len(R)):\n",
|
||
" if R[i][i] > 0:\n",
|
||
" return False\n",
|
||
" return True\n",
|
||
"\n",
|
||
"# Check if a matrix is transitive\n",
|
||
"def transitive(matrix):\n",
|
||
" is_transitive = True\n",
|
||
" for i in range(len(matrix)):\n",
|
||
" for j in range(len(matrix)):\n",
|
||
" if matrix[i][j] > 0:\n",
|
||
" for k in range(len(matrix)):\n",
|
||
" if matrix[j][k] > 0:\n",
|
||
" is_transitive = is_transitive and matrix[i][k] > 0\n",
|
||
"\n",
|
||
" return is_transitive\n",
|
||
"\n",
|
||
"# Check if a matrix is intransitive\n",
|
||
"def intransitive(matrix):\n",
|
||
" is_transitive = True\n",
|
||
" for i in range(len(matrix)):\n",
|
||
" for j in range(len(matrix)):\n",
|
||
" if matrix[i][j] > 0:\n",
|
||
" for k in range(len(matrix)):\n",
|
||
" if matrix[j][k] > 0:\n",
|
||
" is_transitive = is_transitive and matrix[i][k] != 1\n",
|
||
"\n",
|
||
" return is_transitive\n",
|
||
"\n",
|
||
"# Check if a matrix is non-transitive\n",
|
||
"def non_transitive(matrix):\n",
|
||
" n = len(matrix)\n",
|
||
"\n",
|
||
" for i in range(n):\n",
|
||
" for j in range(n):\n",
|
||
" if matrix[i][j] > 0:\n",
|
||
" for k in range(n):\n",
|
||
" if matrix[j][k] > 0 and matrix[i][k] == 0:\n",
|
||
" return True\n",
|
||
" return False"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 80,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"--------------------------------------------------\n",
|
||
"Matrix: R 1\n",
|
||
"reflexive: False\n",
|
||
"irreflexive: False\n",
|
||
"symmetrical: True\n",
|
||
"anti_symmetrical: False\n",
|
||
"asymmetrical: False\n",
|
||
"transitive: False\n",
|
||
"intransitive: False\n",
|
||
"non_transitive: True\n",
|
||
"--------------------------------------------------\n",
|
||
"Matrix: R 2\n",
|
||
"reflexive: False\n",
|
||
"irreflexive: False\n",
|
||
"symmetrical: False\n",
|
||
"anti_symmetrical: True\n",
|
||
"asymmetrical: False\n",
|
||
"transitive: False\n",
|
||
"intransitive: False\n",
|
||
"non_transitive: True\n",
|
||
"--------------------------------------------------\n",
|
||
"Matrix: R 3\n",
|
||
"reflexive: False\n",
|
||
"irreflexive: False\n",
|
||
"symmetrical: False\n",
|
||
"anti_symmetrical: True\n",
|
||
"asymmetrical: False\n",
|
||
"transitive: True\n",
|
||
"intransitive: False\n",
|
||
"non_transitive: False\n",
|
||
"--------------------------------------------------\n",
|
||
"Matrix: R 4\n",
|
||
"reflexive: True\n",
|
||
"irreflexive: False\n",
|
||
"symmetrical: True\n",
|
||
"anti_symmetrical: False\n",
|
||
"asymmetrical: False\n",
|
||
"transitive: True\n",
|
||
"intransitive: False\n",
|
||
"non_transitive: False\n",
|
||
"--------------------------------------------------\n",
|
||
"Matrix: R 5\n",
|
||
"reflexive: False\n",
|
||
"irreflexive: True\n",
|
||
"symmetrical: False\n",
|
||
"anti_symmetrical: True\n",
|
||
"asymmetrical: True\n",
|
||
"transitive: False\n",
|
||
"intransitive: True\n",
|
||
"non_transitive: True\n",
|
||
"--------------------------------------------------\n",
|
||
"Matrix: R 6\n",
|
||
"reflexive: False\n",
|
||
"irreflexive: False\n",
|
||
"symmetrical: False\n",
|
||
"anti_symmetrical: False\n",
|
||
"asymmetrical: False\n",
|
||
"transitive: False\n",
|
||
"intransitive: False\n",
|
||
"non_transitive: True\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Testing all the matrices from the slides\n",
|
||
"\n",
|
||
"for i in range(len(tests)):\n",
|
||
" print(\"--------------------------------------------------\")\n",
|
||
" print(\"Matrix: R\", i+1)\n",
|
||
" a = reflexive(tests[i])\n",
|
||
" print(\"reflexive: \", a)\n",
|
||
" a = irreflexive(tests[i])\n",
|
||
" print(\"irreflexive: \", a)\n",
|
||
" a = symmetrical(tests[i])\n",
|
||
" print(\"symmetrical: \", a)\n",
|
||
" a = anti_symmetrical(tests[i])\n",
|
||
" print(\"anti_symmetrical: \", a)\n",
|
||
" a = asymmetrical(tests[i])\n",
|
||
" print(\"asymmetrical: \", a)\n",
|
||
" a = transitive(tests[i])\n",
|
||
" print(\"transitive: \", a)\n",
|
||
" a = intransitive(tests[i])\n",
|
||
" print(\"intransitive: \", a)\n",
|
||
" a = non_transitive(tests[i])\n",
|
||
" print(\"non_transitive: \", a)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 81,
|
||
"metadata": {},
|
||
"outputs": [],
|
||
"source": [
|
||
"# Equivalence classes\n",
|
||
"\n",
|
||
"def equivalence_classes(R):\n",
|
||
" n = len(R)\n",
|
||
" classes = []\n",
|
||
" scores = []\n",
|
||
"\n",
|
||
" # Count number of (x,y) existing on each row\n",
|
||
" for x in range(n):\n",
|
||
" score = 0\n",
|
||
" for y in range(n):\n",
|
||
" if R[x][y] > 0:\n",
|
||
" score += 1\n",
|
||
" scores.append(score)\n",
|
||
"\n",
|
||
" lastScore = 0\n",
|
||
"\n",
|
||
" for i in range(n):\n",
|
||
" max_score = 0\n",
|
||
" max_index = 0\n",
|
||
" for j in range(n):\n",
|
||
" if scores[j] > max_score:\n",
|
||
" max_score = scores[j]\n",
|
||
" max_index = j\n",
|
||
"\n",
|
||
" if(max_score == lastScore):\n",
|
||
" classes[len(classes)-1].append(max_index)\n",
|
||
" else:\n",
|
||
" # Add the class to the list of classes\n",
|
||
" classes.append([max_index])\n",
|
||
"\n",
|
||
" lastScore = max_score\n",
|
||
" scores[max_index] = 0\n",
|
||
"\n",
|
||
" return classes, scores\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 82,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"([[2], [0, 3], [4], [1]], [0, 0, 0, 0, 0])\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"print(equivalence_classes(CHAMPIONS))"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 83,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"[1, 1, 1, 1]\n",
|
||
"[0, 0, 0, 0]\n",
|
||
"[1, 1, 1, 1]\n",
|
||
"[1, 1, 1, 1]\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"def transitive_closure(adjacency_matrix):\n",
|
||
" \"\"\"\n",
|
||
" Calculate the transitive closure of a directed graph represented as an adjacency matrix.\n",
|
||
"\n",
|
||
" Args:\n",
|
||
" adjacency_matrix (list of lists): The adjacency matrix of the graph.\n",
|
||
"\n",
|
||
" Returns:\n",
|
||
" list of lists: The transitive closure matrix.\n",
|
||
" \"\"\"\n",
|
||
" n = len(adjacency_matrix)\n",
|
||
"\n",
|
||
" # Initialize the transitive closure matrix as a copy of the adjacency matrix\n",
|
||
" closure_matrix = [row[:] for row in adjacency_matrix]\n",
|
||
"\n",
|
||
" # Perform the Floyd-Warshall algorithm to compute transitive closure\n",
|
||
" for k in range(n):\n",
|
||
" for i in range(n):\n",
|
||
" for j in range(n):\n",
|
||
" closure_matrix[i][j] = closure_matrix[i][j] or (closure_matrix[i][k] and closure_matrix[k][j])\n",
|
||
"\n",
|
||
" return closure_matrix\n",
|
||
"\n",
|
||
"# Example usage:\n",
|
||
"adjacency_matrix = [\n",
|
||
" [0, 1, 0, 0],\n",
|
||
" [0, 0, 0, 1],\n",
|
||
" [1, 0, 0, 0],\n",
|
||
" [0, 0, 1, 0]\n",
|
||
"]\n",
|
||
"\n",
|
||
"ex_cours = [\n",
|
||
" [0, 0, 1, 0],\n",
|
||
" [0, 0, 0, 0],\n",
|
||
" [0, 1, 1, 1],\n",
|
||
" [1, 0, 0, 0]\n",
|
||
"]\n",
|
||
"\n",
|
||
"transitive_closure_matrix = transitive_closure(ex_cours)\n",
|
||
"\n",
|
||
"# Print the transitive closure matrix\n",
|
||
"for row in transitive_closure_matrix:\n",
|
||
" print(row)\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 84,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"[3, 2, 1, 2]\n",
|
||
"[0, 0, 0, 0]\n",
|
||
"[2, 1, 1, 1]\n",
|
||
"[1, 3, 2, 3]\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Make transitive closure\n",
|
||
"\n",
|
||
"transitive_closure_matrix = [\n",
|
||
" [1, 0, 0, 0],\n",
|
||
" [0, 1, 0, 1],\n",
|
||
" [1, 0, 0, 0],\n",
|
||
" [0, 0, 1, 1]\n",
|
||
"]\n",
|
||
"\n",
|
||
"def transitive_closure(matrix):\n",
|
||
" modification = True\n",
|
||
" while modification:\n",
|
||
" modification = False\n",
|
||
" for i in range(len(matrix)):\n",
|
||
" for j in range(len(matrix)):\n",
|
||
" for k in range(len(matrix)):\n",
|
||
" if matrix[i][j] > 0 and matrix[j][k] > 0 and matrix[i][k] == 0:\n",
|
||
" matrix[i][k] = matrix[i][j] + matrix[j][k]\n",
|
||
" modification = True\n",
|
||
" else:\n",
|
||
" modification = False\n",
|
||
"\n",
|
||
" return matrix\n",
|
||
"\n",
|
||
"full_closure = transitive_closure(ex_cours)\n",
|
||
"\n",
|
||
"for row in full_closure:\n",
|
||
" print(row)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 85,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"Removing 0 0\n",
|
||
"Removing 1 1\n",
|
||
"Removing 1 3\n",
|
||
"Removing 3 3\n",
|
||
"[0, 0, 0, 0]\n",
|
||
"[0, 0, 2, 0]\n",
|
||
"[1, 0, 0, 0]\n",
|
||
"[2, 0, 1, 0]\n",
|
||
"Removing 0 0\n",
|
||
"Removing 1 1\n",
|
||
"Removing 2 2\n",
|
||
"Removing 3 3\n",
|
||
"Removing 4 4\n",
|
||
"Removing 5 5\n",
|
||
"Removing 6 6\n",
|
||
"Removing 0 4\n",
|
||
"Removing 1 5\n",
|
||
"Removing 3 5\n",
|
||
"Removing 4 6\n",
|
||
"Removing 0 6\n",
|
||
"[0, 1, 1, 1, 0, 1, 0]\n",
|
||
"[0, 0, 0, 0, 1, 0, 1]\n",
|
||
"[0, 0, 0, 0, 0, 0, 1]\n",
|
||
"[0, 0, 0, 0, 1, 0, 1]\n",
|
||
"[0, 0, 0, 0, 0, 1, 0]\n",
|
||
"[0, 0, 0, 0, 0, 0, 1]\n",
|
||
"[0, 0, 0, 0, 0, 0, 0]\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Remove transitive closure\n",
|
||
"\n",
|
||
"transitive_closure_matrix = [\n",
|
||
"[1, 0, 0, 0],\n",
|
||
"[0, 1, 2, 1],\n",
|
||
"[1, 0, 0, 0],\n",
|
||
"[2, 0, 1, 1]\n",
|
||
"]\n",
|
||
"\n",
|
||
"m = [\n",
|
||
" [1,1,1,1,1,1,1],\n",
|
||
" [0,1,0,0,1,1,1],\n",
|
||
" [0,0,1,0,0,0,1],\n",
|
||
" [0,0,0,1,1,1,1],\n",
|
||
" [0,0,0,0,1,1,1],\n",
|
||
" [0,0,0,0,0,1,1],\n",
|
||
" [0,0,0,0,0,0,1]\n",
|
||
"]\n",
|
||
"\n",
|
||
"def remove_transitive_closure(matrix):\n",
|
||
" n = len(matrix)\n",
|
||
" modification = True\n",
|
||
"\n",
|
||
" while modification:\n",
|
||
" # reset modification\n",
|
||
" modification = False\n",
|
||
" for i in range(n):\n",
|
||
" for j in range(n):\n",
|
||
" # checking if there is a path from i to j\n",
|
||
" if matrix[i][j] > 0:\n",
|
||
" for k in range(j,n):\n",
|
||
" # checking if there is a path from i k to to k\n",
|
||
" if matrix[i][k] > 0 and matrix[j][k] > 0:\n",
|
||
" matrix[i][k] = 0\n",
|
||
" modification = True\n",
|
||
" print(\"Removing \", i, k)\n",
|
||
" # restart while loop\n",
|
||
" break\n",
|
||
" if modification:\n",
|
||
" break\n",
|
||
"\n",
|
||
" return matrix\n",
|
||
"\n",
|
||
"no_closure = remove_transitive_closure(transitive_closure_matrix)\n",
|
||
"\n",
|
||
"for row in no_closure:\n",
|
||
" print(row)\n",
|
||
"\n",
|
||
"no_closure = remove_transitive_closure(m)\n",
|
||
"\n",
|
||
"for row in no_closure:\n",
|
||
" print(row)"
|
||
]
|
||
}
|
||
],
|
||
"metadata": {
|
||
"kernelspec": {
|
||
"display_name": "Python 3 (ipykernel)",
|
||
"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.10.12"
|
||
}
|
||
},
|
||
"nbformat": 4,
|
||
"nbformat_minor": 2
|
||
}
|