paludis  Version 2.6.0
graph.hh
Go to the documentation of this file.
1 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
2 
3 /*
4  * Copyright (c) 2007, 2008, 2010, 2011 Ciaran McCreesh
5  *
6  * This file is part of the Paludis package manager. Paludis is free software;
7  * you can redistribute it and/or modify it under the terms of the GNU General
8  * Public License version 2, as published by the Free Software Foundation.
9  *
10  * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
11  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
13  * details.
14  *
15  * You should have received a copy of the GNU General Public License along with
16  * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
17  * Place, Suite 330, Boston, MA 02111-1307 USA
18  */
19 
20 #ifndef PALUDIS_GUARD_PALUDIS_UTIL_GRAPH_HH
21 #define PALUDIS_GUARD_PALUDIS_UTIL_GRAPH_HH 1
22 
24 #include <paludis/util/pimp.hh>
27 #include <memory>
28 
29 /** \file
30  * Declarations for DirectedGraph and related utilities.
31  *
32  * \ingroup g_data_structures
33  *
34  * \section Examples
35  *
36  * - None at this time.
37  */
38 
39 namespace paludis
40 {
41  /**
42  * Base class for DirectedGraph errors.
43  *
44  * \ingroup g_data_structures
45  * \ingroup g_exceptions
46  * \nosubgrouping
47  */
49  public Exception
50  {
51  protected:
52  ///\name Basic operations
53  ///\{
54 
55  GraphError(const std::string & msg) noexcept;
56 
57  ///\}
58  };
59 
60  /**
61  * Thrown if a DirectedGraph operation relies upon a node being present when it is not.
62  *
63  * \ingroup g_exceptions
64  * \ingroup g_data_structures
65  * \nosubgrouping
66  */
68  public GraphError
69  {
70  public:
71  ///\name Basic operations
72  ///\{
73 
74  template <typename Node_>
75  NoSuchGraphNodeError(const Node_ & node) noexcept :
76  GraphError("Node '" + stringify(node) + "' does not exist")
77  {
78  }
79 
80  template <typename Node_>
81  NoSuchGraphNodeError(const std::shared_ptr<Node_> & node) noexcept :
82  GraphError("Node '" + stringify(*node) + "' does not exist")
83  {
84  }
85 
86  ///\}
87  };
88 
89  /**
90  * Thrown if a DirectedGraph operation relies upon an edge being present when it is not.
91  *
92  * \ingroup g_exceptions
93  * \ingroup g_data_structures
94  * \nosubgrouping
95  */
97  public GraphError
98  {
99  public:
100  ///\name Basic operations
101  ///\{
102 
103  template <typename Node_>
104  NoSuchGraphEdgeError(const Node_ & e1, const Node_ & e2) noexcept :
105  GraphError("Edge '" + stringify(e1) + "' -> '" + stringify(e2) + "' does not exist")
106  {
107  }
108 
109  ///\}
110  };
111 
112  /**
113  * Thrown if no ordering is available for a DirectedGraph::topological_sort.
114  *
115  * \ingroup g_data_structures
116  * \ingroup g_exceptions
117  * \nosubgrouping
118  */
120  public GraphError
121  {
122  public:
123  class RemainingNodes;
124 
125  private:
126  std::shared_ptr<const RemainingNodes> _remaining_nodes;
127 
128  public:
129  ///\name Basic operations
130  ///\{
131 
132  NoGraphTopologicalOrderExistsError(const std::shared_ptr<const RemainingNodes> &) noexcept;
134 
135  ///\}
136 
137  /**
138  * The nodes remaining in the graph.
139  */
140  std::shared_ptr<const RemainingNodes> remaining_nodes() const;
141  };
142 
143  /**
144  * A simple directed graph.
145  *
146  * \ingroup g_data_structures
147  * \nosubgrouping
148  */
149  template <typename Node_, typename Edge_, typename Comparator_>
150  class PALUDIS_VISIBLE DirectedGraph
151  {
152  private:
154 
155  void operator= (const DirectedGraph &);
156 
157  public:
158  ///\name Basic operations
159  ///\{
160 
161  DirectedGraph();
162  DirectedGraph(const DirectedGraph &);
163  ~DirectedGraph();
164 
165  ///\}
166 
167  ///\name Node related functions
168  ///\{
169 
170  /**
171  * Add a node, if it does not already exist.
172  */
173  void add_node(const Node_ &);
174 
175  /**
176  * Delete a node, if it exists.
177  */
178  void delete_node(const Node_ &);
179 
180  /**
181  * Return whether a node exists.
182  */
183  bool has_node(const Node_ &) const;
184 
185  ///\}
186 
187  ///\name Iterate over our nodes
188  ///\{
189 
190  class NodeConstIterator;
191  NodeConstIterator begin_nodes() const;
192  NodeConstIterator end_nodes() const;
193 
194  ///\}
195 
196  ///\name Edge related functions
197  ///\{
198 
199  /**
200  * Add an edge, if it does not already exist.
201  *
202  * \throw NoSuchGraphNodeError if either node is not in the graph.
203  */
204  void add_edge(const Node_ &, const Node_ &, const Edge_ &);
205 
206  /**
207  * Delete an edge, if it exists.
208  */
209  void delete_edge(const Node_ &, const Node_ &);
210 
211  /**
212  * Delete all edges leaving a node.
213  */
214  void delete_outgoing_edges(const Node_ &);
215 
216  /**
217  * Delete all edges entering a node.
218  */
219  void delete_incoming_edges(const Node_ &);
220 
221  /**
222  * Return whether an edge exists.
223  */
224  bool has_edge(const Node_ &, const Node_ &) const;
225 
226  /**
227  * Fetch an edge.
228  *
229  * \throw NoSuchGraphEdgeError if the edge does not exist.
230  */
231  const Edge_ fetch_edge(const Node_ &, const Node_ &) const;
232 
233  /**
234  * Return whether a node has outgoing edges.
235  *
236  * \throw NoSuchGraphNodeError if the node does not exist.
237  */
238  bool has_outgoing_edges(const Node_ &) const;
239 
240  ///\}
241 
242  ///\name Ordering functions
243  ///\{
244 
245  /**
246  * Place our nodes, topological sorted, into OutputIterator_.
247  *
248  * \throw NoGraphTopologicalOrderExistsError if no such order exists.
249  */
250  template <typename OutputIterator_>
251  void topological_sort(OutputIterator_ i) const;
252 
253  ///\}
254  };
255 }
256 
257 #endif
Definition: pimp.hh:51
Definition: about_metadata-fwd.hh:23
Definition: graph.hh:48
Definition: graph.hh:96
Definition: exception.hh:74
std::string stringify(const T_ &item)
Definition: stringify.hh:166
Definition: graph.hh:67
#define PALUDIS_VISIBLE
Definition: attributes.hh:59