Hierarchycal graph on Tulip

Some variables:

  • input: the input (original) graph
  • orig: the same input graph, but it is made as a sub graph of input.
  • meta: a node that represents a sub graph

Creating a subgraph

Case: Some of nodes in the original graph will be grouped as a sub graph. Those nodes in the original graph will then be replaced with a (meta) node that represents that sub graph.

Precondition: The original graph must not be the root graph. Create a sub graph of it first that contains the same nodes and edges.

Graph* orig = input->getRoot()->addSubGraph();
copy(input, orig);

Subgraph creation

set<node> nodes = [ list of nodes of the original graph (input) that will be subgraph-ed ]
node meta = tlp::createMetaNode(orig, nodes);

Two local properties of the input will be created: viewMetaNode and viewColor.

viewMetaNode property contains mapping from meta node to the sub graph that it represents.

Edges to nodes in the sub graph will changed. They will be pointed to the meta node after the sub graph is created. However, the original information about the edges is saved, so it can be restored later.

Getting created subgraph

GraphProperty* gp = input->getLocalProperty<GraphProperty*>("viewMetaNode");
Graph* subgraph = gp->getNodeValue(meta);

Restoring a sub graph to its “parent”

tlp::openMetaNode(orig, meta)

Edges connections will be restored.

Remarks

  1. The copy function (taken from GrouseFlocks):
    void copy (Graph *src, Graph *dest) {
      StableIterator <node> nodes (src->getNodes());
      while (nodes.hasNext()) dest->addNode (nodes.next());
      StableIterator <edge> edges (src->getEdges());
      while (edges.hasNext()) dest->addEdge (edges.next());
    }//end copyFeature
    
  2. Edges in a directed graph are handled nicely. Might be a problem if you only expect at most one edge for every pair of nodes (simple graph)
  3. Sub graphs can contain other sub graphs
  4. Opening a sub graph inside another sub graph may lead into a problem. Open the outer subgraph first to avoid unexpected problem.

Hierarchycal graph on Tulip

Some variables:

  • input: the input (original) graph
  • orig: the same input graph, but it is made as a sub graph of input.
  • meta: a node that represents a sub graph

Creating a subgraph

Case: Some of nodes in the original graph will be grouped as a sub graph. Those nodes in the original graph will then be replaced with a (meta) node that represents that sub graph.

Precondition: The original graph must not be the root graph. Create a sub graph of it first that contains the same nodes and edges.

Graph* orig = input->getRoot()->addSubGraph();
copy(input, orig);

Subgraph creation

set<node> nodes = [ list of nodes of the original graph (input) that will be subgraph-ed ]
node meta = tlp::createMetaNode(orig, nodes);

Two local properties of the input will be created: viewMetaNode and viewColor.

viewMetaNode property contains mapping from meta node to the sub graph that it represents.

Edges to nodes in the sub graph will changed. They will be pointed to the meta node after the sub graph is created. However, the original information about the edges is saved, so it can be restored later.

Getting created subgraph

GraphProperty* gp = input->getLocalProperty<GraphProperty*>("viewMetaNode");
Graph* subgraph = gp->getNodeValue(meta);

Restoring a sub graph to its “parent”

tlp::openMetaNode(orig, meta)

Edges connections will be restored.

Remarks

  1. The copy function (taken from GrouseFlocks):
    void copy (Graph *src, Graph *dest) {
      StableIterator <node> nodes (src->getNodes());
      while (nodes.hasNext()) dest->addNode (nodes.next());
      StableIterator <edge> edges (src->getEdges());
      while (edges.hasNext()) dest->addEdge (edges.next());
    }//end copyFeature
    
  2. Edges in a directed graph are handled nicely. Might be a problem if you only expect at most one edge for every pair of nodes (simple graph)
  3. Sub graphs can contain other sub graphs
  4. Opening a sub graph inside another sub graph may lead into a problem. Open the outer subgraph first to avoid unexpected problem.

Calling a Plugin in Tulip

After digging Tulip‘s code for several days, I still couldn’t find out how to load and run a plugin. This afternoon, my thesis project assistant sent me a working sample code that does what I want! Only in one or two days I guess. Oh God, he’s so fast!

This is how it’s done.

  1. Initialize Tulip. At least I can figure this out myself 🙂

    tlp::initTulipLib();
    tlp::loadPlugins();
    
  2. Check the existence of a plugin.

    string layoutName = "Circular";
    tlp::LayoutProperty::factory->pluginExists(layoutName);
    
  3. And this is the most important chunk of code that I’m looking for.

    tlp::LayoutProperty *myLayout = graph->getProperty<tlp::LayoutProperty>("viewLayout");
    graph->computeProperty(layoutName, myLayout, errorMsg);
    

After that, the layouting is hopefully done. We only need to iterate the vertices and get position of each vertex.

tmp1 = myLayout->getNodeValue(n);
printf("node: %d, x=%f, y=%f, z=%fn", n.id, tmp1.getX(), tmp1.getY(), tmp1.getZ());

