| 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 | ␊ |
