package graph;

import java.util.ArrayList;
import java.util.Stack;

public class GraphAdjListOperator extends GraphOperator
{

    protected static int[] etv, ltv; /* ????????????????????????????????? */
    protected static Stack<Integer> stack2;   /* ????????????????? */
    protected static int top2;	   /* ????stack2????? */
    protected ArrayList<VertexNode> adjList = new ArrayList<VertexNode>();

    /* ??????????????? */
    protected static GraphAdjListOperator createALGraph(GraphMatrixOperator g)
    {
        GraphAdjListOperator gl = new GraphAdjListOperator();
        gl.numVertexes = g.numVertexes;
        gl.numEdges = g.numEdges;

        for (int i = 0; i < g.numVertexes; i++) /* ???????????????????? */
        {
            addVertex(gl, i, g.getVertexes().get(i));
            gl.adjList.get(i).setIn(0);
//            gl.adjList[i].firstedge=NULL; 	/* ??????????? */
        }

        for (int i = 0; i < g.numVertexes; i++) /* ??????? */
        {
            for (int j = 0; j < g.numVertexes; j++)
            {
                EdgeType edgeType = g.arcList.get(i).get(j);
                if (edgeType.weight != 0 && edgeType.weight < INFINITY)
                {
                    int in = gl.adjList.get(j).getIn() + 1;
                    addEdgeNode(gl, i, j, edgeType.weight, in);
                }
            }
        }
        return gl;
    }

    protected static void addVertex(GraphAdjListOperator g, int i, VertexType data)
    {
        VertexNode v = new VertexNode();
        v.setData(data); 	/* ????????? */
        g.adjList.add(v);
//        g.adjList.set(i, v);
    }

    protected static void addEdgeNode(GraphAdjListOperator g, int i, int j, int weight, int in)
    {
        EdgeNode e = new EdgeNode(); /* ???????????,??????? */
        e.setAdjvex(j);					/* ???????j */
        e.setInfo(new EdgeType(weight));
        e.setNext(g.adjList.get(i).getFirstedge());	/* ??e?????????????????????  ????*/
        g.adjList.get(i).setFirstedge(e);		/* ????????????????e */
        g.adjList.get(j).setIn(in);
    }

    /* ??????????GL??????????????????????????????1??????????????0?? */
    public static Boolean TopologicalSort(GraphAdjListOperator gl)
    {
        int top = 0;  /* ????????????  */
        int count = 0;/* ??????????????????  */
        Stack<Integer> stack = new Stack<Integer>();	/* ?????????0????????  */

        for (int i = 0; i < gl.numVertexes; i++)
        {
            if (0 == gl.adjList.get(i).getIn()) /* ??????0???????? */
            {
                ++top;
                stack.push(i);
            }
        }

        top2 = 0;
        etv = new int[gl.numVertexes]; /* ????????????????? */
        for (int i = 0; i < gl.numVertexes; i++)
        {
            etv[i] = 0;    /* ????? */
        }
        stack2 = new Stack<Integer>();/* ?????????????? */
        int gettop;
        System.out.println("topologicalSort:\t");
        while (top != 0)
        {
            gettop = stack.pop();
            top--;
            System.out.println(gl.adjList.get(gettop).getData().getName());
            count++;        /* ???i??????????? */
            ++top2;
            stack2.push(gettop);        /* ???????????????????????????? */
            EdgeNode e = gl.adjList.get(gettop).getFirstedge();
            while (null != e)
            {
                int k = e.getAdjvex();
                int in = gl.adjList.get(k).getIn();
                gl.adjList.get(k).setIn(--in);
                if (0 == in)        /* ??i???????????????1??????1???0??????? */
                {
                    ++top;
                    stack.push(k);
                }

                if ((etv[gettop] + e.getInfo().weight) > etv[k])    /* ??????????????????????etv? */
                {
                    etv[k] = etv[gettop] + e.getInfo().weight;
                }
                if (null == e.getNext())
                {
                    break;
                }
                e=e.getNext();
            }
        }
        System.out.println("\n");
        return count >= gl.numVertexes;
    }


    /* ????????,GL??????????G???????? */
    public static void criticalPath(GraphAdjListOperator gl)
    {

//        int ete, lte;  /* ????????????????????????????? */
        TopologicalSort(gl);   /* ????????????????????etv??stack2??? */
        initLtv(gl);

        calcLtv(gl);

        printLtv(gl);

        calcCriticalPath(gl);
    }

    private static void calcCriticalPath(GraphAdjListOperator gl)
    {
        for (int j = 0; j < gl.numVertexes; j++)        /* ??ete,lte????? */
        {
            EdgeNode e = gl.adjList.get(j).getFirstedge();
            while (null != e)
            {

                int k = e.getAdjvex();
                int ete = etv[j];        /* ???????????? */
                int lte = ltv[k] - e.getInfo().weight; /* ??????????? */
                if (ete == lte)    /* ?????????????????? */
                {
                    System.out.println(gl.adjList.get(j).getData().getName() + "-" + gl.adjList.get(k).getData().getName() + ":" + e.getInfo().weight);
                }
                if (null == e.getNext())
                {
                    break;
                }
                e=e.getNext();
            }
        }
    }

    private static void calcLtv(GraphAdjListOperator gl)
    {
        while (top2 != 0)    /* ???????ltv */
        {
            int gettop = stack2.pop();
            top2--;
            EdgeNode e = gl.adjList.get(gettop).getFirstedge();
            while (null != e)
            {
                int k = e.getAdjvex();
                if (ltv[k] - e.getInfo().weight < ltv[gettop])
                {
                    ltv[gettop] = ltv[k] - e.getInfo().weight;
                }
                if (null == e.getNext())
                {
                    break;
                }
                e=e.getNext();
            }

        }
    }

    private static void printLtv(GraphAdjListOperator gl)
    {
        System.out.println("ltv:\t");
        for (int i = 0; i < gl.numVertexes; i++)
        {
            System.out.println(ltv[i]);
        }
        System.out.println("\n");
    }

    private static void initLtv(GraphAdjListOperator gl)
    {
        ltv = new int[gl.numVertexes]; /* ????????????????? */
        for (int i = 0; i < gl.numVertexes; i++)
        {
            ltv[i] = etv[gl.numVertexes - 1];    /* ????? */
        }

        System.out.println("etv:\t");
        for (int i = 0; i < gl.numVertexes; i++)
        {
            System.out.println(etv[i]);
        }
        System.out.println("\n");
    }


    public static void main(String[] args)
    {
//        String[] src = new String[]{"V0,V1,3", "V0,V2,5", "V1,V2,1" ,"V1,V3,1" ,"V3,V2,3","V3,V4,1","V2,V4,1"};
        String[] src = new String[]{
                "V0,V1,3", "V0,V2,4", "V1,V3,5", "V1,V4,6", "V2,V3,8", "V2,V5,7", "V3,V4,3", "V4,V6,9", "V4,V7,4", "V5,V7,6", "V7,V8,5", "V8,V9,3 ", "V6,V9,2"
        };

        GraphMatrixOperator g = createMGraph(src);
        GraphAdjListOperator gl = createALGraph(g);
        criticalPath(gl);

    }


}

图——关键路径用JAVA代码实现,布布扣,bubuko.com

图——关键路径用JAVA代码实现