net.xqhs.graphs.representation.linear
Class LinearGraphRepresentation

java.lang.Object
  extended by net.xqhs.util.config.Config
      extended by net.xqhs.util.logging.Unit
          extended by net.xqhs.graphs.representation.GraphRepresentationImplementation
              extended by net.xqhs.graphs.representation.linear.LinearGraphRepresentation
All Implemented Interfaces:
GraphRepresentation, net.xqhs.util.config.Configurable
Direct Known Subclasses:
GraphicalGraphRepresentation, TextGraphRepresentation

public abstract class LinearGraphRepresentation
extends GraphRepresentationImplementation

Class that allows the representation of a Graph structure.

An instance remains associated with the same Graph instance for all of its lifecycle.

The linearization process works by creating a series of 'paths'. A path is a tree covering part of the graph. Each path attempts to cover as many nodes as possible (ideally all the nodes in a weakly-connected component of the graph). All the edges in the graph are then part of a path, cross between paths, or go from one node in the path to another, without being part of the path. Ideally, most of the edges are on a path and few other edges remain outside paths.

The result of the linearization is the set of paths, which are formed of PathElement instances.

The result of a linearization is always the same for the same graph.

The class is abstract because it does not provide a viewable representation, but rather a structure which other representations may use (e.g. the linear text representation).

Author:
Andrei Olaru

Nested Class Summary
(package private) static class LinearGraphRepresentation.NodeInAlphaComparator
          Compares two Node structures.
(package private) static class LinearGraphRepresentation.PathComparator
          A Comparator for PathElement instances that sorts the element with the longer distance to a leaf first.
 
Nested classes/interfaces inherited from class net.xqhs.util.config.Config
net.xqhs.util.config.Config.ConfigLockedException
 
Field Summary
protected  boolean isBackwards
          Specifies how paths should relate to the direction of edges on the path.
protected  java.util.List<PathElement> paths
          The paths in the representation (sorted by a LinearGraphRepresentation.PathComparator).
protected  java.util.List<Node> sortedNodes
          The nodes of the graph, as sorted by a LinearGraphRepresentation.NodeInAlphaComparator.
 
Fields inherited from class net.xqhs.graphs.representation.GraphRepresentationImplementation
parentRepresentation, theGraph, theRepresentation
 
Fields inherited from class net.xqhs.util.logging.Unit
DEFAULT_LEVEL, DEFAULT_UNIT_NAME
 
Constructor Summary
LinearGraphRepresentation(Graph graph)
          Builds a new LinearGraphRepresentation for the specified graph.
 
Method Summary
protected  void buildPaths()
          Building paths has two phases.
 boolean isBackwards()
          Returns the 'backwards' state of the representation.
protected  void processGraph()
          Processing the graph actually relies on building the paths, after obtaining a sorted list of the nodes in the graph (using LinearGraphRepresentation.NodeInAlphaComparator).
 LinearGraphRepresentation setBackwards()
          Sets the instance to be 'backwards'.
 LinearGraphRepresentation setBackwards(boolean back)
          Specifies how paths should relate to the direction of edges on the path.
protected  java.lang.String setDefaultName(java.lang.String name)
          This can be overridden by other representations to produce the correct suffix.
 
Methods inherited from class net.xqhs.graphs.representation.GraphRepresentationImplementation
displayRepresentation, getRepresentation, getRootRepresentation, setParentRepresentation, setUnitName, update
 
Methods inherited from class net.xqhs.util.logging.Unit
compose, dbg, doExit, getDefaultUnitName, getUnitName, l, le, lf, li, lock, lockedR, lr, lr, lw, setLink, setLink, setLogDisplay, setLogEnsureNew, setLoggerClass, setLoggerType, setLoggerTypeClass, setLogLevel, setLogReporter, setUnitName
 
Methods inherited from class net.xqhs.util.config.Config
build, ensureLocked, locked, lockedEx, makeDefaults
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

isBackwards

protected boolean isBackwards
Specifies how paths should relate to the direction of edges on the path. See the documentation of method setBackwards().


sortedNodes

protected java.util.List<Node> sortedNodes
The nodes of the graph, as sorted by a LinearGraphRepresentation.NodeInAlphaComparator.


paths

protected java.util.List<PathElement> paths
The paths in the representation (sorted by a LinearGraphRepresentation.PathComparator). These represent the output of this representation, to be used by other non-abstract representations.

Constructor Detail

LinearGraphRepresentation

public LinearGraphRepresentation(Graph graph)
Builds a new LinearGraphRepresentation for the specified graph.

Parameters:
graph - : the graph
Method Detail

setBackwards

public LinearGraphRepresentation setBackwards()
Sets the instance to be 'backwards'. See setBackwards(boolean).

Returns:
the updated instance.

setBackwards

public LinearGraphRepresentation setBackwards(boolean back)
Specifies how paths should relate to the direction of edges on the path. If false ('forward'), the paths follow the direction of edges. If true ('backwards'), the path will follow in the opposite direction of edges.

Example of a forward path: a -> b -> c

Example of a backward path: a <- b <- c (with the equivalent forward path c -> b -> a).

The choice of this setting depends on the purpose of the representation. For instance, if the edges mean 'flows-to', the representation should be 'forward'. If the edges mean 'has-parent', a 'backward' representation may be more suitable.

Parameters:
back - : specifies whether the representation should be 'backward'.
Returns:
the updated instance.

isBackwards

public boolean isBackwards()
Returns the 'backwards' state of the representation. See setBackwards(boolean).

Returns:
true if the representation is 'backwards'.

setDefaultName

protected java.lang.String setDefaultName(java.lang.String name)
Description copied from class: GraphRepresentationImplementation
This can be overridden by other representations to produce the correct suffix.

Overrides:
setDefaultName in class GraphRepresentationImplementation
Parameters:
name - : the name of the graph's unit.
Returns:
the name of the representation

processGraph

protected void processGraph()
Processing the graph actually relies on building the paths, after obtaining a sorted list of the nodes in the graph (using LinearGraphRepresentation.NodeInAlphaComparator). See buildPaths().

Overrides:
processGraph in class GraphRepresentationImplementation

buildPaths

protected void buildPaths()
Building paths has two phases.

Phase 1

First, the paths are decided (it is decide what edges are on the paths and in what order). The first node on the path is the first node in the sorted list of nodes not explored so far (white node). Then, children of the node (at the end of outgoing edges if forward or incoming edges if backward, anyway edges that belong to the graph) are inspected: "new" children (white) are added as new, child, path elements (nodes outside the graph at the end of edges inside the graph are added as "other children"), and others are added as "other children": edges that point back in the current path from root - circular; edges that point to nodes already somewhere else in the path - other branches. If the paths reaches a node through with a longer distance (depth) than before, the node is shifted on the current path.

Then, paths are 'measured' and forwardLength information is computed (for each path element, the longest distance to a leaf).

In the third phase, forward lengths are used to switch elements from paths with lower forward lengths to paths with higher ones, in order to be sure that longer paths come first. All paths are then sorted using LinearGraphRepresentation.PathComparator.