src/Graph.java

   1 import java.util.Enumeration;
   2 import java.util.Hashtable;
   3
   4 /**
   5  * Graph
   6  *
   7  * @author "Anton Johansson" <anton.johansson@gmail.com>
   8  * @author "Victor Zamanian-Abasy" <zamanian87@gmail.com>
   9  */
  10
  11 public class Graph {
  12    private Hashtable<Object, GraphNode> nodes;
  13    private int initialCapacityNeighbours;
  14    private int numberOfEdges = 0;
  15
  16    /**
  17     * Creates a new instance of a Graph.
  18     *
  19     * @param initialSize The number of nodes that need
  20     * to have memory allocated for them.
  21     * @param initialCapacityNeighbours The maximum number of neighbours.
  22     * (The number of nodes in the network.)
  23     */
  24    public Graph(int initialSize, int initialCapacityNeighbours) {
  25       this.initialCapacityNeighbours = initialCapacityNeighbours;
  26       nodes = new Hashtable(initialSize);
  27    }
  28
  29    /**
  30     * Inserts a node with name address name into the graph.
  31     *
  32     * @param name The name address of the node to insert.
  33     * @param x the x-coordante of the node.
  34     * @param y the y-coordante of the node.
  35     * @return the newly created GraphNode
  36     */
  37    public GraphNode insertNode(String name, int x, int y) {
  38       GraphNode node = new GraphNode(name, x, y, initialCapacityNeighbours);
  39       nodes.put(name, node);
  40       return node;
  41    }
  42
  43    /**
  44     * Insers an edge between two nodes in the graph.
  45     * It is assumed that the parameter nodes exist in the graph.
  46     *
  47     * @param srcNode The source node.
  48     * @param destNode The destination node.
  49     * @param weight The weight (length) of the edge between the nodes.
  50     * @return true if an edge is inserted.
  51     */
  52    public Boolean insertEdge(String srcName, String destName, Double weight) {
  53       //Om det inte redan finns en kant
  54       GraphNode srcNode = nodes.get(srcName);
  55       GraphNode destNode = nodes.get(destName);
  56
  57       if (srcNode != null && destNode != null) {
  58          srcNode.addNeighbour(destNode, weight);
  59          destNode.addNeighbour(srcNode, weight);
  60          numberOfEdges++;
  61          return true;
  62       }
  63       else {
  64          return false;
  65       }
  66    }
  67
  68    /**
  69     * Inspects the graph to see if it is empty of nodes.
  70     * @return true if the graph contains no nodes, else false.
  71     */
  72    public boolean isEmpty() {
  73       return nodes.isEmpty();
  74    }
  75
  76    /**
  77     * Inspects if the graph has no edges.
  78     * @return true if the graph contains no edges, else false.
  79     */
  80    public boolean hasNoEdges() {
  81       return (numberOfEdges == 0);
  82    }
  83
  84    /**
  85     * The set of nodes which are neighbours
  86     * of the node with name address given by parameter.
  87     *
  88     * @param name The name address of the node.
  89     * @return An Enumeration with the set of neighbours of the node.
  90     */
  91    public Enumeration neighbours(String name) {
  92       return nodes.get(name).getNeighbours();
  93    }
  94
  95    /**
  96     * Inspects the number of nodes in this Graph.
  97     *
  98     * @returns An <code>int</code> representing the number of nodes in
  99     * this Graph.
 100     */
 101    public int size() {
 102       return nodes.size();
 103    }
 104
 105    /**
 106     * The set of nodes in the graph (all nodes).
 107     *
 108     * @return An enumeration with all nodes in the graph.
 109     */
 110    public Enumeration getNodes() {
 111       return nodes.elements();
 112    }
 113
 114    /**
 115     * Inspects the weight of an edge between two nodes in the grapn.
 116     *
 117     * @param srcName The name address of the source node.
 118     * @param destName The name address of the destination node.
 119     * @return The weight of the edge.
 120     */
 121    public Double getWeight(String srcName, String destName) {
 122       GraphNode srcNode = nodes.get(srcName);
 123       GraphNode destNode = nodes.get(destName);
 124       return srcNode.getWeight(destNode);
 125    }
 126
 127    // Modifikatorer
 128
 129    /**
 130     * Removes a node from the graph.
 131     *
 132     * @param node The node to be removed.
 133     */
 134    public void deleteNode(GraphNode node) {
 135       for (Enumeration e = node.getNeighbours(); e.hasMoreElements();) {
 136          ((GraphNode) e.nextElement()).deleteNeighbour(node);
 137       }
 138       nodes.remove(node.getName());
 139    }
 140
 141    /**
 142     * Removes an edge between two nodes.
 143     *
 144     * @param src The source node.
 145     * @param dest The destination node.
 146     */
 147    public void deleteEdge(GraphNode src, GraphNode dest) {
 148       src.deleteNeighbour(dest);
 149       dest.deleteNeighbour(src);
 150
 151       numberOfEdges--;
 152    }
 153
 154    /**
 155     * Alters the weight of an edge between two nodes in the graph.
 156     *
 157     * @param srcNode The source node.
 158     * @param destNode The destination node.
 159     * @param weight The new weight between the two nodes.
 160     */
 161    public void setWeight(GraphNode srcNode, GraphNode destNode, Double weight) {
 162       deleteEdge(srcNode, destNode);
 163       insertEdge(srcNode.getName(), destNode.getName(), weight);
 164    }
 165
 166    /**
 167     * Inspects whether a node with a certain name address
 168     * given by parameter exists in the graph or not.
 169     *
 170     * @param name The name address of the node.
 171     * @return true if the node exists, else false.
 172     */
 173    public boolean isInGraph(String name) {
 174       return (nodes.containsKey(name));
 175    }
 176
 177    public GraphNode getNode(String name) {
 178       return nodes.get(name);
 179    }
 180
 181    public String toString() {
 182       String returnString = "";
 183       for (Enumeration e = nodes.elements(); e.hasMoreElements();) {
 184          returnString += e.nextElement();
 185       }
 186       return returnString;
 187    }
 188 }