package algs64; // section 6.4
import stdlib.*;
import algs13.Bag;
/* ***********************************************************************
 *  Compilation:  javac FlowNetwork.java
 *  Execution:    java FlowNetwork V E
 *  Dependencies: Bag.java FlowEdge.java
 *
 *  A capacitated flow network, implemented using adjacency lists.
 *
 *************************************************************************/
public class FlowNetwork {
	private final int V;
	private int E;
	private final Bag<FlowEdge>[] adj;

	// empty graph with V vertices
	@SuppressWarnings("unchecked")
	public FlowNetwork(int V) {
		this.V = V;
		this.E = 0;
		adj = new Bag[V];
		for (int v = 0; v < V; v++)
			adj[v] = new Bag<>();
	}

	// random graph with V vertices and E edges
	public FlowNetwork(int V, int E) {
		this(V);
		for (int i = 0; i < E; i++) {
			int v = StdRandom.uniform(V);
			int w = StdRandom.uniform(V);
			double capacity = StdRandom.uniform(100);
			addEdge(new FlowEdge(v, w, capacity));
		}
	}

	// graph, read from input stream
	public FlowNetwork(In in) {
		this(in.readInt());
		int E = in.readInt();
		for (int i = 0; i < E; i++) {
			int v = in.readInt();
			int w = in.readInt();
			double capacity = in.readDouble();
			addEdge(new FlowEdge(v, w, capacity));
		}
	}


	// number of vertices and edges
	public int V() { return V; }
	public int E() { return E; }

	// add edge e in both v's and w's adjacency lists
	public void addEdge(FlowEdge e) {
		E++;
		int v = e.from();
		int w = e.to();
		adj[v].add(e);
		adj[w].add(e);
	}

	// return list of edges incident to  v
	public Iterable<FlowEdge> adj(int v) {
		return adj[v];
	}

	// return list of all edges - excludes self loops
	public Iterable<FlowEdge> edges() {
		Bag<FlowEdge> list = new Bag<>();
		for (int v = 0; v < V; v++)
			for (FlowEdge e : adj(v)) {
				if (e.to() != v)
					list.add(e);
			}
		return list;
	}


	// string representation of Graph (excludes self loops) - takes quadratic time
	public String toString() {
		String NEWLINE = System.getProperty("line.separator");
		StringBuilder s = new StringBuilder();
		s.append(V + " " + E + NEWLINE);
		for (int v = 0; v < V; v++) {
			s.append(v + ":  ");
			for (FlowEdge e : adj[v]) {
				if (e.to() != v) s.append(e + "  ");
			}
			s.append(NEWLINE);
		}
		return s.toString();
	}

	// test client
	public static void main(String[] args) {
		In in = new In(args[0]);
		FlowNetwork G = new FlowNetwork(in);
		StdOut.println(G);
	}

}