monotone

monotone Mtn Source Tree

Root/graph.hh

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#ifndef __GRAPH__HH__
11#define __GRAPH__HH__
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.hh"
22#include <utility>
23#include "rev_types.hh"
24
25struct reconstruction_graph
26{
27 virtual bool is_base(id const & node) const = 0;
28 virtual void get_next(id const & from, std::set<id> & next) const = 0;
29 virtual ~reconstruction_graph() {};
30};
31
32void
33get_reconstruction_path(id const & start,
34 reconstruction_graph const & graph,
35 reconstruction_path & path);
36
37void toposort_rev_ancestry(rev_ancestry_map const & graph,
38 std::vector<revision_id> & revisions);
39
40struct rev_graph
41{
42 virtual void get_parents(revision_id const & rev, std::set<revision_id> & parents) const = 0;
43 virtual void get_children(revision_id const & rev, std::set<revision_id> & children) const = 0;
44 virtual void get_height(revision_id const & rev, rev_height & h) const = 0;
45 virtual ~rev_graph() {};
46};
47
48void
49get_uncommon_ancestors(revision_id const & a,
50 revision_id const & b,
51 rev_graph const & hg,
52 std::set<revision_id> & a_uncommon_ancs,
53 std::set<revision_id> & b_uncommon_ancs);
54
55
56
57#endif // __GRAPH__HH__
58
59
60// Local Variables:
61// mode: C++
62// fill-column: 76
63// c-file-style: "gnu"
64// indent-tabs-mode: nil
65// End:
66// 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