edu.neu.ccs.demeter.aplib
Class TraversalGraph

java.lang.Object
  |
  +--edu.neu.ccs.demeter.aplib.Traversal
        |
        +--edu.neu.ccs.demeter.aplib.TraversalGraph

public class TraversalGraph

extends Traversal

A traversal graph TG(S,G,N,B) is constructed from an encapsulated strategy S, a class graph G, a name map N for S and G, and a constraint map B for S and G according to a modified version of Algorithm 1 in the paper "Traversals of Object Structures: Specification and Efficient Implementation" (the modifications allow G to be non-simple and N to be a relation instead of a function). TG is essentially a compilation (that is, a compact and efficient generator) of the set of paths through G that is selected by S. Conceptually, TG(S,G,N,B) consists of a graph G'' and a set T_s of start nodes in G'', where G'' is (a subset of) n copies of G, where n is the number of edges in S, with some extra edges to connect nodes in different copies. However, to keep the representation more compact, G'' is represented as two sets, NS and ES:

• NS is a set of pairs (v, IS) where v is a node in G and IS is a set of indices i such that vⁱ is in G''.
• ES is a set of pairs (u -l-> v, IM) where u -l-> v is an edge in G and IM is a set of pairs of indices (i,j) such that uⁱ -l-> v^j is in G''.

Nested Class Summary

class	TraversalGraph.EdgeSet A set of edges u^i -l-> v^j in a traversal graph, where the edges in the set are all copies of the same class graph edge u -l-> v with different endpoint indices i and j.
class	TraversalGraph.IndexPair A pair of indices, representing the copy indices on the source and target of an edge in the traversal graph.
class	TraversalGraph.NodeSet A set of nodes vi in a traversal graph, where the nodes in the set are all copies of the same class graph node v with different indices i.

Nested classes inherited from class edu.neu.ccs.demeter.aplib.Traversal

Field Summary

static boolean

debug Set this for debugging output.

Constructor Summary

TraversalGraph(SimpleStrategyI S, ClassGraphI G)
Compute the traversal graph TG(S,G,I,B_TRUE) and start and finish sets T_s and T_f, where I is the identity map and B_TRUE returns true for all graph elements.

TraversalGraph(SimpleStrategyI S, ClassGraphI G, NameMapI N, ConstraintMapI B)
Compute the traversal graph TG(S,G,N,B) and start and finish sets T_s and T_f.

Method Summary

ConstraintMapI	getConstraintMap() The constraint map B for S and G used in computing this traversal graph.
Traversal.EdgeSet	getEdgeSet(String key) The set of copies of the class graph edge with the given key in the traversal graph, or null if there are none.
List	getEdgeSets() An unmodifiable list of EdgeSet objects representing the edges in the traversal graph.
List	getFinishSet() An unmodifiable List of NodeSet objects representing the finish set of the traversal (Tf).
Traversal.NodeSet	getFinishSet(Object v) A NodeSet representing the finish set of tokens (indices) for the class graph node v, or null if v has no finish tokens in the traversal.
NameMapI	getNameMap() The name map N for S and G used in computing this traversal graph.
Traversal.NodeSet	getNodeSet(Object v) The set of copies of class graph node v in the traversal graph, or null if there are none.
List	getNodeSets() An unmodifiable list of NodeSet objects representing the nodes in the traversal graph.
List	getStartSet() An unmodifiable List of NodeSet objects representing the start set of the traversal (Ts).
Traversal.NodeSet	getStartSet(Object v) A NodeSet representing the start set of tokens (indices) for the class graph node v, or null if v has no start tokens in the traversal.
SimpleStrategyI	getStrategy() The strategy S used in computing this traversal graph.
String	toString() A string representation of the graph.

Methods inherited from class edu.neu.ccs.demeter.aplib.Traversal

compute, compute, edgeKey, getAlternationEdgeSet, getClassGraph, getConstructionEdgeSet, getEdgeSet, getInheritanceEdgeSet, getVersion, intersect, toCompactString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

debug

public static boolean debug

Set this for debugging output.

Constructor Detail

TraversalGraph

public TraversalGraph(SimpleStrategyI S,
                      ClassGraphI G)
               throws TraversalException

Compute the traversal graph TG(S,G,I,B_TRUE) and start and finish sets T_s and T_f, where I is the identity map and B_TRUE returns true for all graph elements.

Throws:

TraversalException - if the resulting traversal graph is empty.

TraversalGraph

public TraversalGraph(SimpleStrategyI S,
                      ClassGraphI G,
                      NameMapI N,
                      ConstraintMapI B)
               throws TraversalException

Compute the traversal graph TG(S,G,N,B) and start and finish sets T_s and T_f. If N is null, the default name map is used (the identity map). If B is null, the default constraint map is used (B_TRUE, which returns true for all graph elements). B is conjoined with the constraint map B' specified by the encapsulated strategy S; that is, an element e of G is allowed in TG iff both B(i)(e) and B'(i)(e) are true.

Throws:

TraversalException - if:

• N maps symbolic node names in S to nodes that don't exist in G; or
• TG(S,G,N,B) is empty.

Method Detail

getStrategy

public SimpleStrategyI getStrategy()

The strategy S used in computing this traversal graph.

getNameMap

public NameMapI getNameMap()

The name map N for S and G used in computing this traversal graph.

getConstraintMap

public ConstraintMapI getConstraintMap()

The constraint map B for S and G used in computing this traversal graph.

getNodeSets

public List getNodeSets()

An unmodifiable list of NodeSet objects representing the nodes in the traversal graph.

Specified by:

getNodeSets in class Traversal

See Also:

TraversalGraph.NodeSet

getNodeSet

public Traversal.NodeSet getNodeSet(Object v)

The set of copies of class graph node v in the traversal graph, or null if there are none.

Specified by:

getNodeSet in class Traversal

getEdgeSets

public List getEdgeSets()

An unmodifiable list of EdgeSet objects representing the edges in the traversal graph.

Specified by:

getEdgeSets in class Traversal

See Also:

TraversalGraph.EdgeSet

getEdgeSet

public Traversal.EdgeSet getEdgeSet(String key)

The set of copies of the class graph edge with the given key in the traversal graph, or null if there are none.

Specified by:

getEdgeSet in class Traversal

getStartSet

public List getStartSet()

Description copied from class: Traversal

An unmodifiable List of NodeSet objects representing the start set of the traversal (T_s).

Specified by:

getStartSet in class Traversal

getStartSet

public Traversal.NodeSet getStartSet(Object v)

Description copied from class: Traversal

A NodeSet representing the start set of tokens (indices) for the class graph node v, or null if v has no start tokens in the traversal.

Specified by:

getStartSet in class Traversal

getFinishSet

public List getFinishSet()

Description copied from class: Traversal

An unmodifiable List of NodeSet objects representing the finish set of the traversal (T_f).

Specified by:

getFinishSet in class Traversal

getFinishSet

public Traversal.NodeSet getFinishSet(Object v)

Description copied from class: Traversal

A NodeSet representing the finish set of tokens (indices) for the class graph node v, or null if v has no finish tokens in the traversal.

Specified by:

getFinishSet in class Traversal

toString

public String toString()

A string representation of the graph. Print nodes and edges in each copy of the graph, along with edges between copies.

Overrides:

toString in class Object