From 5a3cc6df08a0aa323d95d7af96792ed10aada624 Mon Sep 17 00:00:00 2001
From: Vincent Le Gallic <legallic@crans.org>
Date: Tue, 14 Aug 2012 00:29:02 +0200
Subject: [PATCH] Initialisation du repo

---
 .gitignore  | 31 +++++++++++++++++++++++++++++++
 chopes.py   | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 dijkstra.py | 24 ++++++++++++++++++++++++
 3 files changed, 107 insertions(+)
 create mode 100644 .gitignore
 create mode 100644 chopes.py
 create mode 100644 dijkstra.py

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..a57fd2e
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,31 @@
+# Custom #
+###################
+*~
+
+# Compiled source #
+###################
+*.pyc
+
+# Packages #
+############
+# it's better to unpack these files and commit the raw source
+# git has its own built in compression methods
+*.7z
+*.dmg
+*.gz
+*.iso
+*.jar
+*.rar
+*.tar
+*.zip
+
+# Logs #
+######################
+*.log
+
+# OS generated files #
+######################
+.DS_Store*
+*ehthumbs.db
+Icon?
+*Thumbs.db
diff --git a/chopes.py b/chopes.py
new file mode 100644
index 0000000..d681cc6
--- /dev/null
+++ b/chopes.py
@@ -0,0 +1,52 @@
+#!/usr/bin/python
+# -*- encoding: utf-8 -*-
+
+# Codé par 20-100 et Gaétan le 13/08/12
+# parce que parfois, à la Mèd, on fait des conneries
+
+import psycopg2
+import psycopg2.extras
+
+from dijkstra import dijkstra
+
+inf = float('Inf')
+
+def getcursor():
+    con = psycopg2.connect(database = "chopes")
+    cur = con.cursor(cursor_factory=psycopg2.extras.DictCursor)
+    return con, cur
+
+
+def matrice(n):
+    con, cur = getcursor()
+    cur.execute("SELECT * FROM chopes;")
+    l = cur.fetchall()
+    m = [ [0 if i==j else inf for i in range(n)] for j in range(n)]
+    for (a,b) in l:
+        m[a][b] = 1 # Deux personnes qui se sont chopées sont à distance 1
+        m[b][a] = m[a][b] # Pour nous, les matrices seront symétriques. (Victime inconsciente : -10 pts)
+    return m
+
+
+def nom(id):
+    con, cur= getcursor()
+    cur.execute("SELECT nom FROM gens WHERE id = %s;", (id,))
+    return cur.fetchone()["nom"]
+
+def distances(m):
+    n = len(m)
+    dists = []
+    for i in range(n):
+        dists.append(dijkstra(m, i))
+    return dists
+
+def moyenne(dists, i):
+    nn = len([a for a in dists[i] if a!=inf])
+    return sum([dist for dist in dists[i] if dist!=inf])/float(nn-1) # On ne se compte pas soi-même
+
+if __name__ == "__main__":
+    con, cur = getcursor()
+    cur.execute("SELECT max(id) FROM gens;")
+    n = cur.fetchone()[0] + 1
+    mat = matrice(n)
+    dists = distances(mat)
diff --git a/dijkstra.py b/dijkstra.py
new file mode 100644
index 0000000..fefce1b
--- /dev/null
+++ b/dijkstra.py
@@ -0,0 +1,24 @@
+#!/usr/bin/python
+# -*- encoding: utf-8 -*-
+
+import heapq as hq
+inf = float('Inf')
+
+def dijkstra(G, s):
+    n = len(G)
+
+    Q = [(0, s)]
+
+    d = [inf for i in range(n)]
+    d[s]=0
+
+
+    while len(Q)!=0:
+        (cost, u) = hq.heappop(Q)
+
+        for v in range(n):
+            if d[v] > d[u] + G[u][v]:
+                d[v] = d[u] + G[u][v]
+                hq.heappush(Q, (d[v], v))
+
+    return d
-- 
2.39.2