Chisio: A Compound Graph Editing and Layout Framework
Cihan Kucukkececi Ugur Dogrusoz Esat Belviranli Alptug Dilek






Chisio



Kucukkececi et al



i-Vis Research Group, Computer Eng. Dept.,

Bilkent University, Ankara 06800, Turkey


<http://www.cs.bilkent.edu.tr/ ivis/chisio>

Chisio: A Compound Graph

Editing and Layout Framework
    Cihan KucukkececiUgur DogrusozTo whom correspondence 
should be addressed (ugur@cs.bilkent.edu.tr)Esat BelviranliAlptug Dilek
    December 30, 2023
=================================================================================================================================




  We introduce a new free, open-source compound graph editing and layout framework named , based on the Eclipse Graph Editing Framework (GEF) and written in Java.  can be used as a finished graph editor with its easy-to-use graphical interface. The framework has an architecture suitable for easy customization of the tool for end-user's specific needs as well.  comes with a variety of graph layout algorithms, most supporting compound structures and non-uniform node dimensions. Furthermore, new algorithms are straightforward to add, making  an ideal test environment for layout algorithm developers. 








§ INTRODUCTION

  As graphical user interfaces have improved, and more state-of-the-art software
  tools have incorporated visual functions, interactive graph editing and 
  layout facilities have become important components of software systems. Over 
  the years, an abundant number of such tools have been made available for 
  consumption both commercially and academically <cit.>.
  However, only a
  few, if any, non-commercial systems seem to address compound structures of 
  graphs both in regards to editing and layout capabilities.  should fill 
  an important gap in this field.

   can be used as a finished graph editor and layout tool. The tool has a
  user-friendly graphical interface for interactive editing of compound graphs,
  accepting graphs in GraphML format <cit.>. It also features a number 
  of graph layout algorithms from spring embedders to Sugiyama algorithm
  for hierarchical graphs. In addition, many aspects of the tool, from graph 
  object UIs to menus to persistency operations may be easily customized for 
  specific applications.
  
	There has been a great deal of work done on general graph 
	layout <cit.> but considerably less on layout of compound graphs, 
	which is a notion that has been in use to represent more complex types of 
	relations or varying levels of abstractions in	data <cit.>. The limited
	work done on compound graph layout has mostly focused on layout of hierarchical
	graphs <cit.>, where underlying relational information is 
	assumed to be under a certain hierarchy.  provides an implementation of a
	relatively recent spring embedder based layout algorithm for undirected 
	compound graphs, with arbitrarily deep nesting relations <cit.>. In 
	addition, some other well-known layout methods have been extended to support
	compound structures in .
	
	Finally,  hosts an implementation of a new spring embedder based 
	circular layout algorithm for clustered graphs.
	



§ GRAPH AND DRAWING MODEL OF 

	 was built on top of the Eclipse Graph Editing Framework (GEF) <cit.>.
	GEF assumes that you have a model that you would like to display and edit
	graphically. The controllers bridge the view and model (Figure <ref>). 
	Each controller is responsible both for mapping the model to its view, and for
	making changes to the model. The controller also observes the model, and updates
	the view to reflect changes in the model's state. Controllers are the objects 
	with which the user interacts. 
  

	The compound graphs are modeled in  using this framework and the concept
	of graph managers described earlier (Figure <ref>). A compound 
	node manages a list of children graph objects. A dedicated one is set as the 
	root of the nesting hierarchy. Through recursive use of compound nodes as child
	objects, an arbitrary level of nesting can be created.
  

	Nodes, edges and compound nodes in  all have distinct properties and UIs,
	which can be changed by its graphical user interface or through programming.
	Each node is drawn as a rectangle, ellipse or triangle. Edges can be drawn in
	a variety of styles. Compound nodes are always drawn with a rectangle, where
	the name text is displayed on its bottom margin and its geometry is 
	auto-calculated using the geometry of its contents to tightly bound its 
	contents plus user-defined child graph margins. Figure <ref> 
	shows the basics of drawing compound graphs in .
  




§ CHISIO AS AN EDITOR

	 can be used as a finished graph editing and layout 
	tool <cit.>. Graphs created with other tools (and saved in GraphML
	format <cit.>) and loaded into  or graphs created in  can be 
	edited and laid out interactively. 
	
	The tool features standard graph editing facilities such as zoom, scroll, 
	add or remove graph objects, move, and resize. Object property and layout 
	options dialogs are provided to modify existing graph object properties and 
	layout options, respectively. In addition, printing or saving the current
	drawing as a static image and persistent storage facilities are supported.
	Furthermore, a highlight mechanism is provided to emphasize subgraphs of 
	user's interest. Figure <ref> shows a sample screen-shot of .
	Drawing in <ref> is a partial drawing produced by  for 
	a biological pathway.
  
  




