import java.util.Collection;import java.util.HashSet;import java.util.Iterator;/* classinvariants are valid for every method (except constructor) and therefor not mentioned again! classinvariant 1: Every nodename is unique. classinvariant 2: Every edgename is unique between two nodes and his direction. classinvariant 3: After instance is created, nodesList and edgelist are never null (but can be empty) classinvariant 4: Nodes with edges cannot be deleted. */public class GenGraph<Knotenname, Kantenname> { private Collection<Knoten<Knotenname>> nodeslist; private Collection<Kante<Kantenname>> edgelist; /* * postcondition: New graph is created. The nodeslist and edgelist are not * null, but empty. */ public GenGraph() { this.nodeslist = new HashSet<Knoten<Knotenname>>(); this.edgelist = new HashSet<Kante<Kantenname>>(); } /* * precondition: The parameter nodename is not null. postcondition: Return * value is true, if the GenGraph contains the nodename, otherwise false. */ private boolean containsNode(Knotenname nodename) { try { getNode(nodename); return true; } catch (NodeNotFoundException nnf) { return false; } } /* * * precondition: The parameter nodename is not null postcondition: The node * for the given nodename is returned or a NodeNotFoundException is thrown. */ protected Knoten<Knotenname> getNode(Knotenname nodename) throws NodeNotFoundException { Iterator<Knoten<Knotenname>> nodeiter = this.nodeslist.iterator(); while (nodeiter.hasNext()) { Knoten<Knotenname> node = nodeiter.next(); if (node.getName().equals(nodename)) return node; } throw new NodeNotFoundException(); } /* * precondition: The parameter start, end and caption are not null. * postcondition: Return value is true, if the GenGraph contains the edge, * otherwise false. */ private boolean containsEdge(Knotenname start, Knotenname end, Kantenname caption) throws NodeNotFoundException { try { if (getEdge(start, end, caption) != null) return true; } catch (NodeNotFoundException nnf) { } return false; } /* * precondition: The parameters start, end and caption are not null. * postcondition: The specified edge or null is returned or a * NodeNotFoundException is thrown. */ private Kante<Kantenname> getEdge(Knotenname start, Knotenname end, Kantenname caption) throws NodeNotFoundException { Knoten<Knotenname> startnode = this.getNode(start); Knoten<Knotenname> endnode = this.getNode(end); Kante<Kantenname> edgetofind = new Kante<Kantenname>(caption, startnode, endnode); Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator(); while (edgeiter.hasNext()) { Kante<Kantenname> edge = edgeiter.next(); if (edge.equals(edgetofind)) return edge; } return null; } /* * precondition: The parameters start and end are not null. postcondition: * The edge or null is returned or a NodeNotFoundException is thrown. */ private Collection<Kante<Kantenname>> getEdges(Knotenname start, Knotenname end) throws NodeNotFoundException { Collection<Kante<Kantenname>> result = new HashSet<Kante<Kantenname>>(); Knoten<Knotenname> startnode = this.getNode(start); Knoten<Knotenname> endnode = this.getNode(end); Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator(); while (edgeiter.hasNext()) { Kante<Kantenname> edge = edgeiter.next(); if ((edge.getStart().equals(startnode)) && (edge.getEnd().equals(endnode))) result.add(edge); } return result; } /* * postcondition: returns the Collection of edges for manipulation */ protected Collection<Kante<Kantenname>> getEdgeslist() { return this.edgelist; } /* * precondition: The parameter a is not null. postcondition: Return value is * a Collection with all outbound edges of a. */ protected Collection<Kante<Kantenname>> getOutboundEdges(Knoten<Knotenname> a) { Collection<Kante<Kantenname>> result = new HashSet<Kante<Kantenname>>(); Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator(); while (edgeiter.hasNext()) { Kante<Kantenname> edge = edgeiter.next(); if (edge.getStart().equals(a)) result.add(edge); } return result; } /* * precondition: The parameter a is not null. postcondition: Return value is * a Collection with all inbound edges of a. */ protected Collection<Kante<Kantenname>> getInboundEdges(Knoten<Knotenname> a) { Collection<Kante<Kantenname>> result = new HashSet<Kante<Kantenname>>(); Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator(); while (edgeiter.hasNext()) { Kante<Kantenname> edge = edgeiter.next(); if (edge.getEnd().equals(a)) result.add(edge); } return result; } /* * precondition: The parameter a is not null. postcondition: Return value is * true, if node a has successor nodes, otherwise false, or throws a * NodeNotFoundException, if a is not contained in the nodeslist. */ protected boolean nodeHasSuccessors(Knoten<Knotenname> a) throws NodeNotFoundException { if (!this.containsNode(a.getName())) { throw new NodeNotFoundException(); } Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator(); while (edgeiter.hasNext()) { Kante edge = edgeiter.next(); if (edge.getStart().equals(a)) return true; } return false; } /* * precondition: The parameter a is not null. postcondition: Return value is * true, if node a has predecessor nodes, otherwise false, or throws a * NodeNotFoundException, if a is not contained in the nodeslist. */ protected boolean nodeHasPredecessors(Knoten<Knotenname> a) throws NodeNotFoundException { if (!this.containsNode(a.getName())) { throw new NodeNotFoundException(); } Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator(); while (edgeiter.hasNext()) { Kante edge = edgeiter.next(); if (edge.getEnd().equals(a)) return true; } return false; } /* * precondition: The parameter nodename is not null and postcondition: The * node is added to the nodeslist. */ public boolean addNode(Knotenname nodename) { if (containsNode(nodename)) { return false; } return this.nodeslist.add(new Knoten<Knotenname>(nodename)); } /* * precondition: The parameter nodename is not null and postcondition: The * node is deleted from the nodeslist. */ public boolean deleteNode(Knotenname nodename) throws NodeNotFoundException { Knoten<Knotenname> node = getNode(nodename); if ((!nodeHasPredecessors(node)) && (!nodeHasSuccessors(node))) return this.nodeslist.remove(node); else return false; } /* * precondition: The parameters are not null. postcondition: A new edge is * addet to the edgelist. */ public boolean addEdge(Knotenname start, Knotenname end, Kantenname caption) throws NodeNotFoundException { if (containsEdge(start, end, caption)) { return false; } Knoten<Knotenname> startnode = this.getNode(start); Knoten<Knotenname> endnode = this.getNode(end); Kante<Kantenname> newEdge = new Kante<Kantenname>(caption, startnode, endnode); return this.edgelist.add(newEdge); } /* * precondition: The parameters are not null. postcondition: The edge is * deleted from the edgelist. */ public boolean deleteEdge(Knotenname start, Knotenname end, Kantenname caption) throws NodeNotFoundException { return this.edgelist.remove(this.getEdge(start, end, caption)); } /* * precondition: The parameter nodename is not null. postcondition: Return * value is a Iterator with all successor nodes. */ public Iterator<Knotenname> getSuccessors(Knotenname nodename) throws NodeNotFoundException { Knoten<Knotenname> node = this.getNode(nodename); Collection<Kante<Kantenname>> outboundEdges = this .getOutboundEdges(node); Collection<Knotenname> successors = new HashSet<Knotenname>(); Iterator<Kante<Kantenname>> edgeiter = outboundEdges.iterator(); while (edgeiter.hasNext()) { successors.add(edgeiter.next().getEnd().getName()); } return successors.iterator(); } /* * precondition: The parameter nodename is not null. postcondition: Return * value is a Iterator with all predecessor nodes. */ public Iterator<Knotenname> getPredecessors(Knotenname nodename) throws NodeNotFoundException { Knoten<Knotenname> node = this.getNode(nodename); Collection<Kante<Kantenname>> inboundEdges = this.getInboundEdges(node); Collection<Knotenname> predecessors = new HashSet<Knotenname>(); Iterator<Kante<Kantenname>> edgeiter = inboundEdges.iterator(); while (edgeiter.hasNext()) { predecessors.add(edgeiter.next().getStart().getName()); } return predecessors.iterator(); } /* * postcondition: Return value is a Iterator with all nodes of the GenGraph. */ public Iterator<Knotenname> getNodenames() { Collection<Knotenname> nodenames = new HashSet<Knotenname>(); Iterator<Knoten<Knotenname>> nodeiter = this.nodeslist.iterator(); while (nodeiter.hasNext()) { nodenames.add(nodeiter.next().getName()); } return nodenames.iterator(); } /* * precondition: The parameter start and end are not null. postcondition: * Return value is a Iterator with all edges, between start and end node. */ public Iterator<Kantenname> getEdgeNames(Knotenname start, Knotenname end) throws NodeNotFoundException { Collection<Kantenname> result = new HashSet<Kantenname>(); Iterator<Kante<Kantenname>> edgeiter = this.getEdges(start, end) .iterator(); while (edgeiter.hasNext()) { result.add(edgeiter.next().getName()); } return result.iterator(); } /* * A nested class to represent nodes. A node is identified by its name. * * classinvariant 1: Every node has a name, which is not null. */ @SuppressWarnings("hiding") protected class Knoten<Knotenname> { private Knotenname name; /* * precondition: The parameter name is not null . postcondition: A new * node is created. */ public Knoten(Knotenname name) { this.name = name; } /* * postcondition: Returns a nodes nameobject. */ public Knotenname getName() { return this.name; } /* * precondition: The parameter node a is not null. postcondition: Return * value is true, if the node names are equal, otherwise false. */ public boolean equals(Knoten a) { return this.name.equals(((Knoten) a).getName()); } } /* * A nested class to represent edges between nodes. A edge is identified by * its name, the start and the end node. * * classinvariant 1: Every edge has a name, a start and a end node, which * are not null. */ @SuppressWarnings("hiding") protected class Kante<Kantenname> { private Kantenname name; private Knoten<Knotenname> start; private Knoten<Knotenname> end; /* * precondition: The paramters name, start and end are not null. * postcondition: A new edge is created. */ protected Kante(Kantenname name, Knoten<Knotenname> start, Knoten<Knotenname> end) { this.name = name; this.start = start; this.end = end; } /* * postcondition: Return value is the edge name. */ protected Kantenname getName() { return name; } /* * postcondition: Return value is the start node of the edge. */ protected Knoten<Knotenname> getStart() { return start; } /* * postcondition: Return value is the end node of the edge. */ protected Knoten<Knotenname> getEnd() { return end; } /* * precondition: The paramter edge a is not null. postcondition: Return * value is true, if the edge names, the start and end nodes are equal. */ protected boolean equals(Kante a) { if ((a.getName().equals(this.name)) && (a.getStart().equals(this.start)) && (a.getEnd().equals(this.end))) return true; else return false; } }}