aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFranklin Wei <me@fwei.tk>2018-11-11 21:23:31 -0500
committerFranklin Wei <me@fwei.tk>2018-11-11 21:23:31 -0500
commitb79dbbe6f8514469c07695a6f85e555332e56ca1 (patch)
tree745c925d7018727071e06768ce563008cf53e6b5
downloadcircgraph-b79dbbe6f8514469c07695a6f85e555332e56ca1.zip
circgraph-b79dbbe6f8514469c07695a6f85e555332e56ca1.tar.gz
circgraph-b79dbbe6f8514469c07695a6f85e555332e56ca1.tar.bz2
circgraph-b79dbbe6f8514469c07695a6f85e555332e56ca1.tar.xz
Initial commit
A mostly functional proof-of-concept
-rw-r--r--README.md30
-rw-r--r--main.cpp302
-rw-r--r--test1.txt6
-rw-r--r--test2.txt5
-rw-r--r--test3.txt5
-rwxr-xr-xtestgraph.sh4
6 files changed, 352 insertions, 0 deletions
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..de2f5e7
--- /dev/null
+++ b/README.md
@@ -0,0 +1,30 @@
+# circgraph
+
+This is a tool for calculating equivalent
+resistances/impedances/capacitances for a circuit (represented as a
+graph, hence "circuit graph"), written in C++.
+
+# Motivation
+
+This program exists for three reasons: boredom, a desire to brush up
+on my C++, and -- most importantly -- laziness. Why do tedious
+arithmetic when you can spend hours writing a program to do it for
+you?
+
+# Usage
+
+Compile with:
+
+```
+g++ main.cpp -o circgraph
+```
+
+`circgraph` takes input from stdin in the following format:
+
+<source_node> <sink_node>
+<node1> [<neighbor1> <resistance2>]...
+<node2>
+...
+<noden>
+
+See the `testX.txt` files for more.
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..a239c9a
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,302 @@
+#include <iostream>
+#include <map>
+#include <queue>
+#include <set>
+#include <sstream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+struct edge {
+ int id; /* connected node */
+ double weight;
+};
+
+struct node {
+ vector<edge> neighbors;
+};
+
+bool is_done(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;
+}
+
+bool is_ynode(node &n)
+{
+ 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;
+}
+
+double combine_s(double a, double b)
+{
+ /* change for capacitance */
+ return a + b;
+}
+
+double combine_p(double a, double b)
+{
+ return 1 / ( 1 / a + 1 / b );
+}
+
+void dump_graph(map<int, node> graph)
+{
+ 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++)
+ cerr << j->id << " ";
+ cerr << endl;
+ }
+}
+
+void dump_dot(map<int, node> graph)
+{
+ cout << "digraph 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;
+ }
+ //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();
+}
+
+double combine_ydelta(double w1, double w2, double w3, double opp)
+{
+ double p = w1 * w2 + w1 * w3 + w2 * w3;
+ return p / opp;
+}
+
+void insert_edge(map<int, node> &graph, int id_a, int id_b, double weight)
+{
+ cerr << "Inserting edge " << id_a << "-" << id_b << endl;
+ node &a = graph[id_a], &b = graph[id_b];
+
+ edge ab, ba;
+ ab.id = id_b;
+ ab.weight = weight;
+
+ ba.id = id_a;
+ ba.weight = weight;
+
+ a.neighbors.push_back(ab);
+ b.neighbors.push_back(ba);
+}
+
+void do_ydelta(map<int, node> &graph, int node_id)
+{
+ /* assumes ynode */
+ node &n = graph[node_id];
+
+ double w1 = n.neighbors[0].weight,
+ w2 = n.neighbors[1].weight,
+ w3 = n.neighbors[2].weight;
+
+ double wa = combine_ydelta(w1, w2, w3, w1);
+ double wb = combine_ydelta(w1, w2, w3, w2);
+ double wc = combine_ydelta(w1, w2, w3, w3);
+
+ /* add delta edges */
+ insert_edge(graph, n.neighbors[1].id, n.neighbors[2].id, wa);
+ insert_edge(graph, n.neighbors[0].id, n.neighbors[2].id, wb);
+ insert_edge(graph, n.neighbors[0].id, n.neighbors[1].id, wc);
+
+ /* delete Y edges */
+ for(int i = 0; i < 3; ++i)
+ {
+ node &neighbor = graph[n.neighbors[i].id];
+ neighbor.neighbors.erase(find_edge(neighbor, node_id));
+ }
+
+ n.neighbors.clear();
+}
+
+void do_p_transforms(map<int, node> &graph, int node_id, int other_node = -1)
+{
+ node &a = graph[node_id];
+
+ /* perform P transform: O(n^2)? */
+ for(vector<edge>::iterator i = a.neighbors.begin(); i < a.neighbors.end(); i++)
+ {
+ for(vector<edge>::iterator j = a.neighbors.begin(); j < a.neighbors.end(); j++)
+ {
+ if(i == j)
+ continue;
+
+ if(i->id == j->id &&
+ (other_node < 0 || other_node == i->id))
+ {
+ cerr << "Performing P-transform on duplicate " << node_id << "-" << i->id << " edges." << endl;
+
+ /* remove edge k */
+ double new_weight = combine_p(i->weight, j->weight);
+
+ i->weight = new_weight;
+
+ /* will be incremented */
+ j = a.neighbors.erase(j) - 1;
+
+ /* recurse to handle the opposite direction */
+ do_p_transforms(graph, i->id, node_id);
+
+ dump_dot(graph);
+ }
+ }
+ }
+}
+
+void simp_iter(map<int,node> &graph, int s, int t, bool ydelta)
+{
+ /* breadth-first search */
+ set<int> visited;
+ set<int> open;
+ open.insert(s);
+
+ while(open.size())
+ {
+ for(set<int>::iterator i = open.begin(); i != open.end();)
+ {
+ int id_a = *i;
+ node &a = graph[id_a];
+
+ cerr << "Visiting node " << id_a << endl;
+
+ vector<edge> &neighbors = a.neighbors;
+
+ /* First remove duplicate edges with the P transform */
+ do_p_transforms(graph, id_a);
+
+ /* Loop over neighbors */
+ for(vector<edge>::iterator j = neighbors.begin(); j < neighbors.end(); j++)
+ {
+ edge &ed_ab = *j;
+ int id_b = ed_ab.id;
+
+ /* get the connected node */
+ node &b = graph[ed_ab.id];
+
+ cerr << "Connected node " << ed_ab.id << " has " << b.neighbors.size() << " emanating edges." << endl;
+
+ /* perform S transform */
+ if(id_b != s && id_b != t &&
+ b.neighbors.size() == 2 &&
+ b.neighbors[0].id != b.neighbors[1].id)
+ {
+ /* Replace A-B-C with A-C */
+ 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;
+
+ /* 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;
+
+ 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);
+
+ ed_cb.id = id_a;
+ ed_cb.weight = new_weight;
+
+ /* node B becomes an orphan node */
+ dump_dot(graph);
+ }
+
+ /* Don't mark if already visited */
+ if(visited.find(ed_ab.id) != visited.end())
+ continue;
+
+ /* Mark neighbors for next iteration. We don't check
+ * for the node already being in the open set, because
+ * it is a set. */
+ open.insert(ed_ab.id);
+ }
+
+ if(ydelta)
+ {
+ /* Try the Y->delta transform */
+ if(is_ynode(a))
+ {
+ cerr << "Performing Y-delta transform on node " << id_a << endl;
+
+ do_ydelta(graph, id_a);
+
+ dump_dot(graph);
+ }
+ }
+
+ visited.insert(id_a);
+
+ /* hack */
+ set<int>::iterator next = ++i;
+ open.erase(--i);
+ i = next;
+ }
+ }
+}
+
+/* source, sink */
+void simp_graph(map<int,node> &graph, int s, int t)
+{
+ dump_dot(graph);
+
+ while(!is_done(graph, s, t))
+ {
+ /* iterate over nodes in a breadth-first fashion */
+ simp_iter(graph, s, t, true);
+ }
+}
+
+int main()
+{
+ /* construct graph from adjacency list */
+ map<int, node> graph;
+ string line;
+ int s, t;
+ cin >> s >> t;
+
+ while(getline(cin, line))
+ {
+ stringstream ss(line);
+
+ int node_id;
+ struct node n;
+ ss >> node_id;
+
+ struct edge e;
+ while(ss >> e.id && ss >> e.weight)
+ {
+ cerr << "Adding neighbor " << e.id << " with weight " << e.weight << endl;
+
+ n.neighbors.push_back(e);
+ }
+
+ graph.insert(std::pair<int, node>(node_id, n));
+ }
+
+ simp_graph(graph, s, t);
+}
diff --git a/test1.txt b/test1.txt
new file mode 100644
index 0000000..0dea2d9
--- /dev/null
+++ b/test1.txt
@@ -0,0 +1,6 @@
+1 5
+1 2 1
+2 1 1 3 1 4 1
+3 2 1 4 1
+4 2 1 3 1 5 1
+5 4 1
diff --git a/test2.txt b/test2.txt
new file mode 100644
index 0000000..4d4506e
--- /dev/null
+++ b/test2.txt
@@ -0,0 +1,5 @@
+1 4
+1 2 1 3 1
+2 1 1 3 1 4 1
+3 1 1 2 1 4 1
+4 3 1 2 1
diff --git a/test3.txt b/test3.txt
new file mode 100644
index 0000000..007cb00
--- /dev/null
+++ b/test3.txt
@@ -0,0 +1,5 @@
+1 4
+1 2 4 3 3.125
+2 1 4 3 3 4 4
+3 1 3.125 2 3 4 5
+4 3 5 2 4
diff --git a/testgraph.sh b/testgraph.sh
new file mode 100755
index 0000000..f184db9
--- /dev/null
+++ b/testgraph.sh
@@ -0,0 +1,4 @@
+#!/bin/bash
+cat - | gvpack -u > graph.dot
+dot -Tpdf -o out.pdf graph.dot
+evince out.pdf