File: graph.hh

package info (click to toggle)
monotone 0.48-3
  • links: PTS
  • area: main
  • in suites: squeeze
  • size: 20,096 kB
  • ctags: 8,077
  • sloc: cpp: 81,000; sh: 6,402; perl: 1,241; lisp: 1,045; makefile: 655; python: 566; sql: 112; ansic: 52
file content (66 lines) | stat: -rw-r--r-- 2,149 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Copyright (C) 2006 Nathaniel Smith <njs@pobox.com>
//
// This program is made available under the GNU GPL version 2.0 or
// greater. See the accompanying file COPYING for details.
//
// This program is distributed WITHOUT ANY WARRANTY; without even the
// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
// PURPOSE.

#ifndef __GRAPH__HH__
#define __GRAPH__HH__

// This file contains generic graph algorithms.  They are split out from any
// particular concrete graph (e.g., the revision graph, the delta storage
// graphs) to easy re-use, and to make them easier to test on their own.  We
// have a number of graph algorithms that are not genericized in this way
// (e.g., in revision.cc); FIXME it would be good to move them in here as
// opportunity permits.

#include <set>
#include "vector.hh"
#include <utility>
#include "rev_types.hh"

struct reconstruction_graph
{
  virtual bool is_base(id const & node) const = 0;
  virtual void get_next(id const & from, std::set<id> & next) const = 0;
  virtual ~reconstruction_graph() {};
};

void
get_reconstruction_path(id const & start,
                        reconstruction_graph const & graph,
                        reconstruction_path & path);

void toposort_rev_ancestry(rev_ancestry_map const & graph,
                          std::vector<revision_id> & revisions);

struct rev_graph
{
  virtual void get_parents(revision_id const & rev, std::set<revision_id> & parents) const = 0;
  virtual void get_children(revision_id const & rev, std::set<revision_id> & children) const = 0;
  virtual void get_height(revision_id const & rev, rev_height & h) const = 0;
  virtual ~rev_graph() {};
};

void
get_uncommon_ancestors(revision_id const & a,
                       revision_id const & b,
                       rev_graph const & hg,
                       std::set<revision_id> & a_uncommon_ancs,
                       std::set<revision_id> & b_uncommon_ancs);



#endif // __GRAPH__HH__


// Local Variables:
// mode: C++
// fill-column: 76
// c-file-style: "gnu"
// indent-tabs-mode: nil
// End:
// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s: