package datastructures.graph;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public abstract class AbstractGraph<T> implements GenericGraph<T> {
  protected Map<T, Vertex<T>> vertices;
  private GraphType graphType;

  public AbstractGraph(GraphType graphType) {
    vertices = new HashMap<T, Vertex<T>>();
    this.graphType = graphType;
  }
  
  @Override
  public boolean addEdge(Vertex<T> sourceVertex, Vertex<T> destVertex) {
    return addEdge(sourceVertex, destVertex, 0);
  }

  @Override
  public boolean addEdge(Vertex<T> sourceVertex, Vertex<T> destVertex, int weight) {
    if (sourceVertex != null && destVertex != null) {
      Edge<T> edge = new Edge<T>(sourceVertex, destVertex, weight);
      sourceVertex.outgoingEdges.add(edge);
      destVertex.incomingEdges.add(edge);
      if (graphType.equals(GraphType.UNDIRECTED)) {
        Edge<T> reverseEdge = new Edge<T>(destVertex, sourceVertex, weight);
        destVertex.outgoingEdges.add(reverseEdge);
        sourceVertex.incomingEdges.add(reverseEdge);
      }
      return true;
    }
    return false;
  }

  @Override
  public Vertex<T> createVertex(T label) {
    Vertex<T> v = new Vertex<T>(label);
    vertices.put(label, v);
    return v;
  }

  @Override
  public boolean addVertex(Vertex<T> v, T label) {
    return (vertices.put(label, v)) != null;
  }

  @Override
  public boolean containsVertex(T label) {
    return vertices.containsKey(label);
  }

  @Override
  public Vertex<T> getVertex(T label) {
    return vertices.get(label);
  }

  @Override
  public List<Edge<T>> edgesOf(Vertex<T> v) {
    if (v != null) {
      return v.outgoingEdges;
    }
    return null;
  }

  @Override
  public List<Vertex<T>> neighboursOf(Vertex<T> v) {
    List<Vertex<T>> neighbours = null;
    if (v != null) {
      neighbours = new LinkedList<Vertex<T>>();
      List<Edge<T>> outgoingEdges = v.outgoingEdges;
      for (Edge<T> edge : outgoingEdges) {
        neighbours.add(edge.destVertex);
      }
    }
    return neighbours;
  }

  @Override
  public Edge<T> getEdge(Vertex<T> sourceVertex, Vertex<T> destVertex) {
    List<Edge<T>> outGoingEdges = sourceVertex.outgoingEdges;
    for (Edge<T> edge : outGoingEdges) {
      if (edge.destVertex.equals(destVertex)) {
        return edge;
      }
    }

    return null;
  }

  @Override
  public void print() {
    Set<Entry<T, Vertex<T>>> entrySet = vertices.entrySet();
    for (Entry<T, Vertex<T>> entry : entrySet) {
      System.out.println("Vertex: " + entry.getKey() + " | Neighbours=[" + neighboursOf(entry.getValue()) + "]");
    }
  }

  @Override
  public int numVertices() {
    return vertices.size();
  }
}

@@ -46,24 +46,50 @@
 il.HashMap;%0A
+import java.util.HashSet;%0A
 import java.
@@ -178,16 +178,40 @@
 .Entry;%0A
+import java.util.Queue;%0A
 import j
@@ -2446,32 +2446,1498 @@
 turn null;%0A  %7D%0A%0A
+  @Override%0A  public boolean depthFirstSearch(Vertex%3CT%3E rootVertex, Vertex%3CT%3E resultVertex) %7B%0A    Set%3CVertex%3CT%3E%3E visitedSet = new HashSet%3CVertex%3CT%3E%3E();%0A    return depthFirstSearch(rootVertex, resultVertex, visitedSet);%0A  %7D%0A%0A  @Override%0A  public boolean breadthFirstSearch(Vertex%3CT%3E rootVertex, Vertex%3CT%3E resultVertex) %7B%0A    if (rootVertex.equals(resultVertex)) %7B%0A      return true;%0A    %7D%0A    %0A    Queue%3CVertex%3CT%3E%3E queue = new LinkedList%3CVertex%3CT%3E%3E();%0A    Set%3CVertex%3CT%3E%3E visitedSet = new HashSet%3CVertex%3CT%3E%3E();%0A    queue.add(rootVertex);%0A    %0A    while(!queue.isEmpty()) %7B%0A      Vertex%3CT%3E current = queue.poll();%0A      visitedSet.add(current);%0A      List%3CVertex%3CT%3E%3E neighbours = neighboursOf(current);%0A      %0A      for(Vertex%3CT%3E vertex:neighbours) %7B%0A        if(!visitedSet.contains(vertex)) %7B%0A          if(vertex.equals(resultVertex)) %7B%0A            return true;%0A          %7D else %7B%0A            queue.add(vertex);%0A          %7D%0A        %7D%0A      %7D%0A    %7D%0A    %0A    return false;%0A  %7D%0A%0A  private boolean depthFirstSearch(Vertex%3CT%3E rootVertex, Vertex%3CT%3E resultVertex, Set%3CVertex%3CT%3E%3E visitedSet) %7B%0A    if (rootVertex.equals(resultVertex)) %7B%0A      return true;%0A    %7D%0A%0A    visitedSet.add(rootVertex);%0A%0A    List%3CVertex%3CT%3E%3E neighbours = neighboursOf(rootVertex);%0A    for (Vertex%3CT%3E vertex : neighbours) %7B%0A      if (!visitedSet.contains(vertex)) %7B%0A        if (depthFirstSearch(vertex, resultVertex, visitedSet)) %7B%0A          return true;%0A        %7D%0A      %7D%0A    %7D%0A%0A    return false;%0A  %7D%0A%0A
   @Override%0A  pu

Add BFS and DFS for AbstractGraph