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.

Method Summary

void	unwind(XMLGraph graph)

Methods inherited from class java.lang.Object

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

Constructor Detail

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

Method Detail

unwind

public void unwind(XMLGraph graph)