Update things

Need to refine termination condition. Apart from that, it's fairly robust.

4 files changed, 125 insertions, 101 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..2f6fb3c
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,10 @@
+CFLAGS=-Og -g
+CXXFLAGS=$(CFLAGS)
+
+all: genrand circgraph Makefile
+genrand: genrand.o
+circgraph: main.o
+	$(CXX) -o $@ $< $(CFLAGS)
+
+clean:
+	rm -f genrand circgraph *.o
diff --git a/genrand.c b/genrand.c
index 47362eb..acc26a6 100644
--- a/genrand.c
+++ b/genrand.c
@@ -14,6 +14,15 @@ int main(int argc, char *argv[])
     srand(time(0));
 
     printf("a b\n");
+    printf("a b 1\n");
     for(int i = 0; i < edges; i++)
-        printf("%c %c 1\n", 'a' + rand() % 26, 'a' + rand() % 26);
+    {
+        char a, b;
+        a = rand() % 26;
+        do {
+            b = rand() % 26;
+        } while(b == a);
+
+        printf("%c %c 1\n", 'a' + a, 'a' + b);
+    }
 }
diff --git a/main.cpp b/main.cpp
index 0064a92..78e2059 100644
--- a/main.cpp
+++ b/main.cpp
@@ -32,20 +32,45 @@ struct node {
     vector<edge> neighbors;
 };
 
-bool is_done(map<int, node> graph, int s, int t)
+vector<edge>::iterator find_edge(node &n, int id)
+{
+    for(vector<edge>::iterator it = n.neighbors.begin(); it != n.neighbors.end(); it++)
+        if(it->id == id)
+            return it;
+    return n.neighbors.end();
+}
+
+bool is_doubly_connected(map<int, node> &graph, int a, int b)
+{
+    return find_edge(graph[a], b) != graph[a].neighbors.end() &&
+        find_edge(graph[b], a) != graph[b].neighbors.end();
+}
+
+int count_edges(node &n, int id)
+{
+    int count = 0;
+    for(vector<edge>::iterator it = n.neighbors.begin(); it != n.neighbors.end(); it++)
+        if(it->id == id)
+            count++;
+    return count;
+}
+
+bool is_one_double_edge(map<int, node> graph, int s, int t)
 {
-    return graph[s].neighbors.size() == 1 &&
-        graph[s].neighbors[0].id == t &&
-        graph[t].neighbors.size() == 1 &&
-        graph[t].neighbors[0].id == s;
+    return is_doubly_connected(graph, s, t) &&
+        count_edges(graph[s], t) == 1;
 }
 
-bool is_ynode(node &n)
+bool is_ynode(map<int, node> &graph, int id)
 {
+    node &n = graph[id];
     return n.neighbors.size() == 3 &&
         n.neighbors[0].id != n.neighbors[1].id &&
         n.neighbors[1].id != n.neighbors[2].id &&
-        n.neighbors[0].id != n.neighbors[2].id;
+        n.neighbors[0].id != n.neighbors[2].id &&
+        is_doubly_connected(graph, id, n.neighbors[0].id) &&
+        is_doubly_connected(graph, id, n.neighbors[1].id) &&
+        is_doubly_connected(graph, id, n.neighbors[2].id);
 }
 
 double combine_s(double a, double b)
@@ -84,40 +109,25 @@ void dump_graph(map<int, node> graph)
 
 void dump_dot(map<int, node> graph)
 {
-    cout << "digraph a {" << endl;
+    cout << "graph a {" << endl;
     for(map<int, node>::iterator it = graph.begin(); it != graph.end(); it++)
     {
         //cerr << "Node " << it->first << ": ";
         struct node &e = it->second;
         for(vector<edge>::iterator j = e.neighbors.begin(); j != e.neighbors.end(); j++)
         {
-            cout << it->first << " -> " <<  j->id << " [label=\"" << j->weight << "\"];" << endl;
+            //cout << graph[it->first].name << " -> " <<  graph[j->id].name << " [label=\"" << j->weight << "\"];" << endl;
+            if(is_doubly_connected(graph, it->first, j->id))
+                cout << it->first << " -- " << j->id << " [label=\"" << j->weight << "\"];" << endl;
         }
         //cerr << endl;
     }
     cout << "}" << endl;
 }
 
