monotone

monotone Mtn Source Tree

Root/graph.hh

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.hh"
22#include <utility>
23
24#include "vocab.hh"
25#include "rev_height.hh"
26
27struct 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
34typedef std::vector<std::string> reconstruction_path;
35
36void
37get_reconstruction_path(std::string const & start,
38 reconstruction_graph const & graph,
39 reconstruction_path & path);
40
41typedef std::multimap<revision_id, revision_id> rev_ancestry_map;
42
43void toposort_rev_ancestry(rev_ancestry_map const & graph,
44 std::vector<revision_id> & revisions);
45
46struct 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
54void
55get_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

Archive Download this file

Branches

Tags

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