Drawing a set-enumeration tree using Java and GraphViz

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:

The set-enumeration tree of {1,2,3,4}

The set-enumeration tree of {1,2,3,4}

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:

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

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

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.

This entry was posted in Data Mining, Mathematics, Programming, Research. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *