Algorithmique de la mobilité

↑ Accueil du cours

Connexité temporelle

L'objectif de cette séance est de tester automatiquement certaines propriétés sur les graphes dynamiques. Dans une première partie, nous rappellons certaines définitions et familles de graphes vues en cours. Nous proposons ensuite une classe java qui permet d'enregistrer les apparitions et disparitions de liens de communication dans JBotSim, afin d'obtenir quelques traces réseaux sur lesquelles travailler. Le coeur de la séance s'intéresse à tester des propriétés temporelles sur ces traces réseaux, permettant de déterminer à quelle famille de graphe dynamique elles appartiennent.

Enregistrer la dynamique du graphe

Si vous le l'avez pas encore fait, suivez le mini tutoriel Enregistrement des liens.

Trajet et connexité temporelle

Une trajet (ou chemin temporel) est un chemin qui se réalise à travers le temps, comme illustré ci-dessous. Lorsque le temps est discret (c'est le cas ici), on distingue deux types de trajets : les trajets stricts et les trajets non-stricts. Un trajet non-strict autorise plusieurs sauts consécutifs à la même date (par exemple, aller de $a$ à $d$ dans le premier graphe). À l'inverse, un trajet strict impose au plus un saut consécutif par graphe (p.ex. le trajet représenté en rouge ci-dessous).

Figure 1: Exemple de trajet (strict) dans un graphe dynamique.

Un graphe dynamique est temporellement connexe s'il existe un trajet de tout sommet vers tout sommet (famille C2 ci-dessous).

Familles de graphes dynamiques

Il existe un grand nombre de familles de graphes dynamiques. Nous nous intéressons ici à quelques familles basiques vues en cours, correspondant aux propriétés temporelles suivantes.

  1. Famille C1: au moins un sommet peut atteindre tous les autres par un trajet
  2. Famille C2: chaque sommet peut atteindre tous les autres par un trajet
  3. Famille C3: au moins un sommet peut atteindre tous les autres par un trajet strict
  4. Famille C4: chaque sommet peut atteindre tous les autres par un trajet strict
  5. Famille C5: au moins un sommet est voisin de tous les autres à un moment ou à un autre
  6. Famille C6: tous les sommets sont voisins à un moment ou à un autre
  7. Famille C7: au moins un sommet peut être atteint par tous les autres par un trajet

Q1. À quelle(s) famille(s) le graphe de la figure 1 appartient-il ?

Test de propriétés

Pour chaque classe de graphe dynamique présentée plus haut (C1 à C7), nous allons écrire des méthodes pour tester automatiquement si les propriétés correspondantes sont vérifiées. Les propriétés des classes C5 et C6 sont les plus faciles à tester. Nous commencerons donc par elles. Si votre format d'enregistrement des liens est une List<Contact> (ou capable d'importer une telle liste), alors vous pouvez utilisez les jeux de données disponibles en bas de page pour tester vos algorithmes.

Q2 (facile). Écrire une méthode qui prend en entrée votre structure de donnée et renvoie vrai si le graphe dynamique correspondant appartient à la famille C5. Idem pour C6.

Q3 (moins facile). Écrire une méthode qui prend en entrée votre structure de donnée ainsi qu'un noeud et renvoie vrai si ce noeud est capable de joindre tous les autres par un trajet strict. Utiliser cette méthode pour tester C3 et C4.

Q4 (plus difficile, bonus). Écrire une méthode qui prend en entrée votre structure de donnée ainsi qu'un noeud et renvoie vrai si ce noeud est capable de joindre tous les autres par un trajet non-strict. Utiliser cette méthode pour tester C1 et C2 (voire C7).

Remarque. Il est possible de construire, puis utiliser des structures intermédiaires telles l'empreinte (pour C5 et C6), la fermeture transitive des trajets stricts (pour C3 et C4) et la fermeture transitive des trajets non-stricts (pour C1, C2 et C7). Mais ce n'est pas obligatoire.

Jeux de données

Voici quelques jeux de données (graphes sous forme de List<Contact>) préparés par Jason. N'hésitez pas à les utiliser pour tester vos algorithmes au fur et à mesure.

public static List<Contact> contactsFigure1(){
    String g = "1-3,2-3,2-4,3-4\n" +
        "1-2,2-3,3-4\n" +
        "1-2,3-4,3-5,4-5\n" +
        "3-5,4-5";
    return parse(g);
}

public static List<Contact> contactsNone(){
    String g = "0-1,2-3\n" +
        "1-2,3-4";
    return parse(g);
}

public static List<Contact> contactsC1(){
    String g = "3-4,4-5\n" +
        "1-2,2-3";
    return parse(g);
}

public static List<Contact> contactsC2(){
    String g = "1-2,2-3\n" +
        "3-4,4-5\n" +
        "1-2,2-3";
    return parse(g);
}

public static List<Contact> contactsC3(){
    String g = "4-5\n" +
        "1-2,3-4\n" +
        "2-3\n" +
        "1-2";
    return parse(g);
}

public static List<Contact> contactsC4(){
    String g = "2-3\n" +
        "2-4\n" +
        "0-2\n" +
        "0-1\n" +
        "0-2\n" +
        "2-3\n" +
        "2-4";
    return parse(g);
}

public static List<Contact> contactsC5(){
    String g = "0-1\n" +
        "1-2\n" +
        "2-3\n" +
        "3-4\n" +
        "0-4\n" +
        "1-4\n" +
        "2-4";
    return parse(g);
}

public static List<Contact> contactsC6(){
    String g = "0-1,0-2,0-3,0-4,1-2,1-3,1-4,2-3,2-4,3-4";
    return parse(g);
}

public static List<Contact> contactsC7(){
    String g = "0-1,1-2,3-4\n" +
        "2-3";
    return parse(g);
}

public static List<Contact> parse(String g){
    List<Contact> contacts = new LinkedList<>();
    int time = 0;
    String[] snapshots = g.split("\n");
    for (String snapshot : snapshots){
        String[] timeEdges = snapshot.split(",");
        for (String timeEdge : timeEdges){
            String[] nodes = timeEdge.split("-");
            int node0 = Integer.parseInt(nodes[0]);
            int node1 = Integer.parseInt(nodes[1]);
            Contact c = new Contact(node0, node1, time);
            contacts.add(c);
        }
        time++;
    }
    return contacts;
}