HRDAG Code
Framework for Hierarchical Graph Decomposition
Status: Pre-Alpha
Brought to you by:
bgodlin
Menu
▾
▴
Tree [bb1138] master / History
Read Me
=== Contents ===
1. Introduction
2. Installation
3. Usage
3.1 Graph decomposition
3.2 Isomorphism testing
3.3 Using the scripts
4. Input formats
4. The author
=== Introduction ===
The HRDAG framework is a part of HRDAG (Hierarchy Representing Directed
Acyclic Graphs) project, which is a research project to create mathematical
representations for graphs which were created from or contain a hierarchy of modules.
The research deals with the mathematical (graph theoretic), logical,
algorithmic and empirical aspects of such hierarchical graphs.
This HRDAG java framework itself currently concentrates on decomposition
or reverse engineering of such hierarchical graphs. This may be useful to understand
the structure of hardware designs for which we know the net-list but not the modular
design and for finding modular structures in biological data.
The main idea is to iteratively recognize similar (isomorphic) sub-graphs of
the input graph and when many similar sub-graphs are recognized, each of them
is collapsed to single vertex which represents the sub-graph as a module
inside the big graph. Currently we use isomorphism for similarity,
but functional similarity criterion can be easily added to the framework.
A side product of this framework is an algorithm for graph ordering up to isomorphism
which compares two graphs in deterministically bounded $O(n^2*log(n))$ time
where $n$ is the number of vertices in the bigger graph.
Thus, finding all isomorphic subsets in a set of $l$ graphs is done in $O(l*log(l)*n^2*log(n))$
where $n$ is the number of vertices in the biggest graph.
Searching for a graph isomorphic to a given graph in a set if $l$
is done in $O(log(l) * n^2*log(n))$ time.
The algorithm IS NOT complete, if it is unable to determine isomorphism or separate
two graphs it throws an exception. But this is very rare: it never happened during graph
decomposition attempts and the only currently known graph families on which
it fails are the "ag" and "pg" series of the Bliss benchmark
(http://www.tcs.hut.fi/Software/bliss/benchmarks/index.shtml)
and MSD, MSN, MZD, and MZN series in the Conauto benchmark
(https://sites.google.com/site/giconauto/home/benchmarks).
Some ideas of the algorithm are based on the PhD thesis of José Luis López-Presa
(http://www.diatel.upm.es/jllopez/tesis/thesis.pdf).
There (chapter 3) you can also find the description of Affine Geometries,
Desarguesian Projective and Miyazaki's construction graph families
on which the HRDAG graph isomorphism compare algorithm fails.
=== Installation ===
Just copy HRDAG-....jar to the directory where you want to execute it.
Set CLASSPATH environment variable or -cp java option to
this jar file.
You can extract scripts.tgz in the same directory to use them.
Note that though the jar and the java source code can be used
in any environment supporting java, the scripts can be executed
only in Unix or Cygwin environments.
You should have at list scripts/runDot.csh and scripts/runDotAndShow.csh
in your PATH as they are used directly by DottyDebugPrinter class.
Execute the scripts from the base directory, i.e., the directory where setRunVars.inc is:
scripts/testIso.csh -Fconauto /tmp/iso_bench/conauto/ MZD MZN
or
scripts/run.csh -Frtl examples/rtl/s420.bench
If you want to use the source code put org directory of the source code
in the base execution directory.
Most of the scripts use scripts/comp.sh to compile the source code
into output/classes. You need to put junit-4.10.jar under the ./lib
directory for the whole source to compile though only TestGraph,
TestMappings, and TestMyList classes depend on it.
Use scripts/makedoc.csh and scripts/etags.csh to create html documentation
and emacs tags for the source code. After creation, the documentation root file is
in output/doc/index.html .
=== Usage ===
3.1) Graph decomposition:
To decompose a graph to a hierarchy of modules use org.HRDAG.test.RunFormCenter:
Usage: java org.HRDAG.test.RunFormCenter [ -F<format> ] <input-graph-file> <result-dir>
Possible formats (for -F) of the input-file are: cnf, bliss, conauto, rtl (see Input Formats section below).
Default format is: cnf
The file <result-dir>/out.txt lists the main findings and decisions of the tool during execution.
All result graphs and sub-graph forms are written in .dot format
(see http://www.graphviz.org/content/dot-language
and http://www.graphviz.org/Documentation/dottyguide.pdf),
one graph per file in the <result-dir>.
HRD.dot is the directed acyclic graph describing the module hierarchy
which the tool discovered in the input graph.
LastGraph.dot is the form of the root module of this hierarchy.
Form_*.dot files are the isomorphic forms of the hierarchy modules
and other sub-graphs encountered in the process of decomposition.
Use: dotty <graph-name>.dot
to see the resulting forms and graphs.
You can also use for that any other tool from
http://www.graphviz.org/Resources.php
which and display .dot files.
You can use scripts/run.csh and scripts/runMany.csh to automate execution of this action.
Note that these scripts gzips out.txt and some of the bigger .dot result files.
3.2) Isomorphism testing:
To find all isomorphic subsets in a set of graphs in <graphs'-dir>
(each graph is in a separate file) use org.HRDAG.test.FindAllIsomorphic class:
Usage: java org.HRDAG.test.FindAllIsomorphic [ -F<format> ] [ -O<result-dir> ] [ -S<seed> ] [ -P ] <graphs'-dir>
When -O is present prints output to <result-dir>, otherwise to <graphs'-dir>.
When -P is present prints each graph Form to a separate .dot file in the output dir.
When -S is present initializes its Random permuter with <seed>.
Possible formats (for -F) are: bliss, cnf, conauto (see Input Formats section below).
Default format is: bliss
You can use scripts/findAllIsomorphic.csh and scripts/testIso.csh to automate execution of this action.
If all went well, the result is a text file listing all subsets with 2 or more isomorphic graphs
and their forms and the names of all single graphs (i.e., graphs which are not isomorphic to
any other int the set).
The tool also generates, for each input graph:
a) 4 permutations of each graph to check that the algorithm
recognizes permutations as isomorphic to the original and 4 versions of the graph, and
b) 4 versions of the graph where the edges between 2vs2 vertices are switched.
Where 2vs2 vertices are 2 pairs of vertices such that: first pair vertices
is in the same VertexClass and each vertex in the pair is connected to
another vertex and these other pair of vertices share a VertexClass
(same as the first pair or other VertexClass).
This edge-pair switch is used to test that the algorithm separates pairs of
very close but no-isomorphic graphs.
3.3) Using the scripts:
The scripts can be used only in Unix or Cygwin environments.
When you use scripts to execute the operating:
Change variable values in setRunVars.inc to control which code is executed
or which source code is compiled and executed.
Set HRDAGJAR to the right .jar file if you use HRDAG .jar file
or set it to "none" if you want to compile and run the java source code.
The scripts compIfNeed.csh and comp.csh is used to compile the source code
to .class files, but most scripts attempt to compile the needed source code
if no HRDAGJAR is used and the source code has changed since last compilation.
You can change the directories to where a script writes execution results
by changing the value of RESULTDIR in the script file.
Examples:
Graph decomposition:
scripts/run.csh examples/dubois20.cnf
scripts/run.csh -Frtl examples/rtl/iscas99/b14.bench
scripts/runMany.csh smallToRun.lst
scripts/runMany.csh -Frtl rtl_small_interesting.lst
scripts/runMany.csh examples/minandmaxor032.cnf examples/minor032.cnf examples/minor064.cnf examples/minxorminand032.cnf
Where dubois20.cnf, minandmaxor032.cnf, minor032.cnf, minor064.cnf,
and minxorminand032.cnf in examples/ are files with single CNF formula each,
examples/rtl/iscas99/b14.bench is an RTL/ISCAS netlist,
smallToRun.lst and rtl_small_interesting.lst are files with lists
of example files - each example in a separate line
Currently, CNF is the default format for RunFormCenter class
so we do not need the -F flag with .cnf files.
By default the decomposition scripts write execution results
to /tmp/HRDAG_results/ directory.
Isomorphism test:
scripts/findAllIsomorphic.csh /tmp/iso_bench/bliss/had-sw bliss /tmp/findAllIso_results
scripts/testIso.csh -Fbliss /tmp/iso_bench/bliss had latin
scripts/testIso.csh -Fconauto /tmp/iso_bench/conauto AG2 LAT
Where had-sw, had and latin in /tmp/iso_bench/bliss/ are directories with files each containing
a graph in bliss format (see below). AG2 and LAT in /tmp/iso_bench/conauto/
are directories with files each containing a graph in conauto format.
Note that to findAllIsomorphic.csh the format is supplied as the second
parameter ($2) but testIso.csh uses the usual -F flag.
=== Input Formats ===
In general the tool supports 4 graph formats:
1) cnf - described in http://people.sc.fsu.edu/~jburkardt/data/cnf/cnf.html .
Source code to read in org.HRDAG.formats.CNFReader .
Examples in Benchmarks of http://www.satcompetition.org/ mainly "industrial".
Note that on my not-very-powerful (< 1GB memory) laptop
I managed to decompose only examples of up to 50000 vars+clauses.
2) bliss - described in http://www.tcs.hut.fi/Software/bliss/fileformat.shtml .
Examples in http://www.tcs.hut.fi/Software/bliss/benchmarks/index.shtml .
Source code to read in org.HRDAG.formats.BlissReader .
3) conauto - described in chapter 3.8 of http://www.diatel.upm.es/jllopez/tesis/thesis.pdf .
Examples in https://sites.google.com/site/giconauto/home/benchmarks .
Source code to read in org.HRDAG.formats.ConautoReader .
4) rtl - (extension on ISCAS), described in http://logic.pdmi.ras.ru/~basolver/rtl.html .
Examples in http://www.pld.ttu.ee/~maksim/benchmarks/ - only the BENCH series !
Source code to read in org.HRDAG.formats.RTLReader .
Note: I had to add the "DFF" construct to accommodate the examples I found.
In general all result forms and graphs are printed in .dot format
described in http://www.graphviz.org/content/dot-language
and http://www.graphviz.org/Documentation/dottyguide.pdf .
=== Author ===
Benny Godlin
Email: bgodlin@cs.technion.ac.il
Homepage: http://www.cs.technion.ac.il/~bgodlin/
