src/Graph.java

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