AbstractGraph.java

Go to the documentation of this file.

package aud.graph;
 
import aud.Vector;
import aud.util.Graphvizable;
import aud.util.GraphvizDecorable;
import aud.util.GraphvizDecorator;
 
import java.util.Iterator;
import java.util.NoSuchElementException;
 
public abstract class
  AbstractGraph<Node extends AbstractNode,Edge extends AbstractEdge>
  implements Iterable<Node>,
             Graphvizable, GraphvizDecorable {
 
  Node                nodeGenerator_ = null;
  Edge                edgeGenerator_ = null;
 
  public AbstractGraph(Node nodeGenerator,Edge edgeGenerator) {
    nodeGenerator_=nodeGenerator;
    edgeGenerator_=edgeGenerator;
  }
 
  public abstract boolean isDirected();
 
  public abstract Node addNode();
 
  public abstract Edge addEdge(Node source,Node destination);
 
  public abstract void removeNode(Node node);
  public abstract void removeEdge(Edge edge);
 
  public abstract int getNumNodes();
 
  public abstract Node getSomeNode();
 
  public abstract Edge getEdge(Node source,Node destination);
 
  public Edge ensureEdge(Node source,Node destination) {
    Edge edge=getEdge(source,destination);
    if (edge==null)
      throw new RuntimeException("no such edge "+source.index()+
                                 (isDirected() ? "->" : "--")+
                                 destination.index());
    return edge;
  }
 
  public abstract Vector<Edge> getInEdges(Node node);
  public abstract Vector<Edge> getOutEdges(Node node);
 
  public int getInDegree(Node node) { return getInEdges(node).size(); }
 
  public int getOutDegree(Node node) { return getOutEdges(node).size(); }
  public int getDegree(Node node) {
    if (isDirected())
      return getInDegree(node)+getOutDegree(node);
    else
      return getInDegree(node);
  }
 
  public abstract Iterator<Edge> getEdgeIterator();
 
  protected Node check(Node node) {
    if (node==null)
      throw new IllegalArgumentException("null node");
    if (node.graph_!=this)
      throw new IllegalArgumentException("node is bound to other graph");
 
    return node;
  }
  protected Edge check(Edge edge) {
    if (edge==null)
      throw new IllegalArgumentException("null edge");
    if (edge.graph_!=this)
      throw new IllegalArgumentException("edge is bound to other graph");
 
    return edge;
  }
 
  public class Edges implements Iterable<Edge> {
    AbstractGraph<Node,Edge> graph_;
    Edges(AbstractGraph<Node,Edge> graph) { graph_=graph; }
    @Override public Iterator<Edge> iterator() {
      return (Iterator<Edge>) graph_.getEdgeIterator();
    }
  }
 
  public Edges edges() { return new Edges(this); }
 
  @Override public String toString() {
    String rv="nodes:\n";
    for (Node node : this)
      rv+=" "+node.toString()+"\n";
    rv+="edges:\n";
    for (Edge edge : this.edges())
      rv+=" "+edge.toString()+"\n";
    return rv;
  }
 
  @Override public GraphvizDecorator getDecorator() {
    return null;
  }
 
  @Override public String toDot() {
    String edgeOp=(isDirected() ? " -> " : " -- ");
    String dot=(isDirected() ? "digraph " : "graph ")+
      "AbstractGraph {\n";
 
    GraphvizDecorator decorator=getDecorator();
    if (decorator!=null) {
      String d=decorator.getGlobalStyle();
      if (d!=null) dot+=" "+d+";\n";
      d=decorator.getGraphDecoration(this);
      if (d!=null) dot+=" graph ["+d+"];\n";
    }
 
    for (Node node : this) {
      decorator=node.getDecorator();
      dot+=" \""+node.index()+"\" [label=\""+node.getLabel()+"\",";
      dot+=(decorator!=null) ? decorator.getFullNodeDecoration(node) : "shape=circle";
 
      double[] p=node.getPosition();
      if (p!=null) {
        dot+=",pos=\""+p[0]+","+p[1]+"\",pin=true,";
      }
 
      dot+="];\n";
    }
 
    dot+="\n\n";
 
    for (Edge edge : this.edges()) {
      decorator=edge.getDecorator();
      dot+=" \""+edge.source().index()+"\""+edgeOp+
           "\""+edge.destination().index()+"\" ";
      String label=edge.getLabel();
      dot+=(label!=null) ? "[label=\""+label+"\"," : "[";
      dot+=edge.hasWeight() ? "weight="+edge.getWeight()+"," : "";
      dot+=edge.hasWeight() ? "len="+edge.getWeight()+"," : "";
      dot+=(decorator!=null) ? decorator.getFullEdgeDecoration(edge) : "";
      dot+="];\n";
    }
 
    dot+="\n}\n";
    //System.out.println(dot);
    return dot;
  }
}