Class ExtList
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.
- Since:
- 2005.07.23
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected int
the index of the destination nodeprotected int
the type of the extension edgeprotected int
the type of the destination nodeprotected int[]
the ring information (if needed)protected int
the index of the source nodeprotected ExtList
the successor in a list -
Constructor Summary
Constructors -
Method Summary
-
Field Details
-
src
protected int srcthe index of the source node -
dst
protected int dstthe index of the destination node -
edge
protected int edgethe type of the extension edge -
node
protected int nodethe type of the destination node -
ring
protected int[] ringthe ring information (if needed) -
succ
the successor in a list
-
-
Constructor Details
-
ExtList
protected ExtList(int src, int dst, int edge, int node) Create an extension list element for a single edge extension.- Parameters:
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 node- Since:
- 2005.07.23 (Christian Borgelt)
-
ExtList
protected ExtList(int src, int dst, int edge, int node, int[] ring, int n) Create an extension list element for a ring extension.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.- Parameters:
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 inring
- Since:
- 2005.07.23 (Christian Borgelt)
-
-
Method Details
-
compareTo
Compare to another extension list element.This function is needed for merging two extension lists.
- Parameters:
e
- the extension list element to compare to- Returns:
-1
,0
, or+1
as this list element is less than, equal to, or greater than the given list element- Since:
- 2005.07.23 (Christian Borgelt)
-
merge
Merge two sorted extension lists (and remove duplicates).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.
- Parameters:
l1
- the first extension list to mergel2
- the second extension list to merge- Returns:
- the merged extension lists
- Since:
- 2005.07.23 (Christian Borgelt)
-
sort
Sort an extension list (and remove duplicates).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.
- Parameters:
list
- the extension list to sort- Returns:
- the sorted extension list
- Since:
- 2005.07.23 (Christian Borgelt)
-