Output-Sensitive Enumeration of Structures like Trees and Graphs

Output Sensitive Enumeration 6. Isomorphism Rooted-tree, Tree, Floorplan Necklace Rooted Tree Non-rooted trees Colored Trees Floorplans Other Geometric Objects

Graph Enumeration Previous enumeration problems aim to enumerate substructures of the given instances (ex. paths in a graph) On the other hand, there is a problem of finding all structures in the given specified class (ex, matrices) For some classes, the problem is trivial + paths, cycles: lengths of 1, 2, + cliques: sizes of 1, 2, + permutations of size n For some classes, the problem is non-trivial + trees, crossing lines (in plane), matriods, 01-matrices

Isomorphism On non-trivial structures, we have to take care of isomorphism Isomorphism: a structure is isomorphic to another if there is one- to-one correspondence between the elements with keeping some condition + a ring sequence (necklace) is isomorphic to another iff it can be transformed to another by rotation + a matrix is isomorphic to another iff it can be transformed to the other by swapping rows, and swapping columns + a graph is isomorphic to another iff there is a one to one mapping between vertices preserving the adjacency Enumerate all structures so that no two are isomorphic

6-1 Necklace Enumeration

Problem Definition Necklace is a cyclic string, in that the first and last letters are adjacent A B C D E B C D E A A D C D E A B D E A B C E A B C D Complete enumeration of necklace, of length nwith alphabet is easy; just enumerate all the strings of length n However several (n) strings give the same necklace, so we have duplicates

Avoiding Duplicates A typical way to avoiding the duplications is store all the solutions in memory, check the existence for each new solution A B A B A A B C D E F F F C C For checking the existence, we rotate the query string in n ways; so we have to issue n queries D D D D D A B A C D ? If we prepare all the rotations of strings in the data, we need only 1 query On the other hand, memory consumption increases with factor of n

Using Normal Form (Representative) In such cases, normal form (representative) does a good help A B C D E B C D E A D C D E A B For a necklace T, consider all strings corresponding to T, and choose the lexicographically minimum one D E A B C E A B C D This is a representative, uniquely defined, and computed in short time A B A B A A B C D E C C F F F The representative of the corresponding necklace is found by testing all the shifts of the string D D D D D

Computing Representative The representative must start from the smallest letter To detect which is the minimum, we extend each as a string Keep those with the smallest letter Delete the others If the extensions touch the next, (it means this is the current min) keep them and delete the others If several touch, choose the longest ones

Computing Representative In each step, the extension seeks a new letter (had not been touched) When touching the next, the next always deleted and the head will be inside (so, never be touched again) In total, each letter is touched at most once, meaning that the algorithm is linear time

Avoiding with Representative Enumerate all the strings of length n Compute the representative of each, and store in memory (a database) A B A B A A B C D E F F F C C Then, for checking the existence, we have to have only one query D D D D D O(n) time to + get representative + store one representative + check one existence query A B A C D ?

Depth-First Way Actually, with representative, the storage for solutions becomes not necessary Just enumerate all strings of length n, and output them only when they are being representatives A B A B A A B C D E F F F C C D D D D D O(n) time to + get representative without storage, so polynomial memory space

Enumerate Representatives, Directly Then, we are naturally motivated to enumerate only representatives A B A B A A B C D E Then, there would be no time consuming Problems F F F C C But, simple enumeration finds all strings, so we need some modifications on string enumeration D D D D D

Representative Enumeration A B C D E F G H The first letter has to be smallest If there are some smallest letters, the prefix of k letters must be always smallest among all substrings of length k Observation For any representative, changing the last non-biggest (say, Z) letter to the biggest letter (Z) yields also a representative We can enumerate all representatives by + starting from ZZZZZ Z, and + changing some Z having no non-Z latter, iteratively A B C A B C B B A B Z A Z Z Z Z

Redundancy + starting from ZZZZZ Z, and + changing some Z having no non-Z latter, iteratively A B C D E Z Z Z This is complete so we can enumerate EnumNecklace (S) 1. output S 2. for each i s,t, S[i] = Z, no j > i satisfies S[j] Z 3. for each letter a S[1], 4. S[i] := a 5. if S is representative then call EnumNecklace (S) 6. end for 7. S[i] := Z 8. end for

Conditions to be Representatives A B C D E F G H The check for being representative is a cost Consider some good conditions to be representative necessary necessary The first letter has to be smallest If there are some smallest letters, the prefix of k letters must be always smallest among all substrings of length k For a representative S, + change Z to a < S[1] is always bad + change Z to a > S[1] is always good, if S is not repetitive If S is partially repetitive, there are several cases always a < head A B C A B C A B C Z Z Z

