1 | #ifndef __GRAPH__HH__␊ |
2 | #define __GRAPH__HH__␊ |
3 | ␊ |
4 | // Copyright (C) 2006 Nathaniel Smith <njs@pobox.com>␊ |
5 | //␊ |
6 | // This program is made available under the GNU GPL version 2.0 or␊ |
7 | // greater. See the accompanying file COPYING for details.␊ |
8 | //␊ |
9 | // This program is distributed WITHOUT ANY WARRANTY; without even the␊ |
10 | // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR␊ |
11 | // PURPOSE.␊ |
12 | ␊ |
13 | // This file contains generic graph algorithms. They are split out from any␊ |
14 | // particular concrete graph (e.g., the revision graph, the delta storage␊ |
15 | // graphs) to easy re-use, and to make them easier to test on their own. We␊ |
16 | // have a number of graph algorithms that are not genericized in this way␊ |
17 | // (e.g., in revision.cc); FIXME it would be good to move them in here as␊ |
18 | // opportunity permits.␊ |
19 | ␊ |
20 | #include <set>␊ |
21 | #include <vector>␊ |
22 | #include <utility>␊ |
23 | ␊ |
24 | #include "vocab.hh"␊ |
25 | #include "rev_height.hh"␊ |
26 | ␊ |
27 | struct reconstruction_graph␊ |
28 | {␊ |
29 | virtual bool is_base(std::string const & node) const = 0;␊ |
30 | virtual void get_next(std::string const & from, std::set<std::string> & next) const = 0;␊ |
31 | virtual ~reconstruction_graph() {};␊ |
32 | };␊ |
33 | ␊ |
34 | typedef std::vector<std::string> reconstruction_path;␊ |
35 | ␊ |
36 | void␊ |
37 | get_reconstruction_path(std::string const & start,␊ |
38 | reconstruction_graph const & graph,␊ |
39 | reconstruction_path & path);␊ |
40 | ␊ |
41 | typedef std::multimap<revision_id, revision_id> rev_ancestry_map;␊ |
42 | ␊ |
43 | void toposort_rev_ancestry(rev_ancestry_map const & graph,␊ |
44 | std::vector<revision_id> & revisions);␊ |
45 | ␊ |
46 | struct rev_graph␊ |
47 | {␊ |
48 | virtual void get_parents(revision_id const & rev, std::set<revision_id> & parents) const = 0;␊ |
49 | virtual void get_children(revision_id const & rev, std::set<revision_id> & children) const = 0;␊ |
50 | virtual void get_height(revision_id const & rev, rev_height & h) const = 0;␊ |
51 | virtual ~rev_graph() {};␊ |
52 | };␊ |
53 | ␊ |
54 | void␊ |
55 | get_uncommon_ancestors(revision_id const & a,␊ |
56 | revision_id const & b,␊ |
57 | rev_graph const & hg,␊ |
58 | std::set<revision_id> & a_uncommon_ancs,␊ |
59 | std::set<revision_id> & b_uncommon_ancs);␊ |
60 | ␊ |
61 | ␊ |
62 | ␊ |
63 | #endif // __GRAPH__HH__␊ |
64 | ␊ |
65 | ␊ |
66 | // Local Variables:␊ |
67 | // mode: C++␊ |
68 | // fill-column: 76␊ |
69 | // c-file-style: "gnu"␊ |
70 | // indent-tabs-mode: nil␊ |
71 | // End:␊ |
72 | // vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:␊ |
73 | ␊ |