Question

JAVA code

Create a new class called BetterDiGraph that implements the EditableDiGraph interface See the interface below for details.

EditableDigraph below:

import java.util.NoSuchElementException;

/**
* Implements an editable graph with sparse vertex support.
*
*
*/
public interface EditableDiGraph {
  
/**
* Adds an edge between two vertices, v and w. If vertices do not exist,
* adds them first.
*
* @param v source vertex
* @param w destination vertex
*/
void addEdge(int v, int w);

/**
* Adds a vertex to the graph. Does not allow duplicate vertices.
*
* @param v vertex number
*/
void addVertex(int v);

/**
* Returns the direct successors of a vertex v.
*
* @param v vertex
* @return successors of v
*/
Iterable getAdj(int v);
  
/**
* Number of edges.
*
* @return edge count
*/
int getEdgeCount();
  
/**
* Returns the in-degree of a vertex.
* @param v vertex
* @return in-degree.
* @throws NoSuchElementException exception thrown if vertex does not exist.
*/
int getIndegree(int v) throws NoSuchElementException;
  
/**
* Returns number of vertices.
* @return vertex count
*/
int getVertexCount();
  
/**
* Removes edge from graph. If vertices do not exist, does not remove edge.
*
* @param v source vertex
* @param w destination vertex
*/
void removeEdge(int v, int w);

/**
* Removes vertex from graph. If vertex does not exist, does not try to
* remove it.
*
* @param v vertex
*/
void removeVertex(int v);

/**
* Returns iterable object containing all vertices in graph.
*
* @return iterable object of vertices
*/
Iterable vertices();

/**
* Returns true if the graph contains at least one vertex.
*
* @return boolean
*/
boolean isEmpty();
  
/**
* Returns true if the graph contains a specific vertex.
*
* @param v vertex
* @return boolean
*/
boolean containsVertex(int v);
}

Answer 1

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;

public class BetterDiGraph implements EditableDiGraph {

   private HashMap<Integer, HashSet<Integer>> adjacencyMap;
   private int numVertices;
   private int numEdges;

   public BetterDiGraph() {
       this.adjacencyMap = new HashMap<>();
   }

   @Override
   public void addEdge(int v, int w) {
       addVertex(v);
       addVertex(w);
       if (this.adjacencyMap.containsKey(v)) {
           if (!this.adjacencyMap.get(v).contains(w)) {
               this.adjacencyMap.get(v).add(w);
               this.numEdges++;
               return;
           }
       }
       return;

   }

   @Override
   public void addVertex(int v) {
       if (!this.adjacencyMap.containsKey(v)) {
           this.adjacencyMap.put(v, new HashSet<>());
           this.numVertices++;
           return;
       }
       return;

   }

   @Override
   public Iterable getAdj(int v) {
       // TODO Auto-generated method stub
       return this.adjacencyMap.get(v);
   }

   @Override
   public int getEdgeCount() {
       // TODO Auto-generated method stub
       return this.numEdges;
   }

   @Override
   public int getIndegree(int v) throws NoSuchElementException {

if (!containsVertex(v)) {
           throw new NoSuchElementException();
       }

       List<Integer> inList = new ArrayList<Integer>();
       for (Integer to : this.adjacencyMap.keySet()) {
           for (Integer e : this.adjacencyMap.get(to))
               if (e.equals(v))
                   inList.add(to);
       }
       return inList.size();

   }

   @Override
   public int getVertexCount() {
       // TODO Auto-generated method stub
       return this.numVertices;
   }

   @Override
   public void removeEdge(int v, int w) {
       if (this.adjacencyMap.containsKey(v) && this.adjacencyMap.containsKey(w)) {
           if (this.adjacencyMap.get(v).contains(w)) {
               this.adjacencyMap.get(v).remove(w);
               this.numEdges--;
               return;
           }
       }
       return;

   }

   @Override
   public void removeVertex(int vertex) {
       if (this.adjacencyMap.containsKey(vertex)) {
           this.adjacencyMap.remove(vertex);
           for (Map.Entry<Integer, HashSet<Integer>> entry : this.adjacencyMap.entrySet()) {
               if (entry.getValue().contains(vertex)) {
                   this.adjacencyMap.get(entry.getKey()).remove(vertex);
               }
           }
           this.numVertices--;
           return;
       }
       return;

   }

   @Override
   public Iterable vertices() {
       // TODO Auto-generated method stub

       List<Integer> inList = new ArrayList<Integer>();
       for (Integer to : this.adjacencyMap.keySet()) {
           if (!inList.contains(to))
               inList.add(to);
       }
       return inList;

   }

   @Override
   public boolean isEmpty() {
       // TODO Auto-generated method stub
       return this.numVertices == 0;
   }

   @Override
   public boolean containsVertex(int v) {
       if (this.adjacencyMap.containsKey(v)) {
           return true;
       }
       return false;
   }

}