Graf di VTK

Beberapa catatan:

  • vtkGraph itu data tentang graf. Bisa sudah pengandung informasi layout (posisi).
  • vtkGraphLayoutView itu membaca data berupa vtkGraph atau langsung dari generator seperti vtkRandomGraphSource
  • vtkGraphLayoutView itu akan menggambar graf
  • Algoritma (yg sekaligus menjadi generator) seperti vtkRandomGraphSource memiliki output berupa vtkGraph
  • vtkGraphLayout jg merupakan algoritma yg dapat mengeluarkan vtkGraph dg memanggil GetOutput()
  • vtkGraphLayout dapat menerima input berupa vtkGraph melalui SetInput()
  • Kalau memakai vtkGraphLayoutView untuk menggambar graf yang sudah memiliki layout, jangan lupa panggil SetLayoutStrategyToPassThrough() agar layout tidak dibuat ulang.

okay.. i know.. talk is cheap. so, here is the code.. http://github.com/fajran/vtk-graph-experiment/tree/master

Prefuse + Jython = Keren

English version of this post can be read at http://ngoprek.fajran.web.id/2009/07/using-prefuse-through-jython.html

Setelah semalem nyobain Jython, jadi kepikiran tuk make Prefuse dari Jython. Ternyata bisa! Utak-atik dikit lagi, dan jadilah sesuatu yg lebih menarik. Silakan lihat di screencast berikut =P

Kodingan bisa dilihat di http://gist.github.com/32288

Kalau mau nyoba:

  1. Download dan install Jython 2.5b0

    $ wget http://downloads.sourceforge.net/jython/jython_installer-2.5b0.jar
    $ java -jar jython_installer-2.5b0.jar
    

    Silakan atur sendiri lokasi instalasi.

  2. Download library prefuse.

    $ wget http://labs.fajran.web.id/p/ubuntu-pkg-vis/lib/prefuse.jar
    
  3. Atur environment variable

    $ export PATH=$PATH:/path/ke/lokasi/instalasi/jython
    $ export JYTHONPATH=$JYTHONPATH:prefuse.jar
    

    Pastikan kalo jalanin jython, muncul interactive shell-nya. Dan bisa ngejalanin yang berikut

    >>> import prefuse
    
  4. Download kodingan yg saya buat.

    $ wget -O igv.py http://gist.github.com/raw/32288/503d011d94c564ffbdca91296b3fc204cf7b5186
    
  5. Jalanin deh..

    $ jython
    >>> from igv import InteractiveGraphVisualization
    >>> ig = InteractiveGraphVisualization()
    
  6. Tambahin node dan edge

    >>> n1 = ig.add_node("satu")
    >>> n2 = ig.add_node("dua")
    >>> n3 = ig.add_node("tiga")
    >>> ig.add_edge(n1, n2)
    >>> ig.add_edge(n1, n3)
    >>> ig.add_edge(n2, n3)
    

Selamat menikmati =D

Bermain dengan graf

Tanpa basa-basi, langsung aja buka http://github.com/fajran/graph-experiment/tree/master =D

Yang sudah ada itu struktur data sangat sederhana untuk graph, node, dan edge. Selain itu, ada juga fungsi layouting dengan teknik force-directed layout dg algoritma Fruchterman Reingold yg di-port dari Prefuse.

Berhubung dibuat pakai Python dan lagi teringat pengen nyoba Jython, maka saya jg sekalian nyoba ngebandingin Python dan Jython. Jython yang dipake adalah Jython 2.5b0. Ujicoba dilakukan di atas Ubuntu 8.04 32bit, Intel Core Duo 1.83GHz, RAM 2GB, aplikasi lain yg nyala yg mungkin mempengaruhi hasil adalah Eclipse (gak dipake, lupa ditutup aja =P), Banshee, dan Firefox. Inilah hasilnya..

Edge Node Python Jython
100 93 5.348 6.421
200 171 17.403 13.945
300 234 33.011 22.798
400 294 53.674 35.107
500 358 77.672 50.576

Waahh.. pake Jython hasilnya lebih cepet euy!

Oprek2 dikit, jadilah graph plotter yg dibuat pake Python Imaging Library. Source code udah ada di repo git yg disebut di atas. Berikut ini 5 gambar dari 5 graf yg dipake di uji coba di atas.

Nyoba2 layouting di Prefuse

Bikin sesuatu yg bernama LevelLayout. Terpaksa dibikin berhubung NodeLinkTreeLayout yang diharapkan tuk bekerja ternyata tidak bekerja. Yaa.. sekalian lah.

Pake data versi lengkap tetep aja lemotubbies. Jadi bikin data versi rada kecil namun komplit. Uh, ini apa emang musti dioptimasi atau emang prefusenya aja yang dodolz?

Oya, sekarang kodingan udah ditaro juga di github. Coba diintip di http://github.com/fajran/ubuntu-pkg-vis-prefuse/tree/master