using System;
using System.Collections.Generic;
//using System.Linq;
//using System.Text;
//using System.Threading.Tasks;

//namespace McGuffinsOfflineNetworkWorkshop {
    public class MNetwork {
        // Data members that you want serialized into XML need to be public.
        // Data members that should NOT be serialized need to be private or marked with [System.Xml.Serialization.XmlIgnoreAttribute]

        [System.Xml.Serialization.XmlIgnoreAttribute]
        public const float SPRING_REST_LENGTH = 1.0f;

        public bool hasLabelStrings = false;
        public bool has2DPositions = false;
        public bool has2DLabels = false;
        public bool has2DEdgeRouting = false;
        public bool has3DPositions = false;

        public List<MNode> nodes = new List<MNode>();
        public List<MEdge> edges = new List<MEdge>();

        // This stores the desired distance between every pair of nodes.
        [System.Xml.Serialization.XmlIgnoreAttribute]
        private MSymmetricMatrix shortestPathMatrix = null;
        [System.Xml.Serialization.XmlIgnoreAttribute]
        private bool isShortestPathMatrixDirty = true;

        private bool isLayoutConstrainedTo2D = false; // if false, layout is done in 3D
        public bool getLayoutConstrainedTo2D() { return isLayoutConstrainedTo2D; }
        public void setLayoutConstrainedTo2D(bool flag) {
            if (flag != isLayoutConstrainedTo2D) {
                isLayoutConstrainedTo2D = flag;
                if (isLayoutConstrainedTo2D) {
                    // We set the y coordinate of all nodes to zero
                    for (int i = 0; i < nodes.Count; ++i) {
                        MNode n_i = nodes[i];
                        n_i.y = 0;
                    }
                }
                else {
                    // We slightly perturb the nodes in different y directions.
                    // If we don't do this, and all the nodes have zero y coordinate,
                    // then any 3D layout algorithm may be unable to move the nodes off the y=0 plane.
                    float dy = 0.01f;
                    for (int i = 0; i < nodes.Count; i += 2 /* only perturb every 2nd node */ ) {
                        MNode n_i = nodes[i];
                        n_i.y += dy;
                    }
                }
            }
        }

        public void copyTemporaryCoordinatesTo2DForSaving() {
            for (int i = 0; i < nodes.Count; ++i) {
                MNode n = nodes[i];
                n.x_2D = n.x;
                n.y_2D = n.z;
            }
        }
        public void copyTemporaryCoordinatesTo3DForSaving() {
            for (int i = 0; i < nodes.Count; ++i) {
                MNode n = nodes[i];
                n.x_3D = n.x;
                n.y_3D = n.y;
                n.z_3D = n.z;
            }
        }
        public void restoreSaved2DCoordinatesToTemporaryCoordinates( bool zeroOutThirdDimension ) {
            for (int i = 0; i < nodes.Count; ++i) {
                MNode n = nodes[i];
                n.x = n.x_2D;
                if ( zeroOutThirdDimension ) n.y = 0;
                n.z = n.y_2D;
            }
        }
        public void restoreSaved3DCoordinatesToTemporaryCoordinates() {
            for (int i = 0; i < nodes.Count; ++i) {
                MNode n = nodes[i];
                n.x = n.x_3D;
                n.y = n.y_3D;
                n.z = n.z_3D;
            }
        }

        // The return value of this can be used to index into nodes.
        public int getIndexOfNode(MNode n) {
            MLogger.Assert(n != null, "gvfk1o88nk");

            // If the cached index is NOT correct ...
            int index = n.getIndex();
            if (index < 0 || index >= nodes.Count || getNode(index) != n) {
                // ... recompute all the indices
                // (this takes linear time, but subsequent calls
                // for this and other nodes will be fast,
                // until the next time the cached indices are
                // made invalid because some nodes have been
                // added or deleted)
                for (int i = 0; i < nodes.Count; ++i) {
                    nodes[i].setIndex(i);
                }
            }

            // assert that the cached index IS now correct
            MLogger.Assert(getNode(n.getIndex()) == n, "qrqmx6joiu");

            // return the cached index
            return n.getIndex();
        }


        public int getNumNodes() {
            return nodes.Count;
        }
        public int getNumEdges() {
            return edges.Count;
        }
        public MNode getNode(int index) {
            if (index < 0 || index >= nodes.Count)
                return null;
            return nodes[index];
        }
        public List<MNode> getNodes() {
            return nodes;
        }
        public void addNode(MNode n) {
            if (!nodes.Contains(n)) {
                nodes.Add(n);
                n.setNetwork(this);
            }
        }
        public bool areNodesAdjacent( int indexOfNode1, int indexOfNode2 ) {
            MNode n1 = nodes[indexOfNode1];
            MNode n2 = nodes[indexOfNode2];
            if ( n1.degree() > n2.degree() ) {
                // swap
                int tmp = indexOfNode1;
                indexOfNode1 = indexOfNode2;
                indexOfNode2 = tmp;
                MNode tmp_n = n1;
                n1 = n2;
                n2 = tmp_n;
            }
            MLogger.Assert(n1.degree() <= n2.degree(),"8oww3jrdyr");
            // n1 has the smaller (or equal) number of neighbors, so we search over its neighbors, not n2's neighbors.
            foreach ( int indexOfEdge in n1.indicesOfEdges ) {
                if (edges[indexOfEdge].getIndexOfOtherNode(indexOfNode1) == indexOfNode2)
                    return true;
            }
            return false;
        }
        public bool areNodesAdjacent(MNode n1, MNode n2) {
            int indexOfNode1 = getIndexOfNode(n1);
            int indexOfNode2 = getIndexOfNode(n2);
            return areNodesAdjacent(indexOfNode1, indexOfNode2);
        }
        public void addEdge(int indexOfNode1, int indexOfNode2) {
            if (indexOfNode1 < 0 || indexOfNode2 < 0 || indexOfNode1 == indexOfNode2) return;

            if (areNodesAdjacent(indexOfNode1, indexOfNode2)) return;
            MEdge e = new MEdge();
            e.indexOfNode1 = indexOfNode1;
            e.indexOfNode2 = indexOfNode2;
            int indexOfEdge = edges.Count;
            edges.Add(e);
            MNode n1 = nodes[indexOfNode1];
            MNode n2 = nodes[indexOfNode2];
            n1.indicesOfEdges.Add(indexOfEdge);
            n2.indicesOfEdges.Add(indexOfEdge);
            MLogger.Assert(areNodesAdjacent(indexOfNode1, indexOfNode2), "te5y8n37cb");
        }
        public void addEdge(MNode n1, MNode n2) {
            if (n1 == n2 || n1 == null || n2 == null) return;
            int indexOfNode1 = getIndexOfNode(n1);
            int indexOfNode2 = getIndexOfNode(n2);
            addEdge(indexOfNode1, indexOfNode2);
        }


        public int getMinDegree() {
            if (nodes.Count == 0) return -1;
            int returnValue = nodes[0].degree();
            for (int i = 1; i < nodes.Count; ++i) {
                MNode n = nodes[i];
                if (n.degree() < returnValue) returnValue = n.degree();
            }
            return returnValue;
        }
        public int getMaxDegree() {
            int returnValue = 0;
            for (int i = 0; i < nodes.Count; ++i) {
                MNode n = nodes[i];
                if (n.degree() > returnValue) returnValue = n.degree();
            }
            return returnValue;
        }
        public int[] getDegreeHistogram() {
            int[] histo = new int[getMaxDegree() + 1];
            for (int i = 0; i < nodes.Count; ++i) {
                histo[nodes[i].degree()]++;
            }
            return histo;
        }
        public string getDegreeHistogramString(bool commented) { // returns a multi-line string describing the distribution of degrees
            int[] histo = getDegreeHistogram();
            string returnValue = "";
            for (int i = 0; i < histo.Length; ++i) {
                if (histo[i] > 0)
                    returnValue += ((commented ? "#  " : "") + "deg " + i + ": " + histo[i] + "\n");
            }
            return returnValue;
        }



        private void computeShortestPathMatrix() {
            if (isShortestPathMatrixDirty) {
                MLogger.Log("Computing shortest path matrix ...",1);
                int N = nodes.Count;
                if (N < 2) return;

                shortestPathMatrix = new MSymmetricMatrix(N, false);

                // Initialize the matrix by filling the (non-diagonal) elements with
                // a value signifying "not yet computed".
                const float NOT_YET_COMPUTED = -1; // should be negative
                for (int i = 1; i < N; ++i) {
                    for (int j = 0; j < i /*only traverse lower triangular half*/; ++j) {
                        shortestPathMatrix.set(i, j, NOT_YET_COMPUTED);
                    }
                }

                // For every edge in the network, write the edge's associated length in the matrix
                for (int i1 = 0; i1 <= N - 2; ++i1) {
                    MNode n1 = nodes[i1];
                    for (int i2 = i1 + 1; i2 < N; ++i2) {
                        MNode n2 = nodes[i2];
                        if (areNodesAdjacent(n1, n2)) {

                            // The value stored here should be the
                            // desired distance between the nodes.
                            // The stress majorization layout will try to match this distance.
                            // For simplicity in this example code, the distance used here is constant;
                            // that is, we assume that the similarity
                            // (and therefore the desired distance)
                            // between any adjacent nodes is a constant.
                            // However, in practice, the distance stored here could
                            // be a function of the similarity between nodes n1 and n2;
                            // for example ( 1.0 / similarity(n1,n2) ) * SPRING_REST_LENGTH

                            shortestPathMatrix.set(i1, i2, SPRING_REST_LENGTH);
                        }
                    }
                }

                // Now the matrix contains the desired distances associated with adjacent pairs of nodes,
                // but we want to compute the desired distances between *any* pair of nodes.
                // To find all these distances, we use the Floyd–Warshall algorithm
                // ( http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm )
                // which finds all shortest paths between the nodes of a graph in O(N^3) time.
                // Note that we save time by only computing the lower triangular half of the matrix,
                // since the matrix is symmetrical.
                //
                // The idea here is to check if we can find a shorter path from node i to node j through node k,
                // i.e. check if distance(i,j) > distance(i,k) + distance(k,j),
                // and if so, then update distance(i,j) to be smaller,
                // and do this for each node k (in an outer loop).

                for (int k = 0; k < N; ++k) {
                    for (int i = 1; i < N; ++i) {
                        if (i == k)
                            continue;
                        float distance_i_k = shortestPathMatrix.get(i, k);
                        if (distance_i_k > 0) {
                            for (int j = 0; j < i /*only traverse lower triangular half*/; ++j) {
                                if ( j == k ) continue;
                                MLogger.Assert( j != i );
                                float distance_k_j = shortestPathMatrix.get(k, j);
                                if (distance_k_j == NOT_YET_COMPUTED)
                                    continue;
                                float distance_i_j = shortestPathMatrix.get(i, j);
                                if (distance_i_j == NOT_YET_COMPUTED || distance_i_j > distance_i_k + distance_k_j) {
                                    distance_i_j = distance_i_k + distance_k_j;
                                    shortestPathMatrix.set(i, j, distance_i_j);
                                }
                            }
                        }
                    }
                }

                MLogger.Log("... done.",1);
                isShortestPathMatrixDirty = false;
            }
        }

        public bool findShortestPath( MNode startNode, MNode endNode, List<int> path ) {
            path.Clear();

            if ( startNode == null || endNode == null )
                return false;
            if ( startNode == endNode ) {
                // this is a trivial path of one node
                path.Add( getIndexOfNode( startNode ) );
                return true;
            }

            Queue<MNode> queue = new Queue<MNode>();

            foreach ( MNode n in this.nodes ) {
                n.bfs_isDiscovered = false;
                n.bfs_predecessor = null;
            }

            bool endNodeFound = false;
            startNode.bfs_isDiscovered = true;
            queue.Enqueue( startNode );
            while ( !endNodeFound && queue.Count > 0 ) {
                MNode currentNode = queue.Dequeue();

                for ( int i = currentNode.degree()-1; i >= 0; i-- ) {
                    MNode neighbor = currentNode.getIthNeighbor(i);
                    if ( ! neighbor.bfs_isDiscovered ) {
                        neighbor.bfs_isDiscovered = true;
                        neighbor.bfs_predecessor = currentNode;
                        if ( neighbor == endNode ) {
                            endNodeFound = true;
                            break;
                        }
                        queue.Enqueue( neighbor );
                    }
                }
            }
            if ( endNodeFound ) {
                MNode n = endNode;
                do {
                    path.Add( getIndexOfNode( n ) );
                    n = n.bfs_predecessor;
                } while ( n != null );
                return true;
            }
            return false;
        }

        public MSymmetricMatrix getShortestPathMatrix() {
            if (isShortestPathMatrixDirty)
                computeShortestPathMatrix();
            return shortestPathMatrix;
        }
        private void markShortestPathMatrixDirty() {
            shortestPathMatrix = null;
            isShortestPathMatrixDirty = true;
        }
        public int getTopologicalDiameter() {
            MSymmetricMatrix m = getShortestPathMatrix();
            int N = nodes.Count;
            int maxLength = 0;
            for (int i = 1; i < N; ++i) {
                for (int j = 0; j < i /*only traverse lower triangular half*/; ++j) {
                    int length = (int)Math.Round( m.get(i, j) );
                    if ( length > maxLength )
                        maxLength = length;
                }
            }
            return maxLength;
        }

        // This returns a matrix with one row and one column for each node.
        // Each cell (i,j) in the matrix contains an integer equal to the number of neighbors
        // shared by node i and node j.
        public MSymmetricMatrix getSharedNeighborsMatrix() {
            // Ensure that the shortest path matrix is up-to-date.
            getShortestPathMatrix();

            int N = nodes.Count;

            MSymmetricMatrix sharedNeighborsMatrix = new MSymmetricMatrix(N, false);

            if (N < 2) return sharedNeighborsMatrix;

            for (int i = 1; i < N; ++i) { // only traverse lower triangular half
                for (int j = 0; j < i; ++j) {
                    if ( shortestPathMatrix.get(i, j ) > 2 ) {
                        // there cannot be any neighbors in common
                        sharedNeighborsMatrix.set(i, j, 0);
                    }
                    else {
                        int numNeigborsInCommon = 0;
                        MNode n_i = nodes[i];
                        foreach ( int indexOfEdge in n_i.indicesOfEdges ) {
                            int k = edges[indexOfEdge].getIndexOfOtherNode(i); // index of candidate common neighbor
                            if ( areNodesAdjacent( k, j ) ) {
                                numNeigborsInCommon ++;
                            }
                        }
                        sharedNeighborsMatrix.set(i, j, numNeigborsInCommon);
                    }
                }
            }
            return sharedNeighborsMatrix;
        }

    }
//}
