Debian Codegraph @

protolib/examples/graphRider.cpp

raw
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