// GraphAdjMatrix (graphADT) -- adjacency matrix implementation

// Update  '07 - uses ArrayList not the depreciated Vector object
//             - no longer uses depreciated StringTokenizer
//             - java 1.6 Type casting
//             - no longer keeps track of 'space' allocated

package graphADT;

import java.io.*;
import java.util.*;

/*
 * Current implementation uses adjacency matrix form of a graph.
 */
public class GraphAdjMatrix implements Graph
{

    //  Internal Representation and Constructors
    //
    protected int order;			// Number of vertices.
    protected boolean adj[][];		// Adjacency matrix of graph.

    public GraphAdjMatrix() 		// default constructor
    {
        order = 0;
    }

    public GraphAdjMatrix(GraphAdjMatrix G) // copy constructor
    {
        int n = order = G.order();
        if ( n>0 )  adj = new boolean[n][n]; 

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                adj[i][j] = G.adj[i][j];
    }
    public GraphAdjMatrix(Graph G) 	// conversion constructor
    {
        int n = order = G.order();
        if ( n>0 ) adj = new boolean[n][n];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (G.isArc(i,j)) adj[i][j] = true;
    }

    public GraphAdjMatrix(BufferedReader buffer)
    {
        try
        {
            String line = buffer.readLine().trim();
            String[] tokens = line.split("\\s+");

            if (tokens.length != 1)
            {
                throw new Error("bad format: number of vertices");
            }
            int n = order = Integer.parseInt(tokens[0]);

            if ( n>0 ) adj = new boolean[n][n];

            for (int i = 0; i < n; i++)
            {
                line = buffer.readLine().trim();
                tokens = line.split("\\s+");
                if (tokens.length != n)
                {
                    throw new Error("bad format: adjacency matrix");
                }

                for (int j = 0; j < n; j++)
                {
                    int entry = Integer.parseInt(tokens[j]);
                    adj[i][j] = entry != 0;
                }
            }
        }
        catch (IOException x) { throw new Error("bad input stream"); }
    }

    //  Mutator Methods
    //
    public void addVertices(int n)
    {
        assert(0 <= n );
        boolean matrix[][] = new boolean[order+n][order+n];

        for (int i = 0; i < order; i++)
        {
            for (int j = 0; j < order; j++)
            {
                matrix[i][j] = adj[i][j];
            }
        }
        order += n;
        adj = matrix;
    }

    public void removeVertex(int v)
    {
        assert(0 <= v && v < order);
        order--;

        for (int i = 0; i < v; i++)
        {
            for (int j = v; j < order; j++)
            {
                adj[i][j] = adj[i][j+1];
            }
        }

        for (int i = v; i < order; i++)
        {
            for (int j = 0; j < v; j++)
            {
                adj[i][j] = adj[i+1][j];
            }
            for (int j = v; j < order; j++)
            {
                adj[i][j] = adj[i+1][j+1];
            }
        }
    }

    public void addArc(int i, int j)
    {
        assert(0 <= i && i < order);
        assert(0 <= j && j < order);
        adj[i][j] = true;
    }

    public void removeArc(int i, int j)  
    {
        assert(0 <= i && i < order);
        assert(0 <= j && j < order);
        adj[i][j] = false;
    }

    public void addEdge(int i, int j)  
    {
        assert(0 <= i && i < order);
        assert(0 <= j && j < order);
        adj[i][j] = adj[j][i] = true;
    }

    public void removeEdge(int i, int j) 
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        adj[i][j] = adj[j][i] = false;
    }

    //  Access Methods
    //
    public boolean isArc(int i, int j)
    {
        assert(0 <= i && i < order);
        assert(0 <= j && j < order);
        return adj[i][j];
    }

    public boolean isEdge(int i, int j)
    {
        assert(0 <= i && i < order);
        assert(0 <= j && j < order);
        return isArc(i,j) && isArc(j,i);
    }

    public int inDegree(int i) // column count
    {
        assert(0 <= i && i < order);
        int sz = 0;
        for (int j = 0; j < order; j++)
        {
            if (adj[j][i]) sz++;
        }
        return sz;
    }

    public int degree(int i) // row count
    {
        assert(0 <= i && i < order);
        int sz = 0;
        for (int j = 0; j < order; j++)
        {
            if (adj[i][j]) sz++;
        }
        return sz;
    }

    public ArrayList<Integer> neighbors(int i)
    {
        assert(0 <= i && i < order);
        ArrayList<Integer> nbrs = new ArrayList<Integer>();

        for (int j = 0; j < order; j++)
        {
            if (adj[i][j])
            {
                nbrs.add(j);
            }
        }

        return nbrs;
    }

    public int order()
    {
        return order;
    }

    public int size() 							// Number of arcs (edges count twice)
    {
        int sz = 0;
        for (int i = 0; i< order; i++)
        {
            for (int j = 0; j< order; j++)
            {
                if ( adj[i][j]) sz++; 
            }
        }
        return sz;  // undirected ? sz / 2 : sz;
    }

    // default output readable by constructor
    //
    public String toString()
    {
        return toStringAdjMatrix();
    }
    public String toStringAdjMatrix()
    {
        StringBuffer o = new StringBuffer();
        o.append(order()+"\n");

        for (int i = 0; i < order(); i++)
        {
            for (int j = 0; j < order(); j++)
            {
                if (isArc(i,j)) o.append("1 ");
                else o.append("0 ");
            }
            o.append("\n");
        }
        return o.toString();
    }

}