src/Graph.java

   1 import java.util.Collection;
   2 import java.util.Enumeration;
   3 import java.util.Hashtable;
   4
   5 /**
   6  * Graph is a representing the complex datastructure graph, which
   7  * stores nodes and connections between them.
   8  *
   9  * @author "Anton Johansson" <anton.johansson@gmail.com>
  10  * @author "Victor Zamanian" <victor.zamanian@gmail.com>
  11  * @version 1.0
  12  */
  13 public class Graph {
  14    private Hashtable<Object, GraphNode> nodes;
  15    private int initialCapacityNeighbours;
  16    private int numberOfEdges = 0;
  17
  18    /**
  19     * Creates a new instance of a Graph.
  20     *
  21     * @param initialSize The number of nodes that need
  22     * to have memory allocated for them.
  23     * @param initialCapacityNeighbours The maximum number of neighbours.
  24     * (The number of nodes in the network.)
  25     */
  26    public Graph(int initialSize, int initialCapacityNeighbours) {
  27       this.initialCapacityNeighbours = initialCapacityNeighbours;
  28       nodes = new Hashtable<Object, GraphNode>(initialSize);
  29    }
  30
  31    /**
  32     * Inserts a node with name address name into the graph.
  33     *
  34     * @param name The name address of the node to insert.
  35     * @param x the x-coordante of the node.
  36     * @param y the y-coordante of the node.
  37     * @return the newly created GraphNode
  38     */
  39    public GraphNode insertNode(String name, int x, int y) {
  40       GraphNode node = new GraphNode(name, x, y, initialCapacityNeighbours);
  41       nodes.put(name, node);
  42       return node;
  43    }
  44
  45    /**
  46     * Insers an edge between two nodes in the graph.
  47     * It is assumed that the parameter nodes exist in the graph.
  48     *
  49     * @param srcName The source node.
  50     * @param destName The destination node.
  51     * @param edge The edge between the nodes.
  52     * @return true if an edge is inserted.
  53     */
  54    public Boolean insertEdge(String srcName, String destName, Object edge) {
  55       //Om det inte redan finns en kant
  56       GraphNode srcNode = nodes.get(srcName);
  57       GraphNode destNode = nodes.get(destName);
  58
  59       if (srcNode != null && destNode != null) {
  60          srcNode.addNeighbour(destNode, edge);
  61          //destNode.addNeighbour(srcNode, weight);
  62          numberOfEdges++;
  63          return true;
  64       }
  65       else {
  66          return false;
  67       }
  68    }
  69
  70    /**
  71     * Inspects the graph to see if it is empty of nodes.
  72     * @return true if the graph contains no nodes, else false.
  73     */
  74    public boolean isEmpty() {
  75       return nodes.isEmpty();
  76    }
  77
  78    /**
  79     * Inspects if the graph has no edges.
  80     * @return true if the graph contains no edges, else false.
  81     */
  82    public boolean hasNoEdges() {
  83       return (numberOfEdges == 0);
  84    }
  85
  86    /**
  87     * The set of nodes which are neighbours
  88     * of the node with name address given by parameter.
  89     *
  90     * @param name The name address of the node.
  91     * @return An Enumeration with the set of neighbours of the node.
  92     */
  93    public Enumeration<GraphNode> neighbours(String name) {
  94       return nodes.get(name).getNeighbours();
  95    }
  96
  97    /**
  98     * Inspects the number of nodes in this Graph.
  99     *
 100     * @return The number of nodes in 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<GraphNode> 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<GraphNode> e = node.getNeighbours(); e.hasMoreElements();) {
 137          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    /**
 179     * Returns the node with the specified name, if it exists in this
 180     * Graph.
 181     *
 182     * @param name The name of the node to fetch.
 183     * @return the node with the specified name.
 184     */
 185    public GraphNode getNode(String name) {
 186       return nodes.get(name);
 187    }
 188
 189    /**
 190     * Returns a String representation of this Graph.
 191     *
 192     * @return the String representation of this Graph.
 193     */
 194    public String toString() {
 195       String returnString = "";
 196       for (Enumeration<GraphNode> e = nodes.elements(); e.hasMoreElements();) {
 197          returnString += e.nextElement();
 198       }
 199       return returnString;
 200    }
 201 }