[ Data Structures with Java ] Section 24.2 : Creating and Using Graphs

Preface :
Our ultimate goal is to develop graph algorithms and use them in application. We need tools to create a graph and operations to access and update its properties. We do this in two steps. The Graph interface defines methods that describe graph operations. The DiGraph class implements the interface and enables us to input the vertices and edges and display the key graph attributes.

The Graph Interface :
The Graph interface defines all of the methods you need to build a graph. The interface applies to both undirected and directed graphs. The sheer number of methods in the interface is deceiving. With a closer look, you will see similarities with the interfaces we developed for the list, set and map structures. Just remember, we must deal with vertices, edges and weights. Rather than a simple add() method, the Graph interface has addVertex() and addEdge(). The same is true for remove(), contains() and size(). The following is the Graph interface :

- Interface Graph :

view plaincopy to clipboardprint?

1. package DSwJ.S24;  
2.   
3. import java.util.Set;  
4.   
5. public interface Graph {  
6.     /** 
7.      * BD : 
8.      *  If the edge(v1, v2) is not in the graph, adds the edge with weight w and return true. 
9.      *  Return false if the edge is already in the graph. If v1 or v2 is not a vertex in the 
10.      *  graph, throws IllegalArgumentException. 
11.      */  
12.     public boolean addEdge(T v1, T v2, int w);  
13.       
14.     /** 
15.      * BD : 
16.      *  If v is not in the graph, adds it to the graph and return true; 
17.      *  otherwise, return false; 
18.      */  
19.     public boolean addVertex(T v);  
20.       
21.     /** 
22.      * BD : 
23.      *  Removes all of the vertices and edges from the graph. 
24.      */  
25.     public void clear();  
26.       
27.     /** 
28.      * BD : 
29.      *  Returns true if there is an edge from v1 to v2 and return false otherwise. 
30.      *  If v1 or v2 is not a vertex in the graph, throws IllegalArgumentException. 
31.      */  
32.     public boolean containsEdge(T v1, T v2);  
33.       
34.     /** 
35.      * BD : 
36.      *  Returns true if v is a vertex in the graph and false otherwise. 
37.      */  
38.     public boolean containsVertex(Object v);  
39.       
40.     /** 
41.      * BD :  
42.      *  Returns the vertices that are adjacent to vertex v in a Set object. 
43.      *  If v is not a graph vertex, throws IllegalArgumentException. 
44.      */  
45.     public Set getNeighbors(T v);  
46.       
47.     /** 
48.      * BD : 
49.      *  Returns the weight of the edge connecting vertex v1 to v2. If the edge(v1, v2) does 
50.      *  not exist, return -1. If v1 or v2 is not a vertex in the graph,  
51.      *  throws IllegalArgumentException. 
52.      */  
53.     public int getWeight(T v1, T v2);  
54.   
55.     /** 
56.      * BD : 
57.      *  Returns true if the graph has no vertices or edges and false otherwise. 
58.      */  
59.     public boolean isEmpty();  
60.       
61.     /** 
62.      * BD : 
63.      *  Returns the number of edges in the graph. 
64.      */  
65.     public int numberOfEdges();  
66.       
67.     /** 
68.      * BD : 
69.      *  Returns the number of vertices in the graph. 
70.      */  
71.     public int numberOfVertices();  
72.       
73.     /** 
74.      * BD :  
75.      *  If (v1, v2) is an edge, removes the edge and returns true; otherwise, returns false. 
76.      *  If v1 or v2 is not a vertex in the graph, throws IllegalArgumentException. 
77.      */  
78.     public boolean removeEdge(T v1, T v2);  
79.       
80.     /** 
81.      * BD : 
82.      *  If v is a vertex in the graph, removes it from the graph and returns true; otherwise return false. 
83.      */  
84.     public boolean removeVertex(Object v);  
85.       
86.     /** 
87.      * BD : 
88.      *  If edge(v1, v2) is in the graph, updates the weight of the edge and returns the previous weight; 
89.      *  otherwise, return -1. If v1 or v2 is not a vertex in the graph, throws IllegalArgumentException. 
90.      */  
91.     public int setWeight(T v1, T v2, int w);  
92.       
93.     /** 
94.      * BD :  
95.      *  Returns a set view of the vertices in the graph. 
96.      */  
97.     public Set vertexSet();  
98. }  

Two methods need to be highlighted. Graph-scanning algorithms require that we provide from vertex along a variable number of edges to a designated vertex. The method getNeighbors() returns all of the adjacen vertices as a Set. An iterator on the set provides access to adjacent vertices. A class that implements the Graph interface does not have an iterator. We use the collection view concept from maps. The method vertexSet() returns a Set reference with methods that allow us to access and update the backing graph collection.
The methods in the Graph interface are a template for implementing directed or undirected graphs. However, there will be differences in implementation. For instance, addEdge(v1, v2, w) in an undirected graph makes v2 a neighbor of v1 and v1 a neighbor of v2 (Below figure-a). In a digraph, the method only makes v2 a neighbor of v1 (below figure-b). The same type of difference occurs with the method removeEdge().


The DiGraph Class :
The DiGraph class implements the Graph interface and adds other methods that are useful in applications. A constructor creates an empty graph. The methods inDegree() and outDegree() are special methods that access properties that are unique to a digraph.
Building the graph vertex by vertex with addVertex() and edge by edge with addEdge() would be a tedious task. The class provides the static method readGraph(), which builds a graph whose vertices are strings. The method inputs the vertices, edges and weights for the graph from a textfile whose name is passed as an argument :
public static DiGraph readGraph(String filename) throws FileNotFoundException;

The format treats the vertices and edges separately. Input begins with the number of vertices, followed by a list of the vertex numbers. Each vertex name is a string :

(Number of Vertices m)
Vertex1 Vertex2 ... Vertex3

For the edges, begin with their number, followed by a sequence of triples where the first two entries are the source and destination vertices of an edge and the third entry is the weight of that edge. For nonweighted graphs, assign the weight of an edge as 1 :

(Number of edges m)
Source1 Destination1 Weight1
Source2 Destination2 Weight2
...
Source-n Destination-n Weight-n

The method toString() provides a representation of a graph. For each vertex, the method gives the list of adjacent vertices along with the weight of the corresponding edge. The information for each vertex also includes in its in-degree and out-degree. Output is in sorted order of vertices :
Output format :

vertex name: in-degree out-degree
Edges: (list of adjacent vertices and edge weights)

Supplement :
* [ Data Structures with Java ] Section 24.2 - Example 24.1
This message was edited 5 times. Last update was at 28/03/2011 10:12:47