i ran into an issue when trying to print out a list of file dependencies.
About the program:
If I understand what the map output is saying, there is a cycle ( a #include loop ) in your header files.
i_50.h=[i_35.h, i_28.h, i_45.h, i_44.h, i_46.h],
....
i_35.h=[i_50.h, i_51.h]
That means that your dependencies are a graph and not a DAG. And that in turn means that a simple recursive walk will not work.
By the looks of it, you are attempting to do a graph walk, but for some reason your cycle detection / avoidance is not working, and your algorithm goes into "infinite" recursion.
After looking at the code, I think I can see where the problems are. In the first method, you check that a dependency has already been printed, and then set the entry in the alreadyPrinted map to say it has. But you then proceed to print it irrespective. Then in the second method you are (inexplicably) creating a new alreadyPrinted map each time you recurse to the first method. In other words, the logic of your cycle avoidance is broken.
Rather than fixing your code for you, I'm going to suggest that you go to your favourite "data structures and algorithms" text book and look up "graph traversal" in the index. Alternatively, here's an page I found in some online lecture notes:
There's also stuff on graph traversal in Wikipedia, and other places. Google for "java recursive graph traversal", and try and find something that makes sense to you.
The general algorithm is something like this:
traverse(Node node):
traverse_0(node, new Set<Node>())
traverse_0(Node node, Set<Node> visited):
if (visited.contains(node))
return
visited.add(node)
for (Node child: node.children)
traverse_o(child, visited)
The only place where you test if a dependency has already been printed, is the first for loop. You should check in the second for loop too!
for (String d : dependencies) {
if (!alreadyPrinted.containsKey(d)) {
LinkedList<String> key = theTable.get(d);
if (key != null)
output += printDependencies(theTable, key, alreadyPrinted);
}
}
It is fairly easy to see that your algorithm recurses, as soon as some dependency looks like:
item: ...., item, ....
(I hear you say: "that cannot happen, because ...". Yet, the SO shows that either it did happen, or your stack is too small.)
By the way, you maintain the map "already printed", but it is nowhere used? This hints to a flaw in your implementation.
As you are maintaining some state (alreadyPrinted and output) I would recommend moving the state to instance-variabes and to use an object and no class-methods.
The problem was that my Graph traversal had cycles which I was not handling. The working code is provided below.
private static String printDependencies(ConcurrentHashMap<String, LinkedList<String>> theTable, LinkedList<String> dependencies, ConcurrentHashMap<String, Boolean> alreadyPrinted) {
String output = "";
for (String d : dependencies) {
boolean isPrinted = alreadyPrinted.containsKey(d);
if (!isPrinted) {
output += " " + d;
alreadyPrinted.put(d, true);
}
}
for (String d : dependencies) {
LinkedList<String> key = theTable.get(d);
if (key != null) {
LinkedList<String> unvisited = new LinkedList<String>();
for (String filename : key)
if (!alreadyPrinted.containsKey(filename))
unvisited.add(filename);
if (unvisited != null)
output += printDependencies(theTable, unvisited, alreadyPrinted);
}
}
return output;
}
private static void printDependencies(ConcurrentHashMap<String, LinkedList<String>> theTable, ConcurrentLinkedQueue<String> toProcess) {
String output = "";
for (String current : toProcess) {
ConcurrentHashMap<String, Boolean> alreadyPrinted = new ConcurrentHashMap<String, Boolean>(); // Keeps track of dependencies already printed
output += current + ":" + printDependencies(theTable, theTable.get(current), alreadyPrinted) + "\n";
}
System.out.println(output);
}