-
Notifications
You must be signed in to change notification settings - Fork 3
/
EdgeWeightedDirectedGraph.java
129 lines (104 loc) · 3.23 KB
/
EdgeWeightedDirectedGraph.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
package Graphs;
import DataStructure.Bag;
public class EdgeWeightedDirectedGraph implements WheightedGraph {
private int edges;
private final int vertices;
private Bag<DirectedEdge>[] adj;
/**
* Build a graph with wheighted directed edges, that is, edges from one vertex
* to another, but not the inverse.
*
* @param numberVertices
*/
public EdgeWeightedDirectedGraph(int numberVertices) {
vertices = numberVertices;
adj = (Bag<DirectedEdge>[]) new Bag[numberVertices];
edges = 0;
for (int i = 0; i < numberVertices; i++) {
adj[i] = new Bag<DirectedEdge>();
}
}
/**
* Adds an wheighted edge from the source vertex to the destination vertex (source -> destination).
*
* @param sourceVertex
* @param destVertex
* @param wheight
*/
public void addEdge(int sourceVertex, int destVertex, int wheight) {
check(sourceVertex);
check(destVertex);
adj[sourceVertex].add(new DirectedEdge(sourceVertex, destVertex, wheight));
edges++;
}
/**
* Adds an wheighted edge from the source vertex to the destination vertex (source -> destination).
*
* @param sourceVertex
* @param destVertex
* @param wheight
*/
public void addEdge(int sourceVertex, int destVertex, double wheight) {
check(sourceVertex);
check(destVertex);
adj[sourceVertex].add(new DirectedEdge(sourceVertex, destVertex, wheight));
edges++;
}
/**
* Adds an edge from the source vertex to the destination vertex (source -> destination).
*
* @param edge
*/
public void addEdge(DirectedEdge edge) {
check(edge.from());
check(edge.to());
adj[edge.from()].add(edge);
edges++;
}
/**
* Returns the weighted edges immediately reachable from the vertex, that is,
* the edges that have a directed edge from the vertex.
*/
public Iterable<DirectedEdge> adjEdges(int vertex) {
return adj[vertex];
}
/**
* Returns all the edges in the current graph.
*/
public Iterable<DirectedEdge> edgesIterator() {
Bag<DirectedEdge> directedEdges = new Bag<DirectedEdge>();
for (int i = 0; i < vertices; i++) {
for (DirectedEdge edge : adj[i]) {
directedEdges.add(edge);
}
}
return directedEdges;
}
private void check(int node) {
if (node < 0 || node >= vertices) throw new IllegalArgumentException();
}
/**
* Returns the number of edges in this graph.
*/
public int edges() {
return edges;
}
/**
* Returns the number of vertices in this vertices.
*/
public int vertices() {
return vertices;
}
/**
* Returns the graph with edges flipped.
*/
public EdgeWeightedDirectedGraph reverse() {
EdgeWeightedDirectedGraph reverseGraph = new EdgeWeightedDirectedGraph(vertices);
for (int source = 0; source < vertices; source++) {
for (DirectedEdge edge : adjEdges(source)) {
reverseGraph.addEdge(edge.to(), source, edge.weight());
}
}
return reverseGraph;
}
}