---
title: "Graphes"
author: "Maxime Wack"
date: "17/11/2020"
output:
  xaringan::moon_reader:
    css: ['default','css/my_style.css']
    lib_dir: libs
    seal: false
    nature:
      ratio: '4:3'
      countIncrementalSlides: false
      self-contained: true
      beforeInit: "addons/macros.js"
---

```{r, include = FALSE}
library(gapminder)
library(tidyverse)
library(DT)
library(knitr)

opts_chunk$set(message = F)

options(DT.options = list(paging = F,
                          info = F,
                          searching = F))

datatable <- partial(datatable, rownames = F)
```

class: center, middle, title
# UE Visualisation
### 2020-2021
## Dr. Maxime Wack
### AHU Informatique médicale
#### Hôpital Européen Georges Pompidou, </br> Université de Paris

---
class: center, middle
# Objectif
## Théorie des graphes
## Créer et manipuler des graphes
## Représenter des graphes

---
# Théorie des graphes

### Étude des graphes et leurs applications
### Topologie des graphes
### Propriétés des graphes
### Développement d'algorithmes
- parcours en largeur/profondeur
- calcul de trajet (A*, Dijkstra)
- détection de sous-graphes
- inférence, effets de réseaux
- résolution de contraintes

---
# Graphes
.pull-left[
## Graphes ou réseaux
*graphs* and *networks*
## Représentation de **relations** entre des **éléments**
]

.pull-right[
![](06-img/graphe.png)
]

---
# Sommets
.pull-left[
### (ou nœuds, ou points)</br> *vertex (vertices)* en anglais
### Servent à représenter les **éléments**
### Peuvent posséder des **attributs** arbitraires (label, valeurs, etc.)
### Des attributs peuvent être **calculés** (degré, centralité, etc.)
]

.pull-right[
![](06-img/vertices.png)
]


---
# Arêtes
.pull-left[
### (ou liens, ou lignes)</br> *edges* en anglais
### Servent à représenter les **relations**
### Peuvent également posséder des **attributs** (label, poids, etc.)
]

.pull-right[
![](06-img/edges.png)
]

---
# Graphe dirigé

.pull-left[
### Graphe dont les arêtes ont une **direction**
### Arêtes **bidirectionnelles** possibles
]

.pull-right[
![](06-img/directed.png)
]

---
# Cycles

.pull-left[
### Groupes de sommets formant un **anneau**
### Dans un graphe dirigé, on doit pouvoir tourner
]

.pull-right[
![](06-img/cycle.png)
]


---
# Clique

.pull-left[
### Ensemble de sommets **tous connectés entre eux**
]

.pull-right[
![](06-img/clique.png)
]

---
# Graphe connecté

.pull-left[
### Graphe dont **tous les sommets** forment une **clique**
]

.pull-right[
![](06-img/connected.png)
]

---
# Arbre

.pull-left[
### Graphe ne comportant **pas de cycle**
### Possède une ou plusieurs **racines**
]

.pull-right[
![](06-img/tree.png)
]


---
# Graphe dirigé acyclique

.pull-left[
### Depuis le graphe dirigé précédent
### Quelles arêtes supprimer pour obtenir un DAG ?
]

.pull-right[
![](06-img/directed.png)
]
---
# Graphe dirigé acyclique

.pull-left[
### **DAG** (Directed Acyclic Graph)
### Structure très reconnue
- Réseaux bayésiens
- Arbres généalogiques
- Systèmes de contrôle de version
- Systèmes de workflow
- Graphe de citations
]

.pull-right[
![](06-img/DAG.png)
]

---
# Représentation numérique

.pull-left[
![](06-img/numbered.png)
]

.pull-right[
## Liste de sommets

`(1, 2, 3, 4, 5, 6, 7, 8)`

## Liste d'arêtes

`((2, 1), (3, 1), (4, 1),`</br>
` (2, 3), (4, 3), (4, 2),`</br>
` (2, 5), (5, 2), (5, 7),`</br>
` (6, 5), (6, 7), (7, 4),`</br>
` (7, 8))`
]

---
# Représentation numérique

.pull-left[
![](06-img/numbered.png)
]

## Matrice d'adjacence

```{r matrice, echo = F}
matrix(c(0, 0, 0, 0, 0, 0, 0, 0,
         1, 0, 1, 0, 1, 0, 0, 0,
         1, 0, 0, 0, 0, 0, 0, 0,
         1, 1, 1, 0, 0, 0, 0, 0,
         0, 1, 0, 0, 0, 0, 1, 0,
         0, 0, 0, 0, 1, 0, 1, 0,
         0, 0, 0, 1, 0, 0, 0, 1,
         0, 0, 0, 0, 0, 0, 0, 0),
       nrow = 8) %>% t
```
---
class: center
# Visualisation
## Cytoscape
## yEd
## ggraph

---
# Outils externes

## Cytoscape

https://cytoscape.org/

Pour l'analyse de réseaux, orienté biologie à l'origine</br>
Visualisation de réseaux</br>
Calculs d'indicateurs</br>
Mapping d'attributs sur des propriété esthétiques

## yEd

https://www.yworks.com/products/yed

Éditeur de graphes, multiples supportés</br>
Visualisation de réseaux</br>
Nombreux algorithmes de layout</br>
Calculs d'indicateurs</br>
Mapping d'attributs sur des propriété esthétiques</br>

---
# ggraph

https://ggraph.data-imaginist.com/

### `geom_node_*` → geom pour les sommets
### `geom_edge_*` → geom pour les arêtes
### Propriété `layout` dans `ggraph()`