Handling Repetition S[1..i-1] is repetitive a substring ending at S[i-1] = prefix of S When no substring ending at S[i-1] = prefix of S + change Z to a > S[1] is always good prefix of S is always smaller than any other ending at S[i], and all letters after S[i]are Z A B C A B C A B F Z Z Z If S is repetitive, some are good and some are bad

Handling Repetition S[1..i-1] is repetitive a substring ending at S[i-1] = prefix of S When S is repetitive, + change Z to a < S[j] is always bad, and a S[j] is always good change Z to a < S[j] yields that the repeat substring will be smaller than the prefix change Z to a S[j] keeps that the prefix is still the smallest j A B C A B C A B Z Z Z

Multiple Repetitions S[1..i-1] is repetitive a substring ending at S[i-1] = prefix of S When S is multiply repetitive, for all same substrings, the same statement holds change Z to a S[j] keeps that the prefix is still the smallest A B C D A B C D A B C D A B Z Z Z Z

Copy Position For position i, define copy position copy(S, i) by smallest j s.t. S[1..j] = S[i-j..i-1] (by 0 if no j satisfies it) by changing S[i] to a, S is still representative if and only if a S[j] So, by maintaining the copy position during the computation, we can easily generate only representatives A B C D A B C D A B C D A B Z Z Z Z

Algorithm with Copy Position changing S[i] to a, S gives a representative a S[copy(S,i)] EnumNecklace (S) 1. output S 2. for each i s,t, S[i] = Z, no j > i satisfies S[j] Z 3. compute copy(S,i) 4. for each letter a S[copy(S,i)], 4. S[i] := a 5. call EnumNecklace (S) 6. end for 7. S[i] := Z 8. end for No check is necessary

Maintaining Copy Position copy(S, i) if S[copy(S, i)] = Z copy(S, i+1) = 0 otherwise By changing S[i] to a ( S[copy(S, i)]) copy(S, i) if S[copy(S, i)] = a copy(S, i+1) changes to 0 otherwise so easy to be maintained in O(1) time A B C D A B C D A B C D A B Z Z

6-2 Reverse Search for Ordered Trees

Ordered Tree Asano, Arimura et.al. 03 Nakano 02 Consider enumeration of trees Tree has many classes among them, we first consider ordered trees Ordered tree: a rooted tree s.t. a children ordering is specified for each vertex They are isomorphic in the sense of tree (graph), but the orders of children, and the roots are different

Ambiguity on Representation Trees (graphs) are represented by combination of sets, thus we need to put indices to vertices (in the case of data structure, same) It results ambiguity on the representation there are many ways to put indices By putting the indices in a unique way, or representing by other objects, we can avoid the ambiguity

