class Edge {
  int count;
  Vertex from, to;
  Spring spring;
  Edge(Vertex from, Vertex to) {
    this.from = from;
    this.to = to;
    count = 0;
  }
  void render() {
    Vector3D fxyz = from.particle.position();
    Vector3D txyz = to.particle.position();
    stroke(0.4, 0.1);
    line(fxyz.x(), fxyz.y(), fxyz.z(), txyz.x(), txyz.y(), txyz.z());
  }
  void resetLength() {
    spring.setRestLength(map(length(),0,1,lengthMin,lengthMax));
  }
  float length() {
    return 1.01 - (float) count / (float) from.count;
  }
  String toString() {
    return "e(" + count + "):" +
      from.toString() + ">" +
      to.toString();
  }
}

import traer.physics.*;
import traer.animation.*;

final float EDGE_LENGTH = 20;
final float EDGE_STRENGTH = 0.01;
final float SPACER_STRENGTH = 1100;
final float RANDOM_INIT = 100;
final float ZOOM = 1.2;

class ForceDirectedGraph extends ParticleSystem {
  Smoother3D centroid;
  ForceDirectedGraph() {
    this(0.25, 0.95);
  }
  ForceDirectedGraph(float friction, float smoothness) {
    super(0, friction);
    centroid = new Smoother3D(smoothness);
    reset();
  }
  void reset() {
    clear();
    centroid.setValue(0, 0, 1);
  }
  Vector3D remap(float x, float y) {
    return new Vector3D(
    centroid.x() + (x - width/2) / centroid.z(),
    centroid.y() + (y - height/2) / centroid.z(),
    0);
  }
  Particle addVertex() {
    Particle p = makeParticle();
    for(int i = 0; i < numberOfParticles(); i++) {
      Particle t = getParticle(i);
      if(t != p)
        makeAttraction(p, t, -SPACER_STRENGTH, 15);
    }
    p.moveTo(random(-RANDOM_INIT, RANDOM_INIT), random(-RANDOM_INIT, RANDOM_INIT), random(-RANDOM_INIT, RANDOM_INIT));
    return p;
  }
  Spring addEdge(Particle a, Particle b) {
    return makeSpring(a, b, EDGE_STRENGTH, EDGE_STRENGTH, EDGE_LENGTH);
  }
  Spring addEdge(Particle a, Particle b, float edgeLength) {
    return makeSpring(a, b, EDGE_STRENGTH, EDGE_STRENGTH, edgeLength);    
  }
  void reposition() {
    centroid.tick();
    translate(width/2 - centroid.x(), height/2 - centroid.y());
    rotateY(frameCount * rotationSpeed);
    scale(centroid.z());
    float 
      xMax = Float.NEGATIVE_INFINITY, 
    xMin = Float.POSITIVE_INFINITY, 
    yMin = Float.POSITIVE_INFINITY, 
    yMax = Float.NEGATIVE_INFINITY;

    for(int i = 0; i < numberOfParticles(); i++) {
      Vector3D p = getParticle(i).position();
      float
        curX = screenX(p.x(), p.y(), p.z()) - width/2,
      curY = screenY(p.x(), p.y(), p.z()) - height/2;
      xMax = max(xMax, curX);
      xMin = min(xMin, curX);
      yMin = min(yMin, curY);
      yMax = max(yMax, curY);
    }

    float deltaX = xMax - xMin;
    float deltaY = yMax - yMin;
    float xOff = lerp(xMin, xMax, .5);
    float yOff = lerp(yMin, yMax, .5);
    float zoom = deltaY > deltaX ?
      height / deltaY:
      width / deltaX;
    centroid.setTarget(
      centroid.x() + xOff,
      centroid.y() + yOff,
      zoom * ZOOM);
  }
}

// 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();
  }
}

Graph graph;
PFont trebuchet;
float lengthMin = 1;
float lengthMax = 100;
float selectDistance = 15;
float rotationSpeed = PI/1000;

Vertex cur, begin, end;
Vector path = null;

void setup() {
  size(640, 640, P3D);
  colorMode(RGB, 1);
  
  trebuchet = loadFont("TrebuchetMS-48.vlw");
  textFont(trebuchet, 10);
  textAlign(CENTER);
  
  graph = loadTags("tags.txt");
  
  cur = begin = end = null;
}

