
/* Implements an adjacency list graph
   using a linked list of nodes.
*/

/*
Type structure of the adjacency list:

  Node -> Node -> Node -> Node -> ... -> null
   V
  Node -> Node -> ... -> null
   V
  Node -> Node -> Node -> ... -> null
   V
  null
*/
public class Graph<T> {

  private int numEdges;
  private Node<T> adjList;

  public Graph() {
    this.numEdges = 0;
    this.adjList  = null;
  }

  /* Return true if firstData points to secondData. */
  // protected boolean hasDirectedEdge(T firstData, T secondData) {
  //   if (this.adjList.hasHorizontalNode(firstData)) {
  //     Node<T> head = this.adjList.getNodeWithData(firstData);
  //     return (head.next.hasNodeData(secondData));
  //   }
  //   return false;
  // }

  /* Return true if both firstData and secondData point to each other. */
  // protected boolean hasUndirectedEdge(T firstData, T secondData) {
  //   return (
  //     this.hasDirectedEdge(firstData, secondData) &&
  //     this.hasDirectedEdge(secondData, firstData)
  //   );
  // }

  /* Add an edge from firstData to secondData. */
  protected void addDirectedEdge(T firstData, T secondData) {
    Node<T> curr = this.adjList;

    /* First edge added. */
    if (curr == null) {
      Node<T> node1 = new Node<T>(firstData);
      Node<T> node2 = new Node<T>(secondData);
      curr = node1;
      curr.appendHorizontal(node2);

      this.adjList = curr;
      ++this.numEdges;
      return;
    }

    this.adjList.appendVertical(new Node<T>(firstData));
    /* Add the node to the adjList. */
    while(curr != null) {
      /* We've found the vertical head node. */
      if (curr.data == firstData && !curr.hasHorizontal(secondData)) {
        curr.appendHorizontal(new Node<T>(secondData));
      }
      curr = curr.down;
    }

    ++this.numEdges;
    return;
  }

  /* Add an edge from firstData and secondData, and
     add another edge from secondData to firstData. */
  protected void addUndirectedEdge(T firstData, T secondData) {
    // this.addDirectedEdge(firstData, secondData);
    // this.addDirectedEdge(secondData, firstData);
    // this.numEdges += 2;
    return;
  }

  /* Remove the edge from firstData to secondData. */
  protected void removeDirectedEdge(T firstData, T secondData) {
    return;
  }

  /* Remove the edge from firstData and secondData, and
     remove the edge from secondData to firstData. */
  protected void removeUndirectedEdge(T firstData, T secondData) {
    // this.removeDirectedEdge(firstData, secondData);
    // this.removeDirectedEdge(secondData, firstData);
    // this.numEdges -= 2;
    return;
  }

  /* Display the AdjacencyList in a readable format. */
  protected void show() {
    Node<T> curr = this.adjList;
    while(curr != null) {
      curr.showTraverse();
      curr = curr.down;
    }
    return;
  }

  /* Return the number of linked lists in the adjacency list. */
  protected int getNumEdges() {
    return this.numEdges;
  }

  public static void main(String[] args) {
    Graph<Integer> g = new Graph<Integer>();

    g.show();
    System.out.println(g.getNumEdges());

    g.addDirectedEdge(1, 2);

    g.addDirectedEdge(2, 1);
    g.addDirectedEdge(2, 2);

    g.show();
    System.out.println(g.getNumEdges());
  }
}

@@ -452,27 +452,24 @@
 ndData. */%0A 
- //
  protected b
@@ -521,19 +521,16 @@
 ata) %7B%0A 
- //
    if (t
@@ -548,22 +548,16 @@
 .has
-HorizontalNode
+Vertical
 (fir
@@ -568,19 +568,16 @@
 ta)) %7B%0A 
- //
      Nod
@@ -581,20 +581,20 @@
 Node%3CT%3E 
-head
+curr
  = this.
@@ -604,41 +604,108 @@
 List
-.getNodeWithData(firstData);%0A  //
+;%0A      while (curr != null) %7B%0A        if (curr.data.equals(firstData) && curr.next != null) %7B%0A     
     
@@ -713,20 +713,20 @@
 return (
-head
+curr
 .next.ha
@@ -730,16 +730,18 @@
 .has
-NodeDa
+Horizon
 ta
+l
 (sec
@@ -757,19 +757,57 @@
 ;%0A  
+ 
-//
+  
    %7D%0A  
-//
+      curr = curr.down;%0A      %7D%0A    %7D%0A 
    r
@@ -820,19 +820,16 @@
 false;%0A 
- //
  %7D%0A%0A  /*
@@ -1526,24 +1526,74 @@
 urn;%0A    %7D%0A%0A
+    if (!this.adjList.hasVertical(firstData)) %7B%0A  
     this.adj
@@ -1633,24 +1633,31 @@
 irstData));%0A
+    %7D%0A%0A
     /* Add t
@@ -1780,51 +1780,21 @@
 data
- == firstData && !curr.hasHorizontal(second
+.equals(first
 Data
@@ -3025,24 +3025,24 @@
 umEdges() %7B%0A
+
     return t
@@ -3062,301 +3062,7 @@
 %0A  %7D
-%0A%0A  public static void main(String%5B%5D args) %7B%0A    Graph%3CInteger%3E g = new Graph%3CInteger%3E();%0A%0A    g.show();%0A    System.out.println(g.getNumEdges());%0A%0A    g.addDirectedEdge(1, 2);%0A%0A    g.addDirectedEdge(2, 1);%0A    g.addDirectedEdge(2, 2);%0A%0A    g.show();%0A    System.out.println(g.getNumEdges());%0A  %7D
 %0A%7D%0A

Implement hasDirectedEdge.