net.xqhs.graphs.matchingPlatform
Class TrackingGraph

java.lang.Object
  extended by net.xqhs.util.config.Config
      extended by net.xqhs.util.logging.Unit
          extended by net.xqhs.graphs.graph.SimpleGraph
              extended by net.xqhs.graphs.matchingPlatform.TrackingGraph
All Implemented Interfaces:
Graph, net.xqhs.util.config.Configurable
Direct Known Subclasses:
GMPImplementation.PrincipalGraph

public class TrackingGraph
extends SimpleGraph

The class implements a graph that applies changes incrementally, allowing their controlled propagation. Changes are represented as TrackingGraph.Transaction instances, representing a single or multiple changes per transaction.

There are two uses of the class -- as 'master' and 'shadow':

An instance that is the master of a set of shadows can as well be a shadow itself.

A shadow graph can never be modified directly, only by taking transactions from its master's transaction queue.

Author:
Andrei Olaru

Nested Class Summary
static class TrackingGraph.Operation
          Types of operations on graphs available.
static class TrackingGraph.Transaction
          The class contains information on one or more changes (operations) to apply to a graph.
 
Nested classes/interfaces inherited from class net.xqhs.graphs.graph.SimpleGraph
SimpleGraph.NodeData
 
Nested classes/interfaces inherited from class net.xqhs.util.config.Config
net.xqhs.util.config.Config.ConfigLockedException
 
Field Summary
protected  java.util.List<TrackingGraph.Transaction> history
          If required by keepHistory, the history of all transactions.
protected  boolean isShadow
          true if the graph is a shadow graph, false if it is not the shadow of any other graph.
protected  boolean keepHistory
          true if a history should be kept of all performed transactions.
protected  java.util.concurrent.atomic.AtomicInteger sequence
          The current sequence of the graph.
protected  java.util.List<java.util.Queue<TrackingGraph.Transaction>> shadowQueues
          The set of transaction queues for the shadow graphs of this graph.
protected  java.util.Queue<TrackingGraph.Transaction> transactionQueue
          Only for shadow graphs, the Queue of transactions to perform.
 
Fields inherited from class net.xqhs.graphs.graph.SimpleGraph
EDGE_LINE, EDGE_SEPARATOR, EDGE_TARGET, edges, nodes
 
Fields inherited from class net.xqhs.util.logging.Unit
DEFAULT_LEVEL, DEFAULT_UNIT_NAME
 
Constructor Summary
TrackingGraph()
          Creates a new graph that is not the shadow of any other graph.
TrackingGraph(java.util.Queue<TrackingGraph.Transaction> transactionsLink, int initialSequence, Graph initialGraph)
          Creates a shadow graph, based on a transactions queue and, optionally, an initial sequence and an initial graph.
 
Method Summary
 TrackingGraph add(GraphComponent component)
          This is the only method that actually adds a component to the graph.
 TrackingGraph addAll(java.util.Collection<? extends GraphComponent> components)
          Adds all the nodes and edges in the argument to the current graph, all in one transaction.
protected  void addTransaction(TrackingGraph.Transaction t)
          Handles adding of new transactions to the history and to shadow graphs queues.
 TrackingGraph applyTransaction(TrackingGraph.Transaction t)
          Public method allowing the application of an already created transaction to the graph.
protected  void applyTransactionInternal(TrackingGraph.Transaction t)
          Internal method for applying a transaction to the graph.
 boolean canIncrement()
           
 TrackingGraph createShadow()
          Creates a new shadow graph of this graph, based on the current state of the graph.
protected  java.util.Queue<TrackingGraph.Transaction> createShadowQueue()
          Creates a new shadow queue to be used by a shadow graph.
 java.util.Map<GraphComponent,TrackingGraph.Operation> getNextSequenceOperations()
          Retrieves the operations that will be applied at the next sequence increment.
 int getSequence()
           
 int incrementSequence()
          Takes one transaction from the graph's transaction queue and applies it to the current state of the graph.
 int incrementSequence(int targetSequence)
          Takes several transactions from the graph's transaction queue and applies them to the current state of the graph, in order to reach the target sequence number.
 int incrementSequenceFastForward()
          Brings the graph up to date with its master graph, transaction by transaction.
protected  void incrementSequenceInternal()
          Internal method that applies one transaction to the graph.
 boolean isShadow()
           
 TrackingGraph keepHistory(boolean keep, boolean clearHistory)
          Sets history keeping.
