src/Graph.java

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