package graphe; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; public class GrapheOrienteImpl implements GrapheOriente { /* * Un graphe est codŽ ˆ l'aide de deux tables : successions et precedences. * * Dans ces deux tables, les entrŽes sont tous les sommets du graphe. * * A chaque sommet s est associŽ une table successions.get(s) et une table * precedences.get(s), Žventuellement vides si s n'a pas de successeur ou de * predecesseur. * * Dans successions.get(s) (resp. precedences.get(s)), les entrŽes sont les * successeurs (resp. predecesseurs) de s. Si t est un successeur (resp. un * predecesseur) de s, alors successions.get(s).get(t) (resp. * precedences.get(s).get(t) est l'ensemble des arcs de s vers t (resp. de t * vers s). */ private int m = 0; private Map>> successions = new HashMap>>(); private Map>> precedences = new HashMap>>(); protected boolean ajouterSommet(Object s) { if (successions.containsKey(s)) { // s est deja un sommet du graphe return false; } successions.put(s, new HashMap>()); precedences.put(s, new HashMap>()); return true; } protected boolean ajouterArc(Arc a) { Object o = a.origine(); Object d = a.destination(); if (!contient(o)) { ajouterSommet(o); } if (!contient(d)) { ajouterSommet(d); } Set succ = successions.get(o).get(d); Set prec = precedences.get(d).get(o); if (succ == null) { // Pas d'arc existant de o vers d succ = new HashSet(); successions.get(o).put(d, succ); prec = new HashSet(); precedences.get(d).put(o, prec); } if (prec.add(a)) { m++; } return succ.add(a); // true ssi a n'est pas deja presente. } /** * Cree un graphe oriente dont les sommets sont les elements de sommets * ainsi que les extremites des arcs non inclues dans sommets, et les arcs * les elements de arcs. */ public GrapheOrienteImpl(Object[] sommets, Arc[] arcs) { for (Object s : sommets) { ajouterSommet(s); } for (Arc a : arcs) { ajouterArc(a); } } }