package graphs;import java.io.*;import java.lang.*;import java.util.*;public class ListGraph<E> implements Graph<E>, Serializable{ private HashMap<E, LinkedList<Edge>> noder = new HashMap<E, LinkedList<Edge>>(); public void addNode(E nod) { if (noder.get(nod) != null) return; noder.put(nod, new LinkedList<Edge>()); } public void connect(E nod1, E nod2, String namn, int vikt) throws NoSuchElementException, IllegalArgumentException, IllegalStateException { if (noder.get(nod1) == null) throw new NoSuchElementException(nod1.toString()); if (noder.get(nod2) == null) throw new NoSuchElementException(nod2.toString()); if (vikt < 0) throw new IllegalArgumentException("Vikt är negativ!"); // Ta fram noderna till varje nod, och kolla om det finns // en kant mellan dem. LinkedList<Edge> l1 = noder.get(nod1); LinkedList<Edge> l2 = noder.get(nod2); if (finnsEdge(l1, nod2) || finnsEdge(l2, nod1)) throw new IllegalStateException( "Det finns redan en kant mellan dessa noder!"); // Om det inte finns någon kant mellan dem, lägg till. Edge e1 = new Edge(namn, vikt, nod2); l1.add(e1); noder.put(nod1, l1); Edge e2 = new Edge(namn, vikt, nod1); l2.add(e2); noder.put(nod2, l2); } private boolean finnsEdge(LinkedList<Edge> l, E till) { return hittaEdge(l, till) != null; } private Edge hittaEdge(LinkedList<Edge> l, E till) { for (Edge e : l) { if (e.getNod() == till) { return e; } } return null; } public LinkedList<E> getNodes() { LinkedList<E> lista = new LinkedList<E>(); Set<Map.Entry<E, LinkedList<Edge>>> set = noder.entrySet(); Iterator<Map.Entry<E, LinkedList<Edge>>> i; for (i = set.iterator(); i.hasNext(); ) { Map.Entry<E, LinkedList<Edge>> e = i.next(); lista.add((E) e.getKey()); } /* Iterator<E, Edge> i; for (i=noder.iterator(); i.hasNext(); ) { lista.add(i.next()); } */ return lista; } public LinkedList<Edge> getEdgesFrom(E nod) throws NoSuchElementException { if (noder.get(nod) == null) throw new NoSuchElementException(nod.toString()); return noder.get(nod); } public String getEdgeName(E nod1, E nod2) throws NoSuchElementException // null { finnsNoder(nod1, nod2); Edge e = hittaEdge(noder.get(nod1), nod2); if (e == null) return null; return e.getNamn(); } public int getEdgeWeight(E nod1, E nod2) throws NoSuchElementException // -1 { finnsNoder(nod1, nod2); Edge e = hittaEdge(noder.get(nod1), nod2); if (e == null) return -1; return e.getVikt(); } public void setEdgeWeight(E nod1, E nod2, int nyVikt) throws NoSuchElementException, IllegalArgumentException { finnsNoder(nod1, nod2); if (nyVikt < 0) throw new IllegalArgumentException("Vikt är negativ!"); Edge e = hittaEdge(noder.get(nod1), nod2); if (e == null) throw new NoSuchElementException("Finns ingen edge mellan!"); e.setVikt(nyVikt); } private void finnsNoder(E nod1, E nod2) throws NoSuchElementException // -1 { if (noder.get(nod1) == null) throw new NoSuchElementException(nod1.toString()); if (noder.get(nod2) == null) throw new NoSuchElementException(nod2.toString()); } public String toString() { String text = ""; Set<Map.Entry<E, LinkedList<Edge>>> entries = noder.entrySet(); for (Map.Entry<E, LinkedList<Edge>> me : entries) { E e = me.getKey(); LinkedList<Edge> l = me.getValue(); text += "from " + e.toString() + ": "; int i = 0; for (Edge edge : l) { text += edge.toString(); if (l.size() > 1 && i < l.size() - 1) text += ", "; i++; } text += "\n"; } return text; } // Frivilligt public void disconnect(E nod1, E nod2) throws NoSuchElementException { finnsNoder(nod1, nod2); LinkedList<Edge> l1 = noder.get(nod1); LinkedList<Edge> l2 = noder.get(nod2); Edge e1 = hittaEdge(l1, nod2); Edge e2 = hittaEdge(l2, nod1); if (e1 != null && e2 != null) { taBortEdge(l1, nod2); taBortEdge(l2, nod1); } } private void taBortEdge(LinkedList<Edge> l, E till) { Iterator<Edge> i; for (i = l.iterator(); i.hasNext(); ) { Edge e = i.next(); if (e.getNod() == till) { i.remove(); return; } } } public void removeNode(E nod) { noder.remove(nod); } public boolean pathExists(E nod1, E nod2) { if (noder.get(nod1) == null || noder.get(nod2) == null) return false; HashMap<E, Boolean> wrap = new HashMap<E, Boolean>(); pathExists(nod1, wrap); return wrap.get(nod2) != null && wrap.get(nod2); } private void pathExists(E nod, HashMap<E, Boolean> wrap) { wrap.put(nod, new Boolean(true)); for (Edge e : noder.get(nod)) { E n = (E) e.getNod(); if (wrap.get(n) == null || !wrap.get(n)) pathExists(n, wrap); } } public LinkedList<E> getShortestPath(E nod1, E nod2) { return null; }}