5
\$\begingroup\$

I want to visualize all unlabeled trees with \$n\$ or fewer nodes, not just count them.

First idea/attempt: Take a list of all \$n-1\$ node trees, then append a new leaf to every tree in every way to get a new list of \$n\$ node trees. Clearly, this new list will contain a lot of isomorphic duplicates. To fix this, we start adding the \$n\$ trees to a new list, and doing so only if they are not isomorphic to any of the trees in the new list. Since graph isomorphism problem is not known to be solvable in polynomial time, this makes the entire process even more horrible performance wise, because this process will do a lot of such checks.

My question is if this can be done more efficiently, or in a better way?

The python code implementing this idea/attempt using networkX and pyplot:

""" trees of order N or less will be generated """
N = 9

import networkx as nx

""" return copy of graph with newNode node appended to toNode node """
def leaf_copy(graph, newNode, toNode):
    g = nx.Graph.copy(graph)
    g.add_node(newNode)
    g.add_edge(newNode,toNode)
    return g


from networkx.algorithms import isomorphism

""" get all n+1 node cases out of all n node cases in prevTreeList """
def genNextTreeList(prevTreeList):
    """ one node case """
    if prevTreeList == None or prevTreeList == []:
        g = nx.Graph()
        g.add_node(1)
        return [g]

    """ new loads of n+1 graphs by all possible list appendations """
    """ this will include loads of isomprhic duplicates... """
    nextTreeList = []
    for g in prevTreeList:
        v = len(g.nodes())+1
        for node in g.nodes():
            nextTreeList.append(leaf_copy(g,v,node))

    """ remove isomorphic duplicates """
    """ it will check every graph to be added with all added graphs for isomorphism... """
    nextTreeListClean = []
    for g in nextTreeList:    
        isomorphic = False
        for clean_g in nextTreeListClean:
            i = isomorphism.GraphMatcher(g,clean_g)
            if i.is_isomorphic():
                isomorphic = True
                break
        if not isomorphic:
            nextTreeListClean.append(g)
    return nextTreeListClean


import matplotlib.pyplot as plt

if __name__ == "__main__":

    print(0, "\t", 1)

    G = []
    figure = 0
    for n in range(N):
        G = genNextTreeList(G)

        """ print the number of examples to check if the code is working properly """
        print(n+1, "\t", len(G))

        """ draw and save the plots """
        for g in G:
            figure += 1
            fig = plt.figure(figure)
            plt.title(str(n+1)+'.'+str(G.index(g)+1))
            nx.draw(g, with_labels=False) 
            plt.figure(figure).savefig('plot'+str(figure)+'.png',bbox_inches='tight',dpi=100)
            plt.close(fig)

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Tree isomorphism is polinomial. Maybe this helps or this \$\endgroup\$ – juvian Aug 29 '18 at 18:42
3
\$\begingroup\$

1. Review

  1. In Python, a docstring goes after the function or class introduction. So instead of:

    """ return copy of graph with newNode node appended to toNode node """
    def leaf_copy(graph, newNode, toNode):
    

    write something like:

    def leaf_copy(graph, newNode, toNode):
        """Return a copy of graph with newNode appended to toNode."""
    

    There are several advantages of doing it this way. Docstrings are available via the help function in the interactive interpreter:

    >>> help(leaf_copy)
    Help on function leaf_copy in module __main__:
    
    leaf_copy(graph, newNode, toNode)
        Return a copy of graph with newNode appended to toNode.
    

    Also, some integrated development environments (for example, PyCharm) can read and interpret docstrings to provide context-sensitive help or to generate reference documentation. And the built-in doctest module can automatically run examples in docstrings.

  2. The trivial graph with one node and no edges is generated like this:

    g = nx.Graph()
    g.add_node(1)
    

    but networkx has the function trivial_graph which does something similar.

  3. The specification of genNextTreeList is:

    """ get all n+1 node cases out of all n node cases in prevTreeList """
    

    but this only the case if prevTreeList is the result of iterating genNextTreeList starting with an empty list. A more accurate specification would be something like this:

    def genNextTreeList(prevTreeList):
        """Return a list of the graphs that can be constructed by attaching a
        new node to any of the nodes in any of the graphs in prevTreeList,
        except that if prevTreeList is None or the empty list, in which
        case a list containing the trivial graph is returned.
    
        """
    
  4. It says in the Zen of Python,

    Special cases aren't special enough to break the rules.

    so I would drop the special case. It is easy enough for the caller to pass the list containing the trivial graph, if that's what's wanted.

    Also, it should be clear now that genNextTreeList does not only operate on trees. So a better name and specification would be something like this:

    def augmented_graphs(graphs):
        """Return a list of the graphs that can be constructed by attaching a
        new node to any of the nodes in any of the graphs in the argument.
    
        """
    
  5. Instead of having a flag isomorphic to determine whether the new graph has been found to be a duplicate, use Python's for ... else: ... statement, or the any or all functions.

  6. There's no need to use networkx.algorithms.isomorphism.GraphMatcher: you could just call networkx.algorithms.isomorphism.is_isomorphic directly.

  7. genNextTreeList has a two-step construction of the result: first, construct a list nextTreeList of augmented graphs, and second, eliminate duplicates. These could be combined into a single step by testing each new graph for isomorphism as soon as you construct it, like this:

    from networkx.algorithms.isomorphism import is_isomorphic
    
    def augmented_graphs(graphs):
        """Return a list of the graphs that can be constructed by attaching a
        new node to any of the nodes in any of the graphs in the argument.
    
        """
        result = []
        for old_graph in graphs:
            new_node = max(old_graph.nodes()) + 1
            for node in old_graph.nodes():
                new_graph = leaf_copy(old_graph, new_node, node)
                if not any(is_isomorphic(new_graph, g) for g in result):
                    result.append(new_graph)
        return result
    
  8. The top-level code does two things: it generates the free trees with up to N nodes, and it plots them. This would be better split into two functions each of which does a single thing, for example:

    from networkx.generators.classic import trivial_graph
    
    def free_trees(n):
        """Return list of free trees with up to n vertices."""
        result = trees = [trivial_graph()]
        for i in range(n - 1):
            trees = augmented_graphs(trees)
            result.extend(trees)
        return result
    

2. Alternative approach

A look at the NetworkX manual finds networkx.generators.nonisomorphic_trees.nonisomorphic_trees which implements the algorithm of

This generates the 19,320 free trees on 16 nodes (see A000055) in just over a second:

>>> from networkx.generators.nonisomorphic_trees import nonisomorphic_trees
>>> from timeit import timeit
>>> timeit(lambda:list(nonisomorphic_trees(16)), number=1)
1.0307372510433197

Here are 100 of these trees:

Last 100 free trees on 16 nodes

\$\endgroup\$
  • \$\begingroup\$ I appreciate the insightful answer! \$\endgroup\$ – Vepir Sep 30 '18 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.