这周的作业可谓是一波三折，但是收获了不少，熟悉了广度优先搜索还有符号图的建立。此外还知道了Integer.MAX_VALUE。

SAP:

求v和w的大概思路是对v和w分别广度优先搜索，然后遍历图中每一个顶点，如果v和w都可以到达一个顶点，就计算v和w到这一顶点的距离和，最后求出最短的距离以及对应的顶点便是所求length和ancestor。

至于Iterable<Integer> v和Iterable<Integer> w，开始我是求v中每一个顶点和w中的每一个顶点的距离，然后求出最短距离，但提交后时间测试通不过。参考了其他人的一些博客后发现可以遍历一次完成对v或w的广度优先搜索，于是自己写了一个BFS类。然而这次提交出现了OperationCountLimitExceededException，最后检查了半天才发现bfs时丢了一句   ' if(!marked[w]) '。。。后来发现官方提供的BreadthFirstDirectedPaths类可以完成Iterable<Integer> v的广度优先搜索，于是干脆直接调用这个。

但是提交后还是有问题。。。对于没有共同祖先的情况判断不正确，不能返回-1，检查了半天发现每次求length或ancestor都应该在前面加上 anc = -1; 否则这次求返回的是上次的anc。

import edu.princeton.cs.algs4.*;import edu.princeton.cs.algs4.In;public class SAP {    private Digraph G;    private int anc = -1;   // constructor takes a digraph (not necessarily a DAG)   public SAP(Digraph G) {       if(G == null) throw new IllegalArgumentException();       this.G = new Digraph(G);   }   // length of shortest ancestral path between v and w; -1 if no such path   public int length(int v, int w) {       if(v < 0 || v > G.V() - 1 || w < 0 || w > G.V() - 1)           throw new IllegalArgumentException();       anc = -1;              BreadthFirstDirectedPaths bv = new BreadthFirstDirectedPaths(G, v);       BreadthFirstDirectedPaths bw = new BreadthFirstDirectedPaths(G, w);              int minLength = Integer.MAX_VALUE;              for(int i = 0; i < G.V(); i++) {           if(bv.hasPathTo(i) && bw.hasPathTo(i)) {               int l = bv.distTo(i) + bw.distTo(i);               if(l < minLength) {                   minLength = l;                   anc = i;               }           }       }              if(minLength == Integer.MAX_VALUE) return -1;       else return minLength;         }   // a common ancestor of v and w that participates in a shortest ancestral path; -1 if no such path   public int ancestor(int v, int w) {       length(v, w);       return anc;   }       // length of shortest ancestral path between any vertex in v and any vertex in w; -1 if no such path   public int length(Iterable
     
       v, Iterable
      
        w) {       if(v == null || w == null)           throw new IllegalArgumentException();       anc = -1;              for(int i : v) {           if(i < 0 || i > G.V() - 1)                throw new IllegalArgumentException();       }       for(int i : w) {           if(i < 0 || i > G.V() - 1)                throw new IllegalArgumentException();       }              BreadthFirstDirectedPaths bv = new BreadthFirstDirectedPaths(G, v);       BreadthFirstDirectedPaths bw = new BreadthFirstDirectedPaths(G, w);              int minLength = Integer.MAX_VALUE;              for(int i = 0; i < G.V(); i++) {           if(bv.hasPathTo(i) && bw.hasPathTo(i)) {               int l = bv.distTo(i) + bw.distTo(i);               if(l < minLength) {                   minLength = l;                   anc = i;               }           }       }              if(minLength == Integer.MAX_VALUE) return -1;       else return minLength;   }   // a common ancestor that participates in shortest ancestral path; -1 if no such path   public int ancestor(Iterable
       
         v, Iterable
        
          w) {       length(v, w);       return anc;   }   // do unit testing of this class   public static void main(String[] args) {            }}
        
       
      
     

WordNet：

wordnet涉及到符号图的问题，开始用ST<String, Integer>来完成noun到id的索引，后来发现一个noun可能对应多个id,于是改为ST<String, Bag<Integer>>。

