/usr/include/claw/graph.hpp is in libclaw-dev 1.7.3-1+b2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 | /*
CLAW - a C++ Library Absolutely Wonderful
CLAW is a free library without any particular aim but being useful to
anyone.
Copyright (C) 2005-2011 Julien Jorge
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
contact: julien.jorge@gamned.org
*/
/**
* \file graph.hpp
* \brief A class to represent a graph.
* \author Julien Jorge
*/
#ifndef __CLAW_GRAPH_HPP__
#define __CLAW_GRAPH_HPP__
#include <claw/meta/no_type.hpp>
#include <map>
#include <vector>
#include <queue>
#include <exception>
#include <iterator>
#include <utility>
#include <cstddef>
namespace claw
{
/**
* \brief The exceptions thrown by the graphs.
* \author Julien Jorge
*/
class graph_exception:
public std::exception
{
public:
graph_exception() throw();
graph_exception( const std::string& s) throw();
virtual ~graph_exception() throw();
virtual const char* what() const throw();
private:
/** \brief A short explanation of the problem. */
const std::string m_msg;
}; // graph_exception
/**
* \brief A class to represent a graph.
*
* <b>Constraints on the template parameters:</b>
* - S is LessThanComparable,
* - A is any Assignable and Default Constructible,
* - Comp is a binary predicate such that Comp(S a, S b) == true if and
* only if a < b.
*
* \author Julien Jorge
*/
template <class S, class A = meta::no_type, class Comp = std::less<S> >
class graph
{
public:
/** \brief Type of the vertices. */
typedef S vertex_type;
/** \brief Type of the edges. */
typedef A edge_type;
/** \brief Binary predicate to compare vertices. */
typedef Comp vertex_compare;
/** \brief The adjacency list of a vertex.
vertex_type is the target vertex,
edge_type is the label on the edge. */
typedef std::map<vertex_type, edge_type, vertex_compare> neighbours_list;
/** \brief The whole graph: an adjacency list for each vertex. */
typedef std::map<vertex_type, neighbours_list, vertex_compare>
graph_content;
/** \brief Type of the current structure. */
typedef claw::graph<vertex_type, edge_type, vertex_compare> self_type;
/**
* \brief Iterator on the graph's vertices.
*/
class graph_vertex_iterator
{
friend class graph<vertex_type, edge_type, vertex_compare>;
public:
typedef const vertex_type value_type;
typedef const vertex_type& reference;
typedef const vertex_type* const pointer;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
public:
graph_vertex_iterator();
graph_vertex_iterator& operator++();
graph_vertex_iterator operator++(int);
graph_vertex_iterator& operator--();
graph_vertex_iterator operator--(int);
reference operator*() const;
pointer operator->() const;
bool operator==(const graph_vertex_iterator& it) const;
bool operator!=(const graph_vertex_iterator& it) const;
private:
explicit
graph_vertex_iterator( typename graph_content::const_iterator it );
private:
/** \brief Iterator on the list of vertex. */
typename graph_content::const_iterator m_iterator;
}; // class graph_vertex_iterator
/**
* \brief Iterator on the graph's edges.
*/
class graph_edge_iterator
{
friend class graph<vertex_type, edge_type, vertex_compare>;
public:
/**
* \brief Value pointed by the iterator.
*/
class edge
{
friend class graph_edge_iterator;
public:
edge();
const edge_type& label() const;
const vertex_type& source() const;
const vertex_type& target() const;
private:
void set( const edge_type& l, const vertex_type& s,
const vertex_type& t );
private:
edge_type const* m_label;
vertex_type const* m_source;
vertex_type const* m_target;
}; // class edge
public:
typedef const edge value_type;
typedef const edge& reference;
typedef const edge* const pointer;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
public:
graph_edge_iterator();
graph_edge_iterator& operator++();
graph_edge_iterator operator++(int);
graph_edge_iterator& operator--();
graph_edge_iterator operator--(int);
reference operator*() const;
pointer operator->() const;
bool operator==(const graph_edge_iterator& it) const;
bool operator!=(const graph_edge_iterator& it) const;
private:
explicit
graph_edge_iterator( typename graph_content::const_iterator it_begin,
typename graph_content::const_iterator it_end,
typename graph_content::const_iterator it_s,
typename neighbours_list::const_iterator it_d );
private:
/** \brief Iterator of the first node. */
typename graph_content::const_iterator m_vertex_begin;
/** \brief Iterator of the last node. */
typename graph_content::const_iterator m_vertex_end;
/** \brief Iterator on the list of vertex. */
typename graph_content::const_iterator m_vertex_iterator;
/** \brief Iterator on the list of edges. */
typename neighbours_list::const_iterator m_neighbours_iterator;
/** \brief Current edge. */
edge m_edge;
}; // class graph_edge_iterator
public:
typedef graph_vertex_iterator vertex_iterator;
typedef graph_edge_iterator edge_iterator;
typedef std::reverse_iterator<vertex_iterator> reverse_vertex_iterator;
typedef std::reverse_iterator<edge_iterator> reverse_edge_iterator;
public:
graph();
void add_edge( const vertex_type& s1, const vertex_type& s2,
const edge_type& e = edge_type() );
void add_vertex( const vertex_type& s );
bool edge_exists( const vertex_type& s, const vertex_type& r ) const;
void neighbours( const vertex_type& s, std::vector<vertex_type>& v ) const;
void vertices( std::vector<vertex_type>& v ) const;
vertex_iterator vertex_begin() const;
vertex_iterator vertex_end() const;
vertex_iterator vertex_begin( const vertex_type& s ) const;
reverse_vertex_iterator vertex_rbegin() const;
reverse_vertex_iterator vertex_rend() const;
reverse_vertex_iterator vertex_rbegin( const vertex_type& s ) const;
edge_iterator edge_begin() const;
edge_iterator edge_end() const;
edge_iterator edge_begin( const vertex_type& s1,
const vertex_type& s2 ) const;
reverse_edge_iterator edge_rbegin() const;
reverse_edge_iterator edge_rend() const;
reverse_edge_iterator edge_rbegin( const vertex_type& s1,
const vertex_type& s2 ) const;
const edge_type& label( const vertex_type& s, const vertex_type& r ) const;
std::size_t outer_degree( const vertex_type& s ) const;
std::size_t inner_degree( const vertex_type& s ) const;
std::size_t vertices_count() const;
std::size_t edges_count() const;
private:
/** \brief The content of the graph (edges and vertices. */
graph_content m_edges;
/** \brief Inner degree of the vertices. */
std::map<vertex_type, std::size_t, vertex_compare> m_inner_degrees;
/** \brief Number of edges. */
std::size_t m_edges_count;
}; // class graph
} // namespace claw
#include <claw/impl/graph.tpp>
#endif // __CLAW_GRAPH_HPP__
|