GREAL  software for the Graph Realization
Problem

The Graph Realization problem:
Graph Realization is the problem of
constructing a tree from a set of its edgelabeled paths. More formally,
Given subsets P_{1},..P_{n} of {0,..,m1}, find a tree T=(V,E)
with E={0,..,m1} such that every P_{i} is a path in T, or determine
that no such tree exists.
Graph Realization was first defined by Tutte [2]. Several
polynomial algorithms for the problem were introduced in [1,3,4]. Graph Realization recently came back to awareness
in computational molecular biology, in problems related to haplotype inference
under the perfect phylogeny model [5].


About GREAL:
GREAL is an implementation of the algorithm for
Graph Realization of Gavril and Tamari [1]. This algorithm
runs in O(nm^{2})time and O(nm) space.
GREAL was written in C++. We supply here executables for Windows, Linux
and SunOS. In addition to its standard interface, GREAL outputs the solution
tree in a format that allows visualization using a graph drawing software
[6]. See the Read Me file for details.
GREAL was written by Tamar Barzuza, under the supervision by Dr. Itsik Pe’er, Prof. Jacques Beckmann (Weizmann
Institute) and Prof. Ron Shamir
(Tel Aviv University).
The GREAL software is freely available for academic
use. Interested users (academic and commercial) should contact
Ron Shamir (rshamir AT tau dot ac dot il)


An example:
For the ground set {0,1,2,3,4}and the subests P_{1}={1,2,3,4},P_{2}={0,2,3}
and P_{3}={0,1}, the graph realization is:
Notice that we merge a path of dependent edges into one edge, such as 2 and 3 in this example. Edges are
dependent if they always appear together in P_{1},..P_{n}.
Using the GREAL input and output formats (see Read Me), the input is the following hypergraph:
0 
1 
1 
1 
1 
1 
0 
1 
1 
0 
1 
1 
0 
0 
0 
It indicates that E={0,..4} and that T must realize the paths {{1,2,3,4},{0,2,3},{0,1}}.
This input is given in hypergraph.txt.
The output of GREAL is:
actual vertices: 
0 = 0 
1 = 1 
2 = 2 3 
3 = 4 
realization: 
1 
1 
1 
0 
2 
1 
1 
1 
1 
1 
1 
1 
1 
1 
3 
0 
1 
1 
1 
1 
2 
1 
3 
1 
1 

The realization matrix is the adjacency matrix of T. It indicates that
V={0,..4} and that E is constructed form edges (0,1),(2,4),(0,3),(0,4) with
initial labeling of 1,3,0,2 respectively.
The actual vertices list indicates that this labeling of E should be changed
such that 0 remains 0, 1 remains 1, 2 is replaced by 2,3; and 3 is replaced
by 4. The tree drawn above is a result of running neato on this
output of GREAL.
For more details see the Read
Me file. For a more complex example of a hypergraph see
hypergraph.txt.


References:


[1] F. Gavril and R. Tamari (1983) An algorithm
for constructing edgetrees from hypergraphs. Networks, 13:377388
[2] W. T.
Tutte (1958) A homotopy theorem for matroids I and II. Transactions of
the American Mathematical Society, 18:144174
[3] W. T.
Tutte (1960) An algoritm for determining whether a given binary matroid
is graphic. Proceedings of the American Mathematical Society, 11:905917
[4] R. E.
Bixby and D. K. Wagner (1988) An almost lineartime algorithm for graph
realization. Mathematics of Operations Research, 13:99123
[5] Gusfield
D (2002) Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient
Solutions. Proceedings of the Sixth Annual International Conference on Computational
Biology (RECOMB '02), 166175
[6] http://www.research.att.com/sw/tools/graphviz/

