public class CycleUnwinder
- extends Object
Detects and eliminates some cycles in an XML graph while maintaining the same
XML language. Removing such cycles enables the validator to validate the graph
Define a reducible component as a set of nodes S satisfying that
If there is an edge from A to B we say that A reaches B.
For a reducible component S, define Out(S) to be the set of nodes
reached by at least one node in S, minus the set S itself. That is, Out(S) and
S are always disjoint.
We reduce such a component by replacing the set of outgoing edges in all
choice nodes in S by Out(S). The result may still be a reducible component
if a cycle of sequence nodes exists.
- Every node in S is either a choice node or a sequence node
- Sequence nodes in S have exactly one outgoing edge
- For any pair of nodes A,B both in S, there exists a path from A to B
where every node on that path is in S.
- There are at least two nodes in S.
Creates an unwinder for an XML graph with the specified number of nodes.
|Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
public CycleUnwinder(int numnodes)
- Creates an unwinder for an XML graph with the specified number of nodes. The instance
can be reused to analyze several XML graphs (but not concurrently).
numnodes - number of nodes in the XML graph to analyze
public void unwind(XMLGraph graph)
Copyright © 2005-2011 Aarhus University.