This file is indexed.

/usr/include/terralib/kernel/graph.h is in libterralib-dev 4.3.0+dfsg.2-11.

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
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
/************************************************************************************
TerraLib - a library for developing GIS applications.
Copyright © 2001-2007 INPE and Tecgraf/PUC-Rio.

This code is part of the TerraLib library.
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.

You should have received a copy of the GNU Lesser General Public
License along with this library.

The authors reassure the license terms regarding the warranties.
They specifically disclaim any warranties, including, but not limited to,
the implied warranties of merchantability and fitness for a particular purpose.
The library provided hereunder is on an "as is" basis, and the authors have no
obligation to provide maintenance, support, updates, enhancements, or modifications.
In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
indirect, special, incidental, or consequential damages arising out of the use
of this library and its documentation.
*************************************************************************************/
/*! \file graph.h
    \brief This file contains structures and definitions used to manipulate a graph strucutre
	\note this code came from the book "Desining Components with C++ STL" -
	Ulrich Breymann - Addison-Wesley - pag 243
*/
#ifndef GRAPH_H
#define GRAPH_H
#include<cassert>
#include<vector>
#include<map>
#include<stack>
#include<iostream>
#include <TeDefines.h>

namespace br_stl
{
	// empty parameter class with a minimal set of operations
	// if there are no weights for edges necessary
	struct TL_DLL Empty
	{
	public:
		Empty(int=0) {}
		bool operator<(const Empty&) const { return true;}
	};

	inline std::ostream& operator<<(std::ostream& os, const Empty&) { return os;}
	inline std::istream& operator>>(std::istream& is, Empty& ) { return is;}

	template<class VertexType, class EdgeType>
	class Graph
	{
	public:
		// public type interface
		typedef std::map<int, EdgeType > Successor;
		typedef std::pair<VertexType, Successor> vertex;
		typedef std::vector<vertex> GraphType;
		typedef typename GraphType::iterator iterator;
		typedef typename GraphType::const_iterator const_iterator;

		/* The following constructor initializes the output channel with
		cerr. A parameter must be specified as to whether the graph is
		directed or undirected, because this is an essential property
		of a graph. */

		Graph(bool g, std::ostream& os = cerr)
		: directed(g), pOut(&os) 
		{ }

		bool isDirected() const { return directed;}

		/* A graph is a special kind of container to which something can
		be added and whose elements can be accessed. Therefore, typical
		container methods follow, which in their extent are limited to
		those needed in the book's examples. Thus, there is no method
		for explicit removal of a vertex or an edge from the graph. */

		size_t size() const  { return C.size();}

		iterator begin()     { return C.begin();}
		iterator end()       { return C.end();}

		// access to vertex i}
		vertex& operator[](int i)
		{
			// the access is safe, because C is a checkedVector
			return C[i];
		}

		// return the position of the vertex, if it does not exist return -1
		int getPosition(const VertexType& e); 

		// addition of a vertex
		int  insert(const VertexType& e);

		// addition of an edge between e1 and e2
		void insert(const VertexType& e1, const VertexType& e2,
					const EdgeType& Value);

		// addition of an edge between vertices no. i and j
		void connectVertices(int i, int j, const EdgeType& Value);

		// set the edge value between vertices no. i and j
		bool setEdgeValue(const VertexType& e1, const VertexType& e2, const EdgeType& Value);

		/* The following methods are useful tools for displaying
		information on a graph and check its structure.*/

		// checking of a read data model
		// output on the channel passed to check()
		void check(std::ostream& = std::cout);

		// determine the number of edges
		size_t CountEdges();

		/* determine whether the graph contains cycles and in which way it
		is connected. The method combines two tasks, because they can
		be carried out in a single run.*/
		void CycleAndConnect(std::ostream& = cout);
		int sucessors(int index);

	private:
		bool directed;
		GraphType C;          // container
		std::ostream* pOut;
	};      // class Graph


	template<class VertexType, class EdgeType>
	int Graph<VertexType,EdgeType>::getPosition(const VertexType& e) 
	{
		for(size_t i = 0; i < size(); ++i)
		if(e == C[i].first)
			return i;

		return -1;
	}
		
	/* In order to avoid ambiguities, a vertex is only entered if it does
	not yet exist. The sequential search is not particularly fast; on the
	other hand, this process is only needed once during the construction
	of the graph. The position of the vertex is returned. */

	template<class VertexType, class EdgeType>
	int Graph<VertexType,EdgeType>::insert(const VertexType& e) 
	{
		int pos = getPosition(e);
		if(pos<0)
		{
			// if not found, insert:
			C.push_back(vertex(e, Successor()));
			return size()-1;
		}

		return pos;
	}

	/* An edge is inserted by first inserting the vertices, if needed, and
	by determining their positions. The edge construction itself is 
	carried out by the function connectVertices(). It is passed the
	vertex numbers and, because of the absence of a search procedure, 
	it is very fast. */

	template<class VertexType, class EdgeType>
	void Graph<VertexType,EdgeType>::insert(const VertexType& e1,
										const VertexType& e2,
										const EdgeType& Value)
	{
		int pos1 = insert(e1);
		int pos2 = insert(e2);
		connectVertices(pos1, pos2, Value);
	}

	template<class VertexType, class EdgeType>
	void Graph<VertexType,EdgeType>::connectVertices(
				int pos1, int pos2, const EdgeType& Value) 
	{
		(C[pos1].second)[pos2] = Value;

		if(!directed)  // automatically insert opposite direction too
		(C[pos2].second)[pos1] = Value;
	}