§ CUSTOMIZING CHISIO

	One can customize  for their specific needs by adding new node/edge types
	or by modifying existing nodes/edges (UI and attributes) <cit.>. 
	In addition, you may customize the menus to add new functionality as well as 
	modifying node and edge menus and property inspectors. Furthermore,  is 
	designed for easy integration of new layout algorithms. Layout researchers will
	especially find  to be useful for implementation and testing of their new
	methods.
	
	A sample application based on Chisio is  (Chisio BioPAX Editor) (<http://sourceforge.net/projects/chibe/>).
	The tool features user-friendly display, viewing, and editing of pathway models
	represented by the BioPAX format (<http://biopax.org>).
	Pathway views are rendered in a feature-rich format, and may be laid out
	automatically (Figure <ref>). Among other things, visualization 
	of experimental data overlaid on pathway views is supported in .
  
	



 §.§ Layout Architecture in Chisio

	The basis in  layout is constructed through an abstract layout class 
	named  and an associated l-structure,
	classes , , , and .
	Here an  maintains and manages a list of 
	instances, which in turn maintains a list of s and s. 
	The  class converts the given  model into a generic
	l-structure used only for layout purposes that is destroyed at the end of 
	layout. Individual layout algorithms extend the  class 
	and run on this l-structure by overriding predefined methods. When the layout 
	is finished, the geometry information of the l-level is transferred to  
	model (Figure <ref>).
  




§ LAYOUT ALGORITHMS IN CHISIO

	 provides implementations of the following layout methods.
	



 §.§ CoSE Layout

	CoSE (Compound graph Spring Embedder) layout is an algorithm specifically
	designed for compound graphs <cit.>. It has been based on the 
	traditional force-directed layout scheme with extensions to handle multi-level
	nesting, varying node sizes, and possibly other application-specific 
	constraints.
	
	An expanded node and its associated nested graph are represented as a single
	entity, similar to a “cart”, which can move freely in orthogonal directions
	(no rotations allowed). Multiple levels of nesting is modeled with smaller 
	carts on top of larger ones. Figure <ref> shows an example drawing
	produced by this layout algorithm.




 §.§ Cluster Layout

	Cluster Layout is designed to place the nodes that belong to the same
	group or cluster (say to refer to molecules with similar functionality or 
	network devices in a LAN) near each other without the use of compound nodes
	(Figure <ref>). It uses CoSE layout as a subroutine to do that.




 §.§ CiSE Layout

	A popular way to draw clustered graphs is in a circular fashion. In other
	words, a circle of appropriate size is created for each cluster and the 
	nodes in that cluster are placed around this circle trying to minimize 
	edge crossings. Circular layout algorithms <cit.> 
	address the issue of placing nodes of a cluster nicely around a circle, 
	minimizing the number of edge crossing and total edge lengths. However most
	of these algorithms do not address the issue of how the cluster graph should
	be laid out (i.e. how the individual circles should be placed with respect
	to each other to minimize crossings and lengths of inter-cluster edges).
	The ones that do, can not handle non-tree structures nicely. CiSE layout 
	algorithm does not place any constraints on the structure of the cluster
	graph and tries to satisfy the following specific requirements:
	
	
  * Nodes in the same cluster should be placed around the same circle
	spaced as evenly as possible.
	
  * Unclustered nodes should not be placed on or overlapping any circles,
	but they might have neighbor nodes placed around a circle.
	
  * The number of (intra-cluster) edge crossings between the nodes in the
	same cluster should be as small as possible.
	
  * The number of (inter-cluster) edge crossings between the nodes in
	different clusters or unclustered nodes should be as small as possible.
	
  
  
  
	
	The layout algorithm is based on the spring embedder, extending it 
	for properly grouping nodes in the same cluster and placing them around a 
	circle by extra constraints. The use of extra constraints is implemented by
	introducing additional properties to the physical model used by the spring 
	embedder, trying to obey the basic laws of physics.
	
	Each cluster/circle is represented by a meta-node of circular shape, on 
	which sits a round-shaped track on the periphery. The physical entities for
	each member node of a cluster is assumed to be either fixed (restrained to
	its current location on the owner circle) or flexible to move around the 
	track on which they sit as needed by the different steps of the algorithm. 
	In addition, we assume a dynamic center of gravity in the middle of the 
	bounding rectangle of the current drawing, towards which an attractive force
	is assumed by unclustered nodes and cluster nodes (all nodes except member 
	nodes of a cluster).

	Following are the main steps of the algorithm:
	
	
  * Step 1: In this step, we run a basic circular layout <cit.>
	for each cluster. 
	
  * Step 2: Next we layout the cluster graph, where each node in the
	graph represent a cluster with the dimensions produced in Step 1, using a
	basic spring embedder. 
	
  * Step 3: Here, our aim is to reposition/rotate circles according
	to the location of their out-nodes and inter-cluster edges incident on 
	these nodes. However, nodes on the circles are not allowed to move 
	individually. They are assumed to be pinned down to their circles. After 
	this step, a draft layout of the whole graph is obtained. 
	
  * Step 4: In this final polishing step, we obtain the final layout 
	of the graph by trying to reduce inter-cluster edge crossing. The main
	difference between this step and Step 3 is that we allow nodes on circles to 
	move on their parent circle (as well as moving with them).
	

	 features a draft-implementation of this algorithm and
	Figure <ref> shows a sample drawing produced by this algorithm.




 §.§ Others

	 also provides implementations for a regular spring embedder <cit.>, 
	a hierarchical layout method <cit.>, and a circular layout
	algorithm <cit.>.
	



§ CONCLUSION

	In this paper we have presented a new open-source, free compound graph editing 
	and layout tool, distributed under Eclipse Public License.  version 1 is
	available at <http://www.cs.bilkent.edu.tr/ ivis/chisio.html>.


abbrv