protected  TrackingGraph performOperation(GraphComponent component, TrackingGraph.Operation operation, boolean externalCall)
          Internal method for performing one operation upon the current state of the graph.
 SimpleGraph readFrom(java.io.InputStream input)
          The current implementation does not support reading nodes and edges, but all the edges and nodes from a graph can be added with addAll(Collection).
 TrackingGraph remove(GraphComponent component)
          This is the only method that actually removes a component from the graph.
 TrackingGraph removeAll(java.util.Collection<? extends GraphComponent> components)
          Removes all the nodes and edges in the argument from the current graph, all in one transaction.
 java.lang.String toString()
          The method returns a string representation of the graph as rendered by TextGraphRepresentation with default layout parameters.
 java.lang.String toString(java.lang.String branchSeparator, java.lang.String separatorIncrement, int limit)
          The method returns a string representation of the graph as rendered by TextGraphRepresentation with the specified parameters.
 java.lang.String toStringBasic()
          Returns a basic string representation of the graph, as rendered by SimpleGraph.toString().
 
Methods inherited from class net.xqhs.graphs.graph.SimpleGraph
addEdge, addNode, computeDistancesFromUndirected, contains, getComponents, getEdges, getInEdges, getNodes, getNodesNamed, getOutEdges, getUnitName, m, n, removeEdge, removeNode, size, toDot
 
Methods inherited from class net.xqhs.util.logging.Unit
compose, dbg, doExit, getDefaultUnitName, l, le, lf, li, lock, lockedR, lr, lr, lw, setLink, setLink, setLogDisplay, setLogEnsureNew, setLoggerClass, setLoggerType, setLoggerTypeClass, setLogLevel, setLogReporter, setUnitName, 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

sequence

protected java.util.concurrent.atomic.AtomicInteger sequence
The current sequence of the graph. The sequence is incremented after each transaction. For shadow graphs, it should mirror the master's sequence, but it is not the same instance.


isShadow

protected boolean isShadow
true if the graph is a shadow graph, false if it is not the shadow of any other graph.


transactionQueue

protected java.util.Queue<TrackingGraph.Transaction> transactionQueue
Only for shadow graphs, the Queue of transactions to perform. The queue is created by the master graph.


shadowQueues

protected java.util.List<java.util.Queue<TrackingGraph.Transaction>> shadowQueues
The set of transaction queues for the shadow graphs of this graph. There is one for each shadow graph.


keepHistory

protected boolean keepHistory
true if a history should be kept of all performed transactions.


history

protected java.util.List<TrackingGraph.Transaction> history
If required by keepHistory, the history of all transactions.

Constructor Detail

TrackingGraph

public TrackingGraph()
Creates a new graph that is not the shadow of any other graph.


TrackingGraph

public TrackingGraph(java.util.Queue<TrackingGraph.Transaction> transactionsLink,
                     int initialSequence,
                     Graph initialGraph)
Creates a shadow graph, based on a transactions queue and, optionally, an initial sequence and an initial graph.

Parameters:
transactionsLink - - the queue of transactions to apply to this graph.
initialSequence - - the initial sequence number.
initialGraph - - the graph containing the nodes and edges to add initially to this graph. Although the node and edge instances will be the same, there will exist no other relation to the specified graph.
Method Detail

isShadow

public boolean isShadow()
Returns:
true if the graph is the shadow of another graph.

createShadow

public TrackingGraph createShadow()
Creates a new shadow graph of this graph, based on the current state of the graph.

While overriding this method may not be useful because a TrackingGraph is returned, extending classes may use createShadowQueue() to get the shadow queue and create the graph themselves.

Returns:
the newly created shadow graph.

createShadowQueue

protected java.util.Queue<TrackingGraph.Transaction> createShadowQueue()
Creates a new shadow queue to be used by a shadow graph. The queue is also added to the list of shadow queues.

Returns:
the queue.

keepHistory

public TrackingGraph keepHistory(boolean keep,
                                 boolean clearHistory)
Sets history keeping. Clearing the history is controlled by the second parameter and is independent of the value of the first.

Turning off history keeping without clearing the history keeps the history so it can be continued with a new call instructing to keep the history without clearing it.

Parameters:
keep - - true if history should be kept as of this call; false if history keeping should be halted.
clearHistory - - true if the history should be cleared with this call.
Returns:
the graph itself.

performOperation

protected TrackingGraph performOperation(GraphComponent component,
                                         TrackingGraph.Operation operation,
                                         boolean externalCall)
Internal method for performing one operation upon the current state of the graph.

If externalCall is true, the method also creates a new transaction with the operation and adds it to shadow queues and to the history. Otherwise, these operations are handled elsewhere.

This method should be overridden by any extending classes needing to do anything with the newly added components. If it is the case, the overriding method should also check if they should throw the exception.

Parameters:
component - - the component contained in the operation.
operation - - the operation to perform.
externalCall - - true if the method is called by an add or remove method, and the transaction should be added.
Returns:
the graph itself.
Throws:
java.lang.UnsupportedOperationException - if the operation is applied from the exterior, to a shadow graph.

addTransaction

protected void addTransaction(TrackingGraph.Transaction t)
Handles adding of new transactions to the history and to shadow graphs queues.

Parameters:
t - - the transaction to add.

applyTransaction

public TrackingGraph applyTransaction(TrackingGraph.Transaction t)
Public method allowing the application of an already created transaction to the graph.

