• fullscreen
  • Edge.pde
  • ForceDirectedGraph.pde
  • Graph.pde
  • TagClustering.pde
  • Vertex.pde
  • 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;
    }
    

    code

    tweaks (0)

    about this sketch

    This sketch is running as Java applet, exported from Processing.

    license

    advertisement

    Kyle McDonald

    Tag Clustering

    Add to Faves Me Likey@! 36
    You must login/register to add this sketch to your favorites.

    Tag similarity is visualized as spatial distance and color similarity, and frequency determines font size. Hit any key to reload. Select a beginning and end tag (which become highlighted red and green, respectively) to see the shortest path between them. Deselect by clicking again, or reselect the end by clicking a new tag. Tags come from old projects of mine I tagged. Distance from each tag to the three most significant and polarized tags determines RGB color. These three tags are found by taking the mode of multiple K-medoids runs for K = 3 using Dijkstra's algorithm as the distance metric.

    wangyiwen
    30 Mar 2013
    where is the Vector for TagClustering's "Vector path = null"?
    You need to login/register to comment.