net.xqhs.graphs.representation.text
Class TextGraphRepresentation

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
                  extended by net.xqhs.graphs.representation.text.TextGraphRepresentation
All Implemented Interfaces:
GraphRepresentation, net.xqhs.util.config.Configurable

public class TextGraphRepresentation
extends LinearGraphRepresentation

The class implements GraphRepresentation to create (or read from) a textual representation of a graph. For creating the representation, it relies on LinearGraphRepresentation.

The created (or read) representation contains a single occurrence of each edge and a number of occurrences of each node equal to its in-degree (except for the 'root' node of each connected subgraph).

Using the default values for symbols (see TextRepresentationElement.Symbol), below are some representations of simple graphs:

A 'backwards' representation is also possible, that may be adequate for some cases. Example:
A (<-inherits-from- B <-inherits-from- C) <-inherits-from- D.

For more details on the output and input formats, see displayRepresentation() and readRepresentation(String).

While the representation has been mentioned in previous works, the main publication that presents it is: Andrei Olaru, Context Matching for Ambient Intelligence Applications, Proceedings of SYNASC 2013, 15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, September 23-26, 2013 Timisoara, Romania, IEEE CPS, 2013.

Author:
Andrei Olaru

Nested Class Summary
 
Nested classes/interfaces inherited from class net.xqhs.util.config.Config
net.xqhs.util.config.Config.ConfigLockedException
 
Field Summary
static java.lang.String DEFAULT_BRANCH_SEPARATOR
          The default branch separator.
static int DEFAULT_INCREMENT_LIMIT
          The default increment limit.
static java.lang.String DEFAULT_SEPARATOR_INCREMENT
          The default separator increment.
protected  int incrementLimit
          Increment limit.
protected  java.lang.String indent
          Branch separator.
protected  java.lang.String indentIncrement
          Separator increment.
 
Fields inherited from class net.xqhs.graphs.representation.linear.LinearGraphRepresentation
isBackwards, paths, sortedNodes
 
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
TextGraphRepresentation(Graph graph)
          Creates a new instance and links it to the specified graph.
 
Method Summary
protected  Graph buildGraph(TextRepresentationElement rootRepresentation)
          Based on the representation elements read from the input, the method assembles the represented graph.
protected  java.util.List<TextRepresentationElement> buildTextChildren(PathElement el, int level, java.util.Set<PathElement> blackNodes)
          Explores the children of the given path element, to create the list of corresponding representation elements.
 java.lang.String displayRepresentation()
          Returns a text representation of the associated graph.
 RepresentationElement getRepresentation()
          Gets the root element of the representation.
 boolean isBackwards()
          Returns the 'backwards' state of the representation.
protected  void processGraph()
          The method relies on a call of buildPaths() in LinearGraphRepresentation.
 Graph readRepresentation(ContentHolder<java.lang.String> input)
          Same as readRepresentation(String), but taking the input from a ContentHolder, leaving any un-consumed input in the holder.
 Graph readRepresentation(java.io.InputStream stream)
          Reads the elements in the input into the represented graph.
 Graph readRepresentation(java.lang.String rawInput)
          Reads the elements in the input into the represented graph.
protected  java.lang.String setDefaultName(java.lang.String name)
          This can be overridden by other representations to produce the correct suffix.
 TextGraphRepresentation setLayout(java.lang.String branchSeparator, java.lang.String separatorIncrement, int limit)
          Configures the presentation of the linear graph representation.
 java.lang.String toString()
          See displayRepresentation().
 
Methods inherited from class net.xqhs.graphs.representation.linear.LinearGraphRepresentation
buildPaths, setBackwards, setBackwards
 
Methods inherited from class net.xqhs.graphs.representation.GraphRepresentationImplementation
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, wait, wait, wait
 

Field Detail

DEFAULT_BRANCH_SEPARATOR

public static final java.lang.String DEFAULT_BRANCH_SEPARATOR
The default branch separator.

See Also:
Constant Field Values

DEFAULT_SEPARATOR_INCREMENT

public static final java.lang.String DEFAULT_SEPARATOR_INCREMENT
The default separator increment.

See Also:
Constant Field Values

DEFAULT_INCREMENT_LIMIT

public static final int DEFAULT_INCREMENT_LIMIT
The default increment limit.

See Also:
Constant Field Values

indent

protected java.lang.String indent
Branch separator. See setLayout(String, String, int).


indentIncrement

protected java.lang.String indentIncrement
Separator increment. See setLayout(String, String, int).


incrementLimit

protected int incrementLimit
Increment limit. See setLayout(String, String, int).

Constructor Detail

TextGraphRepresentation

public TextGraphRepresentation(Graph graph)
Creates a new instance and links it to the specified graph. No processing will occur until GraphRepresentationImplementation.update() is called.

Parameters:
graph - - the Graph instance that will be linked to this representation.
Method Detail

