Avant-propos

Les sources et l’exécutable du programme de simulation sont disponibles ici : simulation d’un petit monde.

L’article complet (incluant le guide d’utilisation et une description technique est disponible ici : Article sur la simulation du petit monde

Introduction

Dans le cadre d’un cours sur les systèmes multi-agents (SMA), il nous a été demandé d’imaginer une application mettant en œuvre des agents logiciels. Pour ce faire, il nous était conseillé d’utiliser l’environnement MadKit http://www.madkit.org/. MadKit est une plateforme facilitant le développement des SMA.

Libre de choisir le type de simulation, nous avons décidé de vérifier la théorie de Frigyes Karinthy selon laquelle « toute personne sur le globe peut être reliée à n’importe quelle autre, au travers d’une chaîne de relations individuelles comprenant au plus cinq autres maillons » (source : Wikipédia).

Nous allons donc simuler un petit monde, avec un nombre donné de personnes, ayant des liens amicaux les unes envers les autres, puis vérifier que deux personnes prisent au hasard sont reliées par cinq maillons (amis d’amis d’amis…).

Mais avant tout, pour mieux situer l’expérience, il est intéressant de voir le résultat :

Simulation du petit monde

C’est donc une copie d’écran du petit monde où :

• Les petits points rouges sont des personnes cherchant des « amis ». Elles sont en mouvement.
• Les petits points bleus foncés sont des personnes « épanouies », elles ne cherchent plus d’amis, elles en ont suffisamment. Elles ne bougent plus.
• Le point jaune est la personne qui a voulu évaluer la distance la séparant d’une autre personne prise au hasard.
• Les carrés bleus ciels sont les personnes se trouvant entre la personne « jaune » et la personne choisie. Celle-ci est représentée par le carré bleu au bout du chemin

Remarque : est-ce un hasard s’il y a cinq personnes sur le chemin ?

Aspects scientifiques de la simulation

1. Déroulement du programme

La première chose à faire est de construire le monde. Ceci consiste à créer les personnes qui vont servir à la simulation. Une fois ajoutées au monde, ces personnes vont alors se socialiser : elles vont se déplacer afin de se faire des amis. Pour que la simulation colle à la réalité, les personnes ont un nombre d’amis limité. Une fois cette limite atteinte, elles arrêteront de se déplacer et attendrons.

Parmi ces personnes, certaines auront un rôle supplémentaire dans la simulation : à la demande de l’utilisateur, elles choisiront une personne au hasard dans le monde afin de connaître la distance qui les sépare. Par la suite, ces personnes seront dîtes « observables ».

2. Le lien social

Il est évident que simuler le monde dans sa globalité est impossible. En effet, il faudrait simuler les interactions de plus de six milliards de personnes ; simuler toutes les relations qui peuvent lier deux personnes : liens familiaux, liens amicaux, liens professionnels etc. Il faudrait aussi simuler les différents « groupes » sociaux : personnes ayant la même langue, personnes polyglottes etc.

Pour simplifier ces problèmes, nous avons imaginé un seul lien entre les personnes : elles ne seront amies que si elles parlent la même langue. Ceci engendrant des communautés non liables, un certain taux de personnes seront bilingues.

3. Les paramètres

Les paramètres sont très importants, ils conditionnent les résultats. En effet, imaginons que les personnes puissent avoir un nombre d’amis égal au nombre de personnes dans la simulation et que toutes les personnes parlent la même langue, alors la distance les séparant serait nulle.

De ce fait, un certain nombre de paramètres permettent de « jouer » sur les résultats :

• Le nombre de personnes dans le monde: plus il y en a, plus les chemins risquent d’être longs. Il est fixé à 20 000.

• Le nombre de langues qu’il existe dans le monde : de même, plus il y a de langues, plus il y a de communautés difficiles à relier. Nous avons choisi 5 langues.

• Les nombres minimum et maximum d’amis qu’une personne peut avoir. Plus ces chiffres sont élevés, plus les chemins seront courts. Ce sont les paramètres à augmenter si le nombre de personnes est augmenté. Ils sont fixés à 5 pour le minimum et à 15 pour le maximum.

• Le taux de personnes bilingues : les bilingues permettent des liens entre les communautés. Plus il y a de langues, plus ce taux doit être important. Il est fixé à 20%.

Autrement dit, notre simulation peut être résumée comme suit : dans un monde de 20 000 personnes, parlant un total de 5 langues équitablement réparties, dont 20% sont bilingues, chaque personne ayant au moins 5 connaissances et au maximum 15, la théorie de Frigyes Karinthy est-elle vérifiée ?

4. Détermination du chemin le plus court

La plus grande difficulté de cette simulation réside dans la détermination du plus court chemin. L’idée est la suivante :

• La personne souhaitant connaitre la distance la séparant d’une autre va écrire un message. Ce message contiendra le nom de la personne destinatrice ainsi que le nom de la personne source. De plus, un espace sera réservé pour une liste de personnes intermédiaires.

• La source va alors s’ajouter aux intermédiaires et envoyer le message à tous ses amis.

• Les amis vont alors regarder à destination de qui est ce message. Chaque ami va alors vérifier le destinataire du message. Si c’est lui même, alors il le garde précieusement. Sinon, il le duplique, s’ajoute à la liste des intermédiaires et l’envoie aussi à tous ses amis.

• Si par hasard une personne recevait plusieurs fois le même message, alors elle regarderait la taille du chemin (taille de la liste des intermédiaires). Si celui-ci est plus court que les fois précédentes, alors elle le renverra à ses amis après s’être ajouté à la liste des intermédiaires, sinon, elle n’en fera rien.

• Ainsi de suite, jusqu’à ce que, s’il existe un chemin, le message arrive à destination.

• De cette manière, le destinataire peut recevoir plusieurs fois le même message, il les garde tous en les triant par ordre de taille de chemin croissant.

Conclusion

Concernant les résultats, ils sont conformes à nos attentes. Les chemins sont dans la majorité d’une longueur inférieure ou égale à 5 intermédiaires. Néanmoins, il faut nuancer ceci. En effet, comme nous l’avons montré dans la première partie, ils sont conditionnés par les valeurs globales choisies (nombre de personnes dans le monde, taux de bilingues, etc.). Donc, « dans un monde de 20 000 personnes, parlant un total de 5 langues équitablement réparties, dont 20% sont bilingues, chaque personne ayant au moins 5 connaissances et au maximum 15 » la théorie de Frigyes Karinthy est vérifiée.

Concernant l’application et son développement, nous sommes particulièrement satisfaits du système de détermination du chemin le plus court. En effet, celui-ci est très orienté « SMA » et il reflète ce qui pourrait réellement se passer si cette expérience était effectuée grandeur nature.

Pour le plaisir, une dernière copie d’écran avec deux personnes observables :

Après un long moment d’inactivité, voici une réalisation à laquelle j’ai énormément contribuée.

Extrait du cahier des charges :

La construction d’une table de reconnaissance LR0 répond à un besoin bien précis dans la phase de conception d’un compilateur : l’analyse syntaxique. Selon la complexité de la grammaire, la table LR0 pourrait ne pas être suffisante pour une analyse syntaxique complète, il faudrait envisager dans ce cas là une table LR1 ou LALR. De plus, on dit d’une grammaire qu’elle est compatible avec une analyse LR si :

• Les alternatives ont été supprimées,
• Un axiome supplémentaire a été rajouté.

Notre travail est donc d’établir cette table à partir des productions d’une grammaire donnée. Si, au cours du programme, il apparaissait que la grammaire est ambigüe, un message d’erreur le signalera, mais n’empêchera pas le programme de se terminer. Il en résultera une table non exploitable telle quel.

En plus d’être fournie au groupe chargé de l’analyse syntaxique, il convient de la fournir sous un format très facilement compréhensible afin de vérifier manuellement sa validité. La construction d’une table LR0 se répartit de la manière suivante :

• Suppression des alternatives,
• Ajout de l’axiome pour obtenir une grammaire augmentée,
• Déduction de la collection d’item initiale issue de la grammaire augmentée grâce à fermeture(I) ou I est l’axiome ajouté,
• Détermination de la table des fermetures,
• Déduction de la table des transitions,
• Détermination des suivants,
• Construction de la table LR0 à partir de la table des transitions et des suivants.

Ce mini projet a été réalisé en Java, voici toutes les ressources :

• Le programme (java 1.5) et ses sources : lr0.jar
• Les librairies jdom [site] et jxl [site]
• La javadoc
• Le rapport complet en pdf, avec les sources (88 pages) : lr0.pdf

Toutes les remarques seront les bienvenues.

Dans le cadre d’un mini-projet, nous avons choisi de mettre en place un réseau Peer-to-Peer centralisé. Ce réseau est donc composé d’un serveur et de clients devant s’y connecter lors de la recherche de fichiers. Ce réseau est implémenté en RMI afin de faciliter les communications entre les différents éléments. Les principes de transfert de données basiques tels que l’utilisation de sockets sont ainsi masqués.

Notre implémentation permet :

• La recherche de fichier selon un mot clé,

• Le téléchargement d’un fichier depuis plusieurs sources simultanément,

• Le téléchargement de plusieurs fichiers simultanément,

• La reprise du téléchargement d’un fichier partiellement téléchargé,

• La déconnexion « sauvage » des clients.

Néanmoins, il n’est pas possible :

• De partager des parties de fichier non complet (un fichier en cours de téléchargement ne peut être téléchargé par d’autres peers simultanément),

• De contrôler les vitesses d’émission et de réception.

Nous pouvons néanmoins ajouter que l’architecture de notre application ne poserait aucun problème à qui voudrait implémenter ces fonctionnalités.

Le client (jar executable, incluant jdom et fast md5)
Le serveur (jar executable)
Les sources du client et du serveur (incluant jdom et fast md5)
Le rapport

Quel développeur n’utilise pas « e.printStrackTrace()»  ou « System.out.println(e)»  ? Ceci est très pratique, voir indispensable lors de l’écriture d’un programme. Mais que devient le sort de ces instructions lors de l’utilisation de l’application une fois finie ? Au mieux, quelques lignes incompréhensibles par l’utilisateur si l’application a été lancée dans un terminal, sinon rien. Au final, un cas non prévu par le développeur qui peut entrainer un bug.

Un solution consiste à afficher l’erreur dans une fenêtre plutôt que dans la console. Pour ce faire, j’ai écrit une méthode permettant d’afficher une exception et son détail dans un JOptionPane et de laisser le choix à l’utilisateur de continuer ou d’interrompre l’exécution du programme.

Voici le code source permettant d’afficher l’exception :

import java.awt.BorderLayout;
import java.awt.FlowLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.PrintWriter;
import java.io.StringWriter;

import javax.swing.BorderFactory;
import javax.swing.JButton;
import javax.swing.JComponent;
import javax.swing.JDialog;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;

/**
 *
 * @author Romain Bouleis
 *
 */
public class Tools {
	public static void showError(Exception e) {
		//stock la trace d'execution dans une String
		StringWriter sw = new StringWriter();
		e.printStackTrace(new PrintWriter(sw));

		//cree un JTextArea pour afficher le contenu de l'exception
		JTextArea textArea = new JTextArea(sw.toString(),20,40);
		textArea.setEditable(false);
		textArea.setBorder(BorderFactory.createTitledBorder("Détails de l'exception"));
		final JScrollPane scrollPane = new JScrollPane(textArea);
		scrollPane.setVisible(false);

		//boutton details
		JButton details = new JButton("Détails...");
		details.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) {
				scrollPane.setVisible(!scrollPane.isVisible());
				JDialog dialog =  (JDialog) ((JComponent) e.getSource()).getRootPane().getParent();
				dialog.pack();
			}
		});

		//boutton continuer
		JButton ok = new JButton("Continuer");
		ok.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) {
				JDialog dialog =  (JDialog) ((JComponent) e.getSource()).getRootPane().getParent();
				dialog.dispose();
			}
		});

		//boutton exit
		JButton cancel = new JButton("Arrêter");
		cancel.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) {
				System.exit(0);
			}
		});

		//placement des composants
		JPanel buttonsPanel = new JPanel(new FlowLayout());
		buttonsPanel.add(ok);
		buttonsPanel.add(cancel);
		buttonsPanel.add(details);

		JPanel mainPanel = new JPanel(new BorderLayout());
		mainPanel.add(scrollPane, BorderLayout.CENTER);
		mainPanel.add(buttonsPanel,BorderLayout.SOUTH);

		//affichage du message
		JOptionPane.showOptionDialog(null, e.getMessage(), "Erreur", JOptionPane.OK_OPTION, JOptionPane.ERROR_MESSAGE, null, new Object[]{mainPanel}, ok);
	}

	public static void main(String[] args) {
		Tools.showError(new Exception("Une erreur !"));
	}
}

