Return the lexicographic order

Given set of words that are lexicographically sorted, return
lexicographic order.


E.g:

abc
acd
bcc
bed
bdc
dab

The order of letters for the given example would be

a->b->c->e->d

Time:


Part-1:


Complexity of constructing graph: \$O(n * m)\$, where \$n\$ is number
of words and \$m\$ is max length of any word.


Part-2:


Topological sort: \$O(V + E)\$, where \$V\$ is number of vertices and
\$E\$ is number of edges

Space:


\$O(V + E)\$ - entire graph is stored

Looking for request code review, optimizations and best practices.
Also verifying if how would final answer for complexity look like.

E.g: Would it be \$O(n*m + E + V)\$?

```
class GraphLexico implements Iterable {

/* A map from nodes in the graph to sets of outgoing edges. Each
* set of edges is represented by a map from edges to doubles.
*/
private final Map> graph = new HashMap>();

/**
* Adds a new node to the graph. If the node already exists then its a
* no-op.
*
* @param node Adds to a graph. If node is null then this is a no-op.
* @return true if node is added, false otherwise.
*/
public boolean addNode(T node) {
if (node == null) {
throw new NullPointerException("The input node cannot be null.");
}
if (graph.containsKey(node)) return false;

graph.put(node, new ArrayList());
return true;
}

/**
* Given the source and destination node it would add an arc from source
* to destination node. If an arc already exists then the value would be
* updated the new value.
*
* @param source the source node.
* @param destination the destination node.
* @param length if length if
* @throws NullPointerException if source or destination is null.
* @throws NoSuchElementException if either source of destination does no

You code has lots of strengths. Its main weakness is the lack of explanation for the algorithm.

-
Why are you building the reverse graph? A reverse post order visiting of the graph is a topo sort order. Just get the post order and then reverse it! Saves lots of effort and space.

-
I can't grok how your topo sort is finding DAG roots. You can't afford to start searching at nodes that don't have zero parents. Keeping a parent count for each character makes it super-easy to find the roots.

-
Your cycle detection is too complex. A cycle occurs if and only if a recursive call to explore encounters a node that's already on the stack. Just keep an "active" set. Add a node before a recursive call to explore and remove it afterward. If you encounter a node that's active, you've found a cycle. The active set will generally be much smaller than the node set, so this is a tiny performance win as well.

Additional things to think about:

-
You can use a LinkedHashSet to maintain the post order of visits and keep track of already-visited nodes efficiently with one data structure instead of two.

-
Using sets instead of lists of successors in the graph removes a run time dependency on graph degree. This is a small thing.

-
Learn how to use JavaDoc format comments. It's worth the time in the long run.

-
A few of your names are deceptive. A dictionary in code usually refers to a hash of strings. Etc., etc.

-
Not sure why you broke strings into character arrays.

-
It's simpler to have the graph edge adder create missing nodes than to deem
missing nodes an error condition.

I liked this problem so well I coded my own version to check some of the ideas above:

```
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class LexiDetective {

/**
* A little unit test of the lexicographic detective.
*/
public static void main(String[] args) {
String [] words = { "abc", "acd", "bcc", "bed", "bdc", "dab" };
CharacterGraph graph = new CharacterGraph();
graph.insertWordList(words);
try {
List order = graph.topoSort();
for (Character ch : order) {
System.out.print(ch);
}
System.out.println();
} catch (Exception ex) {
// Topo sort might find cycle and raise this exception.
System.err.println(ex.getMessage());
}
}
}

/**
* Symbol graph specialized for characters and enhanced to deal
* with lexicographically ordered word lists.
*/
class CharacterGraph extends SymbolGraph {

/**
* Insert a lexicographically ordered word pair into the
* character graph using the first non-equal character pair to
* add an edge.
*
* @param x first word in lexicographic order
* @param y second word
*/
void insertWordPair(String x, String y) {
int len = Math.min(x.length(), y.length());
for (int i = 0; i ordered symbol type
*/
class SymbolGraph {

/**
* Information about a symbol and its successors in the graph.
*
* @param symbol type
*/
static class NodeData {

/**
* Count of symbols with this one as successor.
*/
int parentCount = 0;
/**
* Set of successor symbols.
*/
final Set successors = new HashSet<>();
}

/**
* Graph adjacencies stored as a map from symbols to node data. The node
* data stores information about the symbol and its successors.
*/
Map adjacencies = new HashMap<>();

/**
* Add a node to the graph unless it's already there.
*
* @param a datum for node
* @return node, either existing or newly created
*/
NodeData addNode(Symbol a) {
NodeData data = adjacencies.get(a);
if (data == null) {
data = new NodeData<>();
adjacencies.put(a, data);
}
return data;
}

/**
* Add an edge to the graph unless it's already there.
*
* @param a edge origin
* @param b edge destination
*/
void addEdge(Symbol a, Symbol b) {
NodeData aData = addNode(a);
if (!aData.successors.contains(b)) {
aData.successors.add(b);
NodeData bData = addNode(b);
++bData.parentCount;
}
}

/**
* Visit the graph rooted at given symbol in post order, accumulating an
* ordered set of visited symbols.
*
* @param a the symbol for the (sub)graph to search
* @param visited an ordered set that gives the post visit order
*/
void postOrderVisit(Symbol a, Set ancestors, LinkedHashSet visited)
throws Exception {
if (ancestors.contains(a)) {
throw new Exception("Cycle detected. No p

StackExchange Code Review Q#48292, answer score: 6