---
# System prepended metadata

title: 'OLA, TP 1'

---

# OLA, TP 1

Rappels de Python :

Pour définir une variable:
```python=
my_var = 12
```
Pour définir une fonction:

```python=
def f(i):
    if i < 0:
        return True
    else:
        return False
``` 



## Exercice 1:

1. Représentation en Python du graphe

Correction :

```python =
exemple_matrice = 
    [[0, 1, 1, 0, 1, 0, 0, 0], #0
     [0, 0, 0, 1, 0, 1, 0, 0], #1
     [0, 0, 0, 1, 0, 0, 1, 0], #2
     [0, 0, 0, 0, 0, 0, 0, 1], #3
     [0, 0, 0, 0, 0, 1, 1, 0], #4
     [0, 0, 0, 0, 0, 0, 0, 1], #5
     [0, 0, 0, 0, 0, 0, 0, 1], #6
     [0, 0, 0, 0, 0, 0, 0, 0]] #7 
     
exemple_liste =
    [[1, 2, 4],
    [3, 5],
    [3, 6],
    [7],
    [5, 6],
    [7],
    [7],
    []]
```
    
2. Question 2

```python=
def compte_sommet(g):
    return len(g)

def compte_arete_m(g):
    nb=0
    for i in range(len(g)):
        for j in range (len(g)):
            nb+=g[i][j]
    return nb
    
print(compte_arete_m(exemple_matrice))

def compte_arete_l(g):
    nb=0
    for i in range(len(g)):
        nb+=len(g[i])
    return nb

print(compte_arete_l(exemple_liste))
```

3. Question 3:

```python=
def adjacents_matrice(g,i,j):
    return g[i][j]==1 or g[j][i]==1

def adjacents_liste(g,i,j):
    return j in g[i] or i in g[j]
```

4. Question 4:

```python= 
def successeurs_matrice(g, s):
    l=[]
    for i in range(len(g)):
        if g[s][i]==1:
            l.append(i)
    return l
def successeurs_liste(g, s):
    return g[s]
```
    
5. Question 5 :

```python=
def predecesseurs_matrice(g, s):
    l=[]
    for i in range(len(g)):
        if g[i][s]==1:
            l.append(i)
    return l
    
def predecesseurs_liste(g, s):
    l=[]
    for i in range(len(g)):
        if s in g[i]:
            l.append(i)
    return l
```
    
6. Question 6 : réflexif

```python=
def reflexif_m(g):
    for i in range(len(g)):
        if not g[i][i]==1:
            return False
    return True

def reflexif_l(g):
    for i in range(len(g)):
        if not (i in g[i]):
            return False
    return True
```
    
7. Question 7 : symétrique 

```python=
def symetrique_m(g):
    for i in range(len(g)):
        for j in range(len(g)):
            if g[i][j]==1:
                if g[j][i]==0:
                    return False
    return True

print(symetrique_m(g))

def symetrique_l(g):
    for i in range(len(g)):
        for j in g[i]:
            if not i in g[j]:
                return False
    return True
```

8. Symétrisation 

```python=
def symetrisation_m(g):
   for i in range(len(g)):
        for j in range(len(g)):
            if g[i][j]==1:
                g[j][i]=1
    
def symetrisation_l(g):
    for i in range (len(g)):
        for j in g[i]:
            if not i in g[j]:
                g[j].append(i)
```

9. Transitif

```python=
def transitif_matrice(g):
    for i in range(len(g)):
        for j in successeurs_matrice(g, i):
            for k in successeurs_matrice(g, k):
                if not g[i][k]:
                    return False
    return True
    
def transitif_liste(g):
    for i in range(len(g)):
        for j in g[i]:
            for k in g[j]:
                if not k in g[i]:
                    return False
    return True
```


