monotone

monotone Mtn Source Tree

Root/src/graph.cc

1// Copyright (C) 2006 Nathaniel Smith <njs@pobox.com>
2//
3// This program is made available under the GNU GPL version 2.0 or
4// greater. See the accompanying file COPYING for details.
5//
6// This program is distributed WITHOUT ANY WARRANTY; without even the
7// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8// PURPOSE.
9
10#include "base.hh"
11#include <map>
12#include <utility>
13#include <list>
14#include <boost/shared_ptr.hpp>
15
16#include "sanity.hh"
17#include "graph.hh"
18#include "safe_map.hh"
19#include "numeric_vocab.hh"
20#include "hash_map.hh"
21#include "vocab_hash.hh"
22#include "rev_height.hh"
23#include "transforms.hh"
24
25using boost::shared_ptr;
26using std::string;
27using std::vector;
28using std::set;
29using std::pair;
30using std::map;
31using std::multimap;
32using std::make_pair;
33using std::list;
34
35using hashmap::hash_set;
36
37void
38get_reconstruction_path(id const & start,
39 reconstruction_graph const & graph,
40 reconstruction_path & path)
41{
42 // This function does a breadth-first search from a starting point, until it
43 // finds some node that matches an arbitrary condition. The intended usage
44 // is for finding reconstruction paths in a database of deltas -- we start
45 // from the node we want to reconstruct, and follow existing deltas outward
46 // until we reach a full-text base. We return the shortest path from
47 // 'start' to a base version.
48 //
49 // The algorithm involves keeping a set of parallel linear paths, starting
50 // from 'start', that move forward through the DAG until we hit a base.
51 //
52 // On each iteration, we extend every active path by one step. If our
53 // extension involves a fork, we duplicate the path. If any path
54 // contains a cycle, we fault.
55 //
56 // If, by extending a path C, we enter a node which another path
57 // D has already seen, we kill path C. This avoids the possibility of
58 // exponential growth in the number of paths due to extensive forking
59 // and merging.
60
61 // Long ago, we used to do this with the boost graph library, but it
62 // involved loading too much of the storage graph into memory at any
63 // moment. this imperative version only loads the descendents of the
64 // reconstruction node, so it much cheaper in terms of memory.
65
66 set<id> seen_nodes;
67 vector< shared_ptr<reconstruction_path> > live_paths;
68
69 {
70 shared_ptr<reconstruction_path> pth0 = shared_ptr<reconstruction_path>(new reconstruction_path());
71 pth0->push_back(start);
72 live_paths.push_back(pth0);
73 seen_nodes.insert(start);
74 }
75
76 shared_ptr<reconstruction_path> selected_path;
77
78 while (!selected_path)
79 {
80 vector< shared_ptr<reconstruction_path> > next_paths;
81
82 I(!live_paths.empty());
83 for (vector<shared_ptr<reconstruction_path> >::const_iterator i = live_paths.begin();
84 i != live_paths.end(); ++i)
85 {
86 shared_ptr<reconstruction_path> pth = *i;
87 id tip = pth->back();
88
89 if (graph.is_base(tip))
90 {
91 selected_path = pth;
92 break;
93 }
94 else
95 {
96 // This tip is not a root, so extend the path.
97 set<id> next;
98 graph.get_next(tip, next);
99 I(!next.empty());
100
101 // Replicate the path if there's a fork.
102 bool first = true;
103 for (set<id>::const_iterator j = next.begin();
104 j != next.end(); ++j)
105 {
106 if (global_sanity.debug_p())
107 L(FL("considering %s -> %s") % tip % *j);
108 if (seen_nodes.find(*j) == seen_nodes.end())
109 {
110 shared_ptr<reconstruction_path> pthN;
111 if (first)
112 {
113 pthN = pth;
114 first = false;
115 }
116 else
117 {
118 // NOTE: this is not the first iteration of the loop, and
119 // the first iteration appended one item to pth. So, we
120 // want to remove one before we use it. (Why not just
121 // copy every time? Because that makes this into an
122 // O(n^2) algorithm, in the common case where there is
123 // only one direction to go at each stop.)
124 pthN = shared_ptr<reconstruction_path>(new reconstruction_path(*pth));
125 I(!pthN->empty());
126 pthN->pop_back();
127 }
128 // check for a cycle... not that anything would break if
129 // there were one, but it's nice to let us know we have a bug
130 for (reconstruction_path::const_iterator k = pthN->begin();
131 k != pthN->end(); ++k)
132 I(*k != *j);
133 pthN->push_back(*j);
134 next_paths.push_back(pthN);
135 seen_nodes.insert(*j);
136 }
137 }
138 }
139 }
140
141 I(selected_path || !next_paths.empty());
142 live_paths = next_paths;
143 }
144
145 path = *selected_path;
146}
147
148
149
150
151// graph is a parent->child map
152void toposort_rev_ancestry(rev_ancestry_map const & graph,
153 vector<revision_id> & revisions)
154{
155 typedef multimap<revision_id, revision_id>::const_iterator gi;
156 typedef map<revision_id, int>::iterator pi;
157
158 revisions.clear();
159 revisions.reserve(graph.size());
160 // determine the number of parents for each rev
161 map<revision_id, int> pcount;
162 for (gi i = graph.begin(); i != graph.end(); ++i)
163 pcount.insert(pcount.end(), make_pair(i->first, 0));
164 for (gi i = graph.begin(); i != graph.end(); ++i)
165 ++(pcount[i->second]);
166
167 // find the set of graph roots
168 list<revision_id> roots;
169 for (pi i = pcount.begin(); i != pcount.end(); ++i)
170 if(i->second==0)
171 roots.push_back(i->first);
172
173 while (!roots.empty())
174 {
175 revision_id cur = roots.front();
176 roots.pop_front();
177 if (!null_id(cur))
178 revisions.push_back(cur);
179
180 std::pair<gi, gi> bounds = graph.equal_range(cur);
181 for(gi i = bounds.first;
182 i != bounds.second; i++)
183 if(--(pcount[i->second]) == 0)
184 roots.push_back(i->second);
185 }
186}
187
188
189// get_uncommon_ancestors
190typedef std::pair<rev_height, revision_id> height_rev_pair;
191
192static void
193advance_frontier(set<height_rev_pair> & frontier,
194 hash_set<revision_id> & seen,
195 rev_graph const & rg)
196{
197 const height_rev_pair h_node = *frontier.rbegin();
198 const revision_id & node(h_node.second);
199 frontier.erase(h_node);
200 set<revision_id> parents;
201 rg.get_parents(node, parents);
202 for (set<revision_id>::const_iterator r = parents.begin();
203 r != parents.end(); r++)
204 {
205 if (seen.find(*r) == seen.end())
206 {
207 rev_height h;
208 rg.get_height(*r, h);
209 frontier.insert(make_pair(h, *r));
210 seen.insert(*r);
211 }
212 }
213}
214
215void
216get_uncommon_ancestors(revision_id const & a,
217 revision_id const & b,
218 rev_graph const & rg,
219 set<revision_id> & a_uncommon_ancs,
220 set<revision_id> & b_uncommon_ancs)
221{
222 a_uncommon_ancs.clear();
223 b_uncommon_ancs.clear();
224
225 // We extend a frontier from each revision until it reaches
226 // a revision that has been seen by the other frontier. By
227 // traversing in ascending height order we can ensure that
228 // any common ancestor will have been 'seen' by both sides
229 // before it is traversed.
230
231 set<height_rev_pair> a_frontier, b_frontier, common_frontier;
232 {
233 rev_height h;
234 rg.get_height(a, h);
235 a_frontier.insert(make_pair(h, a));
236 rg.get_height(b, h);
237 b_frontier.insert(make_pair(h, b));
238 }
239
240 hash_set<revision_id> a_seen, b_seen, common_seen;
241 a_seen.insert(a);
242 b_seen.insert(b);
243
244 while (!a_frontier.empty() || !b_frontier.empty())
245 {
246 // We take the leaf-most (ie highest) height entry from any frontier.
247 // Note: the default height is the lowest possible.
248 rev_height a_height, b_height, common_height;
249 if (!a_frontier.empty())
250 a_height = a_frontier.rbegin()->first;
251 if (!b_frontier.empty())
252 b_height = b_frontier.rbegin()->first;
253 if (!common_frontier.empty())
254 common_height = common_frontier.rbegin()->first;
255
256 if (a_height > b_height && a_height > common_height)
257 {
258 a_uncommon_ancs.insert(a_frontier.rbegin()->second);
259 advance_frontier(a_frontier, a_seen, rg);
260 }
261 else if (b_height > a_height && b_height > common_height)
262 {
263 b_uncommon_ancs.insert(b_frontier.rbegin()->second);
264 advance_frontier(b_frontier, b_seen, rg);
265 }
266 else if (common_height > a_height && common_height > b_height)
267 {
268 advance_frontier(common_frontier, common_seen, rg);
269 }
270 else if (a_height == b_height) // may or may not also == common_height
271 {
272 // if both frontiers are the same, then we can safely say that
273 // we've found all uncommon ancestors. This stopping condition
274 // can result in traversing more nodes than required, but is simple.
275 if (a_frontier == b_frontier)
276 break;
277
278 common_frontier.insert(*a_frontier.rbegin());
279 a_frontier.erase(*a_frontier.rbegin());
280 b_frontier.erase(*b_frontier.rbegin());
281 }
282 else if (a_height == common_height)
283 {
284 a_frontier.erase(*a_frontier.rbegin());
285 }
286 else if (b_height == common_height)
287 {
288 b_frontier.erase(*b_frontier.rbegin());
289 }
290 else
291 I(false);
292 }
293}
294
295
296// Local Variables:
297// mode: C++
298// fill-column: 76
299// c-file-style: "gnu"
300// indent-tabs-mode: nil
301// End:
302// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status