public class ExtList
extends java.lang.Object
Extension lists are used to determine whether a fragment is closed, that is, whether no superstructure has the same support. The basic idea is to try to find an extension that is possible in all graphs by maintaining a list of extensions that are possible in all already processed graphs. In each processing step all extensions that are impossible in the next graph are removed from the list. A fragment is closed if the list gets empty before all graphs have been processed, otherwise it is not closed.
Modifier and Type | Field and Description |
---|---|
protected int |
dst
the index of the destination node
|
protected int |
edge
the type of the extension edge
|
protected int |
node
the type of the destination node
|
protected int[] |
ring
the ring information (if needed)
|
protected int |
src
the index of the source node
|
protected ExtList |
succ
the successor in a list
|
Modifier | Constructor and Description |
---|---|
protected |
ExtList(int src,
int dst,
int edge,
int node)
Create an extension list element for a single edge extension.
|
protected |
ExtList(int src,
int dst,
int edge,
int node,
int[] ring,
int n)
Create an extension list element for a ring extension.
|
Modifier and Type | Method and Description |
---|---|
protected int |
compareTo(ExtList e)
Compare to another extension list element.
|
protected static ExtList |
merge(ExtList l1,
ExtList l2)
Merge two sorted extension lists (and remove duplicates).
|
protected static ExtList |
sort(ExtList list)
Sort an extension list (and remove duplicates).
|
protected int src
protected int dst
protected int edge
protected int node
protected int[] ring
protected ExtList succ
protected ExtList(int src, int dst, int edge, int node)
src
- the index of the source nodedst
- the index of the destination node (or -1)edge
- the type of the extension edgenode
- the type of the destination nodeprotected ExtList(int src, int dst, int edge, int node, int[] ring, int n)
The information about the ring edges, contained in the array
ring
, is copied before it is stored in the extension
list element. Hence the array passed as an argument may be reused
for collecting information about another ring.
src
- the index of the source nodedst
- the index of the destination node (or -1)edge
- the type of the (first) extension edgenode
- the type of the destination nodering
- an array containing information about the ring edgesn
- the number of relevant fields in ring
protected int compareTo(ExtList e)
This function is needed for merging two extension lists.
e
- the extension list element to compare to-1
, 0
, or +1
as this list element is less than, equal to, or greater
than the given list elementprotected static ExtList merge(ExtList l1, ExtList l2)
This function is used to implement a simple merge sort for extension lists. In addition, all elements that occur in both extension lists are joined by transferring only one of two equal elements to the output list, thus removing duplicates.
l1
- the first extension list to mergel2
- the second extension list to mergeprotected static ExtList sort(ExtList list)
The algorithm is a simple merge sort. The input list is split into two lists of roughly equal size by traversing it and storing its elements alternatingly into two output lists. These two lists are sorted recursively and then merged.
list
- the extension list to sort