From 08ad4a86bab882c519b805204ffaeb3163ce642e Mon Sep 17 00:00:00 2001
From: Ian Jackson <ijackson@chiark.greenend.org.uk>
Date: Mon, 14 Jan 2019 13:13:42 +0000
Subject: [PATCH] wip cc

---
 parse-input-graph | 44 +++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 43 insertions(+), 1 deletion(-)

diff --git a/parse-input-graph b/parse-input-graph
index f970808..3ea008f 100755
--- a/parse-input-graph
+++ b/parse-input-graph
@@ -3,6 +3,7 @@
 use strict;
 use Carp;
 use Data::Dumper;
+use Graph;
 
 our %region;
 # $region{NAME}{Colour}
@@ -13,6 +14,8 @@ our %region;
 # $region{NAME}{Adj}[]{Regexp}
 # $region{NAME}{Adj}[]{Dikes}
 # $region{NAME}{Adj}[]{L}
+# computed by dual():
+# %region{NAME}{Adj}[]{Vertices}[0..1]
 
 our %adj;
 # $adj{EARLIER}{LATER}{Dikes}
@@ -139,7 +142,46 @@ sub dual () {
   # We want to turn the graph from a graph on the regions, to
   # one where the nodes are the vertices of region boundaries.
   #
-  # Each adjacency in 
+  # Each adjacency in %adj has two ends, each of which is at
+  # such a vertex.  We need to identify which of these vertices
+  # are the same.  We do this by assigning an id to each vertex.
+  #
+  # This is actually a DJF, where the to-be-vertices are the connected
+  # components, and the edges indicate that two vertices are the same.
+
+  my $g = Graph::Undirected->new(unionfind => 1);
+
+  # vertex "<Region Name> # <i>" is the vertex at the
+  # anticlockwise end of the i'th listed edge of Region Name.
+
+  foreach my $ra (sort keys %region) {
+    my $adjsa = $region{$ra}{Adj};
+    foreach my $adjia (0..$#$adjsa) {
+      my $adja = $adjsa->[$adjia];
+      my $va = "$ra # $adjia";
+      # $va is the vertex at the anticlockwise end
+      # of edge no.$adjia of region $ra
+      my $rb = $adja->{Name};
+      # $rb is the region on the other side of that edge
+      my $adjsb = $region{$rb}{Adj};
+      foreach my $adjib (0..$#$adjsb) {
+	my $adjb = $adjsb->[$adjib];
+	next unless $adjb->{Name} eq $ra;
+	# $adjb is the same edge seen from the other side
+	my $adjibc = ($adjib + 1) % @$adjsb;
+	my $vb = "$rb # $adjibc";
+	# $vb is the vertex at the *clockwise* end
+	# of that same edge, which is edge no $adjib of region $rb
+	print STDERR "vertex $va = $vb\n";
+	$g->add_edge($va,$vb);
+	last;
+      }
+    }
+  }
+  foreach my $cc ($g->connected_components) {
+    print STDERR "CC:\n";
+    print STDERR "    $_\n" foreach @$cc;
+  }
 }
 
 sub o { print @_ or die $!; }
-- 
2.30.2