// Mike Maxim
// Graph Implementation

package edu.cmu.cs.l3.graph;

import java.util.*;

// Adjacency-List Implementation
// TODO: Provide means for switching between matrix and lists
public abstract class Graph {

    public static final int INDEGREE=0,OUTDEGREE=1,DEGREE=2;

    public Graph() {
        m_adjlists = new ArrayList();
        m_vertices = new ArrayList();
    }

    abstract public Vertex createVertex();

    protected void addVertex(Vertex v) {

        List vlist = new ArrayList();

        v.setOwner(this,m_adjlists.size());
        m_adjlists.add(vlist);
        m_vertices.add(v);
    }

    public abstract void removeVertex(Vertex v);

    public abstract void createEdge(Vertex u, Vertex v);

    public abstract void removeEdge(Vertex u, Vertex v);

    public Vertex getVertex(int id) {
        return (Vertex)m_vertices.get(id);
    }

    public List getVertices() {
        return m_vertices;
    }

    public int getNumVertices() {
        return m_vertices.size();
    }

    public abstract int getDegree(Vertex v, int type) throws GraphException;

    public abstract boolean isAdjacent(Vertex u, Vertex v);

    public abstract List getAdjacents(Vertex v);

    public String toString() {

        int i,j;
        List verts = getVertices();
        String str="";

        // Verts
        for (i = 0; i < verts.size(); i++) {
            Vertex v = (Vertex) verts.get(i);

            if (v.deadIsMarked()) continue;

            str += v.toString() + ":";

            List vlist = (List)m_adjlists.get(v.getID());
            for (j = 0; j < vlist.size(); j++) {
                Vertex u = (Vertex) vlist.get(j);
                str += "(" + v.toString() + "," + u.toString() + ")";
            }
            str += "\n";
        }

        return str;
    }

    protected List m_vertices;
    protected ArrayList m_adjlists;
}