1 | // License: GPL v3 or later courtesy of author Kevin Wayne
|
---|
2 | package edu.princeton.cs.algs4;
|
---|
3 |
|
---|
4 | /*************************************************************************
|
---|
5 | * Compilation: javac EdgeWeightedDigraph.java
|
---|
6 | * Execution: java EdgeWeightedDigraph V E
|
---|
7 | * Dependencies: Bag.java DirectedEdge.java
|
---|
8 | *
|
---|
9 | * An edge-weighted digraph, implemented using adjacency lists.
|
---|
10 | *
|
---|
11 | *************************************************************************/
|
---|
12 |
|
---|
13 | /**
|
---|
14 | * The <tt>EdgeWeightedDigraph</tt> class represents an directed graph of vertices
|
---|
15 | * named 0 through V-1, where each edge has a real-valued weight.
|
---|
16 | * It supports the following operations: add an edge to the graph,
|
---|
17 | * iterate over all of edges leaving a vertex.
|
---|
18 | * Parallel edges and self-loops are permitted.
|
---|
19 | * <p>
|
---|
20 | * For additional documentation, see <a href="http://algs4.cs.princeton.edu/44sp">Section 4.4</a> of
|
---|
21 | * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
|
---|
22 | */
|
---|
23 |
|
---|
24 |
|
---|
25 |
|
---|
26 | public class EdgeWeightedDigraph {
|
---|
27 | private final int V;
|
---|
28 | private int E;
|
---|
29 | private Bag<DirectedEdge>[] adj;
|
---|
30 |
|
---|
31 | /**
|
---|
32 | * Create an empty edge-weighted digraph with V vertices.
|
---|
33 | */
|
---|
34 | public EdgeWeightedDigraph(int V) {
|
---|
35 | if (V < 0) throw new RuntimeException("Number of vertices must be nonnegative");
|
---|
36 | this.V = V;
|
---|
37 | this.E = 0;
|
---|
38 | adj = (Bag<DirectedEdge>[]) new Bag[V];
|
---|
39 | for (int v = 0; v < V; v++)
|
---|
40 | adj[v] = new Bag<DirectedEdge>();
|
---|
41 | }
|
---|
42 |
|
---|
43 | /**
|
---|
44 | * Create a edge-weighted digraph with V vertices and E edges.
|
---|
45 | */
|
---|
46 | public EdgeWeightedDigraph(int V, int E) {
|
---|
47 | this(V);
|
---|
48 | if (E < 0) throw new RuntimeException("Number of edges must be nonnegative");
|
---|
49 | for (int i = 0; i < E; i++) {
|
---|
50 | int v = (int) (Math.random() * V);
|
---|
51 | int w = (int) (Math.random() * V);
|
---|
52 | double weight = Math.round(100 * Math.random()) / 100.0;
|
---|
53 | DirectedEdge e = new DirectedEdge(v, w, weight);
|
---|
54 | addEdge(e);
|
---|
55 | }
|
---|
56 | }
|
---|
57 |
|
---|
58 | /**
|
---|
59 | * Create an edge-weighted digraph from input stream.
|
---|
60 | */
|
---|
61 | // public EdgeWeightedDigraph(In in) {
|
---|
62 | // this(in.readInt());
|
---|
63 | // int E = in.readInt();
|
---|
64 | // for (int i = 0; i < E; i++) {
|
---|
65 | // int v = in.readInt();
|
---|
66 | // int w = in.readInt();
|
---|
67 | // double weight = in.readDouble();
|
---|
68 | // addEdge(new DirectedEdge(v, w, weight));
|
---|
69 | // }
|
---|
70 | // }
|
---|
71 |
|
---|
72 | /**
|
---|
73 | * Copy constructor.
|
---|
74 | */
|
---|
75 | public EdgeWeightedDigraph(EdgeWeightedDigraph G) {
|
---|
76 | this(G.V());
|
---|
77 | this.E = G.E();
|
---|
78 | for (int v = 0; v < G.V(); v++) {
|
---|
79 | // reverse so that adjacency list is in same order as original
|
---|
80 | Stack<DirectedEdge> reverse = new Stack<DirectedEdge>();
|
---|
81 | for (DirectedEdge e : G.adj[v]) {
|
---|
82 | reverse.push(e);
|
---|
83 | }
|
---|
84 | for (DirectedEdge e : reverse) {
|
---|
85 | adj[v].add(e);
|
---|
86 | }
|
---|
87 | }
|
---|
88 | }
|
---|
89 |
|
---|
90 | /**
|
---|
91 | * Return the number of vertices in this digraph.
|
---|
92 | */
|
---|
93 | public int V() {
|
---|
94 | return V;
|
---|
95 | }
|
---|
96 |
|
---|
97 | /**
|
---|
98 | * Return the number of edges in this digraph.
|
---|
99 | */
|
---|
100 | public int E() {
|
---|
101 | return E;
|
---|
102 | }
|
---|
103 |
|
---|
104 |
|
---|
105 | /**
|
---|
106 | * Add the edge e to this digraph.
|
---|
107 | */
|
---|
108 | public void addEdge(DirectedEdge e) {
|
---|
109 | int v = e.from();
|
---|
110 | adj[v].add(e);
|
---|
111 | E++;
|
---|
112 | }
|
---|
113 |
|
---|
114 |
|
---|
115 | /**
|
---|
116 | * Return the edges leaving vertex v as an Iterable.
|
---|
117 | * To iterate over the edges leaving vertex v, use foreach notation:
|
---|
118 | * <tt>for (DirectedEdge e : graph.adj(v))</tt>.
|
---|
119 | */
|
---|
120 | public Iterable<DirectedEdge> adj(int v) {
|
---|
121 | return adj[v];
|
---|
122 | }
|
---|
123 |
|
---|
124 | /**
|
---|
125 | * Return all edges in this graph as an Iterable.
|
---|
126 | * To iterate over the edges, use foreach notation:
|
---|
127 | * <tt>for (DirectedEdge e : graph.edges())</tt>.
|
---|
128 | */
|
---|
129 | public Iterable<DirectedEdge> edges() {
|
---|
130 | Bag<DirectedEdge> list = new Bag<DirectedEdge>();
|
---|
131 | for (int v = 0; v < V; v++) {
|
---|
132 | for (DirectedEdge e : adj(v)) {
|
---|
133 | list.add(e);
|
---|
134 | }
|
---|
135 | }
|
---|
136 | return list;
|
---|
137 | }
|
---|
138 |
|
---|
139 | /**
|
---|
140 | * Return number of edges leaving v.
|
---|
141 | */
|
---|
142 | public int outdegree(int v) {
|
---|
143 | return adj[v].size();
|
---|
144 | }
|
---|
145 |
|
---|
146 |
|
---|
147 |
|
---|
148 | /**
|
---|
149 | * Return a string representation of this graph.
|
---|
150 | */
|
---|
151 | public String toString() {
|
---|
152 | String NEWLINE = System.getProperty("line.separator");
|
---|
153 | StringBuilder s = new StringBuilder();
|
---|
154 | s.append(V + " " + E + NEWLINE);
|
---|
155 | for (int v = 0; v < V; v++) {
|
---|
156 | s.append(v + ": ");
|
---|
157 | for (DirectedEdge e : adj[v]) {
|
---|
158 | s.append(e + " ");
|
---|
159 | }
|
---|
160 | s.append(NEWLINE);
|
---|
161 | }
|
---|
162 | return s.toString();
|
---|
163 | }
|
---|
164 |
|
---|
165 | /**
|
---|
166 | * Test client.
|
---|
167 | */
|
---|
168 | // public static void main(String[] args) {
|
---|
169 | // In in = new In(args[0]);
|
---|
170 | // EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
|
---|
171 | // StdOut.println(G);
|
---|
172 | // }
|
---|
173 |
|
---|
174 | }
|
---|