From 617fe9cba506a816a313ba621c726347a6b19aa1 Mon Sep 17 00:00:00 2001
From: Petr Baudis <pasky@ucw.cz>
Date: Mon, 7 Feb 2011 17:13:00 +0100
Subject: [PATCH] Create virtual ancestors for joints of components

---
 TODO              |  3 ---
 matrix_to_tree.sh | 18 +++++++++++++++---
 tree_render.sh    |  4 +++-
 3 files changed, 18 insertions(+), 7 deletions(-)

diff --git a/TODO b/TODO
index 90c04c8..294b7b4 100644
--- a/TODO
+++ b/TODO
@@ -1,6 +1,3 @@
-General:
-* Create virtual tree nodes for common ancestors.
-
 Methods:
 * cFast compression
 * Classic diff
diff --git a/matrix_to_tree.sh b/matrix_to_tree.sh
index c14ee59..589657f 100755
--- a/matrix_to_tree.sh
+++ b/matrix_to_tree.sh
@@ -1,6 +1,7 @@
 #!/bin/sh
 # Normalize the matrix (on stdin), removing the diagonal and merging
-# complementary cells and producing a minimum spanning tree (on stdout).
+# complementary cells and producing a minimum spanning tree with virtual
+# nodes per component join (on stdout).
 
 cat |
 	egrep -v '^[^ ]* (.) \1$' | # weed out edges to self
@@ -14,9 +15,20 @@ cat |
 			}
 		} }' | # merge A_ij and A_ji
 	sort -f | # lowest weights first (they have highest priority)
-	perl -nle 'BEGIN { our @c = (0, 1, 2, 3, 4, 5, 6); our @e; }
+	perl -nle 'BEGIN { our @c = (0, 1, 2, 3, 4, 5, 6); our @v; my $vv = 0; }
 		chomp; my ($w, $a, $b) = split / /;
 		$c[$a] != $c[$b] or next;
+		# Each graph component is either a singleton, or
+		# has "virtual head", merging two sub-components;
+		# virtual heads have negative id, assigned sequentially.
+		my $va = $e[$c[$a]] || $a; # virtual nodes
+		my $vb = $e[$c[$b]] || $b;
+		#print "\n$a($c[$a]):$va -- $b($c[$b]):$vb";
 		my $d = $c[$b];
 		for (0..$#c) { $c[$_] == $d and $c[$_] = $c[$a]; }
-		print "$w $a $b";' # remove reflexive edges and extract minimum spanning tree
+		my $vc = --$vv;
+		$e[$c[$a]] = $vc;
+		$w /= 2;
+		print "$w $va $vc";
+		print "$w $vb $vc";
+		' # remove reflexive edges and extract minimum spanning tree
diff --git a/tree_render.sh b/tree_render.sh
index ffeec22..e9632dc 100755
--- a/tree_render.sh
+++ b/tree_render.sh
@@ -12,6 +12,8 @@ cat |
 			print "graph philo {";
 		}
 		chomp; my ($w, $a, $b) = split / /;
-		printf "%s -- %s [w=%f, label=\"%.3f\"]\n", $l[$a], $l[$b], $w, $w;
+		my $la = $a < 0 ? "$a" : $l[$a];
+		my $lb = $b < 0 ? "$b" : $l[$b];
+		printf "%s -- %s [w=%f, label=\"%.3f\"]\n", $la, $lb, $w, $w;
 		END { print "}"; }' |
 	dot -Tpng
-- 
2.11.4.GIT