From e7b25fdad653cebdc4356919803514c3234723b2 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Thu, 15 Nov 2018 21:55:42 -0500 Subject: Refine algorithm termination condition; add pruning Now checks for "proper" completion: no paths from s to t except the one direct edge. Also prunes the graph at each step. --- main.cpp | 160 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 142 insertions(+), 18 deletions(-) (limited to 'main.cpp') 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 graph, int s, int t) count_edges(graph[s], t) == 1; } +/* DFS */ +int count_paths(map &graph, int id, int goal, set &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 &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 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 &graph, int id) { node &n = graph[id]; @@ -226,6 +268,99 @@ void erase_edges(map &graph, int id_a, int id_b) b.neighbors.erase(it); } +/* *it is modified to point to next element */ +void erase_node(map &graph, map::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 &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::iterator it = graph.begin(); it != graph.end();) + { + int id = it->first; + if(id == s || id == t) + { + it++; + continue; + } + + { + set 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 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 &graph, int node_id) { /* assumes ynode */ @@ -327,7 +462,7 @@ bool do_p_transforms(map &graph, int node_id, int other_node = -1) /* ydelta and deltay control whether the Y->delta and delta->Y * transforms are performed, respectively */ -pair simp_iter(map &graph, int s, int t, bool ydelta, bool deltay) +bool simp_iter(map &graph, int s, int t, bool ydelta, bool deltay) { bool progress = false; @@ -336,8 +471,6 @@ pair simp_iter(map &graph, int s, int t, bool ydelta, bool set open; open.insert(s); - int t_visited = 0; - while(open.size()) { for(set::iterator i = open.begin(); i != open.end();) @@ -359,9 +492,6 @@ pair simp_iter(map &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 simp_iter(map &graph, int s, int t, bool ydelta, bool } } - return pair(progress, t_visited); + return progress; } /* source, sink */ double simp_graph(map &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 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; } } -- cgit v1.1