src/Graph.java

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