Code d'Ariane
```python=
#Q1
#a) Matrice
g1 = [[False, True, True, False, True, False, False, False],
     [False, False, False, True, False, True, False, False],
     [False, False, False, True, False, False, True, False],
     [False, False, False, False, False, False, False, True],
     [False, False, False, False, False, True, True, False],
     [False, False, False, False, False, False, False, True],
     [False, False, False, False, False, False, False, True],
     [False, False, False, False, False, False, False, False]]

#b) Liste
g2 = [[1, 2, 4],
     [3, 5],
     [3, 6],
     [7],
     [5, 6],
     [7],
     [7],
     []]

#Q2
#a)
def compte_sommets(g):
    return len(g)
    
def compte_aretes_m(g):
    nb = 0
    for i in range(len(g)): # de 0 à len(g)-1
        for j in range(len(g)):
            if g[i][j]:
                nb+=1
    return nb

def compte_aretes_l(g):
    nb = 0
    for i in range(len(g)):
        nb+=len(g[i])
    return nb
#Q3
#a)
def adjacents_m(g, i, j):
    return g[i][j] or g[j][i]
#b)
def adjacents_l(g, i, j):
    return (i in g[j]) or (j in g[i])
    
#Q4
#a)
def successeurs_m(g, s):
    res=[]
    for i in range(len(g)):
        if g[s][i]:
            res.append(i)
    return res
    
#b)
def successeurs_l(g, s):
    return g[s]
#Q5
#a)
def predecesseurs_m(g, s):
    res=[]
    for i in range(len(g)):
        if g[i][s]:
            res.append(i)
    return res
#b)
def predecesseurs_l(g, s):
    res=[]
    for i in range(len(g)):
        if s in g[i]:
            res.append(i)
    return res
#Q6
#a)
def reflexif_m(g):
    for i in range(len(g)):
        if not g[i][i]:
            return False
    return True

#b)
def reflexif_l(g):
    for i in range(len(g)):
        if not (i in g[i]):
            return False
    return True
#Q7
#a)
def symetrique_m(g):
    for i in range(len(g)):
        for j in range(len(g)):
            if g[i][j]:
                if not g[j][i]:
                    return False
    return True
#b)
def symetrique_l(g):
    for i in range(len(g)):
        for j in range(len(g)):
            if j in g[i]:
                if not i in g[i]:
                    return False
    return True
#Q8
#a)
def symetrisation_m(g):
    for i in range(len(g)):
        for j in range(len(g)):
            if g[i][j]:
                g[j][i]=True
#b)
def symetrisation_l(g):
    for i in range(len(g)):
        for j in g[i]:
            if not i in g[j]:
                g[j].append(i)
#Q9
#a)
def transitif_m(g):
    for i in range(len(g)):
        for j in successeurs_m(g, i):
            for k in successeurs_m(g, j):
                if not g[i][k]:
                    return False
    return True
#b)
def transitif_l(g):
    for i in range(len(g)):
        for j in g[i]:
            for k in g[j]:
                if not k in g[i]:
                    return False
    return True

```