Désormais, vos « try-catch»  ressembleront plutôt à ceci :

try {
	int error = 69/0;
} catch (Exception e) {
	Tools.showError(e);
}

Simulation d’un système de drainage dans une mine en C++ et MPI avec une interface en Java

On s’intéresse ici à la réalisation d’un système de commande assurant une fonction de drainage dans une mine. Le but de ce système est de réguler le niveau d’eau au fond de la mine, par la mise en route d’une pompe lorsqu’un certain seuil (« niveau-eau-haut ») est atteint voir dépassé et ceci jusqu’à ce qu’il soit ramené au niveau d’un autre seuil (« niveau-eau-bas »).
La pompe ne doit toutefois pas fonctionner si les niveau en gaz toxiques présents dans la galerie, méthane et monoxyde de carbone, sont supérieurs à certains seuils (« seuil-CH4 » et « seuil CO »). Un ventilateur permet donc, lorsque cela est nécessaire, d’évacuer ces gaz vers la surface. On souhaite par ailleurs minimiser l’utilisation du ventilateur.

Seront utilisés pour modéliser ce système :

• MPI pour la communication en entre les différents processus (pompe, capteurs, ventilateur…)
• C++ comme langage de développement pour l’applicatif
• Le langage Java avec Swing pour l’interface graphique
• Les threads et les sockets en C++ et en Java pour la communication entre l’applicatif et l’interface

