Graph.java import java.io.BufferedReader; import java.io.File; import java.io.Fi

ID: 3704771 • Letter: G

Question

Graph.java

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

public class Graph {
public int V;
public int E;

public LinkedList<Integer>[] adj;

public Graph()
{
V = 0;
E = 0;
}

public Graph(BufferedReader reader) throws IOException
{
String line;
line = reader.readLine();
V = Integer.parseInt(line);
line = reader.readLine();
E = Integer.parseInt(line);
adj = new LinkedList[V];
for (int v = 0; v < V; v++) {
adj[v] = new LinkedList<Integer>();
}
while ((line = reader.readLine()) != null) {
int tempV1, tempV2;
StringTokenizer st = new StringTokenizer(line, " ");
tempV1 = Integer.parseInt(st.nextToken());
tempV2 = Integer.parseInt(st.nextToken());
addEdge(tempV1, tempV2);
}
}


public void addEdge(int v, int w) {

}

public String tostring()
{
String s = new String();
s = "There are "+V+" vertices and "+E+" edges ";
for(int i=0;i<V;i++)
{
s = s+i+": ";
for(int j = 0; j<adj[i].size();j++)
{
s = s+adj[i].get(j)+" ";
}
s = s+" ";

}
return s;
}

}

mediumG.txt

250
1273
244 246
239 240
238 245
235 238
233 240
232 248
231 248
229 249
228 241
226 231
223 242
223 249
222 225
220 247
219 221
218 224
218 227
217 232
216 232
214 219
214 221
213 235
213 238
212 214
212 219
212 221
212 244
211 222

largeG.txt

1000000
7586063
999812 999997
999592 999782
999499 999881
999213 999297
999082 999896
999067 999159
999063 999354
999037 999626
998991 999808
998856 999431
998602 998726
998601 998719
998494 999657
998475 999232
998456 999256
998375 999945
998353 999790
998347 999348
998299 998335
998292 998433
998261 999240
998244 999924
998013 999598
998008 999192
997936 998069
997905 999016
997877 999937
997847 998290

xtraLargeG.txt

Implement a weighted graph class from the Graph.java used previously. Graph.java uses integer value for storing an edge. Instead of using integer value for storing edges, create an “Edge" class that holds information of edge. Edge class has following attributes (not limited to): Vertex v1, v2 int edgeID int edgeWeight Change the adjacency list to hold the vertex and edge weight. Write a driver program, which reads input files mediumGraph.txt, LargeGraph.txt and Xtra LargeGraph.txt (on Canvas) and display the weighted graphs by printing adjacency list.

Explanation / Answer

Dear,

import java.io.BufferedReader;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.IOException;

import java.util.LinkedList;

import java.util.StringTokenizer;

public class Graph {

public int V;

public int E;

public int weight;

public LinkedList<Integer>[] adj;

public Graph()

{

V = 0;

E = 0;

}

public Graph(BufferedReader reader) throws IOException

{

String line;

line = reader.readLine();

V = Integer.parseInt(line.trim());

line = reader.readLine();

E = Integer.parseInt(line.trim());

adj = new LinkedList[V];

for (int v = 0; v < V; v++) {

adj[v] = new LinkedList<Integer>();

}

while ((line = reader.readLine()) != null) {

int tempV1, tempV2;

StringTokenizer st = new StringTokenizer(line, " ");

tempV1 = Integer.parseInt(st.nextToken());

tempV2 = Integer.parseInt(st.nextToken());

addEdge(tempV1, tempV2);

}

public void addEdge(int v, int w) {

if (v < 0) throw new IllegalArgumentException("vertex index must be a nonnegative integer");

if (w < 0) throw new IllegalArgumentException("vertex index must be a nonnegative integer");

if (Double.isNaN(weight)) throw new IllegalArgumentException("Weight is NaN");

this.V = v;

this.E = w;

this.weight = weight;

}

public String tostring()

{

String s = new String();

s = "There are "+V+" vertices and "+E+" edges ";

for(int i=0;i<V;i++)

{

s = s+i+": ";

for(int j = 0; j<adj[i].size();j++)

{

s = s+adj[i].get(j)+" ";

}

s = s+" ";

}

return s;

}

public static void main(String[] args) throws Exception, IOException {

Graph gm=new Graph(new BufferedReader(new FileReader("src/mediumG.txt")));

System.out.println(gm.tostring());

Graph glarge=new Graph(new BufferedReader(new FileReader("src/largeG.txt")));

System.out.println(glarge.tostring());

Graph gxlarge=new Graph(new BufferedReader(new FileReader("src/xtraLargeG.txt")));

System.out.println(gxlarge.tostring());

}

output :

There are 211 vertices and 222 edges
0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:

Thank You.

Navigate

Graph.java import java.io.BufferedReader; import java.io.File; import java.io.Fi

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Graph.java import java.io.BufferedReader; import java.io.File; import java.io.Fi

Question

Explanation / Answer

Related Questions

Navigate