	template<class VertexType, class EdgeType>
	bool Graph<VertexType,EdgeType>::setEdgeValue(const VertexType& e1,
										const VertexType& e2,
										const EdgeType& Value) 
	{
		int pos1 = getPosition(e1);
		int pos2 = getPosition(e2);

		if((pos1<0) || (pos2<0))
			return false;

		(C[pos1].second)[pos2] = Value;

		if(!directed)  // automatically insert opposite direction too
		(C[pos1].second)[pos2] = Value;

		return true;
	}


	template<class VertexType, class EdgeType>
	void Graph<VertexType,EdgeType>::check(std::ostream& os)
	{
		os << "The graph is ";
		if(!isDirected())
			os << "un";

		os << "directed and has "
		<< size() << " vertices and "
		<< CountEdges()
		<< " edges\n";
		CycleAndConnect(os);
	}

	template<class VertexType, class EdgeType>
	size_t Graph<VertexType,EdgeType>::CountEdges()
	{
		size_t edges = 0;
		iterator temp = begin();

		while(temp != end())
			edges += (*temp++).second.size();

		if(!directed)
			edges /= 2;
		return edges;
	}

	// Type for next function
	enum VertStatus {notVisited, visited, processed};

	template<class VertexType, class EdgeType>
	int Graph<VertexType, EdgeType>::sucessors(int index) {
		typename Successor::const_iterator
		start  = operator[](index).second.begin(),
		end    = operator[](index).second.end();
		int nSucc = 0;
		while(start != end)
		{
			nSucc++;
			++start;
		}

		return nSucc;
	}
	template<class VertexType, class EdgeType>
	void Graph<VertexType, EdgeType>::CycleAndConnect(std::ostream& os) {
		int Cycles = 0;
		int ComponentNumber = 0;
		std::stack<int, std::vector<int> > verticesStack;  // vertices to be visited

		/* In order to prevent multiple visits to vertices in possible
		cycles, which entails the risk of infinite loops, the vertices
		are marked for having been visited or finished being processed.
		This purpose is served by the vector VertexState. */
	       
		// assign all vertices the state `not visited'
		std::vector<VertStatus> VertexState(size(), notVisited);

		/* If, starting from one vertex, an attempt is made to reach all
		other vertices, success is not guaranteed in weakly or
		non-connected graphs. Therefore, each vertex is visited. If it
		is found that a vertex has already been visited, it does not
		need to be processed any further. */

		// visit all vertices
		for(size_t i = 0; i < size(); ++i)
		{
			if(VertexState[i] == notVisited)
			{
				++ComponentNumber;
				// store on stack for further processing
				verticesStack.push(i);

				// process stack
				while(!verticesStack.empty())
				{
					int theVertex = verticesStack.top();
					verticesStack.pop();
					if(VertexState[theVertex] == visited)
					VertexState[theVertex] = processed;
					else
					if(VertexState[theVertex] == notVisited)
					{
						VertexState[theVertex] = visited;
						// new vertex, earmark for processed mark
						verticesStack.push(theVertex);

						/* If one of the successors of a newly found vertex
							bears the visited mark, the algorithm has already
							passed this point once, and there is a cycle. */
		                     
						// earmark successor:
						typename Successor::const_iterator
							start  = operator[](theVertex).second.begin(),
							end    = operator[](theVertex).second.end();

						while(start != end)
						{
							int Succ = (*start).first;

							if(VertexState[Succ] == visited)
							{
								++Cycles;   // someone's been here already!
								(*pOut) << "at least vertex "
								<< operator[](Succ).first
								<< " lies in a cycle\n";
							}

							/* Otherwise, the vertex has already been
								processed and therefore should not be
								considered again, or it has not yet been
								visited and is earmarked on the stack. */
		                          
							if(VertexState[Succ] == notVisited)
								verticesStack.push(Succ);
							++start;
						}
					}
				}  // stack empty?
			}     //  if(VertexState}...
		}       // for()} ...

		/* Now we only need the output. In case of directed, weakly
		connected graphs, the algorithm counts several components. In
		order to make the output conform to the above definitions,
		although with less content of information, a distinction is
		made as to whether the graph is directed or not. */

		if(directed)
		{
			if(ComponentNumber == 1)
				os << "The graph is strongly connected.\n";
			else
				os << "The graph is not or weakly "
					"connected.\n";
		}
		else
			os	<< "The graph has "
				<< ComponentNumber
				<< " component(s)." << std::endl;

		os << "The graph has ";
		if(Cycles == 0)
			os << "no ";
		os << "cycles." << std::endl;
	}

	template<class VertexType, class EdgeType>
	std::ostream& operator<<(std::ostream& os, Graph<VertexType,EdgeType>& G)
	{
		// display of vertices with successors
		for(size_t i = 0; i < G.size(); ++i)
		{
			os << G[i].first << " <";
			typename Graph<VertexType,EdgeType>::Successor::const_iterator
								startN = G[i].second.begin(),
								endN   = G[i].second.end();

			while(startN != endN)
			{
				os << G[(*startN).first].first << ' ' // vertex
				<< (*startN).second << ' ';        // edge value
				++startN;
			}
			os << ">" << std::endl;
		}
		return os;
	}
} // namespace br_stl



#endif