Discussion :

[aragog]

Bonsoir.

J'ai un projet de fin de semestre à réaliser en théorie des graphes, et je me vois être obligé de développer deux méthodes permettant de sauvegarder/charger mon graphe (connexe ou non).

Par conséquent, et dans cette optique, j'aurais souhaité savoir si certains d'entre vous pouvaient me diriger vers des documentations ou des exemples de tels procédés. Je n'attends pas de code.

Merci d'avance pour votre aide.

[zhouyu]

Salut pour le avant de charger/sauvegarder il va déjà te falloir une structure qui représentera ton graphe et une pour tes noeuds. Recherche du coté des arbres c'est assez proche. Pour la méthode de sauvegarde chargement tu devrais trouver quelque chose de simple pour le sauver/charger en xml.
Pour la deuxième je ne sais, tu peux en faire une méthode maison qui te sauve ton graphe dans un .txt mais ce sera à toi de faire l'algo de sauvegarde (le chargement etant très similaire).
Bon courage .

[aragog]

Merci pour ta réponse.

Ma structure est déjà spécifiée et implantée (graphes, sommets, arêtes).
Quant à la méthode de sauvegarde/chargement, en effet elle peut-être faite maison, mais je me disais qu'un gars bien plus futé que moi avait certainement déjà trouvé une méthode pour ce genre de problème.

Recherche du coté des arbres c'est assez proche

J'ai l'impression que le codage de Prüfer se porterait mal, à moins que cela ne soit possible ? Auquel cas, je m'y mets de suite.

Bon courage.

Merci.

[sinok]

http://graphml.graphdrawing.org/

(par contre, ce sera probablement plus complexe que ce dont tu as besoin).


Sinon, de base, dans xml il existe les notions d'ID/IDRef.

Donc tu crées des tags nods qui contiennent un attribut/élément id de type xs:ID, des informations et une liste de liens qui contiennent chacun un attribut/élément de type xs:IDREF.


Par contre, ouaip, c'est sur, XML c'est particulièrement verbeux comme schéma.


Un peu plus d'infos: http://sta.uwi.edu/staff/mbernard/re...ileformats.pdf

[kolodz]

Si ton graphe est un objet sérialisable, je pense que tu va trouver ça simple :
http://java.developpez.com/faq/java/..._serialisation

Cordialement,
Patrick Kolodziejczyk.

Edit : La solution XML est sympathique, mais pas forcément nécessaire.
Re-edit: fallait être plus rapide =)

[ced00]

Si ton graphe est représenté par un objet, tu peux essayer de le sérialiser ?

Edit : grillé de 4 secondes.....

[aragog]

Merci beaucoup pour toutes vos réponses.

XML me semble en effet extrêmement complet, peut-être trop au vu du projet.
Enfin, la sérialisation me parait très simple mais (peut-être à tort) trop peu optimisée.

Je crains qu'il ne faille réinventer la roue afin de créer un format bien plus amateur mais aussi plus simple et économe.

De fait, je vous remercie tous encore une fois, je reposte un message dès que j'ai quelque chose de correct.

[sinok]

Au niveau GraphML tu n'as pas que des formats XML de définis.
Pour le coup, le GML est moins lourd que du XML.

[aragog]

Merci beaucoup, et sois-sûr que je te crois sur parole. Cependant, le problème est que je ne peux me lancer dans de telles expéditions (pourtant excitantes) en effet, je me dois de garder du temps pour les examens.

Dans cette optique, j'ai créé un petit format trèèès artisanal mais qui comble amplement mes attentes. Il est basé sur l'une des deux représentations archi-classiques des graphes : la représentation par listes d'adjacences.

Ainsi donc, si mon graphe non orienté est de la forme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
1            7
 \          /
  2--4--5--6          
 /          \
3            8

le fichier texte pourrait avoir cette tête :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
1 : 2
2 : 1 3 4
3 : 2
4 : 2 5
5 : 4 6
6 : 5 7 8
7 : 6
8 : 6

"Pourrait" car l'ordre dans lequel apparaisse les sommets n'a pas la moindre importance.

EDIT : Suppression des codes, je les remettrais sur le forum une fois les soutenances passées afin qu'ils puissent aider d'autres personnes.

