In this blog post, I will explain and provide **source code** to automatically **draw the set-enumeration tree of a set **using **Java** and **GraphViz**. Drawing a set-enumeration tree is useful in computer science, for example in frequent itemset mining, a subfield of data mining.

**What is a set-enumeration tree?**

The concept of set-enumeration tree was proposed by Rymon (1992).

Rymon, R. (1992). Search through systematic set enumeration. Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, Cambridge, MA, Morgan Kauffman.

Let be a set X = {a,b,c,d}. A set-enumeration tree for that set is the following structure:

Now, I will show how to draw a nice diagram automatically such as the one above.

**Step 1. Generate a GraphViz input file**

The first step is to have Java installed on your computer and use the following Java program. This Java program will generate a GraphViz input file named “**input.dot**” for the set-enumeration-tree of {a,b,c,d,e}. Note that you can edit the line **String[] set = new String[] { “a”, “b”, “c”, “d”, “e” } **to draw the set-enumeration tree of another set. Note also that the Java code below is not fully optimized. But for the purpose of drawing set-eumeration tree, it is ok.

import java.io.BufferedWriter; import java.io.FileWriter; import java.io.IOException; /** * Draw the set enumeration tree of a set using Graphviz * @author Philippe Fournier-Viger, 2015 */ public class DrawSetEnumerationTree{ public static void main(String[] arg) throws IOException, InterruptedException { // This is the set of integers that we want to draw the powerset of String[] set = new String[] { "a", "b", "c", "d", "e"}; // output file String output = "input.dot"; // create the file BufferedWriter writer = new BufferedWriter(new FileWriter(output)); writer.write("digraph mygraph{" + System.lineSeparator()); writer.write(" node [shape=plaintext]" + System.lineSeparator()); // We will generate all links between subsets with a depth first search recursive("\"{", set, 0, writer); // write end of file writer.write("}"); writer.close(); } private static void recursive(String currentPrefix, String[] set, int offset, BufferedWriter writer) throws IOException { String startVertex = currentPrefix + "}\""; for(int i=offset; i< set.length; i++) { String concatenate; if(offset == 0) { concatenate = currentPrefix + set[i]; }else { concatenate = currentPrefix + "," + set[i]; } String endVertex = concatenate + "}\""; writer.write(" " + startVertex + " -> " + endVertex); writer.write(System.lineSeparator()); recursive(concatenate, set, i+1, writer); } } }

By running the above program, it will create a file called **input.dot** containing a content similar to this, which represents the nodes of the graph that will be drawn and the links between nodes.

digraph mygraph{ node [shape=plaintext] "{}" -> "{a}" "{a}" -> "{a,b}" "{a,b}" -> "{a,b,c}" "{a,b,c}" -> "{a,b,c,d}" "{a,b}" -> "{a,b,d}" "{a}" -> "{a,c}" "{a,c}" -> "{a,c,d}" "{a}" -> "{a,d}" "{}" -> "{b}" "{b}" -> "{b,c}" "{b,c}" -> "{b,c,d}" "{b}" -> "{b,d}" "{}" -> "{c}" "{c}" -> "{c,d}" "{}" -> "{d}" }

**Step 2. Generating a PNG file of the graph using GraphViz**

Then, we can run GraphViz from the command line to generate the graph as a PNG file:

dot -Tpng input.dot > output.png"

This will generate a nice set-enumeration tree:

**A few more powersets**

I have also generated a few more set-enumeration trees that are commonly used for your convenience so that they can be used directly without running the Java program and Graphviz:

set-enumeration tree of {a}

set-enumeration tree of {a,b}

set-enumeration tree of {a,b,c}

set-enumeration tree of {a,b,c,d}

set-enumeration tree of {a,b,c,d,e}

set-enumeration tree of {a,b,c,d,e,f}

set-enumeration tree of {a,b,c,d,e,f,g}

—

Hope that you have enjoyed this post. If you like this blog, you can tweet about it and/or subscribe to my twitter account **@philfv** to get notified about new posts.

**Philippe Fournier-Viger** is a professor of Computer Science and also the founder of the open-source data mining software SPMF, offering more than 52 data mining algorithms.