需要检查有向图是否合格：1.不能有环。通过类DirectedCycle完成。 2.只能有一个root。经参考别人的博客发现一个很巧妙的方法，如果一个顶点是根，那么它不指向其它顶点，所以它不会出现在hypernyms每行的第一个id。

方法sap需要通过id得到noun，用数组的话不能提前知道数组大小，于是参考网上用ArrayList<String>完成id到noun的索引。

import edu.princeton.cs.algs4.*;import java.util.ArrayList;public class WordNet {    private ST
     
      > st;    private ArrayList
      
        idList;    private Digraph G;       // constructor takes the name of the two input files   public WordNet(String synsets, String hypernyms) {       if(synsets == null || hypernyms == null) throw new IllegalArgumentException();              st = new ST
       
        >();       idList = new ArrayList
        
         ();              int count = 0;       In in1 = new In(synsets);       while(in1.hasNextLine()) {           String[] a = in1.readLine().split(",");           String[] a2 = a[1].split(" ");                      for(int i = 0; i < a2.length; i++) {               if(st.contains(a2[i])) st.get(a2[i]).add(Integer.parseInt(a[0]));               else {                    Bag
         
           b = new Bag
          
           (); b.add(Integer.parseInt(a[0])); st.put(a2[i], b); } } count++; idList.add(a[1]); } G = new Digraph(count); In in2 = new In(hypernyms); boolean[] isNotRoot = new boolean[count]; int rootNumber = 0; while(in2.hasNextLine()) { String[] a = in2.readLine().split(","); isNotRoot[Integer.parseInt(a[0])] = true; for(int i = 1; i < a.length; i++) G.addEdge(Integer.parseInt(a[0]), Integer.parseInt(a[i])); } for(int i = 0; i < count; i++) { if(!isNotRoot[i]) rootNumber++; } DirectedCycle d = new DirectedCycle(G); if(rootNumber > 1 || d.hasCycle()) throw new IllegalArgumentException(); } // returns all WordNet nouns public Iterable
           
             nouns() { return st.keys(); } // is the word a WordNet noun? public boolean isNoun(String word) { if(word == null) throw new IllegalArgumentException(); return st.contains(word); } // distance between nounA and nounB (defined below) public int distance(String nounA, String nounB) { if(nounA == null || nounB == null || !isNoun(nounA) || !isNoun(nounB)) throw new IllegalArgumentException(); SAP s = new SAP(G); Bag
            
              ida = st.get(nounA); Bag
             
               idb = st.get(nounB); return s.length(ida, idb); } // a synset (second field of synsets.txt) that is the common ancestor of nounA and nounB // in a shortest ancestral path (defined below) public String sap(String nounA, String nounB) { if(nounA == null || nounB == null || !isNoun(nounA) || !isNoun(nounB)) throw new IllegalArgumentException(); SAP s = new SAP(G); Bag
              
                ida = st.get(nounA); Bag
               
                 idb = st.get(nounB); int root = s.ancestor(ida, idb); return idList.get(root); } // do unit testing of this class public static void main(String[] args) { }}
               
              
             
            
           
          
         
        
       
      
     

Outcast：

 

public class Outcast {    private WordNet wordnet;        // constructor takes a WordNet object    public Outcast(WordNet wordnet) {        this.wordnet = wordnet;    }    // given an array of WordNet nouns, return an outcast       public String outcast(String[] nouns) {        int length = nouns.length;        int[][] distance = new int[length][length];                for(int i = 0; i < length; i++) {            for(int j = i; j < length; j++) {                distance[i][j] = wordnet.distance(nouns[i], nouns[j]);            }        }                int maxDistance = 0;        int sum = 0;        int num = 0;        for(int i = 0; i < nouns.length; i++) {            sum = 0;            for(int j = 0; j < nouns.length; j++) {                if(i < j)                    sum += distance[i][j];                else                    sum += distance[j][i];            }                        if(sum > maxDistance) {                maxDistance = sum;                num = i;            }        }                return nouns[num];    }    // see test client below    public static void main(String[] args) {    }        }