CODEWITHSUNDEEP
algorithmtreepipegraph-theorycombinatorics
Parthasarathy SRINIVASAN
Parthasarathy SRINIVASAN

Reputation: 21

How do I generate (and hence find total possible) non-isomorphic, trees which has binary and 3-ary intermediate nodes given exactly "L" leaf nodes

With the following input conditions

  1. One root node which which can have only 1 output
  2. There are a fixed/finite set of exactly "L" leaf nodes, say 20
  3. The intermediate nodes can be chosen between binary or 3-ary nodes. The intermediate nodes can be a combination of "J2" node (which has one input and 2 outputs) and "J3" node( which has one input and 3 outputs)

I request to let me know, How many non-isomorphic trees can be constructed and what is(are) the algorithm(s) to generate all of them?

Tree = Tree(Node,Edge) such that Node = {root(1), "L" leaf nodes, "n" no. of "J2" nodes and "m" no. of "J3" nodes} where n and m can take any (+ve) integer values that caters to "L" leaf nodes.

This problem arises in piping topology optimization.

Upvotes: 1

Views: 144

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65498

I’m going to assume that outputs and leaves are indistinguishable. The plan of action is

  1. Define a total order on trees with distinguishable outputs.
  2. For each isomorphism class, designate a unique representative (spoiler: the minimum).
  3. Enumerate unique representatives.

Total order

For each n, we give a total order on trees with exactly n indistinguishable leaves and distinguishable outputs.

Trees with a J2 at the root come before trees with a J3 at the root. Among trees with identical roots, we use lexicographic order on the pair or triple of how many leaves the root outputs have. Then we use lexicographic order on the pair or triple of trees themselves.

Unique representatives

With a total order, this is easy: choose the minimum tree in each isomorphism class.

Enumeration

This is a recursive algorithm, with the additional property that it enumerates trees in order. The base case is when there is one one-leaf tree. Otherwise, we loop over all possible divisions of leaves (pairs then triples, each in non-descending order) and tread carefully when numbers repeat. In Python:

import collections
import functools
import itertools

L = collections.namedtuple("L", [])
J2 = collections.namedtuple("J2", ["a", "b"])
J3 = collections.namedtuple("J3", ["a", "b", "c"])


def list_output(f):
    def g(*args, **kwargs):
        return list(f(*args, **kwargs))

    return g


@functools.lru_cache(maxsize=None)
@list_output
def trees(n):
    assert n >= 1
    if n == 1:
        yield L()
        return
    for na in range(1, n // 2 + 1):
        nb = n - na
        assert na <= nb
        for i, a in enumerate(trees(na)):
            for j, b in enumerate(trees(nb)):
                if (na, i) <= (nb, j):
                    yield J2(a, b)
    for na in range(1, n // 3 + 1):
        for nb in range(na, (n - na) // 2 + 1):
            nc = n - na - nb
            assert na <= nb <= nc
            for i, a in enumerate(trees(na)):
                for j, b in enumerate(trees(nb)):
                    for k, c in enumerate(trees(nc)):
                        if (na, i) <= (nb, j) <= (nc, k):
                            yield J3(a, b, c)


for nn in range(1, 21):
    print(len(list(trees(nn))))

Sample output:

1
1
2
4
9
23
58
156
426
1194
3393
9802
28601
84347
250732
750908
2262817
6857386
20882889
63877262

Upvotes: 0

ravenspoint
ravenspoint

Reputation: 20576

First generate the tree with the minimum number of nodes, using all J3 nodes except for the nodes in the last layer connected to the leaves, where some J2 nodes will be needed.

If Y is the number of node layers, then you will need the smallest number of layers ( min Y ) that satisfies 3^Y >= L. ( e.g. for 20 leaves, min Y = 3 )

Now replace J3 nodes one by one with J2 nodes, making the necessary changes to the tree until you have the minimum Y that satisfies 2^Y >= L. ( e.g. for 20 leaves, min Y = 5 )

Upvotes: 0

Related Questions