/
Graph.java
133 lines (120 loc) · 3.38 KB
/
Graph.java
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
/**
* Class to represent a graph
*
*
*/
import java.util.*;
class Graph implements Iterable<Vertex> {
public List<Vertex> verts; // array of vertices
public int numNodes; // number of verices in the graph
/**
* Constructor for Graph
*
* @param size
* : int - number of vertices
*/
Graph(int size) {
numNodes = size;
verts = new ArrayList<>(size + 1);
verts.add(0, null);
// create an array of Vertex objects
for (int i = 1; i <= size; i++)
verts.add(i, new Vertex(i));
}
/**
* Method to add an edge to the graph
*
* @param a
* : int - one end of edge
* @param b
* : int - other end of edge
* @param weight
* : int - the weight of the edge
*/
void addEdge(int a, int b, int weight) {
Vertex u = verts.get(a);
Vertex v = verts.get(b);
Edge e = new Edge(u, v, weight);
u.Adj.add(e);
v.Adj.add(e);
u.degree++;
v.degree++;
}
/**
* Method to add an arc (directed edge) to the graph
*
* @param a
* : int - the head of the arc
* @param b
* : int - the tail of the arc
* @param weight
* : int - the weight of the arc
*/
void addDirectedEdge(int a, int b, int weight) {
Vertex head = verts.get(a);
Vertex tail = verts.get(b);
Edge e = new Edge(head, tail, weight);
head.Adj.add(e);
tail.revAdj.add(e);
}
/**
* Method to create an instance of VertexIterator
*/
public Iterator<Vertex> iterator() {
return new VertexIterator();
}
/**
* A Custom Iterator Class for iterating through the vertices in a graph
*
*/
private class VertexIterator implements Iterator<Vertex> {
private Iterator<Vertex> it;
/**
* Constructor for VertexIterator
*
*/
private VertexIterator() {
it = verts.iterator();
it.next(); // Index 0 is not used. Skip it.
}
/**
* Method to check if there is any vertex left in the iteration
* Overrides the default hasNext() method of Iterator Class
*/
public boolean hasNext() {
return it.hasNext();
}
/**
* Method to return the next Vertex object in the iteration
* Overrides the default next() method of Iterator Class
*/
public Vertex next() {
return it.next();
}
/**
* Throws an error if a vertex is attempted to be removed
*/
public void remove() {
throw new UnsupportedOperationException();
}
}
public static Graph readGraph(Scanner in, boolean directed) {
// read the graph related parameters
int n = in.nextInt(); // number of vertices in the graph
int m = in.nextInt(); // number of edges in the graph
// create a graph instance
Graph g = new Graph(n);
for (int i = 0; i < m; i++) {
int u = in.nextInt();
int v = in.nextInt();
int w = in.nextInt();
if(directed) {
g.addDirectedEdge(u, v, w);
} else {
g.addEdge(u, v, w);
}
}
in.close();
return g;
}
}