setLayout

public TextGraphRepresentation setLayout(java.lang.String branchSeparator,
                                         java.lang.String separatorIncrement,
                                         int limit)
Configures the presentation of the linear graph representation. More precisely, configures what happens in the output when a branch appears. See parameter descriptions for more details.

Parameters:
branchSeparator - - is added before each branch. Usually it is a newline.
separatorIncrement - - d increments are added after the separator, where d is the depth of the parent node. Usually it is a tabbing string.
limit - - the use of separator and increment are limited to a depth specified by this parameter. Use 0 so that no separation will occur. Use -1 to not limit the separation.
Returns:
the LinearGraphRepresentation instance, for chained calls.

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 LinearGraphRepresentation
Parameters:
name - : the name of the graph's unit.
Returns:
the name of the representation

processGraph

protected void processGraph()
The method relies on a call of buildPaths() in LinearGraphRepresentation. After the paths are built, they are explored depth-first to directly build the text representation.

Overrides:
processGraph in class LinearGraphRepresentation

buildTextChildren

protected java.util.List<TextRepresentationElement> buildTextChildren(PathElement el,
                                                                      int level,
                                                                      java.util.Set<PathElement> blackNodes)
Explores the children of the given path element, to create the list of corresponding representation elements. It recurses to completely explore the paths that start from the children.

Parameters:
el - - the element whose children to explore.
level - - the current recursion level (starts at 1).
blackNodes - - the set that contains the visited nodes, to which the method adds nodes that it visits.
Returns:
a List of TextRepresentationElement instances that correspond to the children of the explored element.

toString

public java.lang.String toString()
See displayRepresentation().

Overrides:
toString in class java.lang.Object

getRepresentation

public RepresentationElement getRepresentation()
Description copied from interface: GraphRepresentation
Gets the root element of the representation.

Specified by:
getRepresentation in interface GraphRepresentation
Specified by:
getRepresentation in class GraphRepresentationImplementation
Returns:
the root RepresentationElement instance.

isBackwards

public boolean isBackwards()
Description copied from class: LinearGraphRepresentation
Returns the 'backwards' state of the representation. See LinearGraphRepresentation.setBackwards(boolean).

Overrides:
isBackwards in class LinearGraphRepresentation
Returns:
true if the representation is 'backwards'.

displayRepresentation

public java.lang.String displayRepresentation()
Returns a text representation of the associated graph.

The representation uses the text-representations of the nodes (obtained by Node#toString()) and edges (obtained by Edge.getLabel()), and a few special symbols present in TextRepresentationElement.Symbol. By default, parentheses for branches (the last branch of a node is not surrounded by parentheses) and "*" to refer nodes that have already appeared in the representation earlier. Also, "^" for nodes outside the (sub)graph.

Example: a graph that is a triangle ABC with one other edge BD will be represented as (edges are not labeled):
A->B(->D)->C->*A
That is, there is a cycle A-B-C-A, and also there is also a branch from B to D.

The representation can be customized with the parameters set in setLayout(String, String, int).

If the graph is meant to be printed on several lines (branchSeparator) contains a new line, an additional branchSeparator will be added before the representation.

Specified by:
displayRepresentation in interface GraphRepresentation
Specified by:
displayRepresentation in class GraphRepresentationImplementation
Returns:
the representation of the graph.

readRepresentation

public Graph readRepresentation(java.io.InputStream stream)
Reads the elements in the input into the represented graph. See readRepresentation(String).

Parameters:
stream - - the input stream.
Returns:
the graph instance.

readRepresentation

public Graph readRepresentation(java.lang.String rawInput)
Reads the elements in the input into the represented graph. The representation must resemble one produced by method toString() of this class, but only in syntax, and not necessarily with the same whitespace settings. The rules below are given in general terms, using the constants in TextRepresentationElement.Symbol, and have in parentheses the equivalent strings, using the default symbols. All elements are attached to the existing elements in the represented graph, if any.

Parameters:
rawInput - - the input string.
Returns:
the graph instance.
Throws:
java.lang.IllegalArgumentException - if the input is broken (referenced nodes not found, no target nodes for edges, etc.

readRepresentation

public Graph readRepresentation(ContentHolder<java.lang.String> input)
Same as readRepresentation(String), but taking the input from a ContentHolder, leaving any un-consumed input in the holder.

Parameters:
input - - the input, held be a ContentHolder instance.
Returns:
the graph instance.
Throws:
java.lang.IllegalArgumentException - if the input is broken (referenced nodes not found, no target nodes for edges, etc.

buildGraph

protected Graph buildGraph(TextRepresentationElement rootRepresentation)
Based on the representation elements read from the input, the method assembles the represented graph.

Parameters:
rootRepresentation - - the root TextRepresentationElement of the representation (normally same as #theRepresentation).
Returns:
the built Graph.