Enregistrer la dynamique du graphe

L'objectif ici est d'enregistrer la dynamique du réseau (apparitions et disparitions de liens de communication) sous forme de graphe dynamique. Un tel graphe peut être représenté de nombreuses manières. L'une des plus basique consiste en une liste de contacts, où chaque contact représente l'existence d'un lien entre deux noeuds à un instant donné. Par exemple, si une arête entre $a$ et $b$ est présente du temps $1$ jusqu'au temps $4$, la liste contiendra les contacts $(a,b,1),(a,b,2),(a,b,3)$ et $(a,b,4)$. Ce n'est pas très optimisé, mais rend certains algorithmes plus simples. Nous pouvons donc considérer cela dans un premier temps.

Voici une proposition de classe Contact:

public class Contact {

    private int id1;
    private int id2;
    private int time;

    public Contact(int id1, int id2, int time){
        this.id1 = id1;
        this.id2 = id2;
        this.time = time;
    }

    public int getId1() {
        return id1;
    }

    public int getId2() {
        return id2;
    }

    public int getTime() {
        return time;
    }

    public boolean equals(Object o){ // For comparison when used in a collection
        if (o instanceof Contact) {
            Contact c = (Contact) o;
            return this.time == c.time &&
                ((this.id1 == c.id1 && this.id2 == c.id2) || 
                 (this.id1 == c.id2 && this.id2 == c.id1));
        }else{
            return false;
        }
    }
}

Notre premier objectif sera de créer une liste de contact qui enregistre la dynamique d'un réseau via JBotSim. Concrètement, nous allons faire bouger des noeuds à la souris pour créer/supprimer automatiquement des liens et enregistrer ces derniers. JBotSim permet de détecter l'apparition et la disparition de liens en utilisant l'interface ConnectivityListener et ses deux méthodes onLinkAdded() et onLinkRemoved. Vous pouvez récupérer la classe minimale suivante (LinkRecorder) et l'utiliser comme base.

import io.jbotsim.core.Link;
import io.jbotsim.core.Topology;
import io.jbotsim.core.event.CommandListener;
import io.jbotsim.core.event.ConnectivityListener;

public class LinkRecorder implements ConnectivityListener, CommandListener {
    private Topology tp;
    private final static String START = "Start recording";
    private final static String STOP = "Stop recording";
    private boolean isRecording = false;

    LinkRecorder(Topology tp) {
        this.tp = tp;
        tp.addCommandListener(this);
        tp.addCommand(START);
        tp.addCommand(STOP);
        tp.addCommand(Topology.COMMAND_SEPARATOR);
        tp.addConnectivityListener(this);
    }

    @Override
    public void onLinkAdded(Link link) {
        if (isRecording) {
            System.out.println("Appearance of " + link + " at " + tp.getTime());
        }
    }

    @Override
    public void onLinkRemoved(Link link) {
        if (isRecording) {
            System.out.println("Disappearance of " + link + " at " + tp.getTime());
        }
    }

    @Override
    public void onCommand(String s) {
        if (s.equals(START) && !isRecording){
            isRecording = true;
            for (Link l : tp.getLinks()){ // Mimic appearance of existing links (if any)
                this.onLinkAdded(l);
            }
        }else{
            isRecording = false;
        }
    }
}

import io.jbotsim.core.Topology;
import io.jbotsim.ui.JViewer;

public class Main {
    public static void main(String[] args){
        Topology tp = new Topology();
        tp.setTimeUnit(100); // 100ms per round
        new ContactRecorder(tp);
        new JViewer(tp);
        tp.start();
    }
}

Q1. Testez ce programme en prenant le temps de bien comprendre chaque aspect.

Dans le code fourni, nous nous contentons d'afficher l'apparition et la disparition d'un lien dans la sortie standard

Q2. Créez une liste de Contact dans votre classe LinkRecorder.

Q3. En modifiant le code des méthodes onLinkAdded() et onLinkRemoved(), remplissez votre liste de contacts au fur et à mesure que les apparition et disparition de liens se produisent. Vous avez deux choix ici:

1. Dupliquer les contacts à chaque temps de présence, c'est à dire que si un lien apparait au temps $1$ et disparait au temps $4$, vous devez créer $4$ contacts (un pour chaque temps).
2. Créer une nouvelle classe pour représenter les contacts autrement que par des triplets (par exemple, en mémorisant les temps d'apparition et de disparition du lien explicitement).

Note: nous allons vous fournir quelques jeux de contacts pré-déterminés sous forme de List<Contact>, que vous pourrez utiliser pour tester vos algorithmes, ce qui peut être un argument pour l'option 1. Ceci étant dit, nous vous laissons le choix de la structure de donnée, qui peut être faite de nombreuses manières différentes.

Vous êtes maintenant prêts à développer quelques algorithmes de test de propriétés temporelles.