graph

package hw4;

import java.util.*;



/**
 * Abstraction function: Graph stored as an adjacency list
 * Node are stored as keys in the hash map
 * The edges from that node are stored as the value of hash map
 * The value of the hash map is an array list
 */

public class Graph {

  private HashMap<Node, ArrayList<Edge>> adjList;
  private int numEdges;
  private int numNodes;
  private int numDegrees;


  public Graph() {
    adjList = new HashMap<Node, ArrayList<Edge>>();
    numEdges = 0;
    numNodes = 0;
    numDegrees = 0;
    checkRep();
  }
   /**
     * gets the number of nodes in the graph
     * @requires the graph can't be null
     * @return number of nodes int the graph
     */
  public int getNumNodes(){
    return numNodes;
  }
   /**
     * gets the number of edges in the graph
     * @requires the graph can't be null
     * @return number of edges int the graph
     */
  public int getNumEdges() {
    return numEdges;
  }
   /**
     * gets the number of degrees in the graph
     * @requires the graph can't be null
     * @return number of degrees int the graph
     */

  public int getNumDegrees() {
    return numDegrees;
  }

  /**
     * Figures out if the graph is empty
     * @return true only if the graph is empty
     */

  public boolean isEmpty() {
    return adjList.isEmpty();
  }


    /**
     * Adds a node into the graph
     * @requires the graph can't be null
     * @param tempNode the name of the node to be added to the graph
     * @effects Attempts to put the node in the graph, if node is null or the node is already in the graph then it does nothing
     * @modifies the graph
     * @return true only in when the node has been added to the graph
     */

    public boolean addNode(String nodeString){
        if(nodeString == null) {
          return false;
        }
        return addNode(new Node(nodeString));
    }

    /**
     * Adds a node into the graph
     * @requires the graph can't be null
     * @param tempNode the name of the node to be added to the graph
     * @effects Attempts to put the node in the graph, if node is null or the node is already in the graph then it does nothing
     * @modifies the graph
     * @return true only in when the node has been added to the graph
     */

  public boolean addNode(Node tempNode) {
    if (tempNode == null) {
      return false;
    }
    if(!adjList.containsKey(tempNode)){
      this.adjList.put(tempNode,new ArrayList<Edge>());
      this.numNodes++;
      return true;
    }
    checkRep();
    return false;
  }

   /**
     * Adds a new edge to the graph
     * @requires the graph can't be null
     * @param tempEdge edge to be added to the graph
     * @effects Attempts to put the edge in the graph, if node is null or the node is already in the graph then it does nothing
     * @modifies the graph
     * @return true only if the edge is added to the graph
     */

  public boolean addEdge(Edge tempEdge) {
    if(tempEdge == null) {
      return false;
    }

    Node start = tempEdge.getStartPoint();
    Node end = tempEdge.getEndPoint();
    if(adjList.containsKey(start)) {
      if(!adjList.get(start).contains(tempEdge)) {
        adjList.get(start).add(tempEdge);
        numEdges++;
        numDegrees++;
        addNode(end);
        return true;
      }
      return false;
    }
    addNode(start);
    addNode(end);
    numEdges++;
    numDegrees++;
    adjList.get(start).add(tempEdge);
    checkRep();
    return true;

  }

  /**
     * Adds a new edge to the graph
     * @requires the graph can't be null
     * @param parent String of parent name
     * @param child String of child name
     * @param label String of label
     * @effects Attempts to put the edge in the graph, if edge is null or the edge is already in the graph then it does nothing
     * @modifies the graph
     * @return true only if the edge is added to the graph
     */

  public boolean addEdge(String parent, String child, String label){
      if(parent == null || child == null || label == null){
        return false;
    }
      return addEdge(new Edge(new Node(parent),new Node(child),label));
  }

    /**
     * Removes an edge from the graph
     * @requires the graph can't be null
     * @param tempEdge the edge that's going to be removed from the graph
     * @effects Attempts to remove the edge in the graph, if edge is null or the edge is already not in the graph then it does nothing
     * @modifies the graph
     * @return true only if the edge is removed from the graph
     */

  public boolean removeEdge(Edge tempEdge){
        if (tempEdge == null) return false;
        if(!adjList.containsKey(tempEdge.getStartPoint())) {
          return false;
        }
        ArrayList<Edge> edgeList = adjList.get(tempEdge.getStartPoint());
        for (int i = 0; i < edgeList.size(); i++) {
            if (tempEdge.equals(edgeList.get(i))) {
                numDegrees --;
                numEdges --;
                edgeList.remove(i);
                break;
            }
        }
        checkRep();
        return true;
    }

    /**
     * checks to see if the graph has the respective edge
     * @requires graph can't be null
     * @param edge the edge we're looking to see whether it is in the graph or nah
     * @return true only if the edge exists in the graph
     */

