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

The example creates an empty graph and uses readGraph() with the file samplegraph.dat to load the vertices, edges and weights. An output statement uses toString() to display the graph. The following is a listing of the file with an accompanying picture of the graph :

- File samplegraph.dat :

5 // data for the vertices
A B C D E
6 // data for the edges
A B 3
A C 2
B C 6
C B 4
C D 1
E B 5

Here we create a class JGraph which implements Graph interface to carry out the example here :

- JGraph.java :

view plaincopy to clipboardprint?

1. package DSwJ.S24;  
2.   
3. import java.io.BufferedReader;  
4. import java.io.File;  
5. import java.io.FileReader;  
6. import java.util.ArrayList;  
7. import java.util.HashSet;  
8. import java.util.Iterator;  
9. import java.util.List;  
10. import java.util.Set;  
11. import java.util.TreeMap;  
12.   
13. import DSwJ.S24.sub.Edge;  
14.   
15. public class JGraph implements Graph{  
16.     private TreeMap>> vertexTable;  
17.       
18.     public JGraph(){vertexTable = new TreeMap>>();}  
19.       
20.     public static JGraph readGraph(String fn) {  
21.         JGraph graph = new JGraph();  
22.         File graphFile = new File(fn);  
23.         int vertexCnt = 0;  
24.         int edgeCnt = 0;  
25.         if(graphFile.exists()) {  
26.             try{  
27.                 BufferedReader br = new BufferedReader(new FileReader(graphFile));  
28.                 String line;  
29.                 if((line=br.readLine())!=null) { //Read vertex count                      
30.                     vertexCnt = Integer.valueOf(line.trim());  
31.                     //System.out.println("Vertex Cnt="+vertexCnt+"...");  
32.                 } else return null;  
33.                 if((line=br.readLine())!=null) { //Read vertex set  
34.                     String[] vertexSet = line.split(" ");  
35.                     vertexCnt = vertexCnt>vertexSet.length?vertexSet.length:vertexCnt;  
36.                     for(int i=0; i
37.                         //System.out.println("Add Vertex("+vertexSet[i]+")");  
38.                         graph.addVertex(vertexSet[i].trim());                     
39.                     }                     
40.                 } else return null;  
41.                 if((line=br.readLine())!=null) { //Read edge count  
42.                     edgeCnt = Integer.valueOf(line);      
43.                 } else return null;  
44.                 while((line=br.readLine())!=null && edgeCnt>0) {  
45.                     String[] edgeSet = line.split(" ");  
46.                     if(edgeSet.length==3) {  
47.                         graph.addEdge(edgeSet[0].trim(), edgeSet[1].trim(), Integer.valueOf(edgeSet[2]));  
48.                     }  
49.                     edgeCnt--;  
50.                 }  
51.                 br.close();  
52.             }catch(Exception e){e.printStackTrace(); return null;}  
53.         }  
54.         return graph;  
55.     }  
56.   
57.     @Override  
58.     public boolean addEdge(Object v1, Object v2, int w) {  
59.         if(vertexTable.containsKey(v1) && vertexTable.containsKey(v2)) {  
60.             return vertexTable.get(v1).add(new Edge((T)v1, (T)v2, w));  
61.         }  
62.         throw new java.lang.IllegalArgumentException("JGraph(addEdge): Vertices "+v1+" or "+v2+" doesn't exist");  
63.     }  
64.   
65.     @Override  
66.     public boolean addVertex(Object v) {  
67.         if(!vertexTable.containsKey(v)){  
68.             vertexTable.put((T)v, new ArrayList>());  
69.             return true;  
70.         }  
71.         return false;  
72.     }  
73.   
74.     @Override  
75.     public void clear() {  
76.         vertexTable.clear();  
77.     }  
78.   
79.     @Override  
80.     public boolean containsEdge(Object v1, Object v2) {  
81.         if(vertexTable.containsKey(v1) && vertexTable.containsKey(v2)) {  
82.             ArrayList> list = vertexTable.get(v1);  
83.             if(list!=null) {  
84.                 Iterator> iter = list.iterator();  
85.                 while(iter.hasNext()) {  
86.                     Edge e = iter.next();  
87.                     if(e.dest.equals(v2)) return true;  
88.                 }  
89.             }  
90.             return false;  
91.         }  
92.         throw new java.lang.IllegalArgumentException("JGraph(containsEdge): Vertices "+v1+" or "+v2+" doesn't exist");  
93.     }  
94.   
95.     @Override  
96.     public boolean containsVertex(Object v) {  
97.         return vertexTable.containsKey(v);  
98.     }  
99.   
100.     @Override  
101.     public Set getNeighbors(Object v) {  
102.         if(vertexTable.containsKey(v)) {  
103.             HashSet neighborSet = new HashSet();    
104.             return neighborSet;  
105.         }         
106.         throw new java.lang.IllegalArgumentException("JGraph(containsEdge): Vertex "+v+" doesn't exist");  
107.     }  
108.   
109.     @Override  
110.     public int getWeight(Object v1, Object v2) {  
111.         if(vertexTable.containsKey(v1) && vertexTable.containsKey(v2)) {  
112.             List> list = vertexTable.get(v1);  
113.             if(list!=null) {  
114.                 Iterator> iter = list.iterator();  
115.                 while(iter.hasNext()) {  
116.                     Edge e = iter.next();  
117.                     if(e.dest.equals(v2)) return e.weight;  
118.                 }  
119.             }  
120.             return -1;  
121.         }  
122.         throw new java.lang.IllegalArgumentException("JGraph(getWeight): Vertices "+v1+" or "+v2+" doesn't exist");  
123.     }  
124.   
125.     @Override  
126.     public boolean isEmpty() {  
127.         return vertexTable.isEmpty();  
128.     }  
129.   
130.     @Override  
131.     public int numberOfEdges() {  
132.         int total=0;  
133.         Set keySet = vertexTable.keySet();  
134.         Iterator iter = keySet.iterator();  
135.         while(iter.hasNext()) {  
136.             total+=vertexTable.get(iter.next()).size();  
137.         }  
138.         return total;  
139.     }  
140.   
141.     @Override  
142.     public int numberOfVertices() {  
143.         return vertexTable.size();  
144.     }  
145.   
146.     @Override  
147.     public boolean removeEdge(Object v1, Object v2) {  
148.         if(vertexTable.containsKey(v1) && vertexTable.containsKey(v2)) {  
149.             List> list = vertexTable.get(v1);  
150.             if(list!=null) {  
151.                 Iterator> iter = list.iterator();  
152.                 while(iter.hasNext()) {  
153.                     Edge e = iter.next();  
154.                     if(e.dest.equals(v2)){  
155.                         return list.remove(e);  
156.                     }  
157.                 }  
158.             }  
159.             return false;  
160.         }  
161.         throw new java.lang.IllegalArgumentException("JGraph(removeEdge): Vertices "+v1+" or "+v2+" doesn't exist");  
162.     }  
163.   
164.     @Override  
165.     public boolean removeVertex(Object v) {  
166.         if(vertexTable.remove(v)!=null) return true;  
167.         return false;  
168.     }  
169.   
170.     @Override  
171.     public int setWeight(Object v1, Object v2, int w) {  
172.         if(vertexTable.containsKey(v1) && vertexTable.containsKey(v2)) {  
173.             List> list = vertexTable.get(v1);  
174.             if(list!=null) {  
175.                 Iterator> iter = list.iterator();  
176.                 while(iter.hasNext()) {  
177.                     Edge e = iter.next();  
178.                     if(e.dest.equals(v2)){  
179.                         int prevW =  e.weight;  
180.                         e.weight = w;  
181.                         return prevW;  
182.                     }  
183.                 }  
184.             }  
185.             return -1;  
186.         }  
187.         throw new java.lang.IllegalArgumentException("JGraph(setWeight): Vertices "+v1+" or "+v2+" doesn't exist");  
188.     }  
189.   
190.     @Override  
191.     public Set vertexSet() {          
192.         return vertexTable.keySet();  
193.     }  
194.       
195.     public int outDegree(T vertex) {  
196.         if(vertexTable.containsKey(vertex)) {  
197.             return vertexTable.get(vertex).size();            
198.         }  
199.         throw new java.lang.IllegalArgumentException("JGraph(outDegree): Vertex "+vertex+" doesn't exist");  
200.     }  
201.       
202.     public int inDegree(T vertex){  
203.         int cnt = 0;  
204.         if(vertexTable.containsKey(vertex)) {  
205.             Set keySet = vertexTable.keySet();  
206.             Iterator iter = keySet.iterator();  
207.             while(iter.hasNext()) {  
208.                 T v = iter.next();  
209.                 if(!v.equals(vertex)) {  
210.                     List> edges = vertexTable.get(v);  
211.                     Iterator> eIter = edges.iterator();  
212.                     while(eIter.hasNext()) if(eIter.next().dest.equals(vertex)) cnt++;  
213.                 }  
214.             }  
215.             return cnt;  
216.         }  
217.         throw new java.lang.IllegalArgumentException("JGraph(inDegree): Vertex "+vertex+" doesn't exist");        
218.     }  
219.       
220.     public int size(){return vertexTable.size();}  
221.       
222.     @Override  
223.     public String toString(){  
224.         StringBuffer buffer = new StringBuffer("");  
225.         Set keySet = vertexTable.keySet();  
226.         Iterator iter = keySet.iterator();  
227.         while(iter.hasNext()) {  
228.             T vertex = iter.next();  
229.             buffer.append(vertex+":\tin-degree "+inDegree(vertex)+" out-degree "+outDegree(vertex)+"\n");  
230.             buffer.append("\tEdges: ");  
231.             List> edges = vertexTable.get(vertex);  
232.             Iterator> eIter = edges.iterator();  
233.             while(eIter.hasNext()) {  
234.                 Edge edge = eIter.next();  
235.                 buffer.append(edge.dest+"("+edge.weight+") ");  
236.             }  
237.             buffer.append("\n");  
238.         }  
239.         return buffer.toString();  
240.     }  
241.       
242.     public static void main(String args[]) {  
243.         JGraph graph = JGraph.readGraph("samplegraph.dat");  
244.         System.out.println(graph);  
245.     }  
246. }  

Output :

A: in-degree 0 out-degree 2
Edges: B(3) C(2)
B: in-degree 3 out-degree 1
Edges: C(6)
C: in-degree 2 out-degree 2
Edges: B(4) D(1)
D: in-degree 1 out-degree 0
Edges:
E: in-degree 0 out-degree 1
Edges: B(5)

This message was edited 3 times. Last update was at 08/11/2010 16:20:12