// maps objects to vertices
class Graph extends HashMap {
  ForceDirectedGraph fdg;
  Vector medoids;
  Graph() {
    fdg = new ForceDirectedGraph();
    resetMemos();
  }
  HashMap distanceMemo;
  void resetMemos() {
    distanceMemo = new HashMap();
  }
  Vertex addVertex(Object o) {
    Vertex v = getVertex(o);
    v.count++;
    return v;
  }
  Edge addEdge(Object from, Object to) {
    Edge e = getEdge(from, to);
    e.count++;
    e.resetLength();
    return e;
  }
  Vertex getVertex(Object o) {
    Vertex v = (Vertex) get(o);
    if(v != null)
      return v;
    v = new Vertex(o);
    v.particle = fdg.addVertex();
    put(o, v);
    return v;
  }
  Edge getEdge(Object from, Object to) {
    Vertex vfrom = getVertex(from);
    Vertex vto = getVertex(to);
    return vfrom.getEdge(vto, fdg);
  }
  void render() {
    fdg.tick(1);
    fdg.reposition();
    Vector V = new Vector(values());
    for(int i = 0; i < V.size(); i++)
      ((Vertex) V.get(i)).render(this);
  }
  float distance(Object from, Object to) {
    return distance(getVertex(from), getVertex(to));
  }
  float distance(Vertex from, Vertex to) {
    if(from == to) return 0;
    Vector args = new Vector();
    args.add(from);
    args.add(to);
    if(distanceMemo.containsKey(args))
      return ((Float) distanceMemo.get(args)).floatValue();
    Vector Q = new Vector(values());
    for(int i = 0; i < Q.size(); i++) {
      Vertex cur = ((Vertex) Q.get(i));
      cur.pathLength = Float.POSITIVE_INFINITY;
      cur.previousVertex = null;
    }
    from.pathLength = 0;
    while(Q.size() != 0) {
      Vertex u = null; // u is cur min length
      for(int i = 0; i < Q.size(); i++)
        if(u == null || ((Vertex) Q.get(i)).pathLength < u.pathLength)
          u = (Vertex) Q.get(i);
      if(u == to) break;
      Q.remove(u);
      Vector outgoing = new Vector(u.values());
      for(int i = 0; i < outgoing.size(); i++) {
        Edge e = (Edge) outgoing.get(i);
        Vertex v = e.to;
        if(u.pathLength + e.length() < v.pathLength) {
          v.pathLength = u.pathLength + e.length();
          v.previousVertex = u;
        }
      }
    }
    distanceMemo.put(args, new Float(to.pathLength));
    return to.pathLength;
  }
  Vertex at() {
    Vector V = new Vector(values());
    Vertex near = null;
    float dmin = Float.POSITIVE_INFINITY;
    for(int i = 0; i < V.size(); i++) {
      Vertex cur = (Vertex) V.get(i);
      Vector3D pos = cur.particle.position();
      float
        cx = screenX(pos.x(), pos.y(), pos.z()),
      cy = screenY(pos.x(), pos.y(), pos.z());
      float d = dist(cx, cy, mouseX, mouseY);
      if(d < selectDistance && d < dmin)
        near = cur;
    }
    return near;
  }
  Vector kMedoids(int k, int r) {
    // populate medoids with k unique objects
    Vector medoids = new Vector();
    Vector choices = new Vector(values());
    for(int i = 0; i < k; i++) {
      Vertex choice = (Vertex) choices.get((int) random(choices.size()));
      medoids.add(choice);
      choices.remove(choice);
    }
    for(int repetitions = 0; repetitions < r; repetitions++) {
      // make k empty groups
      Vector groups = new Vector();
      for(int i = 0; i < k; i++) 
        groups.add(new Vector());
      // assign each object to closest medoid
      Vector all = new Vector(values());
      for(int i = 0; i < all.size(); i++) {
        float mind = Float.POSITIVE_INFINITY;
        Vertex cur = (Vertex) all.get(i);
        int group = 0;
        for(int j = 0; j < k; j++) {
          Vertex curm = (Vertex) medoids.get(j);
          float curd = distance(curm, cur);
          if(curd < mind) {
            group = j;
            mind = curd;
          }
        }
        ((Vector) groups.get(group)).add(cur);
      }
      // recalculate medoids
      medoids = new Vector(); // empty medoids
      for(int i = 0; i < k; i++) { // with each group
        float mind = Float.POSITIVE_INFINITY;
        Vertex medoid = null;
        Vector curgroup = (Vector) groups.get(i);
        for(int j = 0; j < all.size(); j++) { // with all vertices
          Vertex cur = (Vertex) all.get(j);
          float totd = 0;
          for(int m = 0; m < curgroup.size(); m++) // to all vertices in group
            totd += distance(cur, (Vertex) curgroup.get(m)); // sum distance from cur to it
          if(totd < mind && !medoids.contains(cur)) { // unique medoids
            medoid = cur; // get vertex with shortest distance to all in group
            mind = totd;
          }
        }
        medoids.add(medoid);
      }
    }
    return medoids;
  }
  // run kMedoids(k,r) t times, take the most common clustering
  Vector kMedoidsMode(int k, int r, int t)  {
    resetMemos();
    Vector clusterings = new Vector();
    for(int i = 0; i < t; i++)
      clusterings.add(new HashSet(kMedoids(k, r)));
    int maxCount = 0;
    Set mode = null;
    for(int i = 0; i < t; i++) {
      int count = 0;
      for(int j = 0; j < t; j++)
        if(clusterings.get(i).equals(clusterings.get(j)))
          count++;
      if(count > maxCount) {
        maxCount = count;
        mode = (HashSet) clusterings.get(i);
      }
    }
    return new Vector(mode);
  }
  void setMedoids(int k, int r, int t) {
    medoids = kMedoidsMode(k, r, t);
  }
  String toString() {
    return keySet().size() + " " + super.toString();
  }
}