Señor Alexis :
```python=
# Q1
g_M = [[False, True, True, False, True, False, False, False],
       [False, False, False, True, False, True, False, False],
       [False, False, False, True, False, False, True, False],
       [False, False, False, False, False, False, False, True],
       [False, False, False, False, False, True, True, False],
       [False, False, False, False, False, False, False, True],
       [False, False, False, False, False, False, False, True],
       [False, False, False, False, False, False, False, False]]

g_L = [[1, 2, 4],
       [3, 5],
       [3, 6],
       [7],
       [6, 5],
       [7],
       [7],
       []]

# Q2
def compte_sommets(g):
    return len(g)

def compte_aretes_matrice(g):
    nb_aretes = 0
    for s in g:
        for a in s:
            if a is True:
                nb_aretes += 1
    return nb_aretes

def compte_aretes_liste(g):
    nb_aretes = 0
    for s in g:
        nb_aretes+=len(s)
    return nb_aretes

# Q3
def adjacents_matrice(g,i,j):
    return g[i][j] or g[j][i]
    
def adjacents_liste(g,i,j):
    return j in g[i] or i in g[j]

# Q4
def successeurs_matrice(g,s):
    successeurs = []
    for index_a, a in enumerate(g[s]):
        if a is True:
            successeurs.append(index_a)
    return successeurs

def successeurs_list(g,s):
    return g[s]

# Q5
def predecesseurs_matrice(g, s):
    predecesseurs = []
    for index_v,v in enumerate(g):
        if v[s] is True:
            predecesseurs.append(index_v)
    return predecesseurs

def predecesseurs_list(g, s):
    predecesseurs = []
    for index_v, v in enumerate(g):
        if s in v:
            predecesseurs.append(index_v)
    return predecesseurs

# Q6
def reflexif_matrice(g):
    for index_v, v in enumerate(g):
        if v[index_v] is False:
            return False
    return True

def reflexif_list(g):
    for index_v, v in enumerate(g):
        if index_v not in v:
            return False
    return True

# Q7
def symetrique_matrice(g):
    for i in range(len(g)):
        for j in range(len(g[i])):
            if g[i][j] is True:
                if g[j][i] is False:
                    return False
    return True

def symetrique_list(g):
    for index_s, s in enumerate(g):
        for v in s:
            if index_s not in g[v]:
                return False
    return True
    
# Q8
def symetrisation_matrice(g):
    for s1, s in enumerate(g):
        for s2, a in enumerate(s):
            if a is True:
                g[s2][s1] = True;
    return g

def symetrisation_list(g):
    for s1, s in enumerate(g):
        for s2 in s:
            g[s2].append(s1)
    return g

# Q9 (Brut)
def transitif_matrice(g):
    for i in range(len(g)):
        for j in range(len(g[i])):
            for k in range(g[i][j]):
                if g[i][j] is True and g[j][k] is True:
                    if g[i][k] is False:
                        return False
    return True
```





Jacobo


```python=
#1
#graphe_M= deja fait par les autres.

graphe_L = 
[[1,2,4],
[3,5],
[3,6],
[7],
[6,5],
[7],
[7],
[]]

#2

def compte_somets(graphe):
 return len(graphe)

def compte_aretes_L(graphe):
    res=0
    for i in range (len(graphe)):
        res += len(graphe[i])
    return res

def compte_aretes_M(graphe)
     sum=0
    for sommet in graphe:
        for i in sommet:
            if i==True:
                sum+=1
    return sum

#3
def adjacents_M(g, i, j)
    return g[i][j] or g[j][i]
    
def adjacents_L(g, i,j)
    for t in g[i]:
        if t == j:
            return true
    for x in g[j]:
        if x == i:
            return true    
    return false

#return j in g[i] or i in g[j] OP
#4

def succeseurs_L(g, s)
    return g[s]

def succeseurs_M(g, s)
    res = []
    for i in range len(g[s]):
        if g[i]:
            res.append(i)
    return res

#5
def predecesseurs_L(g, s):
    res=[]
    for i in range compte_sommets(g):
        if s in g[i]:
            res.append(i)
    return res

def predecesseurs_M(g,s)
    res=[]
    for i in range compte_sommets(g):
        if g[s]:
            res.append(i)
    return res

def reflexif_L(g)
    for i in range len(g):
        if !(i in g[i]):
            return False
    return True

def reflexif_M(g)
    for i in range len(g):
        if !g[i][i]: 
            return False
    return True
    
#7
def symetrique_L(g)
    for i in range len(g):
        for j in range len(i):
            if !(j in g[i] and i in g[j]):
                return False
    return True
    
def symetrique_M(g)
    for i in range len(g):
        for j in range len(i):
            if !(g[i][j] and g[j][i])
                return False
    return True

def symetrisation_L(g)
    for i in range len(g):
        for j in range len(i):
            if !(j in g[i] and i in g[j]):
                res = g[]
    return res
    
def symetrisation_M(g)

#

```