void draw() {
  background(1);
  graph.render();
    
  if(begin != null && end != null)  { // render path
    for(int i = 1; i < path.size(); i++) {
      Vector3D lastp = ((Vertex) path.get(i-1)).particle.position();
      Vector3D curp = ((Vertex) path.get(i)).particle.position();
      stroke(0,0,.5,.6);
      line(lastp.x(), lastp.y(), lastp.z(), curp.x(), curp.y(), curp.z());
      ((Vertex) path.get(i)).light = true;
    }
    ((Vertex) path.lastElement()).light = false;
  }
  
  cur = graph.at();
  noStroke();
  if(cur != null) {
    fill(.5,.5);
    renderSelection(cur);
  }
  if(begin != null) {
    fill(1,.5,.5,.5);
    renderSelection(begin);
  }
  if(end != null) {
    fill(.5,1,.5,.5);
    renderSelection(end);
  }
}

void renderSelection(Vertex v) {
  Vector3D pos = v.particle.position();
  pushMatrix();
  translate(pos.x(), pos.y(), pos.z());
  rotateY(-frameCount*rotationSpeed);
  ellipse(0,0,selectDistance,selectDistance);
  popMatrix();
}

void mousePressed() {
  if(cur != null) {
    if(begin == null && cur != end)
      begin = cur;
    else if(begin == cur)
      begin = null;
    else if(end == null) {
      end = cur;
    } else if(end == cur)
      end = null;
    else
      end = cur;
    if(begin != null && end != null) { // compile path
      graph.resetMemos(); // memoization keep us from building a path
      graph.distance(begin, end);
      path = new Vector();
      Vertex inpath = end;
      path.add(inpath);
      while((inpath = inpath.previousVertex) != null)
        path.add(inpath);
    }
  }
}

void keyPressed() {
  setup();
}

Graph loadTags(String filename) {
  Graph graph = new Graph();
  String[] file = loadStrings(filename);
  for(int i = 0; i < file.length; i++) {
    String[] tags = subset(split(file[i], ' '), 1); // all but the first
    for(int j = 0; j < tags.length; j++) {
      graph.addVertex(tags[j]);
      for(int k = 0; k < tags.length; k++)
        if(j != k)
          graph.addEdge(tags[j], tags[k]);
    }
  }
  graph.setMedoids(3, 1, 5);
  return graph;
}

// maps connected vertices to edges
class Vertex extends HashMap {
  // distance info
  float pathLength;
  Vertex previousVertex;
  
  // rendering properties
  boolean light;
  Particle particle;
  
  // essential properties
  int count;
  Object value;
  
  Vertex(Object value) {
    this.value = value;
    light = false;
    count = 0;
  }
  Edge getEdge(Vertex to, ForceDirectedGraph fdg) {
    Edge e = (Edge) get(to);
    if(e != null)
      return e;
    e = new Edge(this, to);
    e.spring = fdg.addEdge(particle, to.particle);
    put(to, e);
    return e;
  }
  void render(Graph parent) {    
    Vector3D xyz = particle.position();
    pushMatrix();
    translate(xyz.x(), xyz.y(), xyz.z());
    rotateY(-frameCount*rotationSpeed);
        
    float[] rgb = {
      parent.distance((Vertex) parent.medoids.get(0), this),
      parent.distance((Vertex) parent.medoids.get(1), this),
      parent.distance((Vertex) parent.medoids.get(2), this)
    };
    rgb = normalize(rgb);
    rgb = divide(rgb, 1.5);
    
    if(light) {
      fill(rgb[0], rgb[1], rgb[2], 0.5);
      ellipse(0,0,selectDistance,selectDistance);
      light = false;
    }
    
    fill(rgb[0], rgb[1], rgb[2], 0.9);
    textSize(count / 2 + 8);
    text(value.toString(),0,textAscent()/2);
    popMatrix();
    Vector E = new Vector(values());
    for(int i = 0; i < E.size(); i++)
      ((Edge) E.get(i)).render();
  }
  int hashCode() {
    return value.hashCode();
  }
  String toString() {
    return "v(" + count + "):" +
      value.toString();
  }
}

float[] normalize(float[] array) {
  float m = 0;
  for(int i = 0; i < array.length; i++)
    m = max(m, array[i]);
  float[] result = new float[array.length];
  for(int i = 0; i < array.length; i++)
    result[i] = array[i] / m;
  return result;
}

float[] divide(float[] array, float scalar) {
  float[] result = new float[array.length];
  for(int i = 0; i < array.length; i++)
    result[i] = array[i] / scalar;
  return result;
}