Implement all methods in Degrees class according to the following definition: A

Question

Implement all methods in Degrees class according to the following definition:

A source vertex is one with indegree 0

A sink vertex is one with outdegree 0

A digraph is map if every vertex has outdegree1

public class Degrees {
  
   public Degrees(Digraph digraph) {
       // unimplemented
   }
  
   // returns indegree of v
   public int indegree(int v) {
       throw new UnsupportedOperationException();
   }
  
   // returns outdegree of v
   public int outdegree(int v) {
       throw new UnsupportedOperationException();
   }
  
   // returns all vertices with indegree 0
   public Iterable<Integer> sources() {
       throw new UnsupportedOperationException();
   }
  
   // return all vertices with outdegree 0
   public Iterable<Integer> sinks() {
       throw new UnsupportedOperationException();
   }
  
   // return true if every vetex has outdegree 1; otherwise false
   public boolean isMap() {
       throw new UnsupportedOperationException();
   }

}

Explanation / Answer

public class Degrees
{
   private int[] indegree;
   private int[] outdegree;
   private List<Integer> sources;
   private List<Integer> sinks;

   public Degrees(Digraph G)
   {
   indegree = new int[G.V()];
   outdegree = new int[G.V()];
   sources = new LinkedList<>();
   sinks = new LinkedList<>();
   for (int v = 0; v < G.V(); v++)
   {
   for (int w : G.adj(v))
   {
   indegree[w]++;
   outdegree[v]++;
   }
   }
   for (int v = 0; v < G.V(); v++)
   {
   if (indegree[v] == 0)
   sources.add(v);
   if (outdegree[v] == 0)
   sinks.add(v);
   }
   }

   public int indegree(int v)
   {
   return indegree[v];
   }

   public int outdegree(int v)
   {
   return outdegree[v];
   }

   public Iterable<Integer> sources()
   {
   return sources;
   }

   public Iterable<Integer> sinks()
   {
   return sinks;
   }

   public boolean isMap()
   {
   for (int v = 0; v < outdegree.length; v++)
   if (outdegree[v] != 1)
   return false;
   return true;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.