From 7ecbf44ebe06054ba05ca4525a7865c3e4c814e2 Mon Sep 17 00:00:00 2001
From: Yann Dirson <ydirson@altern.org>
Date: Mon, 9 May 2005 21:54:07 +0000
Subject: [PATCH] keep count of edges "value" after transitive reduction, and
 display them

---
 NEWS                         |  4 ++++
 README                       |  1 -
 graph-includes               |  1 +
 lib/graphincludes/project.pm | 18 +++++++++++-------
 4 files changed, 16 insertions(+), 8 deletions(-)

diff --git a/NEWS b/NEWS
index 6c846c2..205c15c 100644
--- a/NEWS
+++ b/NEWS
@@ -7,6 +7,10 @@ Version 0.7
 
  Other end-user-visible changes
 
+ * Visible edges are now labelled with the number of real dependencies
+   they represent, so we have some visual feedback of transitive
+   reduction.
+
  * Huge performance boost for the transitive reduction.
 
  * When cycles are present, the specific reduction selected is usually
diff --git a/README b/README
index d0cf473..c28e8fb 100644
--- a/README
+++ b/README
@@ -395,7 +395,6 @@ TODO
   - color intra-group edges with the same color as nodes (post-processing ?)
   - allow to request drawing of who in a high-level node points to
     another node (ie. violates some constraint)
-  + label edges with the number of explicit inclusions flowing through them
   - propagate excuses in some way when they are dropped by the transitive reducer
   - investigate candidate tools for hyperbolic layout ?
 - documentation
diff --git a/graph-includes b/graph-includes
index 7c168c8..faa35ef 100644
--- a/graph-includes
+++ b/graph-includes
@@ -164,6 +164,7 @@ foreach my $file ($project->get_dep_origins) {
     print "$file -> $dest";
     my $special = $project->special_edge($file, $dest);
     # special handling for label, as array
+    push @{$special->{label}}, '[' . $project->get_dependency_weight($file, $dest) . ']';
     $special->{label} = join '\n', @{$special->{label}};
     #
     print " [", join (',', map {$_ . '="' . $special->{$_} . '"'} keys %$special), "]" if defined $special;
diff --git a/lib/graphincludes/project.pm b/lib/graphincludes/project.pm
index d5c3ccc..cb47b7f 100644
--- a/lib/graphincludes/project.pm
+++ b/lib/graphincludes/project.pm
@@ -61,6 +61,11 @@ sub get_dependencies {
   my ($origin) = @_;
   keys %{$self->{DEPS}->{$origin}};
 }
+sub get_dependency_weight {
+  my $self = shift;
+  my ($src,$dst) = @_;
+  $self->{DEPS}->{$src}->{$dst};
+}
 
 sub filelabel {
   my $self = shift;
@@ -168,16 +173,12 @@ sub reduce {
     print STDERR "node $node\n" if $graphincludes::params::debug;
     if (defined $reduceddeps{$node}) {
       my %newdeps = %{$reduceddeps{$node}};
+      delete $newdeps{$node};	# remove intra-node dependencies
       my @considered = ($node);
       foreach my $child (keys %{$reduceddeps{$node}}) {
 	# do not explore children already removed, or some circles cause lost edges
 	next unless defined $newdeps{$child};
 	print STDERR " child $child\n" if $graphincludes::params::debug;
-	if ($child eq $node) {
-	  # remove self-deps induced by trivial #include
-	  print STDERR "  --$node\n" if $graphincludes::params::debug;
-	  delete $newdeps{$node};
-	} else {
 	  if (defined $reduceddeps{$child}) {
 	    foreach my $gchild (keys %{$reduceddeps{$child}}) {
 	      if ($gchild ne $node and $gchild ne $child) { # XXX
@@ -186,7 +187,6 @@ sub reduce {
 	      }
 	    }
 	  }
-	}
       }
       $reduceddeps{$node} = \%newdeps;
     }
@@ -240,7 +240,11 @@ sub _suppress {
       $self->{SPECIALEDGES}->{$considered->[0]}->{$node} = {color => "#FFCCCC"};
     } else {
       $self->{_DROPCOUNT}++;
-      # FIXME: make more efficient ?
+      # increment "use count" on each step of the alternate path in @context
+      for (my $i = 0; $i < $#context; $i++) {
+	$reduceddeps->{$context[$i]}->{$context[$i+1]} += $list->{$node};
+      }
+      # remove it
       delete $list->{$node};
     }
     print STDERR "    --$node (", join (',', @context), ")\n" if $graphincludes::params::debug;
-- 
2.11.4.GIT