import java.util.Map;

import java.util.Set;

import java.util.ArrayList;

public class main{

static public void main(String argv[]){

// Dijkstra

java.util.List<Graph.Vertex<Integer>> verticies = new java.util.ArrayList<Graph.Vertex<Integer>>();

Graph.Vertex<Integer> v1 = new Graph.Vertex<Integer>(1);

verticies.add(v1);

Graph.Vertex<Integer> v2 = new Graph.Vertex<Integer>(2);

verticies.add(v2);

Graph.Vertex<Integer> v3 = new Graph.Vertex<Integer>(3);

verticies.add(v3);

Graph.Vertex<Integer> v4 = new Graph.Vertex<Integer>(4);

verticies.add(v4);

Graph.Vertex<Integer> v5 = new Graph.Vertex<Integer>(5);

verticies.add(v5);

Graph.Vertex<Integer> v6 = new Graph.Vertex<Integer>(6);

verticies.add(v6);

java.util.List<Graph.Edge<Integer>> edges = new java.util.ArrayList<Graph.Edge<Integer>>();

Graph.Edge<Integer> e1_2 = new Graph.Edge<Integer>(7, v1, v2);

edges.add(e1_2);

Graph.Edge<Integer> e1_3 = new Graph.Edge<Integer>(9, v1, v3);

edges.add(e1_3);

Graph.Edge<Integer> e1_6 = new Graph.Edge<Integer>(14, v1, v6);

edges.add(e1_6);

Graph.Edge<Integer> e2_3 = new Graph.Edge<Integer>(10, v2, v3);

edges.add(e2_3);

Graph.Edge<Integer> e2_4 = new Graph.Edge<Integer>(15, v2, v4);

edges.add(e2_4);

Graph.Edge<Integer> e3_4 = new Graph.Edge<Integer>(11, v3, v4);

edges.add(e3_4);

Graph.Edge<Integer> e3_6 = new Graph.Edge<Integer>(2, v3, v6);

edges.add(e3_6);

Graph.Edge<Integer> e5_6 = new Graph.Edge<Integer>(9, v5, v6);

edges.add(e5_6);

Graph.Edge<Integer> e4_5 = new Graph.Edge<Integer>(6, v4, v5);

edges.add(e4_5);

Graph<Integer> undirected = new Graph<Integer>(verticies, edges);

Graph.Vertex<Integer> start = v1;

System.out.println("---Dijkstra---");

java.util.Map<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>> map1 = Dijkstra.getShortestPaths(undirected, start);

System.out.println(getPathMapString(start, map1));

System.out.println("---BellmanFord---");

Map<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>> map2 = BellmanFord.getShortestPaths(undirected, start);

System.out.println(getPathMapString(start, map2));

System.out.println("---Prim---");

Graph.CostPathPair<Integer> pair = Prim.getMinimumSpanningTree(undirected, start);

System.out.println(pair.toString());

}

private static final String getPathMapString(Graph.Vertex<Integer> start, Map<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>> map) {

StringBuilder builder = new StringBuilder();

for (Graph.Vertex<Integer> v : map.keySet()) {

Graph.CostPathPair<Integer> pair = map.get(v);

builder.append("From ").append(start.getValue()).append(" to vertex=").append(v.getValue()).append("\n");

if (pair != null)

builder.append(pair.toString()).append("\n");

}

return builder.toString();

}

private static final String getPathMapString(Map<Graph.Vertex<Integer>, Map<Graph.Vertex<Integer>, Set<Graph.Edge<Integer>>>> paths) {

StringBuilder builder = new StringBuilder();

for (Graph.Vertex<Integer> v : paths.keySet()) {

Map<Graph.Vertex<Integer>, Set<Graph.Edge<Integer>>> map = paths.get(v);

for (Graph.Vertex<Integer> v2 : map.keySet()) {

builder.append("From=").append(v.getValue()).append(" to=").append(v2.getValue()).append("\n");

Set<Graph.Edge<Integer>> path = map.get(v2);

builder.append(path).append("\n");

}

}

return builder.toString();

}

}