C12

package PAZ1b.cviceni11;

import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import sk.upjs.jpaz2.*;
import sk.upjs.paz.graph.*;

public class Launcher {

        public static List<Edge> primCudny(Graph g, Vertex s) {
//              ds[s] = 0;
//              p[s] = NULL;
//              for (v: vrcholy G okrem s)
//              ds[v] = ∞;
                Map<Vertex, Double> ds = g.createVertexMap(Double.POSITIVE_INFINITY);
                ds.put(s, 0d);
                Map<Vertex, Vertex> p = g.createVertexMap(null);

//              Q = vrcholy G;
                Set<Vertex> Q = g.getVertices();
                Set<Vertex> vybavene = new HashSet<Vertex>();

//              while (!Q.isEmpty()) {
                while (Q.size() != vybavene.size()) {
//                      vyber v z Q taký, že
//                      ds[v] = min{ds[u]|u patrí do Q}
                        double min = Double.MAX_VALUE;
                        Vertex v = null;
                        for (Vertex u : Q) {
                                if (ds.get(u) < min && !vybavene.contains(u)) {
                                        min = ds.get(u);
                                        v = u;
                                }
                        }
                        vybavene.add(v);
                        System.out.println(v);
//                      for (w: susedia vrcholu v)
//                      if (w  Q and c(v,w) < ds[w] ){
//                      p[w] = v;
//                      ds[w] = c(v,w);
                        for (Vertex w : v.getOutNeighbours()) {
                                if (!vybavene.contains(w) && g.getEdge(v, w).getWeight() < ds.get(w)) {
                                        ds.put(w, g.getEdge(v, w).getWeight());
                                        p.put(w, v);
                                }
                        }
                }

                System.out.println(p);

                return null;
        }

        public static List<Edge> prim(Graph g, Vertex s) {
//              ds[s] = 0;
//              p[s] = NULL;
//              for (v: vrcholy G okrem s)
//              ds[v] = ∞;
                Map<Vertex, Double> ds = g.createVertexMap(Double.POSITIVE_INFINITY);
                ds.put(s, 0d);
                Map<Vertex, Vertex> p = g.createVertexMap(null);

//              Q = vrcholy G;
                Set<Vertex> Q = new HashSet<Vertex>();
                Q.addAll(g.getVertices());
                System.out.println(Q);

//              while (!Q.isEmpty()) {
                while (!Q.isEmpty()) {
//                      vyber v z Q taký, že
//                      ds[v] = min{ds[u]|u patrí do Q}
                        double min = Double.MAX_VALUE;
                        Vertex v = null;
                        for (Vertex u : Q) {
                                if (ds.get(u) < min) {
                                        min = ds.get(u);
                                        v = u;
                                }
                        }
                        Q.remove(v);
//                      for (w: susedia vrcholu v)
//                      if (w  Q and c(v,w) < ds[w] ){
//                      p[w] = v;
//                      ds[w] = c(v,w);
                        for (Vertex w : v.getOutNeighbours()) {
                                if (Q.contains(w) && g.getEdge(v, w).getWeight() < ds.get(w)) {
                                        ds.put(w, g.getEdge(v, w).getWeight());
                                        p.put(w, v);
                                }
                        }
                }

                System.out.println(p);

                return null;
        }

        public static void main(String[] args) {
                Graph g = Graph.createFromFile("graf.txt");
                g.setDirected(true);
                System.out.println(g);
                prim(g, g.getVertex("D"));

        }
}