Find "connected components" in the graph
I am creating a thesaurus using HashMap <String,ArrayList<String>>
to store words and their synonyms (this data structure is required).
For designation purposes, the relationship of synonyms is considered transient. (We can think of the thesaurus as a graph.) What I am trying to accomplish is to print this graph in a text file with a connected component on each line. In other words, all words that can be combined together as synonyms must go on the same line.
public void save() {
try {
FileWriter fw = new FileWriter(defaultDefinitionFile);
BufferedWriter out = new BufferedWriter(fw);
Set<String> keys = thesaurus.keySet();
Iterator<String> ite = keys.iterator();
while (ite.hasNext()) {
String key = ite.next();
out.write(key);
ArrayList<String> synonyms = thesaurus.get(key);
Iterator<String> i = synonyms.iterator();
while (i.hasNext()) {
String syn = i.next();
out.write(","+syn);
keys.remove(syn);
}
out.write("\r\n");
}
out.close();
fw.close();
}
catch (Exception e) {
System.out.println("Error writing to file");
e.printStackTrace();
}
}
This is how I imagined it:
Print out the word along with each of its synonyms, then remove those synonyms from the data structure so that we don't have duplicate rows.
The problem, of course, is that I cannot delete anything while I iterate over the contents of the hashmap.
Any alternative approaches I am missing?
PS I only keep the "graph" metaphor because I need a title to be eloquent and succinic. I understand that this metaphor is of limited usefulness.
a source to share
You can store words that have been typed into Set and then only process words that have not yet been set.
Side note: while it is true that this can be thought of as a graph problem, your code does not treat it as such. If we viewed this as a graph problem, then we would not make the assumption that each word has all its synonyms listed in the corresponding one ArrayList
, thereby calling for the computation of symmetric and transitive closures. Only then will we extract the equivalence classes.
(Actually the synonym relationship is not transitive, I know.)
a source to share