Methodology for Determining Cyclic Conditions Within a Directed Transformation Graph
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Williams, ML: AUTHOR [+2]
This article describes a methodology by which one can determine if the existing directed transform graph allows an object to be transformed back to its original format after the object has been transformed into another object.
Methodology for Determining Cyclic Conditions Within a
describes a methodology by which one can
determine if the existing directed transform graph allows an object
to be transformed back to its original format after the object has
been transformed into another object.
enterprise, particularly in a multi-vendor network
environment, documents are created using many different editors.
Transforms must be provided when sending a document created by one
editor to another user using a different editor to view and/or modify
the document. When a document is transformed to another format, the
user needs to know if the document can be transformed back to its
original format. If such paths exist, the user would want to know the
number of intermediate transforms that is required to convert it
back. If the reversion transform path does not exist, the user or
application may have to keep copies of original objects in storage
each time an object is transformed, so as to preserve the original
object for its native environment. By preserving the original
document, the user can continue to edit or view the document using
the editor he is familiar with. Otherwise, the original document may
not need to be kept on the sending system so as to conserve storage
requirements and improve system performance.
provides a methodology for determining the
1. a methodology for determining if an object can be transformed
back into its original form after a transformation has been performed
on the object, i.e., this article detects if a cyclic condition
exists for an object.
2. the total number of transformation paths available to transform
one object format to another object format within a transformation
graph. Thus, this article detects if a path of intermediate
transforms exists within the transformation graph to permit an object
be transformed into another object.
capability of an object to be transformed into other
objects and eventually back to itself can be viewed as a cycle. Such
transforms are said to be cyclic. This is the case where object A
can be transformed into object B and object B can be transformed back
into object A.
each instance of a transform and denoting its
relationship with other objects within the system permits an adjacent
matrix to be constructed. Fig. 1 shows an example of a directed
graph of a multiple transform service. A 1 is designated within the
cell if the IN object can be transformed into the OUT object. A
designation of 0 is given for the object to be transformed into
itself. By converting the directed graph to an adjacent matrix
representation, the following technique lets the number of ways an
object can be transformed in r stages to be calculated:
(I(G))r = A = ( aij(r))
where I(G) is the adjacent matrix of a directed graph G and the rth
power of I(G) be A, then the ith, jt...