Software Engineering Praxis im Sommersemester 2006
|
Hauptprogrammpackage blatt4; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; public class FileSrc { public static void main(String[] args) { try { BufferedReader r = new BufferedReader(new FileReader("erdos.in")); ErdosNumber e = new ErdosNumber(); String line; while((line=r.readLine()) != null){ ReferenceParser p = new ReferenceParser(); p.parse(line); e.addCombination(p.getAuthors()); } e.print(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } } Klasse zum Bestimmen der Erdös-Zahlpackage blatt4; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.Set; /**Diese Klasse bestimmt die Erdoes-Zahl eines Autors aus einer Literatur-Datenbank * @author rguderlei */ public class ErdosNumber { HashMap map = new HashMap(); HashMap fullName = new HashMap(); /**Diese Methode fuellt die Datenstrukturen mit den Autoren-Listen * @param authors String-Array aus den vollen Namen der Autoren. */ public void addCombination(String[] authors){ if(authors.length>1){ for(int i=0; i<authors.length; i++){ String author = ReferenceParser.getName(authors[i]); for(int j=0; j<authors.length; j++){ String coauthor = ReferenceParser.getName(authors[j]); if(i!=j){ if(map.keySet().contains(author)){ HashSet set = (HashSet)map.get(author); set.add(coauthor); map.put(author, set); } else { HashSet set = new HashSet(); set.add(coauthor); map.put(author, set); } if(!fullName.keySet().contains(author)){ fullName.put(author, authors[i]); } if(!fullName.keySet().contains(coauthor)){ fullName.put(coauthor, authors[j]); } } } } } } /** * Diese Methode gibt die Namen und Erdoes-Zahlen aus. */ public void print(){ Set keys = map.keySet(); Iterator i = keys.iterator(); while(i.hasNext()){ String name = (String)i.next(); //System.err.println(name); HashSet visited = new HashSet(); visited.add(name); System.out.println((String)fullName.get(name) + ": " + erdosNumber(name, visited)); } } /** * Diese Methode gibt zu Debugging-Zwecken die Haupt-Datenstruktur aus. */ public void printMap(){ Set keys = map.keySet(); Iterator i = keys.iterator(); while(i.hasNext()){ String name = (String)i.next(); Set s = (Set)map.get(name); System.out.println(name + ": " + s.toString()); } } /**rekursive Berechnung der Erdoes-Zahl * @param name der (Nach)Name des Autors * @param visited Set mit den bereits besuchten knoten des Graphen * @return die Erdoes-Zahl des angegebenen Autors */ private int erdosNumber(String name, Set visited) { //Es existiert im Datensatz IMMER ein Pfad zu Erdoes!! //Erdoes selbst hat Erdoes-Zahl 0 if(name.equals("Erdoes")) return 0; Set s = (Set)map.get(name); //Seine Ko-Autoren haben Erdoes-Zahl 1 if(s.contains("Erdoes")) return 1; //Tiefensuche zur Bestimmung aller Pfade zu einem Ko-Autor von Erdoes Iterator i = s.iterator(); int number = 1000; // im datensatz gibt es max. EZ 3 , evtl tritt bei ungeeigneter init ein Überlauf auf while(i.hasNext()){ //Jede Kante hat Laenge 1, die Laenge des Pfades entspricht der EZ String next = (String)i.next(); if(!visited.contains(next)){ //aktuellen Knoten als besucht markieren visited.add(next); //rekursiv die EZ des Teilgraphen bestimmen int tmp = erdosNumber(next, visited); //akt. Knoten wieder als nicht-besucht markieren visited.remove(next); //falls ein kuerzerer Pfad gefunden wurde, diesen nehmen if(tmp<number) number = tmp; } } //System.out.println(number); return number+1; } } Parserpackage blatt4; import java.util.regex.*; /**Diese Klasse implementiert einen einfachen Parser zum Parsen der Einträge in der Literatur-Datenbank. * Die Methode <code>parse()<code> zerlegt den Eintrag. * * @author rguderlei * */ public class ReferenceParser { private String[] authors; private String title; /**Konstruktor. * */ public ReferenceParser(){ authors = new String[1]; } /**Diese Methode parst den Eintrag. * @param entry */ public void parse(String entry){ Pattern p = Pattern.compile("\\^"); String[] tmp = p.split(entry); p = Pattern.compile(";"); String[] tmp2 = p.split(tmp[0]); authors = new String[tmp2.length]; for(int i = 0; i<tmp2.length; i++) authors[i] = tmp2[i].trim(); p = Pattern.compile("\\."); tmp2 = p.split(tmp[1]); title = tmp2[0]; } static String getName(String author){ Pattern p = Pattern.compile(","); return p.split(author)[0].trim(); } /**Diese Methode liefert die Autoren als String-Array zurück. Jeder Eintrag des String-Arrays besteht * aus "Name, Vornamen" des Autors. * @return den vollen Namen des Autors. */ public String[] getAuthors() { return authors; } /**Diese Methode liefert den Titel der Publikation. * @return den Titel der Publikation. */ public String getTitle() { return title; } } |