Parameters:
t - - the transaction to apply.
Returns:
the graph itself.
Throws:
java.lang.UnsupportedOperationException - if the method is called for a shadow graph.

applyTransactionInternal

protected void applyTransactionInternal(TrackingGraph.Transaction t)
Internal method for applying a transaction to the graph. The operation is performed and the transaction is added to the history and shadow graph queues.

Parameters:
t - - the transaction to apply.

add

public TrackingGraph add(GraphComponent component)
Description copied from class: SimpleGraph
This is the only method that actually adds a component to the graph. Any other methods call (should call) this method.

Specified by:
add in interface Graph
Overrides:
add in class SimpleGraph
Parameters:
component - - the component to add. Must be an implementation of GraphComponent that the implementing class can recognize.
Returns:
the graph itself, for chained calls.

addAll

public TrackingGraph addAll(java.util.Collection<? extends GraphComponent> components)
Adds all the nodes and edges in the argument to the current graph, all in one transaction.

Specified by:
addAll in interface Graph
Overrides:
addAll in class SimpleGraph
Parameters:
components - - the GraphComponent instances to add.
Returns:
the graph itself.

remove

public TrackingGraph remove(GraphComponent component)
Description copied from class: SimpleGraph
This is the only method that actually removes a component from the graph. Any other methods call (should call) this method.

Specified by:
remove in interface Graph
Overrides:
remove in class SimpleGraph
Parameters:
component - - the component to remove. Must be an implementation of GraphComponent that the implementing class can recognize.
Returns:
the graph itself, for chained calls.

removeAll

public TrackingGraph removeAll(java.util.Collection<? extends GraphComponent> components)
Removes all the nodes and edges in the argument from the current graph, all in one transaction.

Specified by:
removeAll in interface Graph
Overrides:
removeAll in class SimpleGraph
Parameters:
components - - the GraphComponent instances to remove.
Returns:
the graph itself.

getSequence

public int getSequence()
Returns:
the current sequence number.

canIncrement

public boolean canIncrement()
Returns:
true if there are transactions in the transaction queue that can be applied to the current state of the graph.
Throws:
java.lang.IllegalStateException - if the method is called on a graph that is not a shadow graph.

getNextSequenceOperations

public java.util.Map<GraphComponent,TrackingGraph.Operation> getNextSequenceOperations()
Retrieves the operations that will be applied at the next sequence increment.

Returns:
the operations to be performed, or null if the shadow is synchronized with its master.

incrementSequenceInternal

protected void incrementSequenceInternal()
Internal method that applies one transaction to the graph.


incrementSequence

public int incrementSequence()
Takes one transaction from the graph's transaction queue and applies it to the current state of the graph.

FIXME: if there are no elements in the queue, the sequence is not incremented. should check for dsynchronization; is it possible?

Returns:
the new current sequence number.
Throws:
java.lang.IllegalStateException - if the method is called on a graph that is not a shadow graph.

incrementSequence

public int incrementSequence(int targetSequence)
Takes several transactions from the graph's transaction queue and applies them to the current state of the graph, in order to reach the target sequence number.

Parameters:
targetSequence - - the sequence number to reach before stopping.
Returns:
the new current sequence number. If there are enough transactions in the queue, it is equal to the targetSequence.
Throws:
java.lang.IllegalStateException - if the method is called on a graph that is not a shadow graph.

incrementSequenceFastForward

public int incrementSequenceFastForward()
Brings the graph up to date with its master graph, transaction by transaction.

Returns:
the new current sequence number.
Throws:
java.lang.IllegalStateException - if the method is called on a graph that is not a shadow graph.

readFrom

public SimpleGraph readFrom(java.io.InputStream input)
The current implementation does not support reading nodes and edges, but all the edges and nodes from a graph can be added with addAll(Collection).

Overrides:
readFrom in class SimpleGraph
Parameters:
input - - a stream to read from
Returns:
the enriched SimpleGraph instance

toString

public java.lang.String toString()
The method returns a string representation of the graph as rendered by TextGraphRepresentation with default layout parameters.

A customized representation can be obtained by calling toString(String, String, int).

The basic string representation of the graph can be obtained by calling toStringBasic().

Overrides:
toString in class SimpleGraph

toString

public java.lang.String toString(java.lang.String branchSeparator,
                                 java.lang.String separatorIncrement,
                                 int limit)
The method returns a string representation of the graph as rendered by TextGraphRepresentation with the specified parameters.

Parameters:
branchSeparator - - see TextGraphRepresentation.setLayout(String, String, int).
separatorIncrement - - see TextGraphRepresentation.setLayout(String, String, int).
limit - - see TextGraphRepresentation.setLayout(String, String, int).
Returns:
the string representation.

toStringBasic

public java.lang.String toStringBasic()
Returns a basic string representation of the graph, as rendered by SimpleGraph.toString().

Returns:
the string representation.