[zhouyu]

Pour ton test ça depend comment compare le contain de ton HashSet.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

System.out.println(edge.equals(edgeb));

c'est pas edgea ? ^^

Pour voir si c'est le contain qui n'appelle pas ton equals fait une boucle qui parcourt les elements du HashSet et qui test si l'element en cour est egal à ton objet.

Si ta boucle fonctionne c'est qu'il faut que tu fasses ta methode ou une surcharge du HashSet.

Regarde dans le doc comment fonctionne contain dans HashSet .

[aragog]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Node<String> nodea = new StdNode<String>("a");
Node<String> nodeb = new StdNode<String>("b");
Edge<String> edgea = new StdEdge<String>(nodea, nodeb);
Edge<String> edgeb = new StdEdge<String>(nodeb, nodea);
Set<Node<String>> set = new HashSet<Node<String>>();
set.add(nodea);
set.add(nodeb);
Set<Edge<String>> set2 = new HashSet<Edge<String>>();
set2.add(edgea);
set2.add(edgeb);
for (Edge<String> edge : set2) {
    System.out.println(edgeb.equals(edge) + " " + edgeb.compareTo(edge));
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
true 0
true 0

La doc me dit ceci :

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e))

Que dois-je faire ? Hashcode, equals et compareTo sont consistantes, je n'ai plus d'idée.

EDIT : je me suis fais ma propre méthode de comparaison, seulement, et forcément, je suis en O(n) plutôt qu'en O(1). Je perds les avantages de mon ensemble.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
public boolean contains(Edge<E> edge) {
    if (edge == null) {
        throw new IllegalArgumentException();
    }
    for (Edge<E> e : edgesSet) {
        if (e.equals(edge)) {
	    return true;
	}
    }
    return false;
}

Alors que de base, j'avais seulement ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
public boolean contains(Edge<E> edge) {
    return edgesSet.contains(edge);
}

[zhouyu]

d'accord avant tu n'avais qu'une ligne mais que crois tu que la fonction faisait? pour un contain je pense qu'il parcourt les éléments aussi, surtout au vu de la doc où il cherche un element e correspondant.
Ca fonctionne maintenant ?

[aragog]

Aïe, pour moi l'intérêt d'avoir inventé une nouvelle structure (un ensemble), c'est de pouvoir tester l'appartenance d'un élément à ce dernier en temps constant (facilement reproductible en Turbo Pascal voire en C ou même en Ocaml d'ailleurs).

De plus, quant aux collections de Java, ce site semble appuyer mon pressentiment : http://blog.xebia.fr/2011/02/17/java...n-performance/

Maintenant, oui en effet, ça fonctionne, même très bien. Cependant, je suis intimement convaincu que je perds en vitesse (O(n) sur 10 éléments c'est bien, mais sur 100000, ça commence à se faire ressentir [à comparer avec du O(1)]).

Enfin, et c'est surtout ce qui me gêne le plus, je ne comprends pas d'où vient l'erreur, et ça, ça m'ennuie vraiment.

[aragog]

Bon j'ai enfin compris.

Pour ceux que ça intéresseraient encore, voici la solution :

Soient :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Node<Integer> node1  = new StdNode<Integer>(1);
Node<Integer> node2  = new StdNode<Integer>(2);
Edge<Integer> edgea = new StdEdge<Integer>(node1, node2);
Edge<Integer> edgeb = new StdEdge<Integer>(node2, node1);

Avec la méthode de hashcode que je vous ai présenté, ses valeurs diffèrent alors que edgea.equals(edgeb), ce qui n'est pas terrible (la preuve) puisqu'il est recommandé que x.equals(y) => x.hashcode() == y.hashcode().

En effet :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
edgea.hashcode() == 1986
edgeb.hashcode() == 2016

C'était aussi bête que ça.

Je vous remercie tous pour votre aide et merci encore à zhouyu pour sa pugnacité.

Bonne soirée à vous.

PS : il me semble d'ailleurs, maintenant que j'y pense, que quand on fait (en prenant l'exemple d'une table de hachage) ajouter(k, v), la JVM recherche k la clé avec k.hashcode().

[zhouyu]

Merci pour la solution ça m'interpellait aussi