##
dk.brics.xact.analysis.xmlgraph

Class CycleUnwinder

java.lang.Object
**dk.brics.xact.analysis.xmlgraph.CycleUnwinder**

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
more precisely.

Define a *reducible component* as a set of nodes S satisfying that

- 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.

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.

**Constructor Summary** |

**CycleUnwinder**(int numnodes)
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` |

###
CycleUnwinder

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).

**Parameters:**`numnodes`

- number of nodes in the XML graph to analyze

###
unwind

public void **unwind**(XMLGraph graph)

* Copyright © 2005-2011 Aarhus University. *