SimpleGraph.java
SimpleGraph.java
—
Java source code,
2 KB (2812 bytes)
Dateiinhalt
package minijava.util; import java.io.PrintStream; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; public class SimpleGraph<NodeInfo> { private Set<Node> nodes = new HashSet<Node>(); private Map<Node, Set<Node>> successors = new HashMap<Node, Set<Node>>(); private Map<Node, Set<Node>> predecessors = new HashMap<Node, Set<Node>>(); public class Node { public final NodeInfo info; public Node(NodeInfo info) { this.info = info; nodes.add(this); successors.put(this, new HashSet<Node>()); predecessors.put(this, new HashSet<Node>()); } /** * n.successors() gibt die Menge aller Nachfolger des Knotes n zurueck, * d.h. die Menge {n | (n, m) in E} */ public Set<Node> successors() { return Collections.unmodifiableSet(successors.get(this)); } /** * n.predecessors() gibt die Menge aller Nachfolger des Knotes n zurueck, * d.h. die Menge {m | (m, n) in E} */ public Set<Node> predecessors() { return Collections.unmodifiableSet(predecessors.get(this)); } public Set<Node> neighbours() { Set<Node> neigbours = new HashSet<Node>(); neigbours.addAll(successors.get(this)); neigbours.addAll(predecessors.get(this)); return neigbours; } public int inDegree() { return predecessors.get(this).size(); } public int outDegree() { return successors.get(this).size(); } public int degree() { return inDegree() + outDegree(); } } public Set<Node> nodeSet() { return Collections.unmodifiableSet(nodes); } public Node addNewNode(NodeInfo info) { return new Node(info); } public void removeNode(Node n) { nodes.remove(n); successors.remove(n); predecessors.remove(n); for (Node m : nodes) { successors.get(m).remove(n); predecessors.get(m).remove(n); } } public void addEdge(Node src, Node dst) { successors.get(src).add(dst); predecessors.get(dst).add(src); } public void removeEdge(Node src, Node dst) { successors.get(src).remove(dst); predecessors.get(dst).remove(src); } /** * Prints the graph in dot representation. The output can be opened * with dotty (<code>dotty output.dot</code>) or converted to PDF * with dot (<code>dot -Tpdf output.dot > output.pdf</code>). * Siehe: http://www.graphviz.com */ public void printDot(PrintStream out) { out.println("digraph G {"); for (Node n : nodes) { out.println("\"" + n + "\" [label=\"" + n.info.toString() + "\"];"); } for (Node n : nodes) { for (Node m : n.successors()) { out.println("\"" + n + "\" -> \"" + m + "\""); } } out.println("}"); } }
Artikelaktionen