aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFranklin Wei <me@fwei.tk>2018-11-12 13:26:04 -0500
committerFranklin Wei <me@fwei.tk>2018-11-12 13:26:04 -0500
commitbb87e0d168d01ca4a02d6d438f165e6f20bebbf0 (patch)
treeca7a66e1198aa77669a476eb7c1de901562c180d
parentea945ff4ffae82bb1ee77ec28ce373ba4525d283 (diff)
downloadcircgraph-bb87e0d168d01ca4a02d6d438f165e6f20bebbf0.zip
circgraph-bb87e0d168d01ca4a02d6d438f165e6f20bebbf0.tar.gz
circgraph-bb87e0d168d01ca4a02d6d438f165e6f20bebbf0.tar.bz2
circgraph-bb87e0d168d01ca4a02d6d438f165e6f20bebbf0.tar.xz
Update things
Need to refine termination condition. Apart from that, it's fairly robust.
-rw-r--r--Makefile10
-rw-r--r--genrand.c11
-rw-r--r--main.cpp136
-rw-r--r--test6.txt69
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