Left-first DFS Put indices to vertices by visiting order of depth-first search that visits the leftmost child first, and the remaining from left to right indices are put uniquely an ordered tree is isomorphic another if any its edge is included in the other (and #edges are equal) 1 1 2 5 6 2 4 5 3 4 7 3 6 7 Isomorphism can be checked by comparing edge sets

Depth Sequence The left-first DFS can be used to encode ordered trees The movement of the DFS is encoded by the sequence of the depth of the visiting vertices (depth sequence) the sequence of depths of the vertices ordered by the indices 1 1 2 5 2 4 5 6 3 6 7 3 4 7 0122112 0121122 Isomorphism can be checked by comparing the sequences

Parent-Child Relation for Ordered Trees Based on the idea of these representations, we define the parent of each ordered tree The parent of an ordered tree is defined by the tree, obtained by removing the vertex having the largest index T grandparent parent 0,1,2,3,3,2,1,2,3,2 0,1,2,3,3,2,1,2,3 0,1,2,3,3,2,1,2,3,2,1 size decreases by going to the parent acyclic & spans all ordered trees

Family Tree of Ordered Trees Parent is removal of the rightmost leaf child is an attachment of a rightmost leaf

Finding Children For an ordered tree T, we can obtain its children by adding a vertex so that the vertex has the largest index add to right-hand of the rightmost path parent 0,1,2,3,3,2,1,2,3,2 addition always yields a child 0,1,2,3,3,2,1,2,3,2,3 0,1,2,3,3,2,1,2,3,2,1 0,1,2,3,3,2,1,2,3,2,2

Pseudo Code By giving the size limitation, we can enumerate all ordered trees of size less than the specified number k EnumOrderedTree (T) 1. output T 2. if (size of T) = k then return 3. for each vertex v in the right most path 4. add a rightmost child to v 5. call EnumOrderedTree (T) 6. remove the child added in 4 7. end for The inside of the for loop takes constant time, thus time is O(1) for each (output by difference from the previous)

6-3 Reverse Search for Rooted Trees

Ordered Trees Un-ordered Trees Nakano Uno 04 There are many ordered trees isomorphic to an ordinary un- ordered tree (rooted tree) If we enumerate un-ordered trees in the same way, many duplications occur Use canonical form

Canonical Form depth sequences are the same Ordered trees are isomorphic left heavy embedding of a rooted tree T the lexicographically maximum depth sequence, among all ordered trees obtained from T (by giving children orderings) left heavy embeddings are the same Rooted trees are isomorphic 0,1,2,3,3,2,2,1,2,3 0,1,2,2,3,3,2,1,2,3 0,1,2,3,1,2,3,3,2,2

Parent-Child Relation for Canonical Forms The parent of left-heavy embedding T is the removal of the rightmost leaf (same as ordered trees) the parent is also a left-heavy embedding, since the rightmost subtree becomes lexicographically smaller by the removal T parent grandparent 0,1,2,3,3,2,1,2,3,2,1 0,1,2,3,3,2,1,2,3,2 0,1,2,3,3,2,1,2,3 The relation is acyclic and spanning all

Family Tree of Un-ordered Trees Pruning branches of ordered trees

Finding Children Any child of a rooted tree (parent) is obtained by adding a vertex so that it is the rightmost leaf However, some additions do not yield a child parent 0,1,2,3,3,2,1,2,3,2 0,1,2,3,3,2,1,2,2,3 0,1,2,3,3,2,1,2,2,1 0,1,2,3,3,2,1,2,2,2

Finding Children Addition is not a child at some level, right subtree becomes larger than the left It happens only when the depth sequence of the right is a prefix of that of the left Below the next depth of the left, no addition yields a child For all above that, yields a child We have to take care only the upmost such vertex (being prefix) violate only lower prefix corresponding prefix on the left too 34564545 345645

Copy Vertex Copy vertex the upmost vertex s.t. the right subtree is a prefix of the left Copy vertex changes by the addition of the rightmost leaf. It + does not change if the addition is the same level to the left + becomes to u, if the level is above (u is the parent of the added leaf) 34564545 345645 We can compute copy depth in constant time for each child

Pseudo Code EnumRootedTree (T, x) 1. output T 2. if the size of T = k then return 3. y := the vertex next to x in the depth sequence 4. for each v in rightmost path, in increasing order of the depth 5. c := the rightmost child of v 6. add a rightmost child to v 7. if (depth of v) = (depth of y) then call EnumRootedTree (T, y); break 8. call EnumRootedTree (T, c) 9. remove the rightmost child of v 10. end for The inside of the for loop takes O(1) time, thus the time is O(1) for each (output by difference from the previous)

6-4 Free Trees

Enumerate Un-rooted Trees An un-rooted tree has no root, so depth sequence is not defined define the root by its center(s) Center: vertex minimizing the distance to the furthest leaf The diameter is even We first consider the case of even diameter the center is unique

Parent of Left Heavy Embedding Parent of a left-heavy embedding of m vertices and diameter k removal of the rightmost leaf, removal of the second rightmost leaf if its diameter changes Parent is a left-heavy embedding of m-1 vertices and diameter k rightmost leaf leftmost spine (longest path) Diameter changes Leftmost spine does not change by removing the leaf parent and child shares leftmost spine constant time for each tree of at most n vertices diameter k parent of parent T parent

Family Tree of (Un-rooted) Trees diameter 4

Generating Only Trees of n Vertices Active leaf: rightmost leaf s.t. not a child of rootand whose removal does not change the diameter Parent of a left-heavy embedding of n vertices and diameter k : remove active leaf and add a leaf to the root also a left-heavy embedding of n vertices and diameter k parent of parent T parent

Family Tree of Trees of n Vertices 7 vertices diameter 4

Odd Diameter There are always two centers Similar algorithm by considering two centers as the single root vertex (the order of children of the root has to be an exception)

6-5 Free Trees and Colored Version

Colored Tree (c-tree) Colored tree is a tree s.t. each vertex has a color taken from a color set color = { color = {a,b,c,d} a } or b b a d a d PROBLEM For given n, m and d, enumerate all non-isomorphic colored trees of n vertices of diameter d with at most m colors, without duplications

Isomorphism and Duplication Two colored trees are isomorphic iff there is a mapping of the vertices preserving the adjacency and colors = = same!

Why Difficult? Any colored tree can be generated by adding vertex and edge one-by- one, so we can incrementally generate all colored trees, but We have many duplications