Brahim
 ```python=
g = [[False,True,True,False,True,False,False,False],
     [False,False,False,True,False,False,True,False],
     [False,False,False,False,False,False,False,True],
     [False,False,False,False,False,True,True,False],..
     ...

 ]
g = [[1,2,4],
     [3,5],
     [3,6],
     [7],
     [5,6],
     [7],
     [7],
     []]
 
 
def compte_sommet(g):
    return len(g)



def compte_arete(g):
    res=0
    for i in range (len(g)):
       for j in range(len(g[i])):
           if g[i][j] == True then :
              res=res+1

    return res

def adjacents(la,i,j):
    b=False
    for k in range(len(la(i))):
        if k ==j :
           b=True
    for k in range(len(la(j)):
        if k==i : 
            b=True

    return b

def sucesseurs(g,s):
    l=[]
    for i in range(len(g[s])):
        if g[s][i]:
           l.append(i)
    return l
    
def predecesseurs(g,s):
    l=[]
    for i in range(len(g)):
        for j in range(len(g[i])):
            if j==s and g[i][s] :
                l.append(i)
    return l
    
def reflexif(g):
    for i in range(len(g)):
        
        if not(g[i][i]):
            return False
    return True            
    
def symetrique(g):
    for i in range(len(g)):
        for j in range(len(g[i])):
            if g[i][j] and not(g[j][i]):
                return False
    return True
    
def symetrisation(g):
    g_prime=g
    for i in range(len(g)):
        for j in range(len(g[i])):
            if g[i][j] and not(g[j][i]):
                g_prime[j][i]=True
    return g_prime
    
```
Rachad 
```python=
Q1)
exemple_matrice = 
    [[0, 1, 1, 0, 1, 0, 0, 0], #0
     [0, 0, 0, 1, 0, 1, 0, 0], #1
     [0, 0, 0, 1, 0, 0, 1, 0], #2
     [0, 0, 0, 0, 0, 0, 0, 1], #3
     [0, 0, 0, 0, 0, 1, 1, 0], #4
     [0, 0, 0, 0, 0, 0, 0, 1], #5
     [0, 0, 0, 0, 0, 0, 0, 1], #6
     [0, 0, 0, 0, 0, 0, 0, 0]] #7 
Q2)
def compte_sommet(g):
    return len(g)
def nbr_arrete(graphe):

    return sum([sum(i) for i in graphe ]) #output=12
Q3):
def adjacent(graphe,first,second):
    
        
Q4):
def Succeseur(graphe,sommet):
    """  Succeseur(g,2) =[3, 6]"""
    return [som for som in range(8) if g[sommet][som]] #len(g) =8
Q5)
def predecesseurs(graphe,sommet):

    return [som for som in range(8) if   g[som][sommet]] #len(g) =8
Q6)
def reflexive(graphe):
"""1 case de la diagonale =1 <=> True"""
    return any([g[e][e] for e in range(8)]) #len(g) =8
Q7)

    
def symetrique(graphe):
    nb=len(graphe)
    return all([graphe[i][j]==graphe[j][i] for i in range(nb) for j in range(nb) ])
Q8)
def symetrisation(graphe):
    nb=len(graphe)
    for i in range(nb):
        for j in range(nb):
            if graphe[i][j]==1:
                graphe[j][i]=1
    return graphe
Q9)
def transitif(graphe):
    pass
#---------Fonction annexe-------------------------------
def createMiniListe(Liste):
    init=[False]*8
    for i in Liste:
        init[i]=True 
    return init
def m12(listeadja):
    MatriceAdja=[]
    for i in listeadja:
        MatriceAdja.append(createMiniListe(i))
    return MatriceAdja
#----------------------------------------
def getIndex(miniListe):
    init=[]
    for e,i in enumerate(miniListe):
        if i: init.append(e)
    return init
def m21(MatriceAdja):
    init=[]
    for i in MatriceAdja:
        init.append(getIndex(i))
    return init
Q10)
def verifie_chemin(graphe,c):
    None not in g[c]
    
    
    
    
    
    
    

```

Brice
Q1)

g1 = [[False, True, True, False, True, False, False, False], #0
        [False, False, False, True, False, True, False, False], #1
        [False, False, False, True, False, False, True, False], #2
        [False, False, False,False, False, False, False, True], #3
        [False, False, False, False, False, True, True, False], #4
        [False, False, False, False, False, False, False, True], #5
        [False, False, False, False, False, False, False, True], #6
        [False, False, False, False, False, False, False, False]] #7

g1liste = [[1,2,4],  #0
    [3, 5],     #1
    [3, 6],     #2
    [7],        #3
    [5, 6],     #4
    [7],        #5
    [7],        #6
    []]         #7
    
    
