|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnet.xqhs.util.config.Config
net.xqhs.util.logging.Unit
net.xqhs.graphs.representation.GraphRepresentationImplementation
net.xqhs.graphs.representation.linear.LinearGraphRepresentation
public abstract class LinearGraphRepresentation
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).
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 |
---|
protected boolean isBackwards
setBackwards()
.
protected java.util.List<Node> sortedNodes
LinearGraphRepresentation.NodeInAlphaComparator
.
protected java.util.List<PathElement> paths
LinearGraphRepresentation.PathComparator
). These represent the output of this
representation, to be used by other non-abstract representations.
Constructor Detail |
---|
public LinearGraphRepresentation(Graph graph)
LinearGraphRepresentation
for the specified graph.
graph
- : the graphMethod Detail |
---|
public LinearGraphRepresentation setBackwards()
setBackwards(boolean)
.
public LinearGraphRepresentation setBackwards(boolean back)
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.
back
- : specifies whether the representation should be 'backward'.
public boolean isBackwards()
setBackwards(boolean)
.
true
if the representation is 'backwards'.protected java.lang.String setDefaultName(java.lang.String name)
GraphRepresentationImplementation
setDefaultName
in class GraphRepresentationImplementation
name
- : the name of the graph's unit.
protected void processGraph()
LinearGraphRepresentation.NodeInAlphaComparator
). See buildPaths()
.
processGraph
in class GraphRepresentationImplementation
protected void buildPaths()
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
.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |