src/Graph.java

   1 /*
   2  * @(#)Graph.java
   3  * Time-stamp: "2008-10-13 16:54:16 anton"
   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     * The set of nodes in the graph (all nodes).
 104     *
 105     * @return A Vector with all nodes in the graph.
 106     */
 107    public Enumeration getNodes() {
 108       return nodes.elements();
 109    }
 110
 111    /**
 112     * Inspects the weight of an edge between two nodes in the grapn.
 113     *
 114     * @param srcName The name address of the source node.
 115     * @param destName The name address of the destination node.
 116     * @return The weight of the edge.
 117     */
 118    public int getWeight(String srcName, String destName) {
 119       GraphNode srcNode = nodes.get(srcName);
 120       GraphNode destNode = nodes.get(destName);
 121       return srcNode.getWeight(destNode);
 122    }
 123
 124    // Modifikatorer
 125
 126    /**
 127     * Removes a node from the graph.
 128     *
 129     * @param node The node to be removed.
 130     */
 131    public void deleteNode(GraphNode node) {
 132       for (Enumeration e = node.getNeighbours(); e.hasMoreElements();) {
 133          ((GraphNode) e.nextElement()).deleteNeighbour(node);
 134       }
 135       nodes.remove(node.getName());
 136    }
 137
 138    /**
 139     * Removes an edge between two nodes.
 140     *
 141     * @param src The source node.
 142     * @param dest The destination node.
 143     */
 144    public void deleteEdge(GraphNode src, GraphNode dest) {
 145       src.deleteNeighbour(dest);
 146       dest.deleteNeighbour(src);
 147
 148       numberOfEdges--;
 149    }
 150
 151    /**
 152     * Alters the weight of an edge between two nodes in the graph.
 153     *
 154     * @param srcNode The source node.
 155     * @param destNode The destination node.
 156     * @param weight The new weight between the two nodes.
 157     */
 158    public void setWeight(GraphNode srcNode, GraphNode destNode, int weight) {
 159       deleteEdge(srcNode, destNode);
 160       insertEdge(srcNode.getName(), destNode.getName(), weight);
 161    }
 162
 163    /**
 164     * Inspects whether a node with a certain name address
 165     * given by parameter exists in the graph or not.
 166     *
 167     * @param name The name address of the node.
 168     * @return true if the node exists, else false.
 169     */
 170    public boolean isInGraph(String name) {
 171       return (nodes.containsKey(name));
 172    }
 173
 174    public GraphNode getNode(String name) {
 175       return nodes.get(name);
 176    }
 177 }