2009年9月15日星期二

Webpage 增长的可视化


关于wiki.tudelft.nl page的增长可视化,这个概念是从2004年底开始的,可以从这里Wiki Growth Over Time了解到,跟前一篇在可视化上看起来是一致的,但是在核心却有着千差万别,它是基于的是整个网络每个Node是一个web page的,Edge是hyperlink,表示了这个web page的网页流向,而前一篇Node是一个一个的tags,Edge是连接Children的生成关系。一个网页虽说是动态的,但是tag最多也不会超过3000个(个人估计,看sports sina 全部节点,不去掉js和plugins的话,有2200个左右),但是Wiki Growth却不同了,它会一直生成下去,可见wiki在这短短时间内是怎样壮大了的吧,有点象一个细菌的繁殖,还有从视频中,可以了解到节点生成的动向(Force-Directed )。

2009年9月9日星期三

aharef: html标签可视化的qt实现过程

aharef:是一个动态生成网页标签元素的网站,是由stanford university的学生写出来的,里面涉及到Processing, Traer Physics, HTMLParser

Processing 的中文资料: http://www.douban.com/group/topic/3637024/
但是这些都是由java写成的,是生成的时候是也是调用applet来实现的。现在我要用qt实现上述功能。先给一张afaref上google的tag的生成图片
未标题-3
然后对比一下,主要一个优点(也可以说瓶颈的地方就是),我实现了粒子的拖拽,但是因为要遍历所有点与对其的作用力(大量的运算,因为如果其中一个点发生运动的话,想想看,如果是root tag:的话,那里对于上1000个节点来说,terrible),所以,相对google来说,还好一点,但是对于节点超过了1000个点左右的话,我的机子风扇就开始轰鸣了(我的笔记本是最老的双核 :-( )。但是没有办法,如果减少节点的话,那么对网站tag的准确性就存在问题,这对于一个真实存在的html文档来说,是不公平的,对用户来说也是不公平的,因为你的节点树实际上是有错误的。

再看看用qt实现的结果:

未标题-5
参考了elastic nodes里面的源码,其中计算压力的函数,很经典,用向量来表示受力情况,实现机制大致是这样的:
1.html Parse 得到网页中所有的tagName放进一个Vector vectag;
2.利用QXmlStreamWriter将vectag里面的内容写入到一个xml文件中,为得是后面动态生成的时候广度优先,这里要判断是否是前缀 后缀或者比如img、 embed(引文通常写法没有后缀结束符)
递归生成节点,广度
ParseXml(const QDomNode & domnode,Node* centerNode)
这里将生产的Node要放入QQueue 以便,下次遍历时取出作为父节点

struct strNode
{
Node* m_center; //父节点指针
Node* m_tag; //this
} m_nodeline;

然后是定时器,每0.1s动态生成一个

m_Mutex.lock();
strNode strnode = m_nodeline.dequeue();
m_Mutex.unlock();
Edge *edge = new Edge(strnode.m_center,strnode.m_tag);

myscene->addItem(strnode.m_tag);
myscene->addItem(edge);

currentpoint.setX(strnode.m_center->pos().x()+Radius*(cos(TwoPi*(1.0/6.0*(i%6)))));
currentpoint.setY(strnode.m_center->pos().y()+Radius*(sin(TwoPi*(1.0/6.0*(i%6)))));

strnode.m_tag->setPos(currentpoint+QPointF(0.1,0.1));

//关键代码是从红色标记的地方开始的,因为真正的受力分析是从生成动态生成new Edge开始的,
因为,这也是代码有点"混乱"的地方
new Edge(strnode.m_center,strnode.m_tag)

edge.cpp......

strnode.m_center->addEdge(this);
strnode.m_tag->addEdge(this);

node.cpp
edgeList<adjust() 调整线段的长度位置( QLineF line(mapFromItem(source, 0, 0), mapFromItem(dest, 0, 0);)

压力计算触发是在绿色标记开始的
当setpos()之后,QGraphicsItem的virtual protected函数
QVariant Node::itemChange(GraphicsItemChange change, const QVariant &value)
{
switch (change) {
case ItemPositionHasChanged:
foreach (Edge *edge, edgeList)
edge->adjust();
graph->itemMoved();
break;
default:
break;
};
return QGraphicsItem::itemChange(change, value);
}

然后先求与之相连接的所有线段,调整一下长度和位置,然后graph->itemMoved()会触发计算器
//算node移动的位置的时候,启动一个定时器
void GraphWidget::itemMoved()
{
//40ms来更新位置
if (!timerId)
timerId = startTimer(1000 / 20);
}

//TimeEvent来更新位置
void GraphWidget::timerEvent(QTimerEvent *event)
{
Q_UNUSED(event);
//遍历屏幕的所有Node
QList nodes;
foreach (QGraphicsItem *item, scene()->items()) {
if (Node *node = qgraphicsitem_cast(item))
nodes <<>calculateForces();
//然后移动实例受力的位置
bool itemsMoved = false;
foreach (Node *node, nodes) {
if (node->advance())
itemsMoved = true;
}
if (!itemsMoved) {
killTimer(timerId);
timerId = 0;
}
}
来看看经典的压力计算函数吧
void Node::calculateForces()
{
if (!scene() scene()->mouseGrabberItem() == this) {
newPos = pos(); //如果抓住的自己的话,那么就直接返回
return;
}

//如果不是被抓到的点,求他垂直方向上合水平方向上的受力(因为所有的点都是由线来连接的,所有说每个点都对其他的任何一个在屏幕中的点有作用力)
// Sum up all forces pushing this item away
qreal xvel = 0;
qreal yvel = 0;
foreach (QGraphicsItem *item, scene()->items())
{
Node *node = qgraphicsitem_cast(item);
if (!node node == this)
continue;

QLineF line(mapFromItem(node, 0, 0), QPointF(0, 0));
qreal dx = line.dx();
qreal dy = line.dy();
double l = 2.0 * (dx * dx + dy * dy);
if (l > 0)
{
xvel += (dx * 8.0) / l;
yvel += (dy * 8.0) / l;
}
}

//然后求与之相连的点的作用力,这样的作用力会显现的更明显
double weight = (edgeList.size() + 1) * 4.5;
foreach (Edge *edge, edgeList) {
QPointF pos;
if (edge->sourceNode() == this)
pos = mapFromItem(edge->destNode(), 0, 0);
else
pos = mapFromItem(edge->sourceNode(), 0, 0);
xvel += pos.x() / weight;
yvel += pos.y() / weight;
}

if (qAbs(xvel) < xvel =" yvel" scenerect =" scene()-">sceneRect();
newPos = pos() + QPointF(xvel, yvel);
}


OVER