Table of Contents
The Tensegrity Graph Framework has been engineered for the creation, manipulation and visualization of graphs. This chapter therefore begins with an explanation of graph theory and provides you with the terms used in the graph domain.
Three major collaborators for a graph visualization must be created and connected to each other: A model, a view, and a controller. These MVC pattern roles will be explained in this chapter in more detail along with our special implementations.
A Graph is used to visualize relationships among different entities.
Organizational charts (orgcharts), workflows and network topologies are
typical domains which require graph visualization software.
A Graph consists of nodes and edges. A Node is something that would be
represented by an employee in an orgchart while an Edge would represent the
relationship between two employees, for example by showing that one employee
is the team leader of another.
A graph is therefore a "container" entity consisting of nodes
and edges. A Node (or vertex) is part of a set of vertices of the Graph.
Additionally, a Graph consists of a set of edges which describe how the
nodes (or vertices) are connected to each other.
A graph is formally defined as:
A set of vertices (nodes [1]) V.
A set of edges E.
Each Edge is a pair (V1,V2), where V1 and V2 denote distinct
vertices that are both elements of V.
All elements of V and E must be unique as required by sets in the mathematical sense.
The Graph class in the Tensegrity API represents this mathematical data and is often
referred to as the “model.” This non-visual component can be used
on its own for applying graph algorithms and deriving specialized graph classes.
When discussing graphs, we usually distinguish between directed and undirected
graphs. In a directed graph, all edges have a direction or orientation, while an
undirected graph has edges with no orientation. Both directed and undirected
graphs are represented by classes which implement the Graph interface.
A directed graph imposes an order on the two nodes that make up an edge. This order can be interpreted as a direction, where the first node of an edge denotes the source node and the second node of an edge denotes the target node. This implies that the edge (N1, N2) of a directed graph (or short: digraph) only defines that N2 is reachable from N1, but not vice versa.
Undirected graphs impose no order on the two vertices of an edge (V1, V2) . V1 is reachable from V2 and V2 is also reachable from V1.
A path in a Graph is a non-empty sequence of edges.
Formally, it is defined as a sequence of edges of length >= 1.
Parts of a Graph G that are not connected to each other
by a path are called connected-components of
G.
There are other types of graphs, especially so-called multi-graphs, which
are allowed to have the same Edge multiple times, thus allowing the same element
to appear more than once in the set E. From a mathematical
point of view, this would make E a vector rather than a set.
Graph types can be classified based on a number of other criteria:
A Planar Graph is a Graph that can be drawn in
the 2-dimensional plane without any crossings. Edges are allowed to
be polylines and are not restricted to straight lines.
A Complete Graph is a graph where every Node has
an edge to every other Node The upper bound for the number of
edges in a complete graph is |V| * |V|.
The Transitive Hull of a Graph is another Graph where
an Edge exists for every pair of nodes (V1, V2) that is
reachable by a path.
A Strongly-Connected Graph is a Graph where all
nodes can reach each other by paths.
An n-Connected Graph is a Graph whereby removing
n nodes and all edges connecting them does not cause
the Graph to collapse into several connected components.
One of the principal features of the Tensegrity Graph Framework is the automatic visualization of graphs and their visual editing. While graphs consist primarily of nodes and edges, these are model aspects only. A visualization or rendering is not a mathematical requirement.
The subject of graph visualization is a hot topic in computer science and is being actively developed by researchers around the world. Many algorithms for drawing graphs exist and are often limited to special kinds of graphs. By restricting the types of a graphs drawn, however, it usually simplifies the the application of specialized drawing algorithms.
[1]
In the Tensegrity API, a vertex is consistently called a Node
and a Graph is usually referred to as the “model”.
© 2004, 2005 Tensegrity Software GmbH