package org.cloudbus.cloudsim.codes.minispanningtree;

import java.util.*;

/**
 * ClassName Graph
 * Description
 * Create by HW
 * Date 2022/5/16 17:50
 */
public class Graph {
    public  ArrayList<Edge> list=new ArrayList<>();
    public HashMap<String,EdgeNode> nodeMap=new HashMap<>();

    public void minitree(){
        String nodeName1;
        String nodeName2;
        //用于存放最小生成树的边
        Map<String, String> Map=new HashMap<>();
        sortList(list);
        int total=0;
        for (int i = 0,j=0; i <list.size(); i++) {
            nodeName1=find(Map,list.get(i).getEdgeNode1().getEdgename());
            nodeName2=find(Map,list.get(i).getEdgeNode2().getEdgename());
            if (! nodeName1.equals(nodeName2)){
                Map.put(nodeName1,nodeName2);
                total+=list.get(i).getWeight();
                System.out.println("路径"+j++ +":"+"开始结点："+list.get(i).getEdgeNode1().getEdgename()
                        +";结束结点："+list.get(i).getEdgeNode2().getEdgename()+";权值："+list.get(i).getWeight());
            }
        }
        System.out.println("总共的花销为："+total);
    }


    //生成图
    public void creatGraph(String node1,String node2, int weight){
        EdgeNode edgeNode = new EdgeNode(node1);
        EdgeNode edgeNode1 = new EdgeNode(node2);
        if(edgeNode != null && edgeNode1 != null){
            nodeMap.put(node1,edgeNode);
            nodeMap.put(node2,edgeNode1);
        }
        list.add(new Edge(edgeNode,edgeNode1,weight));
    }

//判断是否成环
    public String find(Map<String, String> map, String nodeName){
        while(map.get(nodeName) != null){
            nodeName =map.get(nodeName);
        }
        return nodeName;
    }

    public void sortList(ArrayList<Edge> list){
        list.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.getWeight() - o2.getWeight();
            }
        });
    }
}
