Force-Directed Graph Drawing
See wiki Docs
http://en.wikipedia.org/wiki/Force-directed_graph_drawing
You can drag Node.
Double Click to reset.
Add GUI to change num of vertexes/edges plz!
/**
* Copyright Qwaz ( http://wonderfl.net/user/Qwaz )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/i5II
*/
package
{
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Point;
public class Main extends Sprite {
public static const NUM_VERTEX:int=100, NUM_EDGE:int=130;
private var n:int, m:int;
private var dragging:int;
private var nodeList:Vector.<Node>, edgeList:Vector.<Edge>;
private var scale:Number, minX:Number, maxX:Number, minY:Number, maxY:Number, baseX:Number, baseY:Number;
public function Main(){
generateGraph(NUM_VERTEX, NUM_EDGE);
addEventListener(Event.ENTER_FRAME, enterFrameHandler);
stage.addEventListener(MouseEvent.MOUSE_DOWN, mouseDown);
stage.addEventListener(MouseEvent.MOUSE_UP, mouseUp);
stage.doubleClickEnabled = true;
stage.addEventListener(MouseEvent.DOUBLE_CLICK, doubleClicked);
}
private function enterFrameHandler(e:Event):void {
render();
}
private function render():void {
graphics.clear();
minX = minY = Number.MAX_VALUE;
maxX = maxY = Number.MIN_VALUE;
var i:int, j:int;
var f:Node, s:Node, node:Node;
var dist:Number;
for(i=0; i<n; i++){
f = nodeList[i];
for(j=0; j<n; j++){
if(i != j){
s = nodeList[j];
dist = (f.x-s.x)*(f.x-s.x)+(f.y-s.y)*(f.y-s.y);
f.vx += (f.x-s.x)/dist*Node.FORCE;
f.vy += (f.y-s.y)/dist*Node.FORCE;
}
}
minX = Math.min(minX, f.x);
maxX = Math.max(maxX, f.x);
minY = Math.min(minY, f.y);
maxY = Math.max(maxY, f.y);
}
var edge:Edge;
for(i=0; i<m; i++){
edge = edgeList[i];
f = nodeList[edge.first];
s = nodeList[edge.second];
dist = Math.sqrt((f.x-s.x)*(f.x-s.x)+(f.y-s.y)*(f.y-s.y));
f.vx -= (f.x-s.x)*dist*Edge.FORCE;
f.vy -= (f.y-s.y)*dist*Edge.FORCE;
s.vx += (f.x-s.x)*dist*Edge.FORCE;
s.vy += (f.y-s.y)*dist*Edge.FORCE;
}
const scaleW:Number = (stage.stageWidth-20)/(maxX-minX), scaleH:Number = (stage.stageHeight-20)/(maxY-minY);
if(scaleW < scaleH){
scale = scaleW;
baseX = 10;
baseY = 10+(stage.stageHeight-20-(maxY-minY)*scale)/2;
} else {
scale = scaleH;
baseX = 10+(stage.stageWidth-20-(maxX-minX)*scale)/2;
baseY = 10;
}
for(i=0; i<n; i++)
nodeList[i].update();
var rx:Number, ry:Number;
if(dragging != -1){
if(mouseX < baseX) rx = minX;
else if(mouseX > baseX+(maxX-minX)*scale) rx = maxX;
else rx = minX+(mouseX-baseX)/scale;
if(mouseY < baseY) ry = minY;
else if(mouseY > baseY+(maxY-minY)*scale) ry = maxY;
else ry = minY+(mouseY-baseY)/scale;
node = nodeList[dragging];
node.x = rx;
node.y = ry;
node.vx = 0;
node.vy = 0;
}
graphics.lineStyle(1);
for(i=0; i<m; i++){
edge = edgeList[i];
f = nodeList[edge.first];
s = nodeList[edge.second];
graphics.moveTo(getX(f), getY(f));
graphics.lineTo(getX(s), getY(s));
}
graphics.lineStyle();
graphics.beginFill(0x0000FF);
for(i=0; i<n; i++){
node = nodeList[i];
graphics.drawCircle(getX(node), getY(node), Node.NODE_RADIUS);
}
}
private function getX(node:Node):Number {
return baseX+(node.x-minX)*scale;
}
private function getY(node:Node):Number {
return baseY+(node.y-minY)*scale;
}
private function mouseDown(e:MouseEvent):void {
var i:int;
for(i=0; i<n; i++){
if(Point.distance(new Point(stage.mouseX, stage.mouseY), new Point(getX(nodeList[i]), getY(nodeList[i]))) < Node.NODE_RADIUS*5){
dragging = i;
break;
}
}
}
private function mouseUp(e:MouseEvent):void {
dragging = -1;
}
private function doubleClicked(e:MouseEvent):void {
generateGraph(NUM_VERTEX, NUM_EDGE);
}
private function generateGraph(numNode:int, numEdge:int):void {
n = numNode;
m = numEdge;
dragging = -1;
nodeList = new Vector.<Node>;
edgeList = new Vector.<Edge>;
if(m > n*(n-1)/2)
m = n*(n-1)/2;
else if(m < n-1)
m = n-1;
var i:int;
for(i=0; i<n; i++)
nodeList.push(new Node(Math.random(), Math.random()));
var edge:Edge;
var edgeDict:Object = {};
for(i=1; i<n; i++){
var num:int = random(0, i);
edge = new Edge(num, i);
edgeList.push(edge);
edgeDict[edge.hash()] = 1;
}
for(i=0; i<m-n+1; i++){
do {
edge = new Edge(random(0, n), random(0, n));
} while(edge.first == edge.second || edge.hash() in edgeDict);
edgeList.push(edge);
edgeDict[edge.hash()] = 1;
}
}
}
}
class Edge {
public var first:uint, second:uint;
public static const FORCE:Number = 0.01;
public function Edge(first:uint, second:uint){
this.first = first;
this.second = second;
}
public function hash():String {
return "graph.Edge min:"+Math.min(first, second)+" max:"+Math.max(first, second);
}
}
class Node {
public var x:Number, y:Number, vx:Number, vy:Number;
public static const MIN_LIMIT:Number = 0.000001, NODE_RADIUS:Number = 3;
public static const FORCE:Number = 0.0001, FRICTION:Number = 0.96;
public function Node(x:Number, y:Number){
this.x = x;
this.y = y;
vx = 0;
vy = 0;
}
public function update():void {
vx *= FRICTION;
vy *= FRICTION;
if(Math.abs(vx) < MIN_LIMIT) vx = 0;
if(Math.abs(vy) < MIN_LIMIT) vy = 0;
x += vx;
y += vy;
}
}
function random(start:int, end:int):int {
if(end < start) throw new ArgumentError("End must be bigger than start");
return Math.random()*(end-start)+start;
}