-vector<edge>::iterator find_edge(node &n, int id)
-{
-    for(vector<edge>::iterator it = n.neighbors.begin(); it != n.neighbors.end(); it++)
-        if(it->id == id)
-            return it;
-    return n.neighbors.end();
-}
-
-int count_edges(node &n, int id)
-{
-    int count = 0;
-    for(vector<edge>::iterator it = n.neighbors.begin(); it != n.neighbors.end(); it++)
-        if(it->id == id)
-            count++;
-    return count;
-}
-
 void insert_edge(map<int, node> &graph, int id_a, int id_b, double weight)
 {
-    cerr << "Inserting edge " << id_a << "-" << id_b << endl;
+    //cerr << "Inserting edge " << id_a << "-" << id_b << endl;
     node &a = graph[id_a], &b = graph[id_b];
 
     edge ab, ba;
@@ -149,7 +159,7 @@ node &insert_node_if_new(map<int, node> &graph, int id)
 
 void erase_edges(map<int, node> &graph, int id_a, int id_b)
 {
-    cerr << "Erasing edges " << id_a << "-" << id_b << endl;
+    //cerr << "Erasing edges " << id_a << "-" << id_b << endl;
     node &a = graph[id_a], &b = graph[id_b];
 
     vector<edge>::iterator it;
@@ -204,6 +214,7 @@ void do_deltay(map<int, node> &graph, int id_a, int id_b, int id_c)
     int id_d = graph.rbegin()->first + 1;
 
     insert_node(graph, id_d);
+    //graph[id_d].name = "Ynode";
 
     insert_edge(graph, id_a, id_d, w1);
     insert_edge(graph, id_b, id_d, w2);
@@ -257,7 +268,7 @@ bool do_p_transforms(map<int, node> &graph, int node_id, int other_node = -1)
 
 /* ydelta and deltay control whether the Y->delta and delta->Y
  * transforms are performed, respectively */
-bool simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
+pair<bool, int> simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
 {
     bool progress = false;
 
@@ -266,6 +277,8 @@ bool simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
     set<int> open;
     open.insert(s);
 
+    int t_visited = 0;
+
     while(open.size())
     {
         for(set<int>::iterator i = open.begin(); i != open.end();)
@@ -273,7 +286,10 @@ bool simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
             int id_a = *i;
             node &a = graph[id_a];
 
-            //cerr << "Visiting node " << id_a << endl;
+            cerr << "Visiting node " << id_a << endl;
+
+            if(id_a == t)
+                t_visited++;
 
             vector<edge> &neighbors = a.neighbors;
 
@@ -289,7 +305,7 @@ bool simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
                 /* get the connected node */
                 node &b = graph[ed_ab.id];
 
-                //cerr << "Connected node " << ed_ab.id << " has " << b.neighbors.size() << " emanating edges." << endl;
+                cerr << "Connected node " << ed_ab.id << " has " << b.neighbors.size() << " emanating edges." << endl;
 
                 /* perform S transform */
                 if(id_b != s && id_b != t &&
@@ -300,27 +316,30 @@ bool simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
                     edge &ed_bc = b.neighbors[0].id == id_a ? b.neighbors[1] : b.neighbors[0];
                     int id_c = ed_bc.id;
 
-                    cerr << "Performing S-transform on edges " << id_a << "-" << id_b << "-" << id_c << endl;
+                    if(is_doubly_connected(graph, id_b, id_c))
+                    {
+                        cerr << "Performing S-transform on edges " << id_a << "-" << id_b << "-" << id_c << endl;
 
-                    /* note that we have to do the replacement on both
-                     * nodes, because edges are directed */
-                    double new_weight = combine_s(ed_ab.weight, ed_bc.weight);
+                        /* note that we have to do the replacement on both
+                         * nodes, because edges are directed */
+                        double new_weight = combine_s(ed_ab.weight, ed_bc.weight);
 
-                    ed_ab.id = id_c;
-                    ed_ab.weight = new_weight;
+                        ed_ab.id = id_c;
+                        ed_ab.weight = new_weight;
 
-                    node &c = graph[ed_bc.id];
+                        node &c = graph[ed_bc.id];
 
-                    /* find the edge that goes to node b (with id_b) */
-                    edge &ed_cb = *find_edge(c, id_b);
+                        /* find the edge that goes to node b (with id_b) */
+                        edge &ed_cb = *find_edge(c, id_b);
 
-                    ed_cb.id = id_a;
-                    ed_cb.weight = new_weight;
+                        ed_cb.id = id_a;
+                        ed_cb.weight = new_weight;
 
-                    /* node B becomes an orphan node */
-                    dump_dot(graph);
+                        /* node B becomes an orphan node */
+                        dump_dot(graph);
 
-                    progress = true;
+                        progress = true;
+                    }
                 }
 
                 /* Don't mark if already visited */
@@ -336,7 +355,7 @@ bool simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
             if(ydelta)
             {
                 /* Try the Y->delta transform */
-                if(id_a != s && id_a != t && is_ynode(a))
+                if(id_a != s && id_a != t && is_ynode(graph, id_a))
                 {
                     cerr << "Performing Y-delta transform on node " << id_a << endl;
 
@@ -368,7 +387,7 @@ bool simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
                         int id_c = a.neighbors[j].id;
 
                         node &b = graph[id_b];
-                        if(find_edge(b, id_c) != b.neighbors.end() &&
+                        if(is_doubly_connected(graph, id_b, id_c) &&
                            count_edges(b, id_c) == 1)
                         {
                             cerr << "Performing delta-Y transform on " << id_a << ", " << id_b << ", " << id_c << endl;
@@ -391,18 +410,28 @@ bool simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
         }
     }
 
-    return progress;
+    return pair<bool, int>(progress, t_visited);
 }
 
 /* source, sink */
 double simp_graph(map<int,node> &graph, int s, int t)
 {
-    dump_dot(graph);
+    int t_visited = 0;
 
-    while(!is_done(graph, s, t))
+    /* Need to refine this termination condition. There must be
+     * exactly one path between s and t... the current condition isn't
+     * sufficient. */
+
+    while(!(is_one_double_edge(graph, s,t) && t_visited == 1))
     {
         /* iterate over nodes in a breadth-first fashion */
-        simp_iter(graph, s, t, true, true);
+        pair<bool, int> ret = simp_iter(graph, s, t, true, false);
+        t_visited = ret.second;
+        if(!ret.first)
+        {
+            cerr << "Making no progress, saw t " << t_visited << " times." << endl;
+            return 0;
+        }
     }
 
     return graph[s].neighbors[0].weight;
@@ -445,6 +474,9 @@ int main()
         id_a = get_node_id(names, a, id_counter);
         id_b = get_node_id(names, b, id_counter);
 
+        if(id_a == id_b)
+            cerr << "WARNING: Self-loop!" << endl;
+
         insert_node_if_new(graph, id_a);
         insert_node_if_new(graph, id_b);
 
@@ -458,6 +490,8 @@ int main()
     id_s = names.at(s);
     id_t = names.at(t);
 
+    dump_dot(graph);
+
     double eq = simp_graph(graph, id_s, id_t);
 
     cerr << "Equivalent resistance: " << eq << endl;
diff --git a/test6.txt b/test6.txt
index 28c772b..567126c 100644
--- a/test6.txt
+++ b/test6.txt
@@ -1,51 +1,22 @@
 a b
-t h 1
-t t 1
-s w 1
-g y 1
-w e 1
-i t 1
-n e 1
-o j 1
-q v 1
-i k 1
-q g 1
-z o 1
-t r 1
+a b 1
+b r 1
+t a 1
 w k 1
-c s 1
-a e 1
-a v 1
-u v 1
-v u 1
-y a 1
-u t 1
-x i 1
-t j 1
-e n 1
-a l 1
-s n 1
-d q 1
-j t 1
-f y 1
-q i 1
-o i 1
-f s 1
-n o 1
-k z 1
-c k 1
-d k 1
-t y 1
-h b 1
-q o 1
-a n 1
-a s 1
-j u 1
-p f 1
-d u 1
-c v 1
-d u 1
-m r 1
-h i 1
-k c 1
-m s 1
+c j 1
+r j 1
+b q 1
+b m 1
+p g 1
+e j 1
+d i 1
+w l 1
+t w 1
+r w 1
+o g 1
+g u 1
+h x 1
+q h 1
+v a 1
+l e 1
+u i 1