1 /// \file DS_WeightedGraph.h
2 /// \internal
3 /// \brief Weighted graph.
4 /// \details I'm assuming the indices are complex map types, rather than sequential numbers (which could be implemented much more efficiently).
5 ///
6 /// This file is part of RakNet Copyright 2003 Jenkins Software LLC
7 ///
8 /// Raknet is available under the terms of the GPLv3 license, see /usr/local/share/licenses/raknet-3.9.2_10,1/GPLv3.
9 
10 
11 #ifndef __WEIGHTED_GRAPH_H
12 #define __WEIGHTED_GRAPH_H
13 
14 #include "DS_OrderedList.h"
15 #include "DS_Map.h"
16 #include "DS_Heap.h"
17 #include "DS_Queue.h"
18 #include "DS_Tree.h"
19 #include "RakAssert.h"
20 #include "RakMemoryOverride.h"
21 #ifdef _DEBUG
22 #include <stdio.h>
23 #endif
24 
25 #ifdef _MSC_VER
26 #pragma warning( push )
27 #endif
28 
29 /// The namespace DataStructures was only added to avoid compiler errors for commonly named data structures
30 /// As these data structures are stand-alone, you can use them outside of RakNet for your own projects if you wish.
31 namespace DataStructures
32 {
33 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
34 	class RAK_DLL_EXPORT WeightedGraph
35 	{
36 	public:
IMPLEMENT_DEFAULT_COMPARISON(void)37 		static void IMPLEMENT_DEFAULT_COMPARISON(void) {DataStructures::defaultMapKeyComparison<node_type>(node_type(),node_type());}
38 
39 		WeightedGraph();
40 		~WeightedGraph();
41 		WeightedGraph( const WeightedGraph& original_copy );
42 		WeightedGraph& operator= ( const WeightedGraph& original_copy );
43 		void AddNode(const node_type &node);
44 		void RemoveNode(const node_type &node);
45 		void AddConnection(const node_type &node1, const node_type &node2, weight_type weight);
46 		void RemoveConnection(const node_type &node1, const node_type &node2);
47 		bool HasConnection(const node_type &node1, const node_type &node2);
48 		void Print(void);
49 		void Clear(void);
50 		bool GetShortestPath(DataStructures::List<node_type> &path, node_type startNode, node_type endNode, weight_type INFINITE_WEIGHT);
51 		bool GetSpanningTree(DataStructures::Tree<node_type> &outTree, DataStructures::List<node_type> *inputNodes, node_type startNode, weight_type INFINITE_WEIGHT );
52 		unsigned GetNodeCount(void) const;
53 		unsigned GetConnectionCount(unsigned nodeIndex) const;
54 		void GetConnectionAtIndex(unsigned nodeIndex, unsigned connectionIndex, node_type &outNode, weight_type &outWeight) const;
55 		node_type GetNodeAtIndex(unsigned nodeIndex) const;
56 
57 	protected:
58 		void ClearDijkstra(void);
59 		void GenerateDisjktraMatrix(node_type startNode, weight_type INFINITE_WEIGHT);
60 
61 		DataStructures::Map<node_type, DataStructures::Map<node_type, weight_type> *> adjacencyLists;
62 
63 		// All these variables are for path finding with Dijkstra
64 		// 08/23/06 Won't compile as a DLL inside this struct
65 	//	struct
66 	//	{
67 			bool isValidPath;
68 			node_type rootNode;
69 			DataStructures::OrderedList<node_type, node_type> costMatrixIndices;
70 			weight_type *costMatrix;
71 			node_type *leastNodeArray;
72 	//	} dijkstra;
73 
74 		struct NodeAndParent
75 		{
76 			DataStructures::Tree<node_type>*node;
77 			DataStructures::Tree<node_type>*parent;
78 		};
79 	};
80 
81 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
WeightedGraph()82 		WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::WeightedGraph()
83 	{
84 		isValidPath=false;
85 		costMatrix=0;
86 	}
87 
88 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
~WeightedGraph()89 		WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::~WeightedGraph()
90 	{
91 		Clear();
92 	}
93 
94 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
WeightedGraph(const WeightedGraph & original_copy)95 	WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::WeightedGraph( const WeightedGraph& original_copy )
96 	{
97 		adjacencyLists=original_copy.adjacencyLists;
98 
99 		isValidPath=original_copy.isValidPath;
100 		if (isValidPath)
101 		{
102 			rootNode=original_copy.rootNode;
103 			costMatrixIndices=original_copy.costMatrixIndices;
104 			costMatrix = RakNet::OP_NEW_ARRAY<weight_type>(costMatrixIndices.Size() * costMatrixIndices.Size(), __FILE__, __LINE__ );
105 			leastNodeArray = RakNet::OP_NEW_ARRAY<node_type>(costMatrixIndices.Size(), __FILE__, __LINE__ );
106 			memcpy(costMatrix, original_copy.costMatrix, costMatrixIndices.Size() * costMatrixIndices.Size() * sizeof(weight_type));
107 			memcpy(leastNodeArray, original_copy.leastNodeArray, costMatrixIndices.Size() * sizeof(weight_type));
108 		}
109 	}
110 
111 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
112 	WeightedGraph<node_type, weight_type, allow_unlinkedNodes>& WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::operator=( const WeightedGraph& original_copy )
113 	{
114 		adjacencyLists=original_copy.adjacencyLists;
115 
116 		isValidPath=original_copy.isValidPath;
117 		if (isValidPath)
118 		{
119 			rootNode=original_copy.rootNode;
120 			costMatrixIndices=original_copy.costMatrixIndices;
121 			costMatrix = RakNet::OP_NEW_ARRAY<weight_type>(costMatrixIndices.Size() * costMatrixIndices.Size(), __FILE__, __LINE__ );
122 			leastNodeArray = RakNet::OP_NEW_ARRAY<node_type>(costMatrixIndices.Size(), __FILE__, __LINE__ );
123 			memcpy(costMatrix, original_copy.costMatrix, costMatrixIndices.Size() * costMatrixIndices.Size() * sizeof(weight_type));
124 			memcpy(leastNodeArray, original_copy.leastNodeArray, costMatrixIndices.Size() * sizeof(weight_type));
125 		}
126 
127 		return *this;
128 	}
129 
130 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
AddNode(const node_type & node)131 		void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::AddNode(const node_type &node)
132 	{
133 		adjacencyLists.SetNew(node, RakNet::OP_NEW<DataStructures::Map<node_type, weight_type> >( __FILE__, __LINE__) );
134 	}
135 
136 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
RemoveNode(const node_type & node)137 		void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::RemoveNode(const node_type &node)
138 	{
139 		unsigned i;
140 		DataStructures::Queue<node_type> removeNodeQueue;
141 
142 		removeNodeQueue.Push(node, __FILE__, __LINE__ );
143 		while (removeNodeQueue.Size())
144 		{
145 			RakNet::OP_DELETE(adjacencyLists.Pop(removeNodeQueue.Pop()), __FILE__, __LINE__);
146 
147 			// Remove this node from all of the other lists as well
148 			for (i=0; i < adjacencyLists.Size(); i++)
149 			{
150 				adjacencyLists[i]->Delete(node);
151 
152 #ifdef _MSC_VER
153 #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
154 #endif
155 				if (allow_unlinkedNodes==false && adjacencyLists[i]->Size()==0)
156 					removeNodeQueue.Push(adjacencyLists.GetKeyAtIndex(i), __FILE__, __LINE__ );
157 			}
158 		}
159 
160 		ClearDijkstra();
161 	}
162 
163 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
HasConnection(const node_type & node1,const node_type & node2)164 	bool WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::HasConnection(const node_type &node1, const node_type &node2)
165 	{
166 		if (node1==node2)
167 			return false;
168 		if (adjacencyLists.Has(node1)==false)
169 			return false;
170 		return adjacencyLists.Get(node1)->Has(node2);
171 	}
172 
173 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
AddConnection(const node_type & node1,const node_type & node2,weight_type weight)174 		void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::AddConnection(const node_type &node1, const node_type &node2, weight_type weight)
175 	{
176 		if (node1==node2)
177 			return;
178 
179 		if (adjacencyLists.Has(node1)==false)
180 			AddNode(node1);
181 		adjacencyLists.Get(node1)->Set(node2, weight);
182 		if (adjacencyLists.Has(node2)==false)
183 			AddNode(node2);
184 		adjacencyLists.Get(node2)->Set(node1, weight);
185 	}
186 
187 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
RemoveConnection(const node_type & node1,const node_type & node2)188 		void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::RemoveConnection(const node_type &node1, const node_type &node2)
189 	{
190 		adjacencyLists.Get(node2)->Delete(node1);
191 		adjacencyLists.Get(node1)->Delete(node2);
192 
193 #ifdef _MSC_VER
194 #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
195 #endif
196 		if (allow_unlinkedNodes==false) // If we do not allow _unlinked nodes, then if there are no connections, remove the node
197 		{
198 			if (adjacencyLists.Get(node1)->Size()==0)
199 				RemoveNode(node1); // Will also remove node1 from the adjacency list of node2
200 			if (adjacencyLists.Has(node2) && adjacencyLists.Get(node2)->Size()==0)
201 				RemoveNode(node2);
202 		}
203 
204 		ClearDijkstra();
205 	}
206 
207 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
Clear(void)208 		void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::Clear(void)
209 	{
210 		unsigned i;
211 		for (i=0; i < adjacencyLists.Size(); i++)
212 			RakNet::OP_DELETE(adjacencyLists[i], __FILE__, __LINE__);
213 		adjacencyLists.Clear();
214 
215 		ClearDijkstra();
216 	}
217 
218 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
GetShortestPath(DataStructures::List<node_type> & path,node_type startNode,node_type endNode,weight_type INFINITE_WEIGHT)219 		bool WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetShortestPath(DataStructures::List<node_type> &path, node_type startNode, node_type endNode, weight_type INFINITE_WEIGHT)
220 	{
221 		path.Clear(false, __FILE__, __LINE__);
222 		if (startNode==endNode)
223 		{
224 			path.Insert(startNode, __FILE__, __LINE__);
225 			path.Insert(endNode, __FILE__, __LINE__);
226 			return true;
227 		}
228 
229 		if (isValidPath==false || rootNode!=startNode)
230 		{
231 			ClearDijkstra();
232 			GenerateDisjktraMatrix(startNode, INFINITE_WEIGHT);
233 		}
234 
235 		// return the results
236 		bool objectExists;
237 		unsigned col,row;
238 		weight_type currentWeight;
239 		DataStructures::Queue<node_type> outputQueue;
240 		col=costMatrixIndices.GetIndexFromKey(endNode, &objectExists);
241 		if (costMatrixIndices.Size()<2)
242 		{
243 			return false;
244 		}
245 		if (objectExists==false)
246 		{
247 			return false;
248 		}
249 		node_type vertex;
250 		row=costMatrixIndices.Size()-2;
251 		if (row==0)
252 		{
253 			path.Insert(startNode, __FILE__, __LINE__);
254 			path.Insert(endNode, __FILE__, __LINE__);
255 			return true;
256 		}
257 		currentWeight=costMatrix[row*adjacencyLists.Size() + col];
258 		if (currentWeight==INFINITE_WEIGHT)
259 		{
260 			// No path
261 			return true;
262 		}
263 		vertex=endNode;
264 		outputQueue.PushAtHead(vertex, 0, __FILE__,__LINE__);
265 		row--;
266 #ifdef _MSC_VER
267 #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
268 #endif
269 		while (1)
270 		{
271 			while (costMatrix[row*adjacencyLists.Size() + col] == currentWeight)
272 			{
273 				if (row==0)
274 				{
275 					path.Insert(startNode, __FILE__, __LINE__);
276 					for (col=0; outputQueue.Size(); col++)
277 						path.Insert(outputQueue.Pop(), __FILE__, __LINE__);
278 					return true;
279 				}
280 				--row;
281 			}
282 
283 			vertex=leastNodeArray[row];
284 			outputQueue.PushAtHead(vertex, 0, __FILE__,__LINE__);
285 			if (row==0)
286 				break;
287 			col=costMatrixIndices.GetIndexFromKey(vertex, &objectExists);
288 			currentWeight=costMatrix[row*adjacencyLists.Size() + col];
289 		}
290 
291 		path.Insert(startNode, __FILE__, __LINE__);
292 		for (col=0; outputQueue.Size(); col++)
293 			path.Insert(outputQueue.Pop(), __FILE__, __LINE__);
294 		return true;
295 	}
296 
297 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
GetNodeAtIndex(unsigned nodeIndex)298 		node_type WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetNodeAtIndex(unsigned nodeIndex) const
299 	{
300 		return adjacencyLists.GetKeyAtIndex(nodeIndex);
301 	}
302 
303 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
GetNodeCount(void)304 	unsigned WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetNodeCount(void) const
305 	{
306 		return adjacencyLists.Size();
307 	}
308 
309 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
GetConnectionCount(unsigned nodeIndex)310 	unsigned WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetConnectionCount(unsigned nodeIndex) const
311 	{
312         return adjacencyLists[nodeIndex]->Size();
313 	}
314 
315 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
GetConnectionAtIndex(unsigned nodeIndex,unsigned connectionIndex,node_type & outNode,weight_type & outWeight)316 	void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetConnectionAtIndex(unsigned nodeIndex, unsigned connectionIndex, node_type &outNode, weight_type &outWeight) const
317 	{
318 		outWeight=adjacencyLists[nodeIndex]->operator[](connectionIndex);
319 		outNode=adjacencyLists[nodeIndex]->GetKeyAtIndex(connectionIndex);
320 	}
321 
322 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
GetSpanningTree(DataStructures::Tree<node_type> & outTree,DataStructures::List<node_type> * inputNodes,node_type startNode,weight_type INFINITE_WEIGHT)323 	bool WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetSpanningTree(DataStructures::Tree<node_type> &outTree, DataStructures::List<node_type> *inputNodes, node_type startNode, weight_type INFINITE_WEIGHT )
324 	{
325 		// Find the shortest path from the start node to each of the input nodes.  Add this path to a new WeightedGraph if the result is reachable
326 		DataStructures::List<node_type> path;
327 		DataStructures::WeightedGraph<node_type, weight_type, allow_unlinkedNodes> outGraph;
328 		bool res;
329 		unsigned i,j;
330 		for (i=0; i < inputNodes->Size(); i++)
331 		{
332 			res=GetShortestPath(path, startNode, (*inputNodes)[i], INFINITE_WEIGHT);
333 			if (res && path.Size()>0)
334 			{
335 				for (j=0; j < path.Size()-1; j++)
336 				{
337 					// Don't bother looking up the weight
338  					outGraph.AddConnection(path[j], path[j+1], INFINITE_WEIGHT);
339 				}
340 			}
341 		}
342 
343 		// Copy the graph to a tree.
344 		DataStructures::Queue<NodeAndParent> nodesToProcess;
345 		DataStructures::Tree<node_type> *current;
346 		DataStructures::Map<node_type, weight_type> *adjacencyList;
347 		node_type key;
348 		NodeAndParent nap, nap2;
349 		outTree.DeleteDecendants();
350 		outTree.data=startNode;
351 		current=&outTree;
352 		if (outGraph.adjacencyLists.Has(startNode)==false)
353 			return false;
354 		adjacencyList = outGraph.adjacencyLists.Get(startNode);
355 
356 		for (i=0; i < adjacencyList->Size(); i++)
357 		{
358 			nap2.node=RakNet::OP_NEW<DataStructures::Tree<node_type> >( __FILE__, __LINE__ );
359 			nap2.node->data=adjacencyList->GetKeyAtIndex(i);
360 			nap2.parent=current;
361 			nodesToProcess.Push(nap2, __FILE__, __LINE__ );
362 			current->children.Insert(nap2.node, __FILE__, __LINE__);
363 		}
364 
365 		while (nodesToProcess.Size())
366 		{
367 			nap=nodesToProcess.Pop();
368 			current=nap.node;
369 			adjacencyList = outGraph.adjacencyLists.Get(nap.node->data);
370 
371 			for (i=0; i < adjacencyList->Size(); i++)
372 			{
373 				key=adjacencyList->GetKeyAtIndex(i);
374 				if (key!=nap.parent->data)
375 				{
376 					nap2.node=RakNet::OP_NEW<DataStructures::Tree<node_type> >( __FILE__, __LINE__ );
377 					nap2.node->data=key;
378 					nap2.parent=current;
379 					nodesToProcess.Push(nap2, __FILE__, __LINE__ );
380 					current->children.Insert(nap2.node, __FILE__, __LINE__);
381 				}
382 			}
383 		}
384 
385 		return true;
386 	}
387 
388 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
GenerateDisjktraMatrix(node_type startNode,weight_type INFINITE_WEIGHT)389 		void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GenerateDisjktraMatrix(node_type startNode, weight_type INFINITE_WEIGHT)
390 	{
391 		if (adjacencyLists.Size()==0)
392 			return;
393 
394 		costMatrix = RakNet::OP_NEW_ARRAY<weight_type>(adjacencyLists.Size() * adjacencyLists.Size(), __FILE__, __LINE__ );
395 		leastNodeArray = RakNet::OP_NEW_ARRAY<node_type>(adjacencyLists.Size(), __FILE__, __LINE__ );
396 
397 		node_type currentNode;
398 		unsigned col, row, row2, openSetIndex;
399 		node_type adjacentKey;
400 		unsigned adjacentIndex;
401 		weight_type edgeWeight, currentNodeWeight, adjacentNodeWeight;
402 		DataStructures::Map<node_type, weight_type> *adjacencyList;
403 		DataStructures::Heap<weight_type, node_type, false> minHeap;
404 		DataStructures::Map<node_type, weight_type> openSet;
405 
406 		for (col=0; col < adjacencyLists.Size(); col++)
407 		{
408 			// This should be already sorted, so it's a bit inefficient to do an insertion sort, but what the heck
409 			costMatrixIndices.Insert(adjacencyLists.GetKeyAtIndex(col),adjacencyLists.GetKeyAtIndex(col), true, __FILE__,__LINE__);
410 		}
411 		for (col=0; col < adjacencyLists.Size() * adjacencyLists.Size(); col++)
412 			costMatrix[col]=INFINITE_WEIGHT;
413 		currentNode=startNode;
414 		row=0;
415 		currentNodeWeight=0;
416 		rootNode=startNode;
417 
418 		// Clear the starting node column
419 		if (adjacencyLists.Size())
420 		{
421 			adjacentIndex=adjacencyLists.GetIndexAtKey(startNode);
422 			for (row2=0; row2 < adjacencyLists.Size(); row2++)
423 				costMatrix[row2*adjacencyLists.Size() + adjacentIndex]=0;
424 		}
425 
426 		while (row < adjacencyLists.Size()-1)
427 		{
428 			adjacencyList = adjacencyLists.Get(currentNode);
429 			// Go through all connections from the current node.  If the new weight is less than the current weight, then update that weight.
430 			for (col=0; col < adjacencyList->Size(); col++)
431 			{
432 				edgeWeight=(*adjacencyList)[col];
433 				adjacentKey=adjacencyList->GetKeyAtIndex(col);
434 				adjacentIndex=adjacencyLists.GetIndexAtKey(adjacentKey);
435 				adjacentNodeWeight=costMatrix[row*adjacencyLists.Size() + adjacentIndex];
436 
437 				if (currentNodeWeight + edgeWeight < adjacentNodeWeight)
438 				{
439 					// Update the weight for the adjacent node
440 					for (row2=row; row2 < adjacencyLists.Size(); row2++)
441 						costMatrix[row2*adjacencyLists.Size() + adjacentIndex]=currentNodeWeight + edgeWeight;
442 					openSet.Set(adjacentKey, currentNodeWeight + edgeWeight);
443 				}
444 			}
445 
446 			// Find the lowest in the open set
447 			minHeap.Clear(true,__FILE__,__LINE__);
448 			for (openSetIndex=0; openSetIndex < openSet.Size(); openSetIndex++)
449 				minHeap.Push(openSet[openSetIndex], openSet.GetKeyAtIndex(openSetIndex),__FILE__,__LINE__);
450 
451 			/*
452 			unsigned i,j;
453 			for (i=0; i < adjacencyLists.Size()-1; i++)
454 			{
455 				for (j=0; j < adjacencyLists.Size(); j++)
456 				{
457 					RAKNET_DEBUG_PRINTF("%2i ", costMatrix[i*adjacencyLists.Size() + j]);
458 				}
459 				RAKNET_DEBUG_PRINTF("Node=%i", leastNodeArray[i]);
460 				RAKNET_DEBUG_PRINTF("\n");
461 			}
462 			*/
463 
464 			if (minHeap.Size()==0)
465 			{
466 				// Unreachable nodes
467 				isValidPath=true;
468 				return;
469 			}
470 
471 			currentNodeWeight=minHeap.PeekWeight(0);
472 			leastNodeArray[row]=minHeap.Pop(0);
473 			currentNode=leastNodeArray[row];
474 			openSet.Delete(currentNode);
475 			row++;
476 		}
477 
478 		/*
479 #ifdef _DEBUG
480 		unsigned i,j;
481 		for (i=0; i < adjacencyLists.Size()-1; i++)
482 		{
483 			for (j=0; j < adjacencyLists.Size(); j++)
484 			{
485 				RAKNET_DEBUG_PRINTF("%2i ", costMatrix[i*adjacencyLists.Size() + j]);
486 			}
487 			RAKNET_DEBUG_PRINTF("Node=%i", leastNodeArray[i]);
488 			RAKNET_DEBUG_PRINTF("\n");
489 		}
490 #endif
491 		*/
492 
493 		isValidPath=true;
494 	}
495 
496 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
ClearDijkstra(void)497 		void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::ClearDijkstra(void)
498 	{
499 		if (isValidPath)
500 		{
501 			isValidPath=false;
502 			RakNet::OP_DELETE_ARRAY(costMatrix, __FILE__, __LINE__);
503 			RakNet::OP_DELETE_ARRAY(leastNodeArray, __FILE__, __LINE__);
504 			costMatrixIndices.Clear(false, __FILE__, __LINE__);
505 		}
506 	}
507 
508 	template <class node_type, class weight_type, bool allow_unlinkedNodes>
Print(void)509 		void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::Print(void)
510 	{
511 #ifdef _DEBUG
512 		unsigned i,j;
513 		for (i=0; i < adjacencyLists.Size(); i++)
514 		{
515 			//RAKNET_DEBUG_PRINTF("%i connected to ", i);
516 			RAKNET_DEBUG_PRINTF("%s connected to ", adjacencyLists.GetKeyAtIndex(i).systemAddress.ToString());
517 
518 			if (adjacencyLists[i]->Size()==0)
519 				RAKNET_DEBUG_PRINTF("<Empty>");
520 			else
521 			{
522 				for (j=0; j < adjacencyLists[i]->Size(); j++)
523 				//	RAKNET_DEBUG_PRINTF("%i (%.2f) ", adjacencyLists.GetIndexAtKey(adjacencyLists[i]->GetKeyAtIndex(j)), (float) adjacencyLists[i]->operator[](j) );
524 					RAKNET_DEBUG_PRINTF("%s (%.2f) ", adjacencyLists[i]->GetKeyAtIndex(j).systemAddress.ToString(), (float) adjacencyLists[i]->operator[](j) );
525 			}
526 
527 			RAKNET_DEBUG_PRINTF("\n");
528 		}
529 #endif
530 	}
531 }
532 
533 #ifdef _MSC_VER
534 #pragma warning( pop )
535 #endif
536 
537 #endif
538