Overview of LSEdit

A higraph is a graph containing nodes and edges in which nodes may themselves contain nodes, and edges may connect any two nodes, irrespective of where these nodes are located within the graph. Nodes and edges are often referred to as entities and relations.

LSEdit is a graph visualization tool that is particularly suited to viewing, exploring and editing very large higraphs. Possible applications include visualisation of source code, examination of dumps of data memory structures, exploration of database contents, etc. LSEdit strives to use a very small memory footprint and as a consequence can manage very large graphs, directly within main memory.

In LSEdit each viewed higraph has an associated schema. This schema identifies the types of node and edge classes which are supported within the higraph, and provides a specification for which node types may legitimately be connected through which types of edge. While LSEdit imposes no requirement that the higraph conforms to this specification, it does permit violations of the schema specification to be detected.

Classes, nodes and edges have attributes associated with them. Each attribute has a name, and potentially a value. Structure such as a list of values may be encoded within this value. The schema provides the ability both to assign default values to attributes, and to specify which attribute values may legitimately be associated with which nodes and edges. Some attributes convey explicit information to LSEdit regarding such diverse information as node positions, color, name, description, icon, etc. Edges may have an attribute label and description associated with them, as well as instructions regarding how the edge and its label is to be visually presented. Nodes, edges and classes may multiply inherit from other classes, and these inheritance rules are employed in discovering the logical attribute value of attributes not explicitly present in nodes and edges.

The higraph and the schema may both be edited by LSEdit. Nodes may be added, deleted, relocated or resized, and edges may be added or deleted. The class nodes and edges belong to may also be changed. Within the schema new classes may be defined, old classes deleted, inheritance heirarchies changed, and schema constraints modified. Attributes can be viewed, added, deleted or modified within nodes, edges, and node and edge classes. In addition the position where edges leave source nodes and arrive at destination nodes is adjustable, either by node, or by class.

All changes to the higraph and schema are recorded in an undo history, and the state of LSEdit can be returned to any arbitrary point anywhere within this undo history. LSEdit's state may be saved to disk as deemed appropriate. Since some operations may require a history involving massive numbers of changes, this history of changes can be enabled, disabled and cleared as deemed appropriate.

Any visible node may be presented as open, revealing the nodes and edges contained within them, or as closed eliding this information. When closed edges entering such nodes may be lifted so that this closed node becomes the visual destination for such edges, while edges leaving such nodes may be lifted so that this closed node becomes the visual source for such edges. Actual cardinalities of the number of edges visually having a node as its source or destination, may be presented for each edge type.

The higraph may be navigated either directly; through a separate view that provides a tree view of the hierarchy of nodes contained within other nodes; through a further view which shows the route back to the root; by node search; or by hyperlinking to nodes cited in reports produced by LSEdit. A trace of all nodes visited is maintained, and one may also either step through this trace, or navigate to an arbitrary node within it.

In addition to the main higraph being viewed, LSEdit will optionally show nodes that are deemed clients of this higraph, in that they have at least one edge from them to a node in the higraph, and suppliers, which have at least one edge to them from the higraph. Such suppliers may potentially also be clients. Excluded from the definition of clients and suppliers are ancestors of the higraph being viewed. Clients are normally optionally shown as a list of nodes above the higraph, and suppliers optionally as a similar list of nodes below the higraph. In addition to the appropriate edges shown within the graph edges will also be shown to such clients and suppliers. When the number of clients/suppliers makes visualisation of individual clients and suppliers problematic, these nodes can be visually compacted by showing not necessarily the actual clients and suppliers themselves, but rather ancestor nodes of such clients and suppliers.

Collections of nodes contained within a common node may be identified and automated layout algorithms employed to lay these nodes out in a variety of ways. More generally clustering algorithms may be used to restructure nodes under new node containers, in a variety of ways. Statistics about the shape of a higraph both before and after such clustering can be obtained, and selective redistribution of nodes between clusters performed post clustering. Since the graph is highly editable, layout and clustering operations may also be performed manually.

Run time commands can be constructed which use the attribute values of nodes as optional parameters to these commands. This permits very general coupling of nodes and edges with external operations. For example, when a graph which shows source code architecture, commands may be constructed which permits nodes to be associated with source code and line number and for this source code to be viewed and potentially editted.

Nodes and edges can be shown or hidden by class, and edges can be shown or hidden by the way they interact with nodes. In addition edges can be hidden on the grounds that they are of a certain type, and interact with nodes of a certain type in a certain way. The recognised interactions are that the node is the source of the edge; the destination of the edge; one through which the edge enters into the subgraph contained within this node; one through which it exits; or one entirely contained in or under this node. Such elision of edges may be performed by node and relation class, by node or relation class, or by individual selected node. Elided edges are shown as short stubs. The elision rules currently associated with every visible node can rapidly be determined for any given edge class, by using icons which schematically show permitted interactions with this node for the given class of edge.

A number of basic query capabilities exist to trace according to a given set of edges, and specific rules regarding the to be perceived direction of the edge (if any) the paths forwards or backwards from any node or any collection of nodes that share a common parent. Tracing may be performed for 1 or more steps. Root cause analysis may also be performed, which involves discovery of nodes that lie not on a path from a single node, but on nodes which lie on paths from all selected nodes. When querying for such paths only edges participating in the trace are shown. Optionally nodes connected through such a path trace can be temporarily hidden. The paths so discovered as a consequence of performing a path trace, are separately described in the results tab box, and nodes can be navigated to via hyperlinks within this report.

In some applications there either is no well defined logical containment hierarchy, or alternatively there are several alternative candidates. LSEdit permits containment hierarchies to be constructed dynamically from a prioritized list of edge types. This provides a great deal of flexibility regarding how graphs may be presented within LSEdit. In some applications there is a desire to obtain data directly from third party sources such as databases. The architecture of LSEdit permits it to be wrapped under custom java code that will extract data from any desired source given the necesssary code is developed. Documentation on any command reachable from a menu item, or tool button can be obtained directly by right clicking on that menu item/tool button. The browser used to view such external document is configurable, as are all the fonts used within LSEdit. More generally documentation on LSEdit, and the LSEdit source code publically available for download can be found at www.swag.uwaterloo.ca/lsedit/index.html.

Contact information