// This code is from "Algorithms in Java, Third Edition,"
// by Robert Sedgewick, Addison-Wesley, 2003.

// Program 20.4, Weighted-graph class (adjacency lists)

class Graph // sparse multigraph implementation
{
  private int Vcnt, Ecnt;
  private boolean digraph;

  private class Node
  {
    Edge e;
    Node next;

    Node(Edge x, Node t)
    {
      e = x;
      next = t;
    }
  }

  private Node adj[];

  Graph(int V, boolean flag)
  {
    Vcnt = V;
    Ecnt = 0;
    digraph = flag;
    adj = new Node[V];
  }

  int V() { return Vcnt; }
  int E() { return Ecnt; }
  boolean directed() { return digraph; }

  void insert(Edge e)
  {
    int v = e.v(), w = e.w();
    adj[v] = new Node(e, adj[v]);
    if (!digraph)
      adj[w] = new Node(e, adj[w]); 
    Ecnt++;
  } 

  AdjList getAdjList(int v)
  { return new AdjLinkedList(v); }

  // Program 17.10
  private class AdjLinkedList implements AdjList
  { 
    private int v;
    private Node t;

    AdjLinkedList(int v)
      { this.v = v; t = null; }
    public Edge beg()
      { t = adj[v]; 
        return t == null ? null : t.e; }
    public Edge nxt()
      { if (t != null) t = t.next; 
        return t == null ? null : t.e; }
    public boolean end()
      { return t == null; }
  }
}