The algorithm described in Section 3.6 for computing a topological ordering of a

Question

The algorithm described in Section 3.6 for computing a topological ordering of a DAG repeatedly finds a node with no incoming edges and deletes it. This will eventually produce a topological ordering, provided that the input graph really is a DAG. But suppose that we're given an arbitrary graph that may or may not be a DAG. Extend the topological ordering algorithm so that, given an input directed graph G, it outputs one of two things: (a) a topological ordering, thus establishing that G is a DAG; or (b) a cycle in G, thus establishing that G is not a DAG. The running time of your algorithm should be O(m n) or a directed graph with n nodes and m edges.

Explanation / Answer

Whole point is to take a note of the degree and and keep on deleting the verticess which has degree 0,

if you do not find any node with degree 0 but there are nodes in the graph then it has a loop

------------------------------------------------------------------------------------------------------------------------

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Chegg_13_2_2017 {

   static class Graph {
       int noOfVetices;
       List<Integer>[] adjList;
       TreeMap<Integer, Integer> degree = new TreeMap<>();

       Graph(int noOfVertices) {
           this.noOfVetices = noOfVertices;
           adjList = new ArrayList[noOfVertices + 1];

           for (int i = 0; i <= noOfVertices; i++) {
               adjList[i] = new ArrayList<>();
           }
       }

       public void addEdge(HashMap<Integer, String> graphInput) {
           for (Entry<Integer, String> e : graphInput.entrySet()) {
               StringTokenizer st = new StringTokenizer(e.getValue(), ",");
               while (st.hasMoreElements()) {
                   addEdge(e.getKey(), Integer.parseInt(st.nextElement().toString()));
               }
           }
       }

       // edge directed from (u -> v)
       public void addEdge(int u, int v) {
           adjList[u].add(v);

           if (!degree.containsKey(u)) {
               degree.put(u, 0);
           }

           if (degree.containsKey(v)) {
               degree.put(v, degree.get(v) + 1);
           } else {
               degree.put(v, 1);
           }
       }
   }

   public static String getTopologicalSort(Graph g) {
       StringBuilder result = new StringBuilder();

       List<Map.Entry<Integer, Integer>> list = new LinkedList<>(g.degree.entrySet());
       Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
           @Override
           public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
               return (o1.getValue()).compareTo(o2.getValue());
           }
       });

       int min = 0;
       while (!list.isEmpty() && list.get(0).getValue() == 0) {
           min = list.get(0).getKey();
           for (Integer neigh : g.adjList[min]) {
               g.degree.put(neigh, g.degree.get(neigh) - 1);
           }
           result.append(min + "->");
           g.degree.remove(min);

           list = new LinkedList<>(g.degree.entrySet());
           Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
               @Override
               public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                   return (o1.getValue()).compareTo(o2.getValue());
               }
           });
       }
       if (list.isEmpty()) {
           return result.toString();
       } else {
           return "There is a Loop containing the vertices :" + g.degree.keySet();
       }
   }

   public static void main(String[] args) {

       Graph g = new Graph(7);
       HashMap<Integer, String> graphInput = new HashMap<>();
       graphInput.put(1, "4,5,7");
       graphInput.put(2, "3,5,6");
       graphInput.put(3, "4,5");
       graphInput.put(4, "1,5");
       graphInput.put(5, "6,7");
       graphInput.put(6, "7");
       graphInput.put(7, "");

       g.addEdge(graphInput);

       System.out.println(getTopologicalSort(g));

   }

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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