Le rapport avec les sources en annexe.

Reprendre la copie d’un fichier en Java

Voici une petite fonction dont le but est de copier un fichier, et le résumer si il existe déjà. Cette solution est très basique, et son implémentation demanderai quelques contrôles supplémentaires comme par exemple s’assurer que la taille du fichier de destination ne soit pas supérieur à celle du fichier source. Voici donc cette fonction :

public class FileTransfert {

	public static void resume(File in, File out) throws IOException {
		FileInputStream fis  = new FileInputStream(in);
		FileOutputStream fos = new FileOutputStream(out,true);

		try {
			int i;
			byte[] buf = new byte[1024];
			fis.skip(out.length());
			while ((i = fis.read(buf)) != -1) {
				fos.write(buf,0, i);
				//System.out.println(out.length());
			}
		}
		catch (IOException e) {
			e.printStackTrace();
		}
		finally {
			if (fis != null)  fis.close();
			if (fos != null) fos.close();
		}
	}

	public static void main(String args[]) {
		try {
			resume(new File("/home/rb/test"), new File("/home/rb/test2"));
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

Un peu plus sur les transferts de fichiers en Java ici .

Lors de la réalisation d’une application, j’ai été confronté au problème suivant : faire communiquer Java et C++. Il existe plusieurs moyen pour parvenir à cela :

• L’utilisation des pipes
• L’utilisation d’un fichier commun
• L’utilisation des stdin et stdout
• L’utilisation d’une solution réseau : corba, socket…

C’est cette dernière solution que j’ai choisi et dont ce billet va traiter.

Lors de ce type de communication, il faut nécessairement un serveur et un client. Le serveur devra être exécuté avant le client qui s’y connectera. Une fois la connexion établie, il n’y a plus de différences entre le client et le serveur, les deux attendront un éventuel message, et les deux seront prêt à en émettre.

Pour pouvoir se faire (être prêt à émettre et à recevoir en même temps), le client et le serveur devront être multithread, un thread sera chargé d’attendre un message et un autre d’en envoyer.

Dans cet exemple, l’application Java aura le rôle de serveur, et application C++ aura le rôle de client. Si vous comprenez bien le mécanisme, vous n’aurez pas de mal à les intervertir.

Tout d’abord, intéressons nous au serveur (Serveur.java)

Pour faire un Thread en Java, une méthode consiste à faire une classe qui étend de « Thread»  et qui redéfinit la méthode « run» . Le contenu de cette méthode sera celui exécuté par le thread. Dans notre cas, cette méthode devra attendre qu’un client se connecte puis attendra un éventuel message :

/**
 *
 * @author Romain Bouleis www.bouleis.fr
 *
 */
public class Server extends Thread{
	private int port;
	private boolean run = true;
	private PrintWriter out;
	private BufferedReader in;
	public Server(int port) {
		this.port = port;
	}
	/**
	 * {@docRoot} start the server
	 */
	public void run() {
		ServerSocket server;
		Socket client;
		try {
			//crée un nouveau socket
			server = new java.net.ServerSocket (this.port);
			//attend un client
			client  = server.accept();
			System.out.println("[Server] client connected");
			//writer sur le socket
			out = new PrintWriter(client.getOutputStream(), true);
			//reader sur le soket
			in  = new BufferedReader (new InputStreamReader(client.getInputStream()));
			String msg = "";
			//tant que le serveur est actif et que le client est connecte
			while(this.run && msg != null) {
				//attend un message
				msg = in.readLine();
				//traiter le message
				System.out.println("[server] message reçu : "+msg);
				//arete le serveur si le message est "exit"
				if("exit".equals(msg)) this.run = false;
			}
			//ferme le reader et le writer
			out.close();
			in.close();
			//ferme le socket
			client.close();
			server.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	public static void main(String args[]) {
		Server s = new Server(8000);
		s.start();
	}
}

Ce code executera un serveur attendant un client sur le port 8000. Pour pouvoir envoyer un message à un éventuel client, il faut rajouter une méthode :

public void sendCommand(String c) {
	if(out != null) out.println(c);
	else System.err.println("no client");
}

public static void main(String args[]) {
	Server s = new Server(8000);
	s.start();
	//attendre la connexion d'un client
	s.sendCommand("envoie de cette ligne au client");
}

On peut tester le serveur grâce à telnet : telnet localhost 8000. Lors d’envoie de messages, ils devraient s’afficher dans la console depuis laquelle le serveur a été lancé.

Intéressons nous maintenant au client. De la même façon, un thread sera crée pour attendre des messages du serveur.

#define SOCKET_PORT 8000

using namespace std;

int socketDescriptor;

Client::Client() { }

//se connecte au serveur
void Client::init(char* socket_host) {
	struct sockaddr_in serverAddress;
	struct hostent *hostInfo;

	cout << "[Client] connecting..." <<
	//Choix de l'hôte
  	hostInfo = gethostbyname(socket_host);
 	if (hostInfo == NULL) {
    	cout << "[Client] problem interpreting host: " <<
		exit(1);
 	}

	// Creation du socket.
  	socketDescriptor = socket(PF_INET, SOCK_STREAM, 0);
  	if (socketDescriptor < 0) {
   		cerr << "[Client] cannot create socket\n";
    	exit(1);
  	}

	serverAddress.sin_family = hostInfo->h_addrtype;
  	memcpy((char *) &serverAddress.sin_addr.s_addr,
    hostInfo->h_addr_list[0], hostInfo->h_length);
  	serverAddress.sin_port = htons(SOCKET_PORT);
 	memset(serverAddress.sin_zero, '\0', sizeof serverAddress.sin_zero);

	connect(socketDescriptor, (struct sockaddr *)&serverAddress, sizeof(serverAddress));

	cout << "[Client] connected to server" <<
}

//cree un thread executant la methode runWaitMessage
pthread_t Client::runWaitMessageThread() {
	pthread_t attente;
	(void) pthread_create(&attente, NULL, Client::runWaitMessage, (void*) &socketDescriptor);
	return attente;
}

//attends des messages
void * Client::runWaitMessage(void * args) {
	cout << "[Client] Waiting messages thread running..." <
	char line[255];
	memset(line, '\0', sizeof(line));
	while(recv(socketDescriptor, line, sizeof(line), 0) > 1) {
		//remove the \n at the end of the string
		unsigned int i=0;
		char line_[strlen(line)-1];
		for(i=0;i<strlen(line);i++)
			line_[i] = line[i];
		}
		line_[i] = '\0';
		cout << "[Client] " << line_ << " received" <<

		//on traite le message

		memset(line, '\0', sizeof(line));
	}
	return (void *) 1;
}

//send a command
void Client::sendCommande(string s) {
	char * message;
	string s_ = s;
	s += "\r\n";
	message = (char *) s.c_str();
	send(socketDescriptor,message,strlen(message),0);
	cout << "[Client] " << s_ << " sent" <
}

//close the socket
void Client::closeClient() {
	close(socketDescriptor);
	cout << "[Client] disconnected" <<
}

Enfin, on peut lancer le client avec la méthode suivante :

int main(int argc, char* argv[]) {
	Client *client = new Client();
	client->init("localhost");
	client->runWaitMessageThread();
	client->sendCommande(message);
}

Cette application écrite en Java tri des mails fictifs grâce à l’interconnexion de multiples Agents (Thread).

Un agent a pour « mission » de récupérer les mails dans la liste d’attente et de vérifier si il satisfait une règle
interne. Si la règle est satisfaite (par exemple, que le sujet du mail ne contienne pas le mot « drugs »), alors
l’agent donne le mail à l’agent suivant qui va faire de même. Si la règle n’est pas satisfaite, alors le mail sera
mis dans la liste de spams. Enfin, le dernier agent, si sa règle est satisfaite elle aussi, mettra le mail dans la boite
de réception.

le rapport complet : ici
l’application et les sources (java 1.6) : ici

Afin de matérialiser la gestion d’un carrefour, nous avons imaginé une application modulable mettant en scène des voitures circulants sur plusieurs routes sur lesquelles sont placés des feux. Ce compte rendu présente cette application, son développement, ses avantages et ses (quelques) inconvénients ainsi que, en guise de conclusion, un avis personnel sur l’ensemble du sujet traité.

Le rapport complet : ici
Le jar executable avec les sources (java 1.5 min) : ici