1 import java
.util
.Collection
;
2 import java
.util
.Enumeration
;
3 import java
.util
.Hashtable
;
8 * @author "Anton Johansson" <anton.johansson@gmail.com>
9 * @author "Victor Zamanian" <victor.zamanian@gmail.com>
13 private Hashtable
<Object
, GraphNode
> nodes
;
14 private int initialCapacityNeighbours
;
15 private int numberOfEdges
= 0;
18 * Creates a new instance of a Graph.
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.)
25 public Graph(int initialSize
, int initialCapacityNeighbours
) {
26 this.initialCapacityNeighbours
= initialCapacityNeighbours
;
27 nodes
= new Hashtable(initialSize
);
31 * Inserts a node with name address name into the graph.
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
38 public GraphNode
insertNode(String name
, int x
, int y
) {
39 GraphNode node
= new GraphNode(name
, x
, y
, initialCapacityNeighbours
);
40 nodes
.put(name
, node
);
45 * Insers an edge between two nodes in the graph.
46 * It is assumed that the parameter nodes exist in the graph.
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.
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
);
58 if (srcNode
!= null && destNode
!= null) {
59 srcNode
.addNeighbour(destNode
, edge
);
60 //destNode.addNeighbour(srcNode, weight);
70 * Inspects the graph to see if it is empty of nodes.
71 * @return true if the graph contains no nodes, else false.
73 public boolean isEmpty() {
74 return nodes
.isEmpty();
78 * Inspects if the graph has no edges.
79 * @return true if the graph contains no edges, else false.
81 public boolean hasNoEdges() {
82 return (numberOfEdges
== 0);
86 * The set of nodes which are neighbours
87 * of the node with name address given by parameter.
89 * @param name The name address of the node.
90 * @return An Enumeration with the set of neighbours of the node.
92 public Enumeration
neighbours(String name
) {
93 return nodes
.get(name
).getNeighbours();
97 * Inspects the number of nodes in this Graph.
99 * @returns An <code>int</code> representing the number of nodes in
107 * Get all nodes in the graph.
109 * @return An collection of all nodes in the graph.
111 public Collection
getNodes() {
112 return nodes
.values();
116 * Inspects the weight of an edge between two nodes in the grapn.
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.
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
);
131 * Removes a node from the graph.
133 * @param node The node to be removed.
135 public void deleteNode(GraphNode node
) {
136 for (Enumeration e
= node
.getNeighbours(); e
.hasMoreElements();) {
137 ((GraphNode
) e
.nextElement()).deleteNeighbour(node
);
139 nodes
.remove(node
.getName());
143 * Removes an edge between two nodes.
145 * @param src The source node.
146 * @param dest The destination node.
148 public void deleteEdge(GraphNode src
, GraphNode dest
) {
149 src
.deleteNeighbour(dest
);
150 dest
.deleteNeighbour(src
);
156 * Alters the weight of an edge between two nodes in the graph.
158 * @param srcNode The source node.
159 * @param destNode The destination node.
160 * @param weight The new weight between the two nodes.
162 public void setWeight(GraphNode srcNode
, GraphNode destNode
, Double weight
) {
163 deleteEdge(srcNode
, destNode
);
164 insertEdge(srcNode
.getName(), destNode
.getName(), weight
);
168 * Inspects whether a node with a certain name address
169 * given by parameter exists in the graph or not.
171 * @param name The name address of the node.
172 * @return true if the node exists, else false.
174 public boolean isInGraph(String name
) {
175 return (nodes
.containsKey(name
));
178 public GraphNode
getNode(String name
) {
179 return nodes
.get(name
);
182 public String
toString() {
183 String returnString
= "";
184 for (Enumeration e
= nodes
.elements(); e
.hasMoreElements();) {
185 returnString
+= e
.nextElement();