This file is indexed.

/usr/include/claw/graph.hpp is in libclaw-dev 1.7.0-2.

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
/*
  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>

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__