aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--main.cpp160
1 files changed, 142 insertions, 18 deletions
diff --git a/main.cpp b/main.cpp
index e640b0a..01173e8 100644
--- a/main.cpp
+++ b/main.cpp
@@ -65,6 +65,48 @@ bool is_one_double_edge(map<int, node> graph, int s, int t)
count_edges(graph[s], t) == 1;
}
+/* DFS */
+int count_paths(map <int, node> &graph, int id, int goal, set<int> &visited)
+{
+ visited.insert(id);
+ int paths = 0;
+ for(int i = 0; i < graph[id].neighbors.size(); i++)
+ {
+ if(visited.find(graph[id].neighbors[i].id) == visited.end())
+ {
+ if(graph[id].neighbors[i].id == goal)
+ paths++;
+ else
+ paths += count_paths(graph, graph[id].neighbors[i].id, goal, visited);
+ visited.insert(graph[id].neighbors[i].id);
+ }
+ }
+ return paths;
+}
+
+bool is_done(map<int, node> &graph, int s, int t)
+{
+ if(!is_one_double_edge(graph, s, t))
+ return false;
+ /* count paths to t NOT going directly through t */
+
+ for(int i = 0; i < graph[s].neighbors.size(); i++)
+ {
+ set<int> visited;
+ visited.insert(s); /* new set each loop */
+ if(graph[s].neighbors[i].id != t)
+ {
+ if(count_paths(graph, graph[s].neighbors[i].id, t, visited) > 0)
+ return false;
+ }
+ }
+
+ if(verbose)
+ cerr << "Finished!" << endl;
+
+ return true;
+}
+
bool is_ynode(map<int, node> &graph, int id)
{
node &n = graph[id];
@@ -226,6 +268,99 @@ void erase_edges(map<int, node> &graph, int id_a, int id_b)
b.neighbors.erase(it);
}
+/* *it is modified to point to next element */
+void erase_node(map<int, node> &graph, map<int, node>::iterator &it)
+{
+ if(verbose)
+ cerr << "Pruning node " << it->first << endl;
+
+ node &n = it->second;
+
+ for(int i = 0; i < n.neighbors.size(); i++)
+ erase_edges(graph, it->first, n.neighbors[i].id);
+
+ graph.erase(it++);
+}
+
+void prune(map<int, node> &graph, int s, int t)
+{
+ /* Prune all nodes that are neither S nor S AND:
+ ( has no path to T not passing through S ) OR
+ ( has no path to S not passing through T ) OR
+ ( has only 1 neighbor that is not S )
+ */
+ /* Example:
+
+ x - S - y - T - w
+
+ x and w are pruned.
+ */
+
+ for(map<int, node>::iterator it = graph.begin(); it != graph.end();)
+ {
+ int id = it->first;
+ if(id == s || id == t)
+ {
+ it++;
+ continue;
+ }
+
+ {
+ set<int> visited;
+ visited.insert(t); /* do not allow going through T */
+
+ /* see if there's a path from this node to S */
+ if(count_paths(graph, id, s, visited) == 0)
+ {
+ cerr << "Pruning node " << id << ": no path to S without T" << endl;
+
+ erase_node(graph, it);
+
+ if(dumponprogress)
+ dump(graph);
+
+ continue;
+ }
+ }
+
+ {
+ set<int> visited;
+ visited.insert(s); /* do not allow going through S */
+
+ /* see if there's a path from this node to T */
+ if(count_paths(graph, id, t, visited) == 0)
+ {
+ cerr << "Pruning node " << id << ": no path to T without S" << endl;
+
+ erase_node(graph, it);
+
+ if(dumponprogress)
+ dump(graph);
+
+ continue;
+ }
+ }
+
+ int neighbors = it->second.neighbors.size();
+
+ if(neighbors == 0 || (neighbors == 1 && it->second.neighbors[0].id != s))
+ {
+ cerr << "Pruning node " << id << ": zero or one connection" << endl;
+ erase_node(graph, it);
+
+ if(dumponprogress)
+ dump(graph);
+
+ continue;
+ }
+
+ //if(verbose)
+ //cerr << "Not pruning node " << id << endl;
+
+ it++;
+ }
+}
+
void do_ydelta(map<int, node> &graph, int node_id)
{
/* assumes ynode */
@@ -327,7 +462,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 */
-pair<bool, int> simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
+bool simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool deltay)
{
bool progress = false;
@@ -336,8 +471,6 @@ pair<bool, int> simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool
set<int> open;
open.insert(s);
- int t_visited = 0;
-
while(open.size())
{
for(set<int>::iterator i = open.begin(); i != open.end();)
@@ -359,9 +492,6 @@ pair<bool, int> simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool
edge &ed_ab = *j;
int id_b = ed_ab.id;
- if(id_b == t)
- t_visited++;
-
/* get the connected node */
node &b = graph[ed_ab.id];
@@ -476,29 +606,23 @@ pair<bool, int> simp_iter(map<int,node> &graph, int s, int t, bool ydelta, bool
}
}
- return pair<bool, int>(progress, t_visited);
+ return progress;
}
/* source, sink */
double simp_graph(map<int,node> &graph, int s, int t)
{
- int t_visited = 0;
-
- /* 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))
+ while(!is_done(graph, s, t))
{
- /* iterate over nodes in a breadth-first fashion */
- pair<bool, int> ret = simp_iter(graph, s, t, true, false);
- t_visited = ret.second;
+ prune(graph, s, t);
- bool progress = ret.first;
+ /* iterate over nodes in a breadth-first fashion */
+ bool progress = simp_iter(graph, s, t, true, true);
if(!progress)
{
if(verbose)
- cerr << "Making no progress, saw t " << t_visited << " times. Giving up." << endl;
+ cerr << "Warning: making no progress; giving up!" << endl;
break;
}
}