 |
Shadowrun: Awakened 29 September 2011 - Build 871
|
|
Shadowrun: Awakened 29 September 2011 - Build 871
|
#include <DS_WeightedGraph.h>
Classes | |
| struct | NodeAndParent |
Public Member Functions | |
| void | AddConnection (const node_type &node1, const node_type &node2, weight_type weight) |
| void | AddNode (const node_type &node) |
| void | Clear (void) |
| void | GetConnectionAtIndex (unsigned nodeIndex, unsigned connectionIndex, node_type &outNode, weight_type &outWeight) const |
| unsigned | GetConnectionCount (unsigned nodeIndex) const |
| node_type | GetNodeAtIndex (unsigned nodeIndex) const |
| unsigned | GetNodeCount (void) const |
| bool | GetShortestPath (DataStructures::List< node_type > &path, node_type startNode, node_type endNode, weight_type INFINITE_WEIGHT) |
| bool | GetSpanningTree (DataStructures::Tree< node_type > &outTree, DataStructures::List< node_type > *inputNodes, node_type startNode, weight_type INFINITE_WEIGHT) |
| bool | HasConnection (const node_type &node1, const node_type &node2) |
| WeightedGraph & | operator= (const WeightedGraph &original_copy) |
| void | Print (void) |
| void | RemoveConnection (const node_type &node1, const node_type &node2) |
| void | RemoveNode (const node_type &node) |
| WeightedGraph (const WeightedGraph &original_copy) | |
| WeightedGraph () | |
| ~WeightedGraph () | |
Static Public Member Functions | |
| static void | IMPLEMENT_DEFAULT_COMPARISON (void) |
Protected Member Functions | |
| void | ClearDijkstra (void) |
| void | GenerateDisjktraMatrix (node_type startNode, weight_type INFINITE_WEIGHT) |
Protected Attributes | |
| DataStructures::Map< node_type, DataStructures::Map< node_type, weight_type > * > | adjacencyLists |
| weight_type * | costMatrix |
| DataStructures::OrderedList < node_type, node_type > | costMatrixIndices |
| bool | isValidPath |
| node_type * | leastNodeArray |
| node_type | rootNode |
Definition at line 34 of file DS_WeightedGraph.h.
| DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::WeightedGraph | ( | ) |
Definition at line 82 of file DS_WeightedGraph.h.
{
isValidPath=false;
costMatrix=0;
}
| DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::~WeightedGraph | ( | ) |
Definition at line 89 of file DS_WeightedGraph.h.
{
Clear();
}
| DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::WeightedGraph | ( | const WeightedGraph< node_type, weight_type, allow_unlinkedNodes > & | original_copy | ) |
Definition at line 95 of file DS_WeightedGraph.h.
References _FILE_AND_LINE_, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::adjacencyLists, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::costMatrix, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::costMatrixIndices, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::isValidPath, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::leastNodeArray, and DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::rootNode.
{
adjacencyLists=original_copy.adjacencyLists;
isValidPath=original_copy.isValidPath;
if (isValidPath)
{
rootNode=original_copy.rootNode;
costMatrixIndices=original_copy.costMatrixIndices;
costMatrix = RakNet::OP_NEW_ARRAY<weight_type>(costMatrixIndices.Size() * costMatrixIndices.Size(), _FILE_AND_LINE_ );
leastNodeArray = RakNet::OP_NEW_ARRAY<node_type>(costMatrixIndices.Size(), _FILE_AND_LINE_ );
memcpy(costMatrix, original_copy.costMatrix, costMatrixIndices.Size() * costMatrixIndices.Size() * sizeof(weight_type));
memcpy(leastNodeArray, original_copy.leastNodeArray, costMatrixIndices.Size() * sizeof(weight_type));
}
}
| void DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::AddConnection | ( | const node_type & | node1, |
| const node_type & | node2, | ||
| weight_type | weight | ||
| ) |
Definition at line 174 of file DS_WeightedGraph.h.
Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetSpanningTree().
{
if (node1==node2)
return;
if (adjacencyLists.Has(node1)==false)
AddNode(node1);
adjacencyLists.Get(node1)->Set(node2, weight);
if (adjacencyLists.Has(node2)==false)
AddNode(node2);
adjacencyLists.Get(node2)->Set(node1, weight);
}
| void DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::AddNode | ( | const node_type & | node | ) |
Definition at line 131 of file DS_WeightedGraph.h.
References _FILE_AND_LINE_, and RakNet::OP_NEW().
| void DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::Clear | ( | void | ) |
Definition at line 208 of file DS_WeightedGraph.h.
References _FILE_AND_LINE_, and RakNet::OP_DELETE().
{
unsigned i;
for (i=0; i < adjacencyLists.Size(); i++)
RakNet::OP_DELETE(adjacencyLists[i], _FILE_AND_LINE_);
adjacencyLists.Clear();
ClearDijkstra();
}
| void DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::ClearDijkstra | ( | void | ) | [protected] |
Definition at line 497 of file DS_WeightedGraph.h.
References _FILE_AND_LINE_, and RakNet::OP_DELETE_ARRAY().
{
if (isValidPath)
{
isValidPath=false;
RakNet::OP_DELETE_ARRAY(costMatrix, _FILE_AND_LINE_);
RakNet::OP_DELETE_ARRAY(leastNodeArray, _FILE_AND_LINE_);
costMatrixIndices.Clear(false, _FILE_AND_LINE_);
}
}
| void DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GenerateDisjktraMatrix | ( | node_type | startNode, |
| weight_type | INFINITE_WEIGHT | ||
| ) | [protected] |
Definition at line 389 of file DS_WeightedGraph.h.
References _FILE_AND_LINE_, DataStructures::Heap< weight_type, data_type, isMaxHeap >::Clear(), DataStructures::Map< key_type, data_type, key_comparison_func >::Delete(), DataStructures::Map< key_type, data_type, key_comparison_func >::Get(), DataStructures::Map< key_type, data_type, key_comparison_func >::GetIndexAtKey(), DataStructures::Map< key_type, data_type, key_comparison_func >::GetKeyAtIndex(), DataStructures::Heap< weight_type, data_type, isMaxHeap >::PeekWeight(), DataStructures::Heap< weight_type, data_type, isMaxHeap >::Pop(), DataStructures::Heap< weight_type, data_type, isMaxHeap >::Push(), DataStructures::Map< key_type, data_type, key_comparison_func >::Set(), DataStructures::Heap< weight_type, data_type, isMaxHeap >::Size(), and DataStructures::Map< key_type, data_type, key_comparison_func >::Size().
{
if (adjacencyLists.Size()==0)
return;
costMatrix = RakNet::OP_NEW_ARRAY<weight_type>(adjacencyLists.Size() * adjacencyLists.Size(), _FILE_AND_LINE_ );
leastNodeArray = RakNet::OP_NEW_ARRAY<node_type>(adjacencyLists.Size(), _FILE_AND_LINE_ );
node_type currentNode;
unsigned col, row, row2, openSetIndex;
node_type adjacentKey;
unsigned adjacentIndex;
weight_type edgeWeight, currentNodeWeight, adjacentNodeWeight;
DataStructures::Map<node_type, weight_type> *adjacencyList;
DataStructures::Heap<weight_type, node_type, false> minHeap;
DataStructures::Map<node_type, weight_type> openSet;
for (col=0; col < adjacencyLists.Size(); col++)
{
// This should be already sorted, so it's a bit inefficient to do an insertion sort, but what the heck
costMatrixIndices.Insert(adjacencyLists.GetKeyAtIndex(col),adjacencyLists.GetKeyAtIndex(col), true, _FILE_AND_LINE_);
}
for (col=0; col < adjacencyLists.Size() * adjacencyLists.Size(); col++)
costMatrix[col]=INFINITE_WEIGHT;
currentNode=startNode;
row=0;
currentNodeWeight=0;
rootNode=startNode;
// Clear the starting node column
if (adjacencyLists.Size())
{
adjacentIndex=adjacencyLists.GetIndexAtKey(startNode);
for (row2=0; row2 < adjacencyLists.Size(); row2++)
costMatrix[row2*adjacencyLists.Size() + adjacentIndex]=0;
}
while (row < adjacencyLists.Size()-1)
{
adjacencyList = adjacencyLists.Get(currentNode);
// Go through all connections from the current node. If the new weight is less than the current weight, then update that weight.
for (col=0; col < adjacencyList->Size(); col++)
{
edgeWeight=(*adjacencyList)[col];
adjacentKey=adjacencyList->GetKeyAtIndex(col);
adjacentIndex=adjacencyLists.GetIndexAtKey(adjacentKey);
adjacentNodeWeight=costMatrix[row*adjacencyLists.Size() + adjacentIndex];
if (currentNodeWeight + edgeWeight < adjacentNodeWeight)
{
// Update the weight for the adjacent node
for (row2=row; row2 < adjacencyLists.Size(); row2++)
costMatrix[row2*adjacencyLists.Size() + adjacentIndex]=currentNodeWeight + edgeWeight;
openSet.Set(adjacentKey, currentNodeWeight + edgeWeight);
}
}
// Find the lowest in the open set
minHeap.Clear(true,_FILE_AND_LINE_);
for (openSetIndex=0; openSetIndex < openSet.Size(); openSetIndex++)
minHeap.Push(openSet[openSetIndex], openSet.GetKeyAtIndex(openSetIndex),_FILE_AND_LINE_);
/*
unsigned i,j;
for (i=0; i < adjacencyLists.Size()-1; i++)
{
for (j=0; j < adjacencyLists.Size(); j++)
{
RAKNET_DEBUG_PRINTF("%2i ", costMatrix[i*adjacencyLists.Size() + j]);
}
RAKNET_DEBUG_PRINTF("Node=%i", leastNodeArray[i]);
RAKNET_DEBUG_PRINTF("\n");
}
*/
if (minHeap.Size()==0)
{
// Unreachable nodes
isValidPath=true;
return;
}
currentNodeWeight=minHeap.PeekWeight(0);
leastNodeArray[row]=minHeap.Pop(0);
currentNode=leastNodeArray[row];
openSet.Delete(currentNode);
row++;
}
/*
#ifdef _DEBUG
unsigned i,j;
for (i=0; i < adjacencyLists.Size()-1; i++)
{
for (j=0; j < adjacencyLists.Size(); j++)
{
RAKNET_DEBUG_PRINTF("%2i ", costMatrix[i*adjacencyLists.Size() + j]);
}
RAKNET_DEBUG_PRINTF("Node=%i", leastNodeArray[i]);
RAKNET_DEBUG_PRINTF("\n");
}
#endif
*/
isValidPath=true;
}
| void DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetConnectionAtIndex | ( | unsigned | nodeIndex, |
| unsigned | connectionIndex, | ||
| node_type & | outNode, | ||
| weight_type & | outWeight | ||
| ) | const |
Definition at line 316 of file DS_WeightedGraph.h.
{
outWeight=adjacencyLists[nodeIndex]->operator[](connectionIndex);
outNode=adjacencyLists[nodeIndex]->GetKeyAtIndex(connectionIndex);
}
| unsigned DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetConnectionCount | ( | unsigned | nodeIndex | ) | const |
Definition at line 310 of file DS_WeightedGraph.h.
{
return adjacencyLists[nodeIndex]->Size();
}
| node_type DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetNodeAtIndex | ( | unsigned | nodeIndex | ) | const |
Definition at line 298 of file DS_WeightedGraph.h.
{
return adjacencyLists.GetKeyAtIndex(nodeIndex);
}
| unsigned DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetNodeCount | ( | void | ) | const |
Definition at line 304 of file DS_WeightedGraph.h.
{
return adjacencyLists.Size();
}
| bool DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetShortestPath | ( | DataStructures::List< node_type > & | path, |
| node_type | startNode, | ||
| node_type | endNode, | ||
| weight_type | INFINITE_WEIGHT | ||
| ) |
Definition at line 219 of file DS_WeightedGraph.h.
References _FILE_AND_LINE_, DataStructures::List< list_type >::Clear(), DataStructures::List< list_type >::Insert(), DataStructures::Queue< queue_type >::Pop(), DataStructures::Queue< queue_type >::PushAtHead(), and DataStructures::Queue< queue_type >::Size().
{
path.Clear(false, _FILE_AND_LINE_);
if (startNode==endNode)
{
path.Insert(startNode, _FILE_AND_LINE_);
path.Insert(endNode, _FILE_AND_LINE_);
return true;
}
if (isValidPath==false || rootNode!=startNode)
{
ClearDijkstra();
GenerateDisjktraMatrix(startNode, INFINITE_WEIGHT);
}
// return the results
bool objectExists;
unsigned col,row;
weight_type currentWeight;
DataStructures::Queue<node_type> outputQueue;
col=costMatrixIndices.GetIndexFromKey(endNode, &objectExists);
if (costMatrixIndices.Size()<2)
{
return false;
}
if (objectExists==false)
{
return false;
}
node_type vertex;
row=costMatrixIndices.Size()-2;
if (row==0)
{
path.Insert(startNode, _FILE_AND_LINE_);
path.Insert(endNode, _FILE_AND_LINE_);
return true;
}
currentWeight=costMatrix[row*adjacencyLists.Size() + col];
if (currentWeight==INFINITE_WEIGHT)
{
// No path
return true;
}
vertex=endNode;
outputQueue.PushAtHead(vertex, 0, _FILE_AND_LINE_);
row--;
#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
while (1)
{
while (costMatrix[row*adjacencyLists.Size() + col] == currentWeight)
{
if (row==0)
{
path.Insert(startNode, _FILE_AND_LINE_);
for (col=0; outputQueue.Size(); col++)
path.Insert(outputQueue.Pop(), _FILE_AND_LINE_);
return true;
}
--row;
}
vertex=leastNodeArray[row];
outputQueue.PushAtHead(vertex, 0, _FILE_AND_LINE_);
if (row==0)
break;
col=costMatrixIndices.GetIndexFromKey(vertex, &objectExists);
currentWeight=costMatrix[row*adjacencyLists.Size() + col];
}
path.Insert(startNode, _FILE_AND_LINE_);
for (col=0; outputQueue.Size(); col++)
path.Insert(outputQueue.Pop(), _FILE_AND_LINE_);
return true;
}
| bool DataStructures::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 | ||
| ) |
Definition at line 323 of file DS_WeightedGraph.h.
References _FILE_AND_LINE_, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::AddConnection(), DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::adjacencyLists, DataStructures::Tree< TreeType >::children, DataStructures::Tree< TreeType >::data, DataStructures::Tree< TreeType >::DeleteDecendants(), DataStructures::Map< key_type, data_type, key_comparison_func >::Get(), DataStructures::Map< key_type, data_type, key_comparison_func >::GetKeyAtIndex(), DataStructures::Map< key_type, data_type, key_comparison_func >::Has(), DataStructures::List< list_type >::Insert(), DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::NodeAndParent::node, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::NodeAndParent::parent, DataStructures::Queue< queue_type >::Pop(), DataStructures::Queue< queue_type >::Push(), DataStructures::Queue< queue_type >::Size(), DataStructures::Map< key_type, data_type, key_comparison_func >::Size(), and DataStructures::List< list_type >::Size().
{
// 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
DataStructures::List<node_type> path;
DataStructures::WeightedGraph<node_type, weight_type, allow_unlinkedNodes> outGraph;
bool res;
unsigned i,j;
for (i=0; i < inputNodes->Size(); i++)
{
res=GetShortestPath(path, startNode, (*inputNodes)[i], INFINITE_WEIGHT);
if (res && path.Size()>0)
{
for (j=0; j < path.Size()-1; j++)
{
// Don't bother looking up the weight
outGraph.AddConnection(path[j], path[j+1], INFINITE_WEIGHT);
}
}
}
// Copy the graph to a tree.
DataStructures::Queue<NodeAndParent> nodesToProcess;
DataStructures::Tree<node_type> *current;
DataStructures::Map<node_type, weight_type> *adjacencyList;
node_type key;
NodeAndParent nap, nap2;
outTree.DeleteDecendants();
outTree.data=startNode;
current=&outTree;
if (outGraph.adjacencyLists.Has(startNode)==false)
return false;
adjacencyList = outGraph.adjacencyLists.Get(startNode);
for (i=0; i < adjacencyList->Size(); i++)
{
nap2.node=RakNet::OP_NEW<DataStructures::Tree<node_type> >( _FILE_AND_LINE_ );
nap2.node->data=adjacencyList->GetKeyAtIndex(i);
nap2.parent=current;
nodesToProcess.Push(nap2, _FILE_AND_LINE_ );
current->children.Insert(nap2.node, _FILE_AND_LINE_);
}
while (nodesToProcess.Size())
{
nap=nodesToProcess.Pop();
current=nap.node;
adjacencyList = outGraph.adjacencyLists.Get(nap.node->data);
for (i=0; i < adjacencyList->Size(); i++)
{
key=adjacencyList->GetKeyAtIndex(i);
if (key!=nap.parent->data)
{
nap2.node=RakNet::OP_NEW<DataStructures::Tree<node_type> >( _FILE_AND_LINE_ );
nap2.node->data=key;
nap2.parent=current;
nodesToProcess.Push(nap2, _FILE_AND_LINE_ );
current->children.Insert(nap2.node, _FILE_AND_LINE_);
}
}
}
return true;
}
| bool DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::HasConnection | ( | const node_type & | node1, |
| const node_type & | node2 | ||
| ) |
Definition at line 164 of file DS_WeightedGraph.h.
{
if (node1==node2)
return false;
if (adjacencyLists.Has(node1)==false)
return false;
return adjacencyLists.Get(node1)->Has(node2);
}
| static void DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::IMPLEMENT_DEFAULT_COMPARISON | ( | void | ) | [inline, static] |
Definition at line 37 of file DS_WeightedGraph.h.
{DataStructures::defaultMapKeyComparison<node_type>(node_type(),node_type());}
| WeightedGraph< node_type, weight_type, allow_unlinkedNodes > & DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::operator= | ( | const WeightedGraph< node_type, weight_type, allow_unlinkedNodes > & | original_copy | ) |
Definition at line 112 of file DS_WeightedGraph.h.
References _FILE_AND_LINE_, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::adjacencyLists, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::costMatrix, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::costMatrixIndices, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::isValidPath, DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::leastNodeArray, and DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::rootNode.
{
adjacencyLists=original_copy.adjacencyLists;
isValidPath=original_copy.isValidPath;
if (isValidPath)
{
rootNode=original_copy.rootNode;
costMatrixIndices=original_copy.costMatrixIndices;
costMatrix = RakNet::OP_NEW_ARRAY<weight_type>(costMatrixIndices.Size() * costMatrixIndices.Size(), _FILE_AND_LINE_ );
leastNodeArray = RakNet::OP_NEW_ARRAY<node_type>(costMatrixIndices.Size(), _FILE_AND_LINE_ );
memcpy(costMatrix, original_copy.costMatrix, costMatrixIndices.Size() * costMatrixIndices.Size() * sizeof(weight_type));
memcpy(leastNodeArray, original_copy.leastNodeArray, costMatrixIndices.Size() * sizeof(weight_type));
}
return *this;
}
| void DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::Print | ( | void | ) |
Definition at line 509 of file DS_WeightedGraph.h.
References RAKNET_DEBUG_PRINTF.
{
#ifdef _DEBUG
unsigned i,j;
for (i=0; i < adjacencyLists.Size(); i++)
{
//RAKNET_DEBUG_PRINTF("%i connected to ", i);
RAKNET_DEBUG_PRINTF("%s connected to ", adjacencyLists.GetKeyAtIndex(i).systemAddress.ToString());
if (adjacencyLists[i]->Size()==0)
RAKNET_DEBUG_PRINTF("<Empty>");
else
{
for (j=0; j < adjacencyLists[i]->Size(); j++)
// RAKNET_DEBUG_PRINTF("%i (%.2f) ", adjacencyLists.GetIndexAtKey(adjacencyLists[i]->GetKeyAtIndex(j)), (float) adjacencyLists[i]->operator[](j) );
RAKNET_DEBUG_PRINTF("%s (%.2f) ", adjacencyLists[i]->GetKeyAtIndex(j).systemAddress.ToString(), (float) adjacencyLists[i]->operator[](j) );
}
RAKNET_DEBUG_PRINTF("\n");
}
#endif
}
| void DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::RemoveConnection | ( | const node_type & | node1, |
| const node_type & | node2 | ||
| ) |
Definition at line 188 of file DS_WeightedGraph.h.
{
adjacencyLists.Get(node2)->Delete(node1);
adjacencyLists.Get(node1)->Delete(node2);
#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
if (allow_unlinkedNodes==false) // If we do not allow _unlinked nodes, then if there are no connections, remove the node
{
if (adjacencyLists.Get(node1)->Size()==0)
RemoveNode(node1); // Will also remove node1 from the adjacency list of node2
if (adjacencyLists.Has(node2) && adjacencyLists.Get(node2)->Size()==0)
RemoveNode(node2);
}
ClearDijkstra();
}
| void DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::RemoveNode | ( | const node_type & | node | ) |
Definition at line 137 of file DS_WeightedGraph.h.
References _FILE_AND_LINE_, RakNet::OP_DELETE(), DataStructures::Queue< queue_type >::Pop(), DataStructures::Queue< queue_type >::Push(), and DataStructures::Queue< queue_type >::Size().
{
unsigned i;
DataStructures::Queue<node_type> removeNodeQueue;
removeNodeQueue.Push(node, _FILE_AND_LINE_ );
while (removeNodeQueue.Size())
{
RakNet::OP_DELETE(adjacencyLists.Pop(removeNodeQueue.Pop()), _FILE_AND_LINE_);
// Remove this node from all of the other lists as well
for (i=0; i < adjacencyLists.Size(); i++)
{
adjacencyLists[i]->Delete(node);
#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
if (allow_unlinkedNodes==false && adjacencyLists[i]->Size()==0)
removeNodeQueue.Push(adjacencyLists.GetKeyAtIndex(i), _FILE_AND_LINE_ );
}
}
ClearDijkstra();
}
DataStructures::Map<node_type, DataStructures::Map<node_type, weight_type> *> DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::adjacencyLists [protected] |
Definition at line 61 of file DS_WeightedGraph.h.
Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GetSpanningTree(), DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::operator=(), and DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::WeightedGraph().
weight_type* DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::costMatrix [protected] |
Definition at line 70 of file DS_WeightedGraph.h.
Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::operator=(), and DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::WeightedGraph().
DataStructures::OrderedList<node_type, node_type> DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::costMatrixIndices [protected] |
Definition at line 69 of file DS_WeightedGraph.h.
Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::operator=(), and DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::WeightedGraph().
bool DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::isValidPath [protected] |
Definition at line 67 of file DS_WeightedGraph.h.
Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::operator=(), and DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::WeightedGraph().
node_type* DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::leastNodeArray [protected] |
Definition at line 71 of file DS_WeightedGraph.h.
Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::operator=(), and DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::WeightedGraph().
node_type DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::rootNode [protected] |
Definition at line 68 of file DS_WeightedGraph.h.
Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::operator=(), and DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::WeightedGraph().
Copyright © 2007-2010 by The Shadowrun: Awakened Team. This work is licensed under the GNU Lesser General Public License 3.
 |