Allora il file da parsare è un file
.dot che rappresenta un grafo non orientato.
Il contenuto del main al netto di altre istruzioni è così:
Codice: Seleziona tutto
Graph g = null;
try {
g = new Graph(System.in);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
// vari alogritmi sul grafo
...
Uno stralcio della classe Graph:
Codice: Seleziona tutto
public Graph(int V) {
if (V < 0)
throw new IllegalArgumentException(
"Number of vertices must be nonnegative");
this.V = V;
this.E = 0;
adj = (AdjList<Integer>[]) new AdjList[V];
color = new int[V];
d = new int[V];
f = new int[V];
dist = new int[V];
predecessor = new Integer[V];
for (int v = 0; v < V; v++) {
adj[v] = new AdjList<Integer>();
}
}
public Graph(InputStream in) throws FileNotFoundException {
this(countVertices(in));
generateMap(content);
Scanner sc = new Scanner(content);
sc.useDelimiter(";");
sc.nextLine();
while (sc.hasNext()) {
String s = sc.next()
// 1. compress all non-newline whitespaces to single space
.replaceAll("[\\s&&[^\\n]]+", " ")
// 2. remove spaces from beginning or end of lines
.replaceAll("(?m)^\\s|\\s$", "")
// 3. compress multiple newlines to single newlines
.replaceAll("\\n+", "\n")
// 4. remove spaces between numbers
.replace(" ", "")
// 5. remove "}"
.replaceAll("\\}", "")
// 6. remove newlines
.replaceAll("\\n", "")
// 7. removes '--'
//.replaceAll("\\-", "")
.replaceAll("(?m)^[ \t]*\r?\n", "");
String[] res = s.split("--");
if (!s.equals("")) {
for (int i = 1; i < res.length; i++) {
int v = map.getForward(res[i-1]);
int u = map.getForward(res[i]);
addEdge(u, v);
}
}
}
sc.close();
}
private static int countVertices(InputStream in) throws FileNotFoundException {
Scanner sc = new Scanner(in);
sc.nextLine();
content = sc.useDelimiter("\\Z").next();
sc.close();
String adjusted =
// 1. compress all non-newline whitespaces to single space
content.replaceAll("[\\s&&[^\\n]]+", " ")
// 2. remove spaces from beginning or end of lines
.replaceAll("(?m)^\\s|\\s$", "")
// 3. compress multiple newlines to single newlines
.replaceAll("\\n+", "\n")
// 4. remove spaces between numbers
.replace(" ", "")
// 5. remove "}"
.replaceAll("\\}", "")
// 6. remove newlines
.replaceAll("\\n", "--")
// 7. removes '--'
//.replaceAll("\\-", "")
.replaceAll("(?m)^[ \t]*\r?\n", "")
.replaceAll("\\;", "");
String[] str = adjusted.split("--");
// Delete duplicate strings
str = new HashSet<String>(Arrays.asList(str)).toArray(new String[0]);
return str.length;
}
private void generateMap(String content) throws FileNotFoundException {
map = new TwoWayHashMap<String, Integer>();
String adjusted =
// 1. compress all non-newline whitespaces to single space
content.replaceAll("[\\s&&[^\\n]]+", " ")
// 2. remove spaces from beginning or end of lines
.replaceAll("(?m)^\\s|\\s$", "")
// 3. compress multiple newlines to single newlines
.replaceAll("\\n+", "\n")
// 4. remove spaces between numbers
.replace(" ", "")
// 5. remove "}"
.replaceAll("\\}", "")
// 6. remove newlines
.replaceAll("\\n", "--")
// 7. removes '--'
//.replaceAll("\\-", "")
.replaceAll("(?m)^[ \t]*\r?\n", "")
.replaceAll("\\;", "");
String[] s = adjusted.split("--");
// Delete duplicate strings
s = new HashSet<String>(Arrays.asList(s)).toArray(new String[0]);
for (int i = 0; i < s.length; i++) {
map.put(s[i], i);
}
}
La procedura countVertices conta quanti da quanti nodi è formato il grafo, generateMap genera un HashMap a doppia entrata, mi serve per tenere traccia delle etichette dei nodi ed del loro indice. Così che ad esempio se voglio fare una visita DFS per controllare se il grafo è ciclico per poi successivamente eliminare i cicli, posso eseguire la visita semplicemente ciclando i nodi del grafo come se fossero numeri interi.