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 | public class EdgeWeightedDigraph {
|
---|
24 | private final int V;
|
---|
25 | private int E;
|
---|
26 | private Bag<DirectedEdge>[] adj;
|
---|
27 |
|
---|
28 | /**
|
---|
29 | * Create an empty edge-weighted digraph with V vertices.
|
---|
30 | */
|
---|
31 | @SuppressWarnings("unchecked")
|
---|
32 | public EdgeWeightedDigraph(int V) {
|
---|
33 | if (V < 0) throw new RuntimeException("Number of vertices must be nonnegative");
|
---|
34 | this.V = V;
|
---|
35 | this.E = 0;
|
---|
36 | adj = (Bag<DirectedEdge>[]) new Bag[V];
|
---|
37 | for (int v = 0; v < V; v++)
|
---|
38 | adj[v] = new Bag<DirectedEdge>();
|
---|
39 | }
|
---|
40 |
|
---|
41 | /**
|
---|
42 | * Create a edge-weighted digraph with V vertices and E edges.
|
---|
43 | */
|
---|
44 | public EdgeWeightedDigraph(int V, int E) {
|
---|
45 | this(V);
|
---|
46 | if (E < 0) throw new RuntimeException("Number of edges must be nonnegative");
|
---|
47 | for (int i = 0; i < E; i++) {
|
---|
48 | int v = (int) (Math.random() * V);
|
---|
49 | int w = (int) (Math.random() * V);
|
---|
50 | double weight = Math.round(100 * Math.random()) / 100.0;
|
---|
51 | DirectedEdge e = new DirectedEdge(v, w, weight);
|
---|
52 | addEdge(e);
|
---|
53 | }
|
---|
54 | }
|
---|
55 |
|
---|
56 | /**
|
---|
57 | * Create an edge-weighted digraph from input stream.
|
---|
58 | */
|
---|
59 | // public EdgeWeightedDigraph(In in) {
|
---|
60 | // this(in.readInt());
|
---|
61 | // int E = in.readInt();
|
---|
62 | // for (int i = 0; i < E; i++) {
|
---|
63 | // int v = in.readInt();
|
---|
64 | // int w = in.readInt();
|
---|
65 | // double weight = in.readDouble();
|
---|
66 | // addEdge(new DirectedEdge(v, w, weight));
|
---|
67 | // }
|
---|
68 | // }
|
---|
69 |
|
---|
70 | /**
|
---|
71 | * Copy constructor.
|
---|
72 | */
|
---|
73 | public EdgeWeightedDigraph(EdgeWeightedDigraph G) {
|
---|
74 | this(G.V());
|
---|
75 | this.E = G.E();
|
---|
76 | for (int v = 0; v < G.V(); v++) {
|
---|
77 | // reverse so that adjacency list is in same order as original
|
---|
78 | Stack<DirectedEdge> reverse = new Stack<DirectedEdge>();
|
---|
79 | for (DirectedEdge e : G.adj[v]) {
|
---|
80 | reverse.push(e);
|
---|
81 | }
|
---|
82 | for (DirectedEdge e : reverse) {
|
---|
83 | adj[v].add(e);
|
---|
84 | }
|
---|
85 | }
|
---|
86 | }
|
---|
87 |
|
---|
88 | /**
|
---|
89 | * Return the number of vertices in this digraph.
|
---|
90 | */
|
---|
91 | public int V() {
|
---|
92 | return V;
|
---|
93 | }
|
---|
94 |
|
---|
95 | /**
|
---|
96 | * Return the number of edges in this digraph.
|
---|
97 | */
|
---|
98 | public int E() {
|
---|
99 | return E;
|
---|
100 | }
|
---|
101 |
|
---|
102 | /**
|
---|
103 | * Add the edge e to this digraph.
|
---|
104 | */
|
---|
105 | public void addEdge(DirectedEdge e) {
|
---|
106 | int v = e.from();
|
---|
107 | adj[v].add(e);
|
---|
108 | E++;
|
---|
109 | }
|
---|
110 |
|
---|
111 | /**
|
---|
112 | * Return the edges leaving vertex v as an Iterable.
|
---|
113 | * To iterate over the edges leaving vertex v, use foreach notation:
|
---|
114 | * <tt>for (DirectedEdge e : graph.adj(v))</tt>.
|
---|
115 | */
|
---|
116 | public Iterable<DirectedEdge> adj(int v) {
|
---|
117 | return adj[v];
|
---|
118 | }
|
---|
119 |
|
---|
120 | /**
|
---|
121 | * Return all edges in this graph as an Iterable.
|
---|
122 | * To iterate over the edges, use foreach notation:
|
---|
123 | * <tt>for (DirectedEdge e : graph.edges())</tt>.
|
---|
124 | */
|
---|
125 | public Iterable<DirectedEdge> edges() {
|
---|
126 | Bag<DirectedEdge> list = new Bag<DirectedEdge>();
|
---|
127 | for (int v = 0; v < V; v++) {
|
---|
128 | for (DirectedEdge e : adj(v)) {
|
---|
129 | list.add(e);
|
---|
130 | }
|
---|
131 | }
|
---|
132 | return list;
|
---|
133 | }
|
---|
134 |
|
---|
135 | /**
|
---|
136 | * Return number of edges leaving v.
|
---|
137 | */
|
---|
138 | public int outdegree(int v) {
|
---|
139 | return adj[v].size();
|
---|
140 | }
|
---|
141 |
|
---|
142 | /**
|
---|
143 | * Return a string representation of this graph.
|
---|
144 | */
|
---|
145 | public String toString() {
|
---|
146 | String NEWLINE = System.getProperty("line.separator");
|
---|
147 | StringBuilder s = new StringBuilder();
|
---|
148 | s.append(V + " " + E + NEWLINE);
|
---|
149 | for (int v = 0; v < V; v++) {
|
---|
150 | s.append(v + ": ");
|
---|
151 | for (DirectedEdge e : adj[v]) {
|
---|
152 | s.append(e + " ");
|
---|
153 | }
|
---|
154 | s.append(NEWLINE);
|
---|
155 | }
|
---|
156 | return s.toString();
|
---|
157 | }
|
---|
158 | }
|
---|