  public boolean hasEdge(Edge edge){
    if(edge == null) {
      return false;
    }
    if(!adjList.containsKey(edge.getStartPoint())) {
      return false;
    }
    ArrayList<Edge> edgeList = adjList.get(edge.getStartPoint());
    for(int i = 0; i < edgeList.size(); i++) {
      if(edge.equals(edgeList.get(i))) {
        return true;
      }
    }
    return false;
  }

    /**
     * checks to see if the node has the respective edge
     * @requires graph can't be null
     * @param node the node we're looking to see whether it is in the graph or nah
     * @return true node if the edge exists in the graph
     */

  public boolean hasNode(Node node) {
    if(node == null) {
      return false;
    }
    return adjList.containsKey(node);
  }

  /**
     * checks to see if the node has the respective edge
     * @requires graph can't be null
     * @param node the node we're looking to see whether it is in the graph or nah
     * @return true node if the edge exists in the graph
     */

    public boolean hasNode(String node){
        if(node == null) {
          return false;
          }
        return hasNode(new Node(node));
    }
    /**
     * Removes an edge from the graph
     * @requires the graph can't be null
     * @param tempEdge the edge that's going to be removed from the graph
     * @effects Attempts to remove the edge in the graph, if edge is null or the edge is already not in the graph then it does nothing
     * @modifies the graph
     * @return true only if the edge is removed from the graph
     */

  public boolean removeNode(Node tempNode) {
    if(tempNode == null) {
      return false;
    }
    if(!hasNode(tempNode)) {
      return false;
    }

    int temp = adjList.get(tempNode).size();
    adjList.remove(tempNode);
    numNodes--;
    numDegrees-= temp;
    numEdges-= temp;

    Iterator itr = adjList.entrySet().iterator();
    ArrayList<Edge> remove = new ArrayList<Edge>();
    while(itr.hasNext()) {
      Map.Entry pair = (Map.Entry) itr.next();
      ArrayList<Edge> currentEdge = (ArrayList<Edge>) pair.getValue();

      for(int i = 0; i<currentEdge.size(); i++) {
        if(currentEdge.get(i).getEndPoint().equals(tempNode)) {
          numDegrees --;
          numEdges --;
          remove.add(currentEdge.get(i));
        }
      }
    }
    checkRep();
    remove.clear();
    return true;
  }
     /**
     * List the nodes in the graph
     * @requires graph can't be null
     * @return  list of nodes
     */

  public ArrayList<String> listNodes(){
    ArrayList<String> temp = new ArrayList<String>();
    for (Node x : adjList.keySet()) {
          temp.add(x.getName());
      }
    temp.sort(Comparator.naturalOrder());
    return temp;
  }

    /**
     * List the child nodes in the graph
     * @requires graph can't be null
     * @param parentNode the parent node that will have its children listed
     * @return  list of child nodes or an empty list if the parent isn't in the graph or is null
     */

    public ArrayList<Node> listChildren(String parentNode){
        if (parentNode == null || !hasNode(new Node(parentNode))) {
            return new ArrayList<Node>();
        }
        ArrayList<Node> childNodes = new ArrayList<Node>();
        ArrayList<Edge> nodeSort = new ArrayList<Edge>(adjList.get(new Node(parentNode)));
        nodeSort.sort((temp1, temp2) -> {
            if(temp1.getEndPoint().getName().equals(temp2.getEndPoint().getName())){
                return temp1.getLabel().compareTo(temp2.getLabel());
            }
            return temp1.getEndPoint().getName().compareTo(temp2.getEndPoint().getName());
        });

        Iterator<Edge> child = nodeSort.iterator();
        while(child.hasNext()){
            childNodes.add(child.next().getEndPoint());
        }
        return childNodes;
    }

    /**
     * checks to see if the rep invariant holds true
     * @throws RuntimeException if the graph doesn't pass the checks
     */

  public void  checkRep(){
    if(isEmpty()){
      return;
    }

    if(numEdges < 0 || numDegrees < 0 || numNodes< 0) {
      throw new RuntimeException("Error: negative degree, # of edges or # of nodes");
    }

    Iterator itr = adjList.entrySet().iterator();
    while(itr.hasNext()) {
      Map.Entry pair = (Map.Entry) itr.next();
            Node currentNode = (Node) pair.getKey();
            ArrayList<Edge> currentEdge = (ArrayList<Edge>) pair.getValue();
            for (int i = 0; i < currentEdge.size(); i++) {
              if (!currentNode.equals(currentEdge.get(i).getStartPoint())){
                   throw new RuntimeException ("first node in the Edge of each <Node, List<Edge>> is not the node itself");
              }
            }
    }
  }
}