| 1 |
|
| 2 |
// GraphRider (gr) program |
| 3 |
// This program loads a graph from an existing SDT file. It builds the graph from the SDT |
| 4 |
// file by inserting Nodes corresponding to SDT nodes and connects the graph according |
| 5 |
// to SDT "link" commands. Note that SDT scripts can dynamically update the graph state over |
| 6 |
// time and hence this program updates the graph in "snapshots" between SDT "wait" commands. |
| 7 |
// The ECDS relay set selection algorithm is currently implemented here. The SDT input |
| 8 |
// is essentially passed through but modifies the coloring of SDT nodes to illustrate |
| 9 |
// the relay set selection. |
| 10 |
|
| 11 |
#include "manetGraph.h" |
| 12 |
#include "manetGraphML.h" |
| 13 |
#include "protoSpace.h" // we use this for its bounding box iteration |
| 14 |
#include <protoDebug.h> |
| 15 |
#include <protoDefs.h> |
| 16 |
#include <protoString.h> // for ProtoTokenator |
| 17 |
|
| 18 |
#include <stdio.h> // for sprintf() |
| 19 |
#include <stdlib.h> // for rand(), srand() |
| 20 |
#include <ctype.h> // for "isprint()" |
| 21 |
#include <math.h> // for "sqrt()" |
| 22 |
|
| 23 |
//#include <chrono> |
| 24 |
|
| 25 |
|
| 26 |
class Node; // predeclared so it can be passed to templated CdsInterface definition below |
| 27 |
|
| 28 |
class CdsInterface; // predeclared so it can be passed to templated CdsLink definition below |
| 29 |
|
| 30 |
|
| 31 |
// Define a ManetLink type that uses the "SimpleCostDouble" as its cost metric |
| 32 |
class CdsLink : public NetGraph::LinkTemplate<NetGraph::SimpleCostDouble, CdsInterface>, public ProtoQueue::Item |
| 33 |
{ |
| 34 |
public: |
| 35 |
class SimpleList : public ProtoSimpleQueueTemplate<CdsLink> {}; |
| 36 |
}; |
| 37 |
|
| 38 |
class CdsInterface : public NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, CdsInterface, CdsLink, Node> |
| 39 |
{ |
| 40 |
public: |
| 41 |
CdsInterface(Node& theNode) |
| 42 |
: NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, CdsInterface, CdsLink, Node>(theNode), |
| 43 |
rtr_priority(0), relay_status(false), visited(false) |
| 44 |
{ |
| 45 |
} |
| 46 |
CdsInterface(Node& theNode, const ProtoAddress& addr) |
| 47 |
: NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, CdsInterface, CdsLink, Node>(theNode, addr), |
| 48 |
rtr_priority(0), relay_status(false), visited(false) |
| 49 |
{ |
| 50 |
} |
| 51 |
virtual ~CdsInterface() {} |
| 52 |
|
| 53 |
UINT32 GetNodeId() const; |
| 54 |
|
| 55 |
void SetRtrPriority(UINT8 value) |
| 56 |
{rtr_priority = value;} |
| 57 |
UINT8 GetRtrPriority() const |
| 58 |
{return rtr_priority;} |
| 59 |
|
| 60 |
unsigned int GetDegree() const; //{return GetAdjacencyCount();} |
| 61 |
|
| 62 |
void SetRelayStatus(bool state) |
| 63 |
{relay_status = state;} |
| 64 |
bool GetRelayStatus() const |
| 65 |
{return relay_status;} |
| 66 |
|
| 67 |
void SetVisited(bool state) |
| 68 |
{visited = state;} |
| 69 |
bool WasVisited() const |
| 70 |
{return visited;} |
| 71 |
|
| 72 |
private: |
| 73 |
UINT8 rtr_priority; |
| 74 |
bool relay_status; |
| 75 |
bool visited; |
| 76 |
}; // end class CdsInterface |
| 77 |
|
| 78 |
|
| 79 |
class CdsGraph : public NetGraphTemplate<NetGraph::SimpleCostDouble, CdsInterface, CdsLink, Node> {}; |
| 80 |
|
| 81 |
|
| 82 |
void Usage() |
| 83 |
{ |
| 84 |
fprintf(stderr, "Usage: gr input <fileName> [degree][link <name>,<priority>]\n"); |
| 85 |
} |
| 86 |
|
| 87 |
const unsigned int MAX_LINE = 256; |
| 88 |
|
| 89 |
class Node :public NetGraph::NodeTemplate<CdsInterface>, public ProtoQueue::Item |
| 90 |
{ |
| 91 |
public: |
| 92 |
Node(); |
| 93 |
~Node(); |
| 94 |
|
| 95 |
// _MUST_ call init to create a default interface |
| 96 |
bool Init(UINT32 nodeId, const char* nodeName = NULL); |
| 97 |
|
| 98 |
CdsGraph::Interface* AddInterface(const char* ifaceName, unsigned int ifaceId) |
| 99 |
{ |
| 100 |
ProtoAddress addr; |
| 101 |
iface_count += 1; |
| 102 |
if (0 != ifaceId) |
| 103 |
addr.SetEndIdentifier(ifaceId); |
| 104 |
else |
| 105 |
addr.SetEndIdentifier(node_id*1000+iface_count); |
| 106 |
CdsGraph::Interface* iface = new CdsGraph::Interface(*this, addr); |
| 107 |
iface->SetRtrPriority(1); |
| 108 |
if (NULL != iface) |
| 109 |
{ |
| 110 |
iface->SetName(ifaceName); |
| 111 |
// Make first added interface the default interface |
| 112 |
if (AppendInterface(*iface, (1 == iface_count))) |
| 113 |
return iface; |
| 114 |
else |
| 115 |
return NULL; |
| 116 |
} |
| 117 |
else |
| 118 |
{ |
| 119 |
PLOG(PL_ERROR, "Node::Init() new CdsGraph::Interface() error: %s\n", |
| 120 |
GetErrorString()); |
| 121 |
return NULL; |
| 122 |
} |
| 123 |
} |
| 124 |
|
| 125 |
unsigned int GetInterfaceCount() const |
| 126 |
{return iface_count;} |
| 127 |
|
| 128 |
unsigned int GetId() const |
| 129 |
{ |
| 130 |
CdsGraph::Interface* iface = GetDefaultInterface(); |
| 131 |
if (NULL != iface) |
| 132 |
{ |
| 133 |
return (iface->GetAddress().GetEndIdentifier()); |
| 134 |
} |
| 135 |
else |
| 136 |
{ |
| 137 |
ASSERT(0); |
| 138 |
return ((unsigned int)-1); |
| 139 |
} |
| 140 |
} |
| 141 |
|
| 142 |
// We always give our nodes a default interface |
| 143 |
const ProtoAddress& GetAddress() const |
| 144 |
{return GetDefaultInterface()->GetAddress();} |
| 145 |
|
| 146 |
const char* GetName() const |
| 147 |
{return node_name;} |
| 148 |
|
| 149 |
void SetRtrPriority(UINT8 value) |
| 150 |
{rtr_priority = value;} |
| 151 |
UINT8 GetRtrPriority() const |
| 152 |
{return rtr_priority;} |
| 153 |
|
| 154 |
void SetRelayStatus(bool state) |
| 155 |
{relay_status = state;} |
| 156 |
bool GetRelayStatus() const |
| 157 |
{return relay_status;} |
| 158 |
|
| 159 |
void SetVisited(bool state) |
| 160 |
{visited = state;} |
| 161 |
bool WasVisited() const |
| 162 |
{return visited;} |
| 163 |
|
| 164 |
unsigned int GetDegree(); // counts each neighbor only once regardless of redundant links |
| 165 |
unsigned int GetTotalDegree(); // counts neighbors with redundant links multiple time |
| 166 |
|
| 167 |
|
| 168 |
class Queue : public ProtoSimpleQueueTemplate<Node> {}; |
| 169 |
|
| 170 |
class NeighborIterator : public NetGraph::NodeTemplate<CdsInterface>::NeighborIterator |
| 171 |
{ |
| 172 |
public: |
| 173 |
NeighborIterator(Node& node) : NetGraph::NodeTemplate<CdsInterface>::NeighborIterator(node) {} |
| 174 |
virtual ~NeighborIterator() {visited_queue.Empty();} |
| 175 |
|
| 176 |
Node* GetNextNeighbor() |
| 177 |
{ |
| 178 |
Node* nextNeighbor = NULL; |
| 179 |
CdsInterface* nextIface; |
| 180 |
while (NULL != (nextIface = GetNextNeighborInterface())) |
| 181 |
{ |
| 182 |
if ((NULL != nextIface) && !visited_queue.Contains(nextIface->GetNode())) |
| 183 |
{ |
| 184 |
nextNeighbor = &(nextIface->GetNode()); |
| 185 |
visited_queue.Append(*nextNeighbor); |
| 186 |
break; |
| 187 |
} |
| 188 |
} |
| 189 |
return nextNeighbor; |
| 190 |
} |
| 191 |
|
| 192 |
void Reset() |
| 193 |
{ |
| 194 |
NetGraph::NodeTemplate<CdsInterface>::NeighborIterator::Reset(); |
| 195 |
visited_queue.Empty(); |
| 196 |
} |
| 197 |
private: |
| 198 |
Queue visited_queue; |
| 199 |
}; // end class Node::NeighborIterator |
| 200 |
|
| 201 |
// ProtoTree::Item overrides so nodes |
| 202 |
// can be cached by name |
| 203 |
const char* GetKey() const |
| 204 |
{return node_name;} |
| 205 |
unsigned int GetKeysize() const |
| 206 |
{return node_name_bits;} |
| 207 |
|
| 208 |
private: |
| 209 |
char* node_name; |
| 210 |
unsigned int node_name_bits; |
| 211 |
unsigned int node_id; |
| 212 |
unsigned int iface_count; |
| 213 |
UINT8 rtr_priority; |
| 214 |
bool relay_status; |
| 215 |
bool visited; |
| 216 |
|
| 217 |
}; // end class Node |
| 218 |
|
| 219 |
class NodeTree : public ProtoIndexedQueueTemplate<Node> |
| 220 |
{ |
| 221 |
private: |
| 222 |
virtual const char* GetKey(const Item& item) const |
| 223 |
{return static_cast<const Node&>(item).GetKey();} |
| 224 |
virtual unsigned int GetKeysize(const Item& item) const |
| 225 |
{return static_cast<const Node&>(item).GetKeysize();} |
| 226 |
}; |
| 227 |
typedef Node::Queue NodeQueue; |
| 228 |
|
| 229 |
Node::Node() |
| 230 |
: node_name(NULL), node_name_bits(0), iface_count(0), |
| 231 |
rtr_priority(0) |
| 232 |
{ |
| 233 |
} |
| 234 |
|
| 235 |
Node::~Node() |
| 236 |
{ |
| 237 |
} |
| 238 |
|
| 239 |
bool Node::Init(UINT32 nodeId, const char* nodeName) |
| 240 |
{ |
| 241 |
if (NULL != nodeName) |
| 242 |
{ |
| 243 |
if (NULL != node_name) delete[] node_name; |
| 244 |
size_t nameLen = strlen(nodeName) + 1; |
| 245 |
if (NULL == (node_name = new char[nameLen])) |
| 246 |
{ |
| 247 |
PLOG(PL_ERROR, "Node::Init() new node_name error: %s\n", |
| 248 |
GetErrorString()); |
| 249 |
return false; |
| 250 |
} |
| 251 |
strcpy(node_name, nodeName); |
| 252 |
node_name_bits = nameLen << 3; |
| 253 |
} |
| 254 |
node_id = nodeId; |
| 255 |
return true; |
| 256 |
} // end Node::Init() |
| 257 |
|
| 258 |
unsigned int Node::GetTotalDegree() |
| 259 |
{ |
| 260 |
unsigned int count = 0; |
| 261 |
InterfaceIterator it(*this); |
| 262 |
CdsInterface* iface; |
| 263 |
while (NULL != (iface = it.GetNextInterface())) |
| 264 |
count += iface->GetAdjacencyCount(); |
| 265 |
return count; |
| 266 |
} // end Node::GetTotalDegree() |
| 267 |
|
| 268 |
unsigned int Node::GetDegree() |
| 269 |
{ |
| 270 |
unsigned int count = 0; |
| 271 |
NeighborIterator nit(*this); |
| 272 |
Node* neighbor; |
| 273 |
while (NULL != (neighbor = nit.GetNextNeighbor())) |
| 274 |
{ |
| 275 |
count += 1; |
| 276 |
} |
| 277 |
return count; |
| 278 |
} // end Node::GetTotalDegree() |
| 279 |
|
| 280 |
|
| 281 |
UINT32 CdsInterface::GetNodeId() const |
| 282 |
{ |
| 283 |
return GetNode().GetId(); |
| 284 |
} // end CdsInterface::GetNodeId() |
| 285 |
|
| 286 |
unsigned int CdsInterface::GetDegree() const |
| 287 |
{ |
| 288 |
unsigned int result = GetAdjacencyCount(); |
| 289 |
result += GetNode().GetInterfaceCount() - 1; |
| 290 |
return result; |
| 291 |
} // end CdsInterface::GetDegree() |
| 292 |
|
| 293 |
|
| 294 |
|
| 295 |
// This class encapsulates most of the functionality of |
| 296 |
// our "gr" (GraphRider) application. I bothered to do |
| 297 |
// this in case we want to re-use this elsewhere. |
| 298 |
|
| 299 |
class GraphRider |
| 300 |
{ |
| 301 |
public: |
| 302 |
GraphRider(); |
| 303 |
~GraphRider(); |
| 304 |
|
| 305 |
bool SetInputFile(const char* fileName) |
| 306 |
{return fast_reader.SetFile(fileName);} |
| 307 |
|
| 308 |
// This updates the "graph" with data from the next time "epoch" |
| 309 |
// from our SDT input file |
| 310 |
double ReadNextEpoch(); |
| 311 |
|
| 312 |
CdsGraph& AccessGraph() |
| 313 |
{return graph;} |
| 314 |
|
| 315 |
NodeTree& AccessNodeTree() |
| 316 |
{return node_tree;} |
| 317 |
|
| 318 |
static int CalculateFullECDS(NodeTree& nodeTree, |
| 319 |
CdsGraph& graph, |
| 320 |
bool useDegree = false, |
| 321 |
ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool = NULL); |
| 322 |
|
| 323 |
static int CalculateFullMECDS(NodeTree& nodeTree, |
| 324 |
CdsGraph& graph, |
| 325 |
bool useDegree, |
| 326 |
ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool); |
| 327 |
|
| 328 |
static double CalculateDensity(CdsGraph& graph); |
| 329 |
|
| 330 |
// For coloring links, etc |
| 331 |
static const char* COLOR[8]; |
| 332 |
|
| 333 |
// name indices into our COLOR array |
| 334 |
enum Color |
| 335 |
{ |
| 336 |
GREEN, |
| 337 |
RED, |
| 338 |
BLUE, |
| 339 |
PURPLE, |
| 340 |
ORANGE, |
| 341 |
PINK, |
| 342 |
WHITE, |
| 343 |
GRAY |
| 344 |
}; |
| 345 |
|
| 346 |
class LinkType : public ProtoTree::Item |
| 347 |
{ |
| 348 |
public: |
| 349 |
LinkType(const char* name) |
| 350 |
: rtr_priority(0), link_color(GRAY) |
| 351 |
{ |
| 352 |
unsigned int len = strlen(name); |
| 353 |
if (len > 31) len = 31; |
| 354 |
strncpy(link_name, name, len); |
| 355 |
link_name[31] = '\0'; |
| 356 |
link_name_bits = len << 3; |
| 357 |
} |
| 358 |
|
| 359 |
const char* GetName() const |
| 360 |
{return link_name;} |
| 361 |
|
| 362 |
void SetRtrPriority(UINT8 value) |
| 363 |
{rtr_priority = value;} |
| 364 |
UINT8 GetRtrPriority() const |
| 365 |
{return rtr_priority;} |
| 366 |
|
| 367 |
void SetColor(Color theColor) |
| 368 |
{link_color = theColor;} |
| 369 |
const char* GetColorName() const |
| 370 |
{return COLOR[link_color];} |
| 371 |
|
| 372 |
private: |
| 373 |
const char* GetKey() const {return link_name;} |
| 374 |
unsigned int GetKeysize() const {return link_name_bits;} |
| 375 |
|
| 376 |
char link_name[32]; |
| 377 |
unsigned int link_name_bits; |
| 378 |
unsigned int rtr_priority; |
| 379 |
Color link_color; |
| 380 |
|
| 381 |
}; // end class GraphRider::LinkType |
| 382 |
|
| 383 |
class LinkTypeTable : public ProtoTreeTemplate<LinkType> {}; |
| 384 |
|
| 385 |
LinkType* AddLinkType(const char* name); |
| 386 |
LinkType* GetLinkType(const char* name) |
| 387 |
{return link_table.FindString(name);} |
| 388 |
|
| 389 |
private: |
| 390 |
// "FastReader" is handy class I use for doing |
| 391 |
// buffered (fast) reading of a usually text input file. |
| 392 |
class FastReader |
| 393 |
{ |
| 394 |
public: |
| 395 |
enum Result {OK, ERROR_, DONE, TIMEOUT}; |
| 396 |
FastReader(FILE* filePtr = NULL); |
| 397 |
~FastReader(); |
| 398 |
|
| 399 |
bool SetFile(const char* fileName) |
| 400 |
{ |
| 401 |
if (NULL != file_ptr) fclose(file_ptr); |
| 402 |
return (NULL != (file_ptr = fopen(fileName, "r"))); |
| 403 |
} |
| 404 |
|
| 405 |
Result Read(char* buffer, |
| 406 |
unsigned int* len, |
| 407 |
double timeout = -1.0); |
| 408 |
|
| 409 |
Result Readline(char* buffer, |
| 410 |
unsigned int* len, |
| 411 |
double timeout = -1.0); |
| 412 |
|
| 413 |
bool Seek(int offset); |
| 414 |
|
| 415 |
private: |
| 416 |
enum {BUFSIZE = 2048}; |
| 417 |
FILE* file_ptr; |
| 418 |
char savebuf[BUFSIZE]; |
| 419 |
char* saveptr; |
| 420 |
unsigned int savecount; |
| 421 |
}; // end class GraphRider::FastReader |
| 422 |
|
| 423 |
// member variables |
| 424 |
FastReader fast_reader; |
| 425 |
CdsGraph graph; |
| 426 |
NodeTree node_tree; |
| 427 |
UINT32 node_id_index; |
| 428 |
unsigned int iface_id_index; |
| 429 |
LinkTypeTable link_table; |
| 430 |
unsigned int link_color_index; |
| 431 |
double next_epoch_time; |
| 432 |
unsigned int input_line_num; |
| 433 |
|
| 434 |
}; // end class GraphRider |
| 435 |
|
| 436 |
GraphRider::GraphRider() |
| 437 |
: node_id_index(0), iface_id_index(0), link_color_index(0), next_epoch_time(0.0), input_line_num(0) |
| 438 |
{ |
| 439 |
} |
| 440 |
|
| 441 |
GraphRider::~GraphRider() |
| 442 |
{ |
| 443 |
link_table.Destroy(); |
| 444 |
} |
| 445 |
|
| 446 |
const char* GraphRider::COLOR[8] = |
| 447 |
{ |
| 448 |
"green", |
| 449 |
"red", |
| 450 |
"blue", |
| 451 |
"orange", |
| 452 |
"pink", |
| 453 |
"purple", |
| 454 |
"gray", |
| 455 |
"white", |
| 456 |
}; |
| 457 |
|
| 458 |
static bool IsNumber(const char* name) |
| 459 |
{ |
| 460 |
for (int i = 0 ; i < strlen(name); i++) |
| 461 |
{ |
| 462 |
if (!isdigit(name[i])) return false; |
| 463 |
} |
| 464 |
return true; |
| 465 |
} // end IsNumber() |
| 466 |
|
| 467 |
GraphRider::LinkType* GraphRider::AddLinkType(const char* name) |
| 468 |
{ |
| 469 |
LinkType* linkType = new LinkType(name); |
| 470 |
if (NULL == linkType) |
| 471 |
{ |
| 472 |
PLOG(PL_ERROR, "GraphRider::AddLinkType() new LinkType error: %s\n", GetErrorString()); |
| 473 |
return NULL; |
| 474 |
} |
| 475 |
if (IsNumber(name)) |
| 476 |
{ |
| 477 |
if (atoi(name)) |
| 478 |
linkType->SetColor((Color)7); |
| 479 |
else |
| 480 |
linkType->SetColor((Color)6); |
| 481 |
//TRACE("Mapping link type %s to color %s\n", name, COLOR[7]); |
| 482 |
} |
| 483 |
else |
| 484 |
{ |
| 485 |
linkType->SetColor((Color)link_color_index); |
| 486 |
TRACE("Mapping link type %s to color %s\n", name, COLOR[link_color_index]); |
| 487 |
link_color_index = (link_color_index + 1) % 8; |
| 488 |
} |
| 489 |
link_table.Insert(*linkType); |
| 490 |
return linkType; |
| 491 |
} // end GraphRider::AddLinkType() |
| 492 |
|
| 493 |
// returns the start time (in seconds) of the "epoch" |
| 494 |
double GraphRider::ReadNextEpoch() |
| 495 |
{ |
| 496 |
double lastTime = next_epoch_time; |
| 497 |
// Read the SDT "node" from the file, finding new nodes and |
| 498 |
// process SDT "link" and "unlink" commands to determine |
| 499 |
// graph connectivity |
| 500 |
bool gotLine = false; // this is set to false if we find any useful content |
| 501 |
bool reading = true; |
| 502 |
while (reading) |
| 503 |
{ |
| 504 |
char buffer[MAX_LINE]; |
| 505 |
unsigned int len = MAX_LINE; |
| 506 |
switch (fast_reader.Readline(buffer, &len)) |
| 507 |
{ |
| 508 |
case GraphRider::FastReader::OK: |
| 509 |
break; |
| 510 |
case GraphRider::FastReader::ERROR_: |
| 511 |
PLOG(PL_ERROR, "gr: error reading file\n"); |
| 512 |
return -1.0; |
| 513 |
case GraphRider::FastReader::DONE: |
| 514 |
reading = false; |
| 515 |
continue; |
| 516 |
case GraphRider::FastReader::TIMEOUT: |
| 517 |
return -1.0; // should never occur for this program |
| 518 |
} |
| 519 |
|
| 520 |
input_line_num++; |
| 521 |
gotLine = true; |
| 522 |
|
| 523 |
// pass the input line through to STDOUT (except "symbol" lines that "graphRider" will generate its own) |
| 524 |
if (NULL == strstr(buffer, "symbol")) |
| 525 |
printf("%s\n", buffer); |
| 526 |
|
| 527 |
// Is this line the start of a new "epoch"? |
| 528 |
double time; |
| 529 |
if (1 == sscanf(buffer, "wait %lf\n", &time)) |
| 530 |
{ |
| 531 |
// It's an SDT "wait" command ... |
| 532 |
next_epoch_time += time; |
| 533 |
return lastTime; |
| 534 |
} |
| 535 |
|
| 536 |
char nameString[256]; |
| 537 |
if (1 == sscanf(buffer, "node %s", nameString)) |
| 538 |
{ |
| 539 |
// Do we know this node already? |
| 540 |
unsigned int nameBits = (unsigned int)(strlen(nameString)+1) << 3; |
| 541 |
Node* node = static_cast<Node*>(node_tree.Find(nameString, nameBits)); |
| 542 |
if (NULL == node) |
| 543 |
{ |
| 544 |
// It's a new node |
| 545 |
unsigned int nodeId = node_id_index++; |
| 546 |
// Create and insert new node into the "graph" and "node_tree" |
| 547 |
Node* node = new Node(); |
| 548 |
if (!node->Init(nodeId, nameString)) |
| 549 |
{ |
| 550 |
PLOG(PL_ERROR, "gr error: Node initialization failure!\n"); |
| 551 |
return -1.0; |
| 552 |
} |
| 553 |
graph.InsertNode(*node); |
| 554 |
node_tree.Insert(*node); |
| 555 |
} |
| 556 |
} |
| 557 |
else |
| 558 |
{ |
| 559 |
ProtoTokenator tk(buffer, ' ', true); |
| 560 |
const char* cmd = tk.GetNextItem(); |
| 561 |
if (NULL == cmd) continue; |
| 562 |
bool link; |
| 563 |
if (0 == strcmp(cmd, "link")) |
| 564 |
link = true; |
| 565 |
else if (0 == strcmp(cmd, "unlink")) |
| 566 |
link = false; |
| 567 |
else |
| 568 |
continue; |
| 569 |
const char* value = tk.GetNextItem(); // this should be the link or unlink command comma-delimited value |
| 570 |
if (NULL == value) |
| 571 |
{ |
| 572 |
PLOG(PL_ERROR, "gr error: malformed \"%s\" command in input file at line %lu!\n", |
| 573 |
link ? "link" : "unlink", input_line_num); |
| 574 |
return -1.0; |
| 575 |
} |
| 576 |
ProtoTokenator tk2(value, ',', true); |
| 577 |
const char* src = tk2.GetNextItem(true); // detach to keep it |
| 578 |
const char* dst = tk2.GetNextItem(); |
| 579 |
if ((NULL == src) || (NULL == dst)) |
| 580 |
{ |
| 581 |
PLOG(PL_ERROR, "gr error: malformed \"%s\" command in input file at line %lu!\n", |
| 582 |
link ? "link" : "unlink", input_line_num); |
| 583 |
if (NULL != src) delete[] src; |
| 584 |
return -1.0; |
| 585 |
} |
| 586 |
Node* node1 = static_cast<Node*>(node_tree.Find(src, (strlen(src)+1) << 3)); |
| 587 |
Node* node2 = static_cast<Node*>(node_tree.Find(dst, (strlen(dst)+1) << 3)); |
| 588 |
delete[] src; // not needed any further |
| 589 |
if ((NULL == node1) || (NULL == node2)) |
| 590 |
{ |
| 591 |
PLOG(PL_ERROR, "gr error: unknown nodes in \"%s\" command in input file at line %lu!\n", |
| 592 |
link ? "link" : "unlink", input_line_num); |
| 593 |
return -1.0; |
| 594 |
} |
| 595 |
const char* linkName = tk2.GetNextItem(); |
| 596 |
CdsGraph::Interface* iface1; |
| 597 |
CdsGraph::Interface* iface2; |
| 598 |
if (NULL == linkName) linkName = "default"; |
| 599 |
|
| 600 |
LinkType* linkType = GetLinkType(linkName); |
| 601 |
if ((NULL == linkType) && (NULL == (linkType = AddLinkType(linkName)))) |
| 602 |
{ |
| 603 |
PLOG(PL_ERROR, "gr error: unable to add link type\n"); |
| 604 |
return -1.0; |
| 605 |
} |
| 606 |
iface1 = node1->FindInterfaceByName(linkName); |
| 607 |
if (NULL == iface1) |
| 608 |
iface1 = node1->AddInterface(linkName, ++iface_id_index); |
| 609 |
iface2 = node2->FindInterfaceByName(linkName); |
| 610 |
if (NULL == iface2) |
| 611 |
iface2 = node2->AddInterface(linkName, ++iface_id_index); |
| 612 |
if ((NULL == iface1) || (NULL == iface2)) |
| 613 |
{ |
| 614 |
PLOG(PL_ERROR, "gr new interface error: %s\n", GetErrorString()); |
| 615 |
return -1.0; |
| 616 |
} |
| 617 |
else if (NULL != linkType) |
| 618 |
{ |
| 619 |
iface1->SetRtrPriority(linkType->GetRtrPriority()); |
| 620 |
iface2->SetRtrPriority(linkType->GetRtrPriority()); |
| 621 |
} |
| 622 |
// TBD - check to see if graph actually was changed? |
| 623 |
if (link) |
| 624 |
{ |
| 625 |
CdsGraph::SimpleCostDouble cost(1.0); |
| 626 |
TRACE("gr: connecting %s/%s->%s/%s\n", node1->GetName(), linkName, node2->GetName(), linkName); |
| 627 |
if (!graph.Connect(*iface1, *iface2, cost, true)) |
| 628 |
PLOG(PL_ERROR, "gr error: unable to connect interfaces in graph\n"); |
| 629 |
} |
| 630 |
else |
| 631 |
{ |
| 632 |
graph.Disconnect(*iface1, *iface2, true); |
| 633 |
} |
| 634 |
node1->GetDegree(); |
| 635 |
node2->GetDegree(); |
| 636 |
} |
| 637 |
} // end while reading() |
| 638 |
return (gotLine ? lastTime : -1.0); |
| 639 |
} // end ReadNextEpoch() |
| 640 |
|
| 641 |
static int ComparePriority(unsigned int priority1, unsigned int degree1, const ProtoAddress& addr1, |
| 642 |
unsigned int priority2, unsigned int degree2, const ProtoAddress& addr2) |
| 643 |
{ |
| 644 |
// returns 1 if p1 > p2, -1 if p1 < p2, and 0 if equal |
| 645 |
if (priority1 > priority2) |
| 646 |
return 1; |
| 647 |
else if (priority1 < priority2) |
| 648 |
return -1; |
| 649 |
else if (degree1 > degree2) |
| 650 |
return 1; |
| 651 |
else if (degree1 < degree2) |
| 652 |
return -1; |
| 653 |
else if (addr1 > addr2) |
| 654 |
return 1; |
| 655 |
else if (addr1 < addr2) |
| 656 |
return -1; |
| 657 |
else // equal |
| 658 |
{ |
| 659 |
return 0; |
| 660 |
} |
| 661 |
} // end ComparePriority() |
| 662 |
|
| 663 |
int GraphRider::CalculateFullMECDS(NodeTree& nodeTree, |
| 664 |
CdsGraph& graph, |
| 665 |
bool useDegree, |
| 666 |
ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool) |
| 667 |
{ |
| 668 |
bool collapseNodes = false; |
| 669 |
unsigned int K = 2; |
| 670 |
; |
| 671 |
|
| 672 |
// Now that we have a fully updated "graph", perform Relay Set Selection |
| 673 |
// algorithm for each node in graph |
| 674 |
int numberOfRelays = 0; |
| 675 |
NodeTree::Iterator noderator(nodeTree); |
| 676 |
Node* node; |
| 677 |
while (NULL != (node = noderator.GetNextItem())) |
| 678 |
{ |
| 679 |
|
| 680 |
CdsInterface* ifacex = node->GetDefaultInterface(); |
| 681 |
ASSERT(NULL != ifacex); |
| 682 |
CdsGraph::SimpleTraversal bfs(graph, *ifacex, true, collapseNodes); |
| 683 |
unsigned int level; |
| 684 |
CdsInterface* ifacey; |
| 685 |
while (NULL != (ifacey = bfs.GetNextInterface(&level))) |
| 686 |
{ |
| 687 |
TRACE("Test bfs traversal from %s/%s to %s/%s at level %u...\n", |
| 688 |
ifacex->GetNode().GetName(), ifacex->GetName(), |
| 689 |
ifacey->GetNode().GetName(), ifacey->GetName(), level); |
| 690 |
} |
| 691 |
|
| 692 |
node->SetRelayStatus(false); |
| 693 |
unsigned int degree = node->GetDegree(); |
| 694 |
TRACE("\nMECDS check for node %s priority:%d degree:%d id:%d...\n", |
| 695 |
node->GetName(), node->GetRtrPriority(), degree, node->GetId()); |
| 696 |
|
| 697 |
// First, do the E-CDS algorithm Step 1,2 for the "node" to see |
| 698 |
// if it is a leaf node. (This is needed so that the altered |
| 699 |
// E-CDS Step 1,2 below for each iface works properly) |
| 700 |
CdsInterface* iface; |
| 701 |
Node::InterfaceIterator it(*node); |
| 702 |
if (degree < 2) |
| 703 |
{ |
| 704 |
// We are a leaf node, so none of our interfaces will be relays |
| 705 |
while (NULL != (iface = it.GetNextInterface())) |
| 706 |
iface->SetRelayStatus(false); |
| 707 |
continue; |
| 708 |
} |
| 709 |
if (!useDegree) degree = 0; |
| 710 |
|
| 711 |
// E-CDS Steps 3-9 are "compressed" for a "node" because, by definition, it has |
| 712 |
// a larger router priority than any of its interfaces. So, we defer marking |
| 713 |
// the node as a relay. If _any_ of its interfaces are selected as relay, then |
| 714 |
// the node gets marked as a relay, too. So, we init the node's relay |
| 715 |
// status to "false", knowing it will be marked as needed later. |
| 716 |
|
| 717 |
// Now do E-CDS for each of the candidate relay node's interfaces separately |
| 718 |
it.Reset(); |
| 719 |
while (NULL != (iface = it.GetNextInterface())) |
| 720 |
{ |
| 721 |
TRACE(" MECDS check for iface: %s/%s (%d:%d:%d) ...\n", node->GetName(), iface->GetName(), |
| 722 |
iface->GetRtrPriority(), degree, iface->GetAddress().GetEndIdentifier()); |
| 723 |
degree = iface->GetDegree(); |
| 724 |
//degree = iface->GetNode().GetTotalDegree(); |
| 725 |
|
| 726 |
//TRACE(" MECDS Steps 1-2 iface: %s/%s (%d:%d:%d) ...\n", node->GetName(), iface->GetName(), |
| 727 |
// iface->GetRtrPriority(), degree, iface->GetAddress().GetEndIdentifier()); |
| 728 |
|
| 729 |
// E-CDS Step 1,2 |
| 730 |
if (0 == degree) |
| 731 |
{ |
| 732 |
TRACE(" MECDS isabling iface %s/%s degree %d per E-CDS step 2\n", node->GetName(), iface->GetName(), degree); |
| 733 |
iface->SetRelayStatus(false); // 'leaf' interface |
| 734 |
continue; |
| 735 |
} |
| 736 |
|
| 737 |
//TRACE(" MECDS Steps 3-6 iface: %s/%s (%d:%d:%d) ...\n", node->GetName(), iface->GetName(), |
| 738 |
/// iface->GetRtrPriority(), degree, iface->GetAddress().GetEndIdentifier()); |
| 739 |
|
| 740 |
if (!useDegree) degree = 0; |
| 741 |
// E-CDS Step 3, 5, and 6, mark one-hop and two-hop neighbors as unvisited. |
| 742 |
// (Ee set 3-hop neighbors as visited to mark as out-of-bounds.) |
| 743 |
iface->SetVisited(false); |
| 744 |
UINT8 priority = iface->GetRtrPriority(); |
| 745 |
CdsInterface* ifaceN1Max = NULL; |
| 746 |
UINT8 priorityN1Max = priority; |
| 747 |
unsigned int degreeN1Max = degree; |
| 748 |
CdsGraph::SimpleTraversal bfs(graph, *iface, true, collapseNodes); |
| 749 |
CdsInterface* ifaceN1; |
| 750 |
unsigned int level; |
| 751 |
while (NULL != (ifaceN1 = bfs.GetNextInterface(&level))) |
| 752 |
{ |
| 753 |
//TRACE(" bfs to %s/%s at level %u\n", ifaceN1->GetNode().GetName(), ifaceN1->GetName(), level); |
| 754 |
if (ifaceN1 == iface) continue; |
| 755 |
if (level < K) |
| 756 |
{ |
| 757 |
ifaceN1->SetVisited(false); |
| 758 |
UINT8 priorityN1 = ifaceN1->GetRtrPriority(); |
| 759 |
unsigned int degreeN1 = useDegree ? ifaceN1->GetDegree() : 0; |
| 760 |
//unsigned int degreeN1 = useDegree ? ifaceN1->GetNode().GetTotalDegree() : 0; |
| 761 |
if (NULL == ifaceN1Max) |
| 762 |
{ |
| 763 |
priorityN1Max = priorityN1; |
| 764 |
degreeN1Max = degreeN1; |
| 765 |
ifaceN1Max = ifaceN1; |
| 766 |
} |
| 767 |
else |
| 768 |
{ |
| 769 |
/*TRACE(" compare %s/%s %d:%d:%d to %s/%s %d:%d:%d\n", |
| 770 |
ifaceN1->GetNode().GetName(), ifaceN1->GetName(), priorityN1, degreeN1, ifaceN1->GetAddress().GetEndIdentifier(), |
| 771 |
ifaceN1Max->GetNode().GetName(), ifaceN1Max->GetName(), priorityN1Max, degreeN1Max, ifaceN1Max->GetAddress().GetEndIdentifier()); |
| 772 |
*/ |
| 773 |
if (ComparePriority(priorityN1, degreeN1, ifaceN1->GetAddress(), |
| 774 |
priorityN1Max, degreeN1Max, ifaceN1Max->GetAddress()) > 0) |
| 775 |
{ |
| 776 |
priorityN1Max = priorityN1; |
| 777 |
degreeN1Max = degreeN1; |
| 778 |
ifaceN1Max = ifaceN1; |
| 779 |
} |
| 780 |
} |
| 781 |
} |
| 782 |
else if (level < (K+1)) |
| 783 |
{ |
| 784 |
ifaceN1->SetVisited(false); |
| 785 |
} |
| 786 |
else if ((K+1) == level) |
| 787 |
{ |
| 788 |
ifaceN1->SetVisited(true); |
| 789 |
} |
| 790 |
else |
| 791 |
{ |
| 792 |
break; // we're done |
| 793 |
} |
| 794 |
} |
| 795 |
|
| 796 |
TRACE(" MECDS %s/%s n1_max: %s/%s (%d:%d:%d)\n", node->GetName(), iface->GetName(), ifaceN1Max->GetNode().GetName(), ifaceN1Max->GetName(), |
| 797 |
priorityN1Max, degreeN1Max, ifaceN1Max->GetAddress().GetEndIdentifier()); |
| 798 |
// E-CDS Step 4 decision |
| 799 |
//if (ifaceN1Max == iface) |
| 800 |
|
| 801 |
/*TRACE(" MECDS Step 4 compare %s/%s %d:%d:%d to %s/%s %d:%d:%d\n", |
| 802 |
iface->GetNode().GetName(), iface->GetName(), priority, degree, iface->GetAddress().GetEndIdentifier(), |
| 803 |
ifaceN1Max->GetNode().GetName(), ifaceN1Max->GetName(), degreeN1Max, degree, ifaceN1Max->GetAddress().GetEndIdentifier()); |
| 804 |
*/ |
| 805 |
if (ComparePriority(priority, degree, iface->GetAddress(), |
| 806 |
priorityN1Max, degreeN1Max, ifaceN1Max->GetAddress()) > 0) |
| 807 |
{ |
| 808 |
TRACE(" MECDS ENABLING iface %s/%s degree %d per step 4\n", node->GetName(), iface->GetName(), degree); |
| 809 |
iface->SetRelayStatus(true); |
| 810 |
node->SetRelayStatus(true); |
| 811 |
numberOfRelays += 1; |
| 812 |
continue; |
| 813 |
} |
| 814 |
//TRACE(" MCDS Step 7 (ifaceN1Max: %s/%s)...\n", ifaceN1Max->GetNode().GetName(), ifaceN1Max->GetName()); |
| 815 |
// E-CDS Step 7 |
| 816 |
CdsGraph::Interface::SimpleList Q; |
| 817 |
Q.Append(*ifaceN1Max); |
| 818 |
ifaceN1Max->SetVisited(true); |
| 819 |
// E-CDS Step 8 |
| 820 |
//TRACE(" MCDS Step 8 ...\n"); |
| 821 |
CdsInterface* x; |
| 822 |
while (NULL != (x = Q.RemoveHead())) |
| 823 |
{ |
| 824 |
//TRACE(" evaluating %s/%s ...\n", x->GetNode().GetName(), x->GetName()); |
| 825 |
CdsGraph::SimpleTraversal bfs1(graph, *x, true, collapseNodes); |
| 826 |
CdsInterface* n; |
| 827 |
unsigned int level; |
| 828 |
while (NULL != (n = bfs1.GetNextInterface(&level))) |
| 829 |
{ |
| 830 |
if (n == x) continue; |
| 831 |
//TRACE(" checking %s/%s level %u ...\n", n->GetNode().GetName(), n->GetName(), level); |
| 832 |
if (level >= K) break; |
| 833 |
if (n == iface) continue; |
| 834 |
if (n->WasVisited()) |
| 835 |
{ |
| 836 |
//TRACE(" already visited %s/%s ...\n", n->GetNode().GetName(), n->GetName()); |
| 837 |
continue; |
| 838 |
} |
| 839 |
|
| 840 |
n->SetVisited(true); |
| 841 |
UINT8 priorityN = n->GetRtrPriority(); |
| 842 |
unsigned int degreeN = useDegree ? n->GetDegree() : 0; |
| 843 |
//unsigned int degreeN = useDegree ? n->GetNode().GetTotalDegree() : 0; |
| 844 |
|
| 845 |
/*TRACE(" VISITED %s/%s %d:%d:%d and comparing to %s/%s %d:%d:%d\n", |
| 846 |
n->GetNode().GetName(), n->GetName(), priorityN, degreeN, n->GetAddress().GetEndIdentifier(), |
| 847 |
iface->GetNode().GetName(), iface->GetName(), priority, degree, iface->GetAddress().GetEndIdentifier()); |
| 848 |
*/ |
| 849 |
if (ComparePriority(priorityN, degreeN, n->GetAddress(), |
| 850 |
priority, degree, iface->GetAddress()) > 0) |
| 851 |
{ |
| 852 |
Q.Append(*n); |
| 853 |
} |
| 854 |
} |
| 855 |
|
| 856 |
/*CdsGraph::AdjacencyIterator adjacerator(*x); |
| 857 |
CdsInterface* n; |
| 858 |
while (NULL != (n = adjacerator.GetNextAdjacency())) |
| 859 |
{ |
| 860 |
if (n == iface) continue; |
| 861 |
if (n->WasVisited()) continue; |
| 862 |
n->SetVisited(true); |
| 863 |
UINT8 priorityN = n->GetRtrPriority(); |
| 864 |
unsigned int degreeN = useDegree ? n->GetDegree() : 0; |
| 865 |
TRACE(" compare %s/%s %d:%d:%d to %s/%s %d:%d:%d\n", |
| 866 |
n->GetNode().GetName(), n->GetName(), priorityN, degreeN, n->GetAddress().GetEndIdentifier(), |
| 867 |
iface->GetNode().GetName(), iface->GetName(), priority, degree, iface->GetAddress().GetEndIdentifier()); |
| 868 |
if (ComparePriority(priorityN, degreeN, n->GetAddress(), |
| 869 |
priority, degree, iface->GetAddress()) > 0) |
| 870 |
{ |
| 871 |
Q.Append(*n); |
| 872 |
} |
| 873 |
}*/ |
| 874 |
} |
| 875 |
|
| 876 |
// E-CDS Step 9 |
| 877 |
///TRACE(" MCDS Step 9 ...\n"); |
| 878 |
bfs.Reset(); |
| 879 |
bool isRelay = false; |
| 880 |
while (NULL != (ifaceN1 = bfs.GetNextInterface(&level))) |
| 881 |
{ |
| 882 |
if (ifaceN1 == iface) continue; |
| 883 |
if (level >= K) break; |
| 884 |
//if ((ifaceN1->GetDegree() > 0) && !ifaceN1->WasVisited()) |
| 885 |
if (!ifaceN1->WasVisited()) |
| 886 |
{ |
| 887 |
//TRACE("Interface %s/%s was NOT visited\n", ifaceN1->GetNode().GetName(), ifaceN1->GetName()); |
| 888 |
TRACE(" MECDS ENABLING iface %s/%s degree %d per step 9\n", node->GetName(), iface->GetName(), degree); |
| 889 |
iface->SetRelayStatus(true); |
| 890 |
node->SetRelayStatus(true); |
| 891 |
numberOfRelays += 1; |
| 892 |
isRelay = true; |
| 893 |
break; |
| 894 |
} |
| 895 |
} |
| 896 |
if (!isRelay) |
| 897 |
{ |
| 898 |
TRACE(" MECDS Disabling iface %s/%s degree %d per step 9\n", node->GetName(), iface->GetName(), degree); |
| 899 |
iface->SetRelayStatus(false); |
| 900 |
} |
| 901 |
} // end while (NULL != iface ...) |
| 902 |
} // end while (NULL != node ...) |
| 903 |
return numberOfRelays; |
| 904 |
} // end GraphRider::CalculateFullMECDS() |
| 905 |
|
| 906 |
// "relayList" is filled with the selected relays |
| 907 |
int GraphRider::CalculateFullECDS(NodeTree& nodeTree, |
| 908 |
CdsGraph& graph, |
| 909 |
bool useDegree, |
| 910 |
ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool) |
| 911 |
{ |
| 912 |
bool collapseNodes = false; |
| 913 |
// Now that we have a fully updated "graph", perform Relay Set Selection |
| 914 |
// algorithm for each node in graph |
| 915 |
int numberOfRelays = 0; |
| 916 |
NodeTree::Iterator noderator(nodeTree); |
| 917 |
Node* node; |
| 918 |
while (NULL != (node = noderator.GetNextItem())) |
| 919 |
{ |
| 920 |
node->SetVisited(false); |
| 921 |
UINT8 priority = node->GetRtrPriority(); |
| 922 |
unsigned int degree = node->GetDegree(); |
| 923 |
TRACE("ECDS check for node %s priority:%d:%d degree:%d...\n", node->GetName(), priority, node->GetId(), degree); |
| 924 |
// E-CDS Steps 1,2 |
| 925 |
if (degree < 2) |
| 926 |
{ |
| 927 |
// We are a leaf node |
| 928 |
TRACE(" ECDS disabling node %s as relay per Step 2\n", node->GetName()); |
| 929 |
node->SetRelayStatus(false); |
| 930 |
Node::InterfaceIterator it(*node); |
| 931 |
CdsInterface* iface; |
| 932 |
while (NULL != (iface = it.GetNextInterface())) |
| 933 |
iface->SetRelayStatus(false); |
| 934 |
continue; |
| 935 |
} |
| 936 |
if (!useDegree) degree = 0; |
| 937 |
|
| 938 |
|
| 939 |
//TRACE(" ECDS Steps 3-6 for node %s ...\n", node->GetName()); |
| 940 |
// E-CDS Step 3 is implicit as we already have the info in our graph |
| 941 |
|
| 942 |
// E-CDS Steps 4 (Find nodeN1Max) and 5 (mark N1 and N2 as unvisited) |
| 943 |
Node* nodeN1Max = NULL; |
| 944 |
UINT8 priorityN1Max = 0; |
| 945 |
unsigned int degreeN1Max = 0; |
| 946 |
|
| 947 |
CdsGraph::SimpleTraversal bfs(graph, *node->GetDefaultInterface(), true, collapseNodes); |
| 948 |
CdsInterface* ifaceN1; |
| 949 |
unsigned int level; |
| 950 |
Node::Queue visited; |
| 951 |
while (NULL != (ifaceN1 = bfs.GetNextInterface(&level))) |
| 952 |
{ |
| 953 |
Node& nodeN1 = ifaceN1->GetNode(); |
| 954 |
//TRACE(" to %s/%s at level %u\n", nodeN1.GetName(), ifaceN1->GetName(), level); |
| 955 |
if (&nodeN1 == node) continue; |
| 956 |
if (visited.Contains(nodeN1)) |
| 957 |
continue; |
| 958 |
else |
| 959 |
visited.Append(nodeN1); |
| 960 |
if (level < 2) |
| 961 |
{ |
| 962 |
nodeN1.SetVisited(false); |
| 963 |
UINT8 priorityN1 = nodeN1.GetRtrPriority(); |
| 964 |
unsigned int degreeN1 = useDegree ? nodeN1.GetDegree() : 0; |
| 965 |
if (NULL == nodeN1Max) |
| 966 |
{ |
| 967 |
priorityN1Max = priorityN1; |
| 968 |
degreeN1Max = degreeN1; |
| 969 |
nodeN1Max = &nodeN1; |
| 970 |
} |
| 971 |
else |
| 972 |
{ |
| 973 |
/*TRACE(" compare %s/%s %d:%d:%d to %s/%s %d:%d:%d\n", |
| 974 |
nodeN1.GetName(), nodeN1.GetDefaultInterface()->GetName(), priorityN1, degreeN1, nodeN1.GetAddress().GetEndIdentifier(), |
| 975 |
nodeN1Max->GetName(), nodeN1Max->GetDefaultInterface()->GetName(), priorityN1Max, degreeN1Max, nodeN1Max->GetAddress().GetEndIdentifier()); |
| 976 |
*/ |
| 977 |
if (ComparePriority(priorityN1, degreeN1, nodeN1.GetAddress(), |
| 978 |
priorityN1Max, degreeN1Max, nodeN1Max->GetAddress()) > 0) |
| 979 |
{ |
| 980 |
priorityN1Max = priorityN1; |
| 981 |
degreeN1Max = degreeN1; |
| 982 |
nodeN1Max = &nodeN1; |
| 983 |
//TRACE(" update max to %p\n", nodeN1Max); |
| 984 |
} |
| 985 |
} |
| 986 |
} |
| 987 |
else if (level < 3) |
| 988 |
{ |
| 989 |
nodeN1.SetVisited(false); |
| 990 |
} |
| 991 |
else if (3 == level) |
| 992 |
{ |
| 993 |
nodeN1.SetVisited(true); // Marking 3-hop neighbors as "visited" established order of our 2-hop neighborhood |
| 994 |
} |
| 995 |
else |
| 996 |
{ |
| 997 |
break; // we're done |
| 998 |
} |
| 999 |
} // end while bfs |
| 1000 |
visited.Empty(); |
| 1001 |
|
| 1002 |
if (NULL == nodeN1Max) |
| 1003 |
continue; |
| 1004 |
|
| 1005 |
TRACE(" ECDS %s n1_max: %s (%d:%d:%d)\n", node->GetName(), nodeN1Max->GetName(), priorityN1Max, degreeN1Max, nodeN1Max->GetAddress().GetEndIdentifier()); |
| 1006 |
|
| 1007 |
|
| 1008 |
if (ComparePriority(priority, degree, node->GetAddress(), |
| 1009 |
priorityN1Max, degreeN1Max, nodeN1Max->GetAddress()) > 0) |
| 1010 |
{ |
| 1011 |
//TRACE("node:%p max:%p\n", node, nodeN1Max); |
| 1012 |
TRACE(" ECDS ENABLING node %s as relay per Step 4 p:%d/%d pmax:%s/%d/%d \n", |
| 1013 |
node->GetName(), priority, degree, |
| 1014 |
nodeN1Max->GetName(), priorityN1Max, degreeN1Max); |
| 1015 |
node->SetRelayStatus(true); // // selected per E-CDS Step 4 |
| 1016 |
Node::InterfaceIterator it(*node); |
| 1017 |
CdsInterface* iface; |
| 1018 |
while (NULL != (iface = it.GetNextInterface())) |
| 1019 |
iface->SetRelayStatus(true); |
| 1020 |
numberOfRelays++; |
| 1021 |
continue; |
| 1022 |
} |
| 1023 |
// E-CDS Step 7 |
| 1024 |
ASSERT(NULL != nodeN1Max); |
| 1025 |
NodeQueue Q; |
| 1026 |
nodeN1Max->SetVisited(true); |
| 1027 |
Q.Append(*nodeN1Max); |
| 1028 |
Node* x; |
| 1029 |
// E-CDS Step 8 |
| 1030 |
while (NULL != (x = Q.RemoveHead())) |
| 1031 |
{ |
| 1032 |
//bool xIsInN1 = x->IsSymmetricNeighbor(*node); // true if 'x' is 1-hop neighbor of "n0" |
| 1033 |
Node::NeighborIterator nit(*x); |
| 1034 |
Node* n; |
| 1035 |
while (NULL != (n = nit.GetNextNeighbor())) |
| 1036 |
{ |
| 1037 |
if (n == node) continue; |
| 1038 |
if (!n->WasVisited()) |
| 1039 |
{ |
| 1040 |
n->SetVisited(true); |
| 1041 |
UINT8 priorityN = n->GetRtrPriority(); |
| 1042 |
unsigned int degreeN = useDegree ? n->GetDegree() : 0; |
| 1043 |
if (ComparePriority(priorityN, degreeN, n->GetAddress(), |
| 1044 |
priority, degree, node->GetAddress()) > 0) |
| 1045 |
{ |
| 1046 |
Q.Append(*n); |
| 1047 |
} |
| 1048 |
} |
| 1049 |
} |
| 1050 |
} |
| 1051 |
// E-CDS Step 9 |
| 1052 |
node->SetRelayStatus(false); |
| 1053 |
Node::NeighborIterator nit(*node); |
| 1054 |
Node* nodeN1; |
| 1055 |
bool isRelay = false; |
| 1056 |
while (NULL != (nodeN1 = nit.GetNextNeighbor())) |
| 1057 |
{ |
| 1058 |
if (!nodeN1->WasVisited()) |
| 1059 |
{ |
| 1060 |
TRACE(" ECDS ENABLING node %s as relay per Step 9\n", node->GetName()); |
| 1061 |
isRelay = true; |
| 1062 |
node->SetRelayStatus(true); |
| 1063 |
Node::InterfaceIterator it(*node); |
| 1064 |
CdsInterface* iface; |
| 1065 |
while (NULL != (iface = it.GetNextInterface())) |
| 1066 |
iface->SetRelayStatus(true); |
| 1067 |
numberOfRelays++; |
| 1068 |
break; |
| 1069 |
} |
| 1070 |
} |
| 1071 |
if (!isRelay) |
| 1072 |
{ |
| 1073 |
TRACE(" ECDS disabling node %s as relay per Step 9\n", node->GetName()); |
| 1074 |
node->SetRelayStatus(false); |
| 1075 |
Node::InterfaceIterator it(*node); |
| 1076 |
CdsInterface* iface; |
| 1077 |
while (NULL != (iface = it.GetNextInterface())) |
| 1078 |
iface->SetRelayStatus(false); |
| 1079 |
} |
| 1080 |
|
| 1081 |
} // end while (NULL != node ...) |
| 1082 |
return numberOfRelays; |
| 1083 |
} // end GraphRider::CalculateFullECDS() |
| 1084 |
|
| 1085 |
double GraphRider::CalculateDensity(CdsGraph& graph) |
| 1086 |
{ |
| 1087 |
int neighborCount = 0; |
| 1088 |
int nodeCount = 0; |
| 1089 |
CdsGraph::InterfaceIterator it(graph); |
| 1090 |
CdsGraph::Interface* iface; |
| 1091 |
while (NULL != (iface = it.GetNextInterface())) |
| 1092 |
{ |
| 1093 |
CdsGraph::AdjacencyIterator iteratorN1(*iface); |
| 1094 |
nodeCount++; |
| 1095 |
while (NULL != (iteratorN1.GetNextAdjacency())) |
| 1096 |
neighborCount++; |
| 1097 |
} |
| 1098 |
return ((double)neighborCount)/((double)nodeCount); |
| 1099 |
} // end GraphRider::CalculateDensity() |
| 1100 |
|
| 1101 |
////////////////////////////////////////////////////////////////////////////////////////// |
| 1102 |
// "GraphRider::FastReader" implementation |
| 1103 |
GraphRider::FastReader::FastReader(FILE* filePtr) |
| 1104 |
: file_ptr(filePtr), savecount(0) |
| 1105 |
{ |
| 1106 |
} |
| 1107 |
|
| 1108 |
GraphRider::FastReader::~FastReader() |
| 1109 |
{ |
| 1110 |
if (NULL != file_ptr) |
| 1111 |
{ |
| 1112 |
fclose(file_ptr); |
| 1113 |
file_ptr = NULL; |
| 1114 |
} |
| 1115 |
} |
| 1116 |
|
| 1117 |
GraphRider::FastReader::Result GraphRider::FastReader::Read(char* buffer, |
| 1118 |
unsigned int* len, |
| 1119 |
double timeout) |
| 1120 |
{ |
| 1121 |
unsigned int want = *len; |
| 1122 |
if (savecount) |
| 1123 |
{ |
| 1124 |
unsigned int ncopy = MIN(want, savecount); |
| 1125 |
memcpy(buffer, saveptr, ncopy); |
| 1126 |
savecount -= ncopy; |
| 1127 |
saveptr += ncopy; |
| 1128 |
buffer += ncopy; |
| 1129 |
want -= ncopy; |
| 1130 |
} |
| 1131 |
while (want) |
| 1132 |
{ |
| 1133 |
unsigned int result; |
| 1134 |
#ifndef WIN32 // no real-time input for WIN32 yet |
| 1135 |
if (timeout >= 0.0) |
| 1136 |
{ |
| 1137 |
int fd = fileno(file_ptr); |
| 1138 |
fd_set input; |
| 1139 |
FD_ZERO(&input); |
| 1140 |
struct timeval t; |
| 1141 |
t.tv_sec = (unsigned long)timeout; |
| 1142 |
t.tv_usec = (unsigned long)((1.0e+06 * (timeout - (double)t.tv_sec)) + 0.5); |
| 1143 |
FD_SET(fd, &input); |
| 1144 |
int status = select(fd+1, &input, NULL, NULL, &t); |
| 1145 |
switch (status) |
| 1146 |
{ |
| 1147 |
case -1: |
| 1148 |
if (EINTR != errno) |
| 1149 |
{ |
| 1150 |
perror("trpr: GraphRider::FastReader::Read() select() error"); |
| 1151 |
return ERROR_; |
| 1152 |
} |
| 1153 |
else |
| 1154 |
{ |
| 1155 |
continue; |
| 1156 |
} |
| 1157 |
break; |
| 1158 |
|
| 1159 |
case 0: |
| 1160 |
return TIMEOUT; |
| 1161 |
|
| 1162 |
default: |
| 1163 |
result = fread(savebuf, sizeof(char), 1, file_ptr); |
| 1164 |
break; |
| 1165 |
} |
| 1166 |
} |
| 1167 |
else |
| 1168 |
#endif // !WIN32 |
| 1169 |
{ |
| 1170 |
// Perform buffered read when there is no "timeout" |
| 1171 |
result = fread(savebuf, sizeof(char), BUFSIZE, file_ptr); |
| 1172 |
} |
| 1173 |
if (result) |
| 1174 |
{ |
| 1175 |
|
| 1176 |
// This check skips NULLs that have been read on some |
| 1177 |
// use of trpr via tail from an NFS mounted file |
| 1178 |
if (!isprint(*savebuf) && |
| 1179 |
('\t' != *savebuf) && |
| 1180 |
('\n' != *savebuf) && |
| 1181 |
('\r' != *savebuf)) |
| 1182 |
continue; |
| 1183 |
unsigned int ncopy= MIN(want, result); |
| 1184 |
memcpy(buffer, savebuf, ncopy); |
| 1185 |
savecount = result - ncopy; |
| 1186 |
saveptr = savebuf + ncopy; |
| 1187 |
buffer += ncopy; |
| 1188 |
want -= ncopy; |
| 1189 |
} |
| 1190 |
else // end-of-file |
| 1191 |
{ |
| 1192 |
#ifndef WIN32 |
| 1193 |
if (ferror(file_ptr)) |
| 1194 |
{ |
| 1195 |
if (EINTR == errno) continue; |
| 1196 |
} |
| 1197 |
#endif // !WIN32 |
| 1198 |
*len -= want; |
| 1199 |
if (0 != *len) |
| 1200 |
return OK; // we read at least something |
| 1201 |
else |
| 1202 |
return DONE; // we read nothing |
| 1203 |
} |
| 1204 |
} // end while(want) |
| 1205 |
return OK; |
| 1206 |
} // end GraphRider::FastReader::Read() |
| 1207 |
|
| 1208 |
// An OK text readline() routine (reads what will fit into buffer incl. NULL termination) |
| 1209 |
// if *len is unchanged on return, it means the line is bigger than the buffer and |
| 1210 |
// requires multiple reads |
| 1211 |
GraphRider::FastReader::Result GraphRider::FastReader::Readline(char* buffer, |
| 1212 |
unsigned int* len, |
| 1213 |
double timeout) |
| 1214 |
{ |
| 1215 |
unsigned int count = 0; |
| 1216 |
unsigned int length = *len; |
| 1217 |
char* ptr = buffer; |
| 1218 |
while (count < length) |
| 1219 |
{ |
| 1220 |
unsigned int one = 1; |
| 1221 |
switch (Read(ptr, &one, timeout)) |
| 1222 |
{ |
| 1223 |
case OK: |
| 1224 |
if (('\n' == *ptr) || ('\r' == *ptr)) |
| 1225 |
{ |
| 1226 |
*ptr = '\0'; |
| 1227 |
*len = count; |
| 1228 |
return OK; |
| 1229 |
} |
| 1230 |
count++; |
| 1231 |
ptr++; |
| 1232 |
break; |
| 1233 |
|
| 1234 |
case TIMEOUT: |
| 1235 |
// On timeout, save any partial line collected |
| 1236 |
if (count) |
| 1237 |
{ |
| 1238 |
savecount = MIN(count, BUFSIZE); |
| 1239 |
if (count < BUFSIZE) |
| 1240 |
{ |
| 1241 |
memcpy(savebuf, buffer, count); |
| 1242 |
savecount = count; |
| 1243 |
saveptr = savebuf; |
| 1244 |
*len = 0; |
| 1245 |
} |
| 1246 |
else |
| 1247 |
{ |
| 1248 |
memcpy(savebuf, buffer+count-BUFSIZE, BUFSIZE); |
| 1249 |
savecount = BUFSIZE; |
| 1250 |
saveptr = savebuf; |
| 1251 |
*len = count - BUFSIZE; |
| 1252 |
} |
| 1253 |
} |
| 1254 |
return TIMEOUT; |
| 1255 |
|
| 1256 |
case ERROR_: |
| 1257 |
return ERROR_; |
| 1258 |
|
| 1259 |
case DONE: |
| 1260 |
return DONE; |
| 1261 |
} |
| 1262 |
} |
| 1263 |
// We've filled up the buffer provided with no end-of-line |
| 1264 |
return ERROR_; |
| 1265 |
} // end GraphRider::FastReader::Readline() |
| 1266 |
|
| 1267 |
bool GraphRider::FastReader::Seek(int offset) |
| 1268 |
{ |
| 1269 |
bool result = true; |
| 1270 |
if (offset < 0) |
| 1271 |
{ |
| 1272 |
if (0 != savecount) |
| 1273 |
{ |
| 1274 |
int avail = saveptr - savebuf; |
| 1275 |
if (avail >= abs(offset)) |
| 1276 |
{ |
| 1277 |
savecount += abs(offset); |
| 1278 |
saveptr -= abs(offset); |
| 1279 |
offset = 0; |
| 1280 |
} |
| 1281 |
else |
| 1282 |
{ |
| 1283 |
offset -= savecount; |
| 1284 |
savecount = 0; |
| 1285 |
} |
| 1286 |
} |
| 1287 |
if (0 != offset) |
| 1288 |
result = (0 == fseek(file_ptr, offset, SEEK_CUR)); |
| 1289 |
} |
| 1290 |
else if (offset > 0) |
| 1291 |
{ |
| 1292 |
if ((unsigned int)offset < savecount) |
| 1293 |
{ |
| 1294 |
savecount -= offset; |
| 1295 |
saveptr += offset; |
| 1296 |
} |
| 1297 |
else |
| 1298 |
{ |
| 1299 |
if ((unsigned int)offset > savecount) |
| 1300 |
{ |
| 1301 |
result = (0 == fseek(file_ptr, offset - savecount, SEEK_CUR)); |
| 1302 |
} |
| 1303 |
savecount = 0; |
| 1304 |
} |
| 1305 |
} |
| 1306 |
return result; |
| 1307 |
} // end GraphRider::FastReader::Seek() |
| 1308 |
|
| 1309 |
|
| 1310 |
int main(int argc, char* argv[]) |
| 1311 |
{ |
| 1312 |
GraphRider graphRider; |
| 1313 |
const char* inputFile = NULL; |
| 1314 |
bool useDegree = false; |
| 1315 |
bool graphML = false; |
| 1316 |
|
| 1317 |
bool mecds = false; |
| 1318 |
|
| 1319 |
// Parse the command line |
| 1320 |
int i = 1; |
| 1321 |
while (i < argc) |
| 1322 |
{ |
| 1323 |
size_t len = strlen(argv[i]); |
| 1324 |
if (0 == strncmp(argv[i], "input", len)) |
| 1325 |
{ |
| 1326 |
if (++i >= argc) |
| 1327 |
{ |
| 1328 |
fprintf(stderr, "gr error: missing \"input\" argument!\n"); |
| 1329 |
Usage(); |
| 1330 |
return -1; |
| 1331 |
} |
| 1332 |
inputFile = argv[i]; |
| 1333 |
} |
| 1334 |
else if (0 == strncmp(argv[i], "degree", len)) |
| 1335 |
{ |
| 1336 |
useDegree = true; |
| 1337 |
} |
| 1338 |
else if (0 == strncmp(argv[i], "mecds", len)) |
| 1339 |
{ |
| 1340 |
mecds = true; |
| 1341 |
} |
| 1342 |
else if (0 == strncmp(argv[i], "link", len)) |
| 1343 |
{ |
| 1344 |
// link <name>,<priority> |
| 1345 |
if (++i >= argc) |
| 1346 |
{ |
| 1347 |
fprintf(stderr, "gr error: missing \"link\" argument!\n"); |
| 1348 |
Usage(); |
| 1349 |
return -1; |
| 1350 |
} |
| 1351 |
ProtoTokenator tk(argv[i], ','); |
| 1352 |
const char* item = tk.GetNextItem(); |
| 1353 |
GraphRider::LinkType* linkType = graphRider.GetLinkType(item); |
| 1354 |
if ((NULL == linkType) && (NULL == (linkType = graphRider.AddLinkType(item)))) |
| 1355 |
{ |
| 1356 |
fprintf(stderr, "gr new LinkTpye error: %s\n", GetErrorString()); |
| 1357 |
return -1; |
| 1358 |
} |
| 1359 |
item = tk.GetNextItem(); |
| 1360 |
if (NULL == item) |
| 1361 |
{ |
| 1362 |
|
| 1363 |
fprintf(stderr, "gr error: missing \"link priority\" argument!\n"); |
| 1364 |
Usage(); |
| 1365 |
return -1; |
| 1366 |
} |
| 1367 |
unsigned int priority; |
| 1368 |
if (1 != sscanf(item, "%u", &priority)) |
| 1369 |
{ |
| 1370 |
fprintf(stderr, "gr error: invalid \"link priority\" argument!\n"); |
| 1371 |
Usage(); |
| 1372 |
return -1; |
| 1373 |
} |
| 1374 |
linkType->SetRtrPriority(priority); |
| 1375 |
} |
| 1376 |
else |
| 1377 |
{ |
| 1378 |
fprintf(stderr, "gr error: invalid command: %s\n", argv[i]); |
| 1379 |
Usage(); |
| 1380 |
return -1; |
| 1381 |
} |
| 1382 |
i++; |
| 1383 |
} |
| 1384 |
|
| 1385 |
if (NULL == inputFile) |
| 1386 |
{ |
| 1387 |
fprintf(stderr, "gr error: no input file specified!\n"); |
| 1388 |
Usage(); |
| 1389 |
return -1; |
| 1390 |
} |
| 1391 |
|
| 1392 |
size_t len = strlen(inputFile); |
| 1393 |
if ((len > 2) && (0 == strcmp("ml", inputFile+len-2))) |
| 1394 |
graphML = true; |
| 1395 |
|
| 1396 |
if (graphML) |
| 1397 |
{ |
| 1398 |
|
| 1399 |
ManetGraphML graph; |
| 1400 |
if (!graph.Read(inputFile)) |
| 1401 |
{ |
| 1402 |
fprintf(stderr, "gr error: unable to parse GraphML input file!\n"); |
| 1403 |
return -1; |
| 1404 |
} |
| 1405 |
printf("gr: graphML loaded ...\n"); |
| 1406 |
ManetGraphML::InterfaceIterator ifaceIterator(graph); |
| 1407 |
// Get first iface to init Dijkstra |
| 1408 |
ManetGraphML::Interface* iface = ifaceIterator.GetNextInterface(); |
| 1409 |
ManetGraphML::DijkstraTraversal dijkstra(graph, iface->GetNode(), iface); |
| 1410 |
ifaceIterator.Reset(); |
| 1411 |
//std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now(); |
| 1412 |
while (NULL != (iface = ifaceIterator.GetNextInterface())) |
| 1413 |
{ |
| 1414 |
dijkstra.Reset(iface); |
| 1415 |
//std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now(); |
| 1416 |
ManetGraphML::Interface* dface; |
| 1417 |
while (NULL != (dface = dijkstra.GetNextInterface())) |
| 1418 |
{ |
| 1419 |
const ManetGraphML::Cost* cost = dijkstra.GetCost(*dface); |
| 1420 |
if (NULL != cost) |
| 1421 |
TRACE(" dijkstra iterated to iface \"%s\" cost:%lf\n", dface->GetName(), cost->GetValue()); |
| 1422 |
} |
| 1423 |
//std::chrono::high_resolution_clock::time_point t3 = std::chrono::high_resolution_clock::now(); |
| 1424 |
//unsigned int duration = (unsigned int)(std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count()); |
| 1425 |
//TRACE(" duration: %u\n", duration); |
| 1426 |
} |
| 1427 |
//std::chrono::high_resolution_clock::time_point t4 = std::chrono::high_resolution_clock::now(); |
| 1428 |
//unsigned int duration = (unsigned int)(std::chrono::duration_cast<std::chrono::microseconds>(t4 - t1).count()); |
| 1429 |
//TRACE("total duration: %u\n", duration); |
| 1430 |
} |
| 1431 |
else |
| 1432 |
{ |
| 1433 |
NodeTree& nodeTree = graphRider.AccessNodeTree(); |
| 1434 |
CdsGraph& graph = graphRider.AccessGraph(); |
| 1435 |
if (!graphRider.SetInputFile(inputFile)) |
| 1436 |
{ |
| 1437 |
perror("gr error: unable to open input file"); |
| 1438 |
return -1; |
| 1439 |
} |
| 1440 |
// This is a pool of ProtoGraph::Vertice::SortedList::Items |
| 1441 |
// that are used for temporary lists of CdsGraph::Interfaces |
| 1442 |
// for various graph manipulations, etc. Note that the use of an |
| 1443 |
// "external" item pool is _optional_ for the ProtoGraph/CdsGraph |
| 1444 |
// list classes, but can boost performance by reducing memory |
| 1445 |
// alloc/deallocs when doing a lot of list manipulation. |
| 1446 |
// If a list was inited with a "pool", then it is important to |
| 1447 |
// keep the "pool" valid until after any associate "lists" are |
| 1448 |
// destroyed as "pools" do _not_ keep track of which lists are |
| 1449 |
// using them (yet!). |
| 1450 |
ProtoGraph::Vertice::SortedList::ItemPool sortedVerticeItemPool; |
| 1451 |
|
| 1452 |
while (graphRider.ReadNextEpoch() >= 0.0) |
| 1453 |
{ |
| 1454 |
// We also build up a "disconnectedList" by first putting all nodes |
| 1455 |
// into it and then remove the relays and their one-hop neighbors. |
| 1456 |
// The disconnected nodes remaining in the list are colored "red" |
| 1457 |
|
| 1458 |
// a) Initialize our "disconnectedList" with all nodes in graph |
| 1459 |
NodeQueue disconnectedList; |
| 1460 |
NodeTree::Iterator nodeIterator(nodeTree); |
| 1461 |
Node* node; |
| 1462 |
while (NULL != (node = nodeIterator.GetNextItem())) |
| 1463 |
disconnectedList.Append(*node); |
| 1464 |
|
| 1465 |
// "CalculateFullECDS" implements the ECDS relay set selection |
| 1466 |
// algorithm, marking selected nodes using the Node::SetRelayStatus() |
| 1467 |
// method. |
| 1468 |
if (mecds) |
| 1469 |
GraphRider::CalculateFullMECDS(nodeTree, graph, useDegree, &sortedVerticeItemPool); |
| 1470 |
else |
| 1471 |
GraphRider::CalculateFullECDS(nodeTree, graph, useDegree, &sortedVerticeItemPool); |
| 1472 |
|
| 1473 |
// Iterate over our nodeTree and color the relays "purple" and their |
| 1474 |
// (non-relay) one-hop neighbors "green" removing them from the |
| 1475 |
// disconnectedList |
| 1476 |
nodeIterator.Reset(); |
| 1477 |
while (NULL != (node = nodeIterator.GetNextItem())) |
| 1478 |
{ |
| 1479 |
if (node->GetRelayStatus()) |
| 1480 |
{ |
| 1481 |
printf("node %s symbol circle,purple,3\n", node->GetName()); |
| 1482 |
if (disconnectedList.Contains(*node)) |
| 1483 |
disconnectedList.Remove(*node); |
| 1484 |
} |
| 1485 |
else |
| 1486 |
{ |
| 1487 |
printf("node %s symbol circle,green,3\n", node->GetName()); |
| 1488 |
} |
| 1489 |
// Color links from relays to other nodes thick and solid and links among non-relay nodes their link colors with skinny stipple |
| 1490 |
CdsInterface* iface1; |
| 1491 |
Node::InterfaceIterator it(*node); |
| 1492 |
while (NULL != (iface1 = it.GetNextInterface())) |
| 1493 |
{ |
| 1494 |
CdsGraph::AdjacencyIterator adjacerator(*iface1); |
| 1495 |
CdsInterface* iface2; |
| 1496 |
while (NULL != (iface2 = adjacerator.GetNextAdjacency())) |
| 1497 |
{ |
| 1498 |
GraphRider::LinkType* linkType = graphRider.GetLinkType(iface1->GetName()); |
| 1499 |
ASSERT(NULL != linkType); |
| 1500 |
const char* linkColor = linkType->GetColorName(); |
| 1501 |
//TRACE("iterating %s/%s->%s/%s ...\n", iface1->GetNode().GetName(), iface1->GetName(), iface2->GetNode().GetName(), iface2->GetName()); |
| 1502 |
if (iface1->GetRelayStatus() || iface2->GetRelayStatus()) |
| 1503 |
{ |
| 1504 |
if (iface1->GetRelayStatus()) ASSERT(iface1->GetNode().GetRelayStatus()); |
| 1505 |
if (iface2->GetRelayStatus()) ASSERT(iface2->GetNode().GetRelayStatus()); |
| 1506 |
// sdt link usage: link node1,node2,name line color,thickness,opacity,stipple |
| 1507 |
printf("link %s,%s,%s line %s,4,x,0\n", iface1->GetNode().GetName(), iface2->GetNode().GetName(), iface1->GetName(), linkColor); |
| 1508 |
Node& node2 = iface2->GetNode(); |
| 1509 |
if (disconnectedList.Contains(node2)) |
| 1510 |
disconnectedList.Remove(node2); |
| 1511 |
} |
| 1512 |
else |
| 1513 |
{ |
| 1514 |
// Make sure non-relay link colors are returned to non-purple state. |
| 1515 |
printf("link %s,%s,%s line %s,2,x,2,3855\n", iface1->GetNode().GetName(), iface2->GetNode().GetName(), iface1->GetName(), linkColor); |
| 1516 |
} |
| 1517 |
} |
| 1518 |
} |
| 1519 |
} |
| 1520 |
// Color any nodes remaining in "disconnectedList" red (orphans and orphan pairs) |
| 1521 |
// Make sure link colors are returned to non-purple state. |
| 1522 |
NodeQueue::Iterator dcIterator(disconnectedList); |
| 1523 |
while (NULL != (node = dcIterator.GetNextItem())) |
| 1524 |
{ |
| 1525 |
disconnectedList.Remove(*node); |
| 1526 |
printf("node %s symbol circle,red,3\n", node->GetName()); |
| 1527 |
CdsInterface* iface1; |
| 1528 |
Node::InterfaceIterator it(*node); |
| 1529 |
while (NULL != (iface1 = it.GetNextInterface())) |
| 1530 |
{ |
| 1531 |
CdsGraph::AdjacencyIterator adjacerator(*iface1); |
| 1532 |
CdsInterface* iface2; |
| 1533 |
while (NULL != (iface2 = adjacerator.GetNextAdjacency())) |
| 1534 |
{ |
| 1535 |
GraphRider::LinkType* linkType = graphRider.GetLinkType(iface1->GetName()); |
| 1536 |
ASSERT(NULL != linkType); |
| 1537 |
const char* linkColor = linkType->GetColorName(); |
| 1538 |
printf("link %s,%s,%s line %s,2,x,2,3855\n", iface1->GetNode().GetName(), iface2->GetNode().GetName(), iface1->GetName(), linkColor); |
| 1539 |
} |
| 1540 |
} |
| 1541 |
} |
| 1542 |
//double nodeDensity = GraphRider::CalculateDensity(graph); |
| 1543 |
} // end while ReadNextEpoch() |
| 1544 |
} // end if/else graphML |
| 1545 |
fprintf(stderr, "gr: Done.\n"); |
| 1546 |
return 0; |
| 1547 |
} // end main() |
| 1548 |
|