Debian Codegraph @

protolib/examples/graphExample.cpp

raw
1
2 // The purpose of this program is to illustrate use of the "NetGraphTemplate"
3 // classes. (Note the "NetGraphTemplate" allows different graph subclasses to
4 // be created with different metric properties. The "MyGraph" exaple here
5 // assumes a non-negative "double" value metric for "link cost".
6
7 #include "manetGraph.h"
8 #include "protoSpace.h" // we use this for its bounding box iteration
9 #include <protoDebug.h>
10 #include <protoDefs.h>
11
12 #include <stdio.h> // for sprintf()
13 #include <stdlib.h> // for rand(), srand()
14 #include <ctype.h> // for "isprint()"
15 #include <math.h> // for "sqrt()"
16
17 // "FastReader" is handy class I use for doing
18 // buffered (fast) reading of an input file.
19 class FastReader
20 {
21 public:
22 enum Result {OK, ERROR_, DONE, TIMEOUT};
23 FastReader(FILE* filePtr);
24 FastReader::Result Read(char* buffer,
25 unsigned int* len,
26 double timeout = -1.0);
27 FastReader::Result Readline(char* buffer,
28 unsigned int* len,
29 double timeout = -1.0);
30
31 bool Seek(int offset);
32
33 private:
34 enum {BUFSIZE = 2048};
35 FILE* file_ptr;
36 char savebuf[BUFSIZE];
37 char* saveptr;
38 unsigned int savecount;
39 }; // end class FastReader
40
41 void Usage()
42 {
43 fprintf(stderr, "Usage: graphExample <mobilityTraceFile>\n");
44 }
45
46 const unsigned int MAX_LINE = 256;
47
48 class MyNode;
49
50 class MyInterface : public NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, MyInterface, ManetLink, MyNode>
51 {
52 public:
53 MyInterface(MyNode& theNode, const ProtoAddress& addr)
54 : NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, MyInterface, ManetLink, MyNode>(theNode, addr) {}
55 MyInterface(MyNode& theNode)
56 : NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, MyInterface, ManetLink, MyNode>(theNode) {}
57 }; // end class MyInterface
58
59 class MyInterface;
60
61 class MyNode : public NetGraph::NodeTemplate<MyInterface>, public ProtoSpace::Node
62 {
63 public:
64 MyNode();
65 ~MyNode();
66
67 // _MUST_ call init to create a default interface
68 bool Init(const ProtoAddress& addr);
69
70 unsigned int GetId() const;
71
72 void SetRtrPriority(UINT8 value)
73 {rtr_priority = value;}
74 UINT8 GetRtrPriority() const
75 {return rtr_priority;}
76
77 void SetRelayStatus(bool state)
78 {relay_status = state;}
79 bool GetRelayStatus() const
80 {return relay_status;}
81
82 void SetVisited(bool state)
83 {visited = state;}
84 bool WasVisited() const
85 {return visited;}
86
87 void SetPosition(double xPos, double yPos)
88 {
89 ordinate[0] = xPos;
90 ordinate[1] = yPos;
91 }
92 double GetOrdinateX() const
93 {return ordinate[0];}
94 double GetOrdinateY() const
95 {return ordinate[1];}
96
97 // ProtoSpace::Node required overrides
98 unsigned int GetDimensions() const
99 {return 2;}
100 double GetOrdinate(unsigned int index) const
101 {return (ordinate[index]);}
102 const double* GetOrdinatePtr() const
103 {return ordinate;}
104
105 private:
106 UINT8 rtr_priority;
107 bool relay_status;
108 bool visited;
109 double ordinate[2]; // x,y coordinates
110
111 }; // end class MyNode
112
113
114 class MyGraph : public NetGraphTemplate<NetGraph::SimpleCostDouble, MyInterface, ManetLink, MyNode> {};
115
116
117 MyNode::MyNode()
118 : rtr_priority(0)
119 {
120 ordinate[0] = ordinate[1] = 0.0;
121 }
122
123 MyNode::~MyNode()
124 {
125 }
126
127 bool MyNode::Init(const ProtoAddress& addr)
128 {
129 MyGraph::Interface* iface = new MyGraph::Interface(*this, addr);
130 if (NULL != iface)
131 {
132 return AppendInterface(*iface);
133 }
134 else
135 {
136 PLOG(PL_ERROR, "MyNode::Init() new MyGraph::Interface() error: %s\n",
137 GetErrorString());
138 return false;
139 }
140 } // end MyNode::Init()
141
142 unsigned int MyNode::GetId() const
143 {
144 MyGraph::Interface* iface = GetDefaultInterface();
145 if (NULL != iface)
146 {
147 UINT8* addrPtr = (UINT8*)(iface->GetAddress().GetRawHostAddress());
148 unsigned int id = addrPtr[2];
149 id = (id << 8) + addrPtr[3];
150 return id;
151 }
152 else
153 {
154 ASSERT(0);
155 return ((unsigned int)-1);
156 }
157 } // end MyNode::GetId()
158
159 const double RANGE_MAX = 300.0;
160
161 inline double CalculateDistance(double x1, double y1, double x2,double y2)
162 {
163 double dx = x1 - x2;
164 double dy = y1 - y2;
165 return sqrt(dx*dx + dy*dy);
166 } // end CalculateDistance()
167
168 // This updates the "space" with data from the next time "epoch"
169 double ReadNextEpoch(FastReader& reader, ProtoSpace& space, MyGraph& graph);
170
171 // This updates the graph connectivity from the "space" and using "RANGE_MAX" comms range
172 bool UpdateGraphFromSpace(MyGraph& graph,
173 ProtoSpace& space,
174 ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool);
175
176 // This calculates an ECDS relay set given the "graph"
177 int CalculateFullECDS(MyGraph& graph,
178 MyGraph::Interface::SimpleList& relayList,
179 ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool);
180
181 // This calculates the nodal neighbor "density" of the given "graph"
182 double CalculateDensity(MyGraph& graph);
183
184
185 // Some "hacky" scaling factors to output a "GPS" version
186 // (some other code needs to be uncommented, etc to use this)
187 double X_MIN = -77.028633;
188 double X_MAX = -77.021267;
189 double X_SCALE = (X_MAX - X_MIN) / 1600.0;
190
191 double Y_MIN = 38.828533;
192 double Y_MAX = 38.822817;
193 double Y_SCALE = (Y_MAX - Y_MIN) / 600.0;
194
195
196 int main(int argc, char* argv[])
197 {
198
199 // argv[1] is expected to be an ns-2 "mobility trace" file
200 // (i.e. with "setdest" commands). This program uses the
201 // "destinations" given from "setdest" commands to as node
202 // positions. It does _not_ interpolate the "setdest"
203 // locations itself. We will eventually create a more useful
204 // version of this program (likely under a different name, etc)
205 // that can use our more recently developed node location/motion
206 // XML schema (See the NRL Mobile Network Modeling Tools).
207 if (argc < 2)
208 {
209 Usage();
210 return -1;
211 }
212
213 // Create a MyGraph instance that we will populate
214 // with nodes/interfaces from our "mobility trace file"
215 MyGraph graph;
216
217 // This is a pool of ProtoGraph::Vertice::SortedList::Items
218 // that are used for temporary lists of MyGraph::Interfaces
219 // as we adjust graph connectivity, etc. Note that the use of an
220 // "external" item pool is _optional_ for the ProtoGraph/MyGraph
221 // list classes, but can boost performance by reducing memory
222 // alloc/deallocs when doing a lot of list manipulation.
223 // If a list was inited with a "pool", then it is important to
224 // keep the "pool" valid until after any associate "lists" are
225 // destroyed as "pools" do _not_ keep track of which lists are
226 // using them (yet!).
227 ProtoGraph::Vertice::SortedList::ItemPool sortedVerticeItemPool;
228
229 // We use the ProtoSpace to organize nodes by their position
230 // and use the ProtoSpace bounding box iterator to efficiently
231 // find adjacencies
232 ProtoSpace space;
233
234 // Open the trace file for reading
235 FILE* infile = fopen(argv[1], "r");
236 if (NULL == infile)
237 {
238 perror("graphExample: fopen error");
239 return -1;
240 }
241
242 printf("bgbounds -100,-100,1500,500\n");
243
244 // Uncomment this for the "GPS" version
245 //printf("bgbounds -77.028633,38.828533,-77.021267,38.822817\n");
246
247
248 double lastTime = -1.0;
249 double nextTime;
250 FastReader reader(infile);
251 // "ReadNextEpoch" adds new "Nodes" to the "space" (and updates
252 // the position of Nodes from prior epochs - the "graph" is provided
253 // so that already existing "Nodes" can be found.)
254 while (0.0 <= (nextTime = ReadNextEpoch(reader, space, graph)))
255 {
256 // Output "wait" command for SDT visualization, if applicable
257 if (lastTime >= 0.0)
258 printf("wait %f\n", (float)(1000.0 * (nextTime - lastTime)));
259 lastTime = nextTime;
260
261
262 // "UpdateGraphFromSpace()" adds/removes "links" between the Nodes depending
263 // upon their spatial distance and the "RANGE_MAX" communications range
264 // (TBD - pass the "comms range" as a parameter to this function?)
265 TRACE("graphExample: Updating graph connections for time:%lf ..................................\n", nextTime);
266 if (!UpdateGraphFromSpace(graph, space, &sortedVerticeItemPool))
267 {
268 PLOG(PL_ERROR, "graphExample: error updating graph ...\n");
269 return -1;
270 }
271 TRACE("graphExample: Performing E-CDS relay set selection for time:%lf ===================================\n", nextTime);
272
273
274 // "CalculateFullECDS" implements the ECDS relay set selection
275 // algorithm, marking selected nodes using the MyNode::SetRelayStatus()
276 // method. It also copies the selected nodes into the "relayList"
277 // that is passed to it. (This is mainly for illustrative purposes
278 // to demonstrate the utility of the MyGraph lists, iterators, etc
279 MyGraph::Interface::SimpleList relayList;
280 int relays = CalculateFullECDS(graph, relayList, &sortedVerticeItemPool);
281 TRACE("relays is %d\n", relays);
282
283 // Iterate over our relay set and color the relays "blue" and their
284 // (non-relay) one-hop neighbors "green"
285 // We also build up a "disconnectedList" by first putting all nodes
286 // into it and then remove the relays and their one-hop neighbors.
287 // The disconnected nodes remaining in the list are colored "red"
288
289
290 // a) Initialize our "disconnectedList" with all ifaces in graph
291 // (note we _could_ have used the "sortedVerticeItemPool" here as
292 // well, but didn't to illustrate that it is optional. We
293 // would perform better here if did use it, though.
294 MyGraph::Interface::SortedList disconnectedList(&sortedVerticeItemPool);
295 MyGraph::InterfaceIterator ifaceIterator(graph);
296 MyGraph::Interface* iface;
297 while (NULL != (iface = ifaceIterator.GetNextInterface()))
298 disconnectedList.Insert(*iface);
299
300 // b) Remove relays (and their neighbors) from the "disconnectedList"
301 // and output appropriate node colors
302 MyGraph::Interface::SimpleList::Iterator relayIterator(relayList);
303 MyGraph::Interface* relayIface;
304 while (NULL != (relayIface = relayIterator.GetNextInterface()))
305 {
306 // It's a relay, so remove from disconnected list
307 if (NULL != disconnectedList.FindInterface(relayIface->GetAddress()))
308 disconnectedList.Remove(*relayIface);
309
310 MyNode& relayNode = relayIface->GetNode();
311 printf("node %d symbol circle,blue,3\n", relayNode.GetId());
312 MyGraph::AdjacencyIterator neighborIterator(*relayIface);
313 MyGraph::Interface* neighborIface;
314 while (NULL != (neighborIface = neighborIterator.GetNextAdjacency()))
315 {
316 // It's a relay neighbor, so remove from disconnected list
317 if (NULL != disconnectedList.FindInterface(neighborIface->GetAddress()))
318 disconnectedList.Remove(*neighborIface);
319 MyNode& neighborNode = neighborIface->GetNode();
320 if (!neighborNode.GetRelayStatus())
321 printf("node %d symbol circle,green,3\n", neighborNode.GetId());
322 }
323 }
324
325 // c) Color any nodes remaining in "disconnectedList" red
326 MyGraph::Interface::SortedList::Iterator dcIterator(disconnectedList);
327 MyGraph::Interface* disconnectedIface;
328 while (NULL != (disconnectedIface = dcIterator.GetNextInterface()))
329 {
330 MyNode& disconnectedNode =disconnectedIface->GetNode();
331 printf("node %d symbol circle,red,3\n", disconnectedNode.GetId());
332 }
333
334 double nodedensity = 0;
335 nodedensity = CalculateDensity(graph);
336 TRACE("density is %f\n",nodedensity);
337
338 }
339 fprintf(stderr, "graphExample: Done.\n");
340 return 0;
341 } // end main()
342
343
344 double ReadNextEpoch(FastReader& reader, ProtoSpace& space, MyGraph& graph)
345 {
346 double lastTime = -1.0;
347 // Read the "setdest" lines from the file, finding
348 // new nodes and their x,y positions versus time
349
350 // line format we want is '<sim> at <time> "<nodeName> setdest x y velocity"'
351 bool reading = true;
352 while (reading)
353 {
354 char buffer[MAX_LINE];
355 unsigned int len = MAX_LINE;
356 switch (reader.Readline(buffer, &len))
357 {
358 case FastReader::OK:
359 break;
360 case FastReader::ERROR_:
361 PLOG(PL_ERROR, "graphExample: error reading file\n");
362 return false;
363 case FastReader::DONE:
364 reading = false;
365 break;
366 case FastReader::TIMEOUT:
367 return false; // should never occur for this program
368 }
369
370 // Is this a new "time"?
371 char sim[32];
372 double time;
373 if (2 != sscanf(buffer, "%s at %lf", sim, &time))
374 continue; // go to next line
375
376 if (lastTime < 0.0)
377 {
378 TRACE("setting lastTime to %lf\n", time);
379 lastTime = time;
380 }
381 else if (time != lastTime)
382 {
383 // It's a new epoch, so seek backwards length of this line and return
384 reader.Seek(-len);
385 TRACE("returning lastTime %lf\n", lastTime);
386 return lastTime;
387 }
388
389 // Find leading quote of "nodeName setdest x y velocity" command
390 char* ptr = strchr(buffer, '\"');
391 if (NULL == ptr)
392 continue; // go to next line
393 else
394 ptr++;
395 char nodeName[32];
396 double x, y, vel;
397 if (4 != sscanf(ptr, "%s setdest %lf %lf %lf", nodeName, &x, &y, &vel))
398 continue;
399
400 // This rescales to our "gps" bounding box, but breaks our range
401 // calculation ...
402 /*
403 x = ((x + 100)*X_SCALE) + X_MIN;
404 y = ((y + 100)*Y_SCALE) + Y_MIN;
405 */
406
407 // Find numeric portion of "nodeName"
408 char nodeNamePrefix[32];
409 unsigned int nodeId;
410 if (2 != sscanf(nodeName, "%[^0-9]%u", nodeNamePrefix, &nodeId))
411 {
412 PLOG(PL_ERROR, "graphExample: nodeName \"%s\" has no numeric identifier content!\n", nodeName);
413 return false;
414 }
415
416 // Make/Update an entry nodeID into ManetSpace which was just read in
417 // Make an IPv4 addr from the "nodeId" for ManetSpace use
418
419 UINT8 ipv4Addr[4];
420 ipv4Addr[0] = 192;
421 ipv4Addr[1] = 168;
422 ipv4Addr[2] = nodeId / 256;
423 ipv4Addr[3] = nodeId % 256;
424 ProtoAddress addr;
425 addr.SetRawHostAddress(ProtoAddress::IPv4, (char*)ipv4Addr, 4);
426 MyNode* node = graph.FindNode(addr);
427
428 if (NULL == node)
429 {
430 // New node, create and insert into "space"
431 MyNode* node = new MyNode();
432 if (!node->Init(addr))
433 {
434 PLOG(PL_ERROR, "graphExample: error initializing new node!\n");
435 return -1;
436 }
437 node->SetPosition(x, y);
438 graph.InsertNode(*node);
439 if (!space.InsertNode(*node))
440 {
441 PLOG(PL_ERROR, "graphExample: error inserting node into space\n");
442 return -1;
443 }
444 // Output new node position for SDT visualization
445 printf("node %d position %f,%f symbol circle,red,3 label white\n", nodeId, x, y);
446 }
447 else
448 {
449 // Existing node, update position in "space", etc
450 TRACE("Removing node %d from space ...\n", nodeId);
451 space.RemoveNode(*node);
452 node->SetPosition(x, y);
453 space.InsertNode(*node);
454 // Update node position for SDT visualization
455 printf("node %d position %f,%f\n", nodeId, x, y);
456 }
457 } // end while reading()
458
459 TRACE("returning 2 lastTime %lf\n", lastTime);
460
461 return lastTime;
462 } // end ReadNextEpoch()
463
464 bool UpdateGraphFromSpace(MyGraph& graph, ProtoSpace& space, ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool)
465 {
466 MyGraph::InterfaceIterator it(graph);
467 MyGraph::Interface* iface;
468 ;
469 unsigned int count = 0;
470 while (NULL != (iface = it.GetNextInterface()))
471 {
472 MyNode& node = iface->GetNode();
473
474 const ProtoAddress& nodeAddr = iface->GetAddress();
475
476 // Cache list of node's current neighbors into
477 // a list we can retrieve from as we determine
478 // our "within range" nodes.
479 MyGraph::Interface::SortedList nbrList(sortedVerticeItemPool);
480 MyGraph::AdjacencyIterator nbrIterator(*iface);
481 MyGraph::Interface* nbrIface;
482 while (NULL != (nbrIface = nbrIterator.GetNextAdjacency()))
483 {
484 if (!nbrList.Insert(*nbrIface))
485 {
486 PLOG(PL_ERROR, "graphExample: error adding neighbor to temp list\n");
487 return false;
488 }
489 }
490
491 // Iterate through our ProtoSpace from this node's location,
492 // looking for neighbor nodes within RANGE_MAX distance
493 ProtoSpace::Iterator sit(space);
494 if (!sit.Init(node.GetOrdinatePtr()))
495 {
496 PLOG(PL_ERROR, "graphExample: error initializing space iterator\n");
497 return false;
498 }
499
500 MyNode* nbr;
501 count = 0;
502 double lastDist = -1.0;
503 double distance;
504 while (NULL != (nbr = static_cast<MyNode*>(sit.GetNextNode(&distance))))
505 {
506 count++;
507
508 /*
509 TRACE("Distance from %s to ", node.GetDefaultAddress().GetHostString());
510 TRACE("%s is %lf meters (xrange:%lf yrange:%lf) (count:%d)\n",
511 nbr->GetDefaultAddress().GetHostString(), distance,
512 fabs(x - nbr->GetOrdinateX()), fabs(y - nbr->GetOrdinateY()), count);
513 */
514
515 ASSERT(lastDist <= distance);
516 lastDist = distance;
517
518 if (nbr == &node)
519 {
520 TRACE("count:%d - %s found self\n", count, nodeAddr.GetHostString());
521 continue;
522 }
523
524 if (distance <= RANGE_MAX)
525 {
526 // Is this "nbr" already connected as a neighbor in our graph?
527 MyGraph::Interface* defaultIface = nbr->GetDefaultInterface();
528 ASSERT(NULL != defaultIface);
529 const ProtoAddress& nbrAddr = defaultIface->GetAddress();
530 nbrIface = nbrList.FindInterface(nbrAddr);
531 if (NULL == nbrIface)
532 {
533 TRACE("count:%d - connecting %s to ", count, nodeAddr.GetHostString());
534 TRACE("%s\n", nbrAddr.GetHostString());
535 MyGraph::SimpleCostDouble cost(1.0);
536 if (!graph.Connect(*iface, *defaultIface, cost, true))
537 {
538 PLOG(PL_ERROR, "graphExample error: unable to connect interfaces in graph\n");
539 return false;
540 }
541 printf("link %u,%u,green\n", node.GetId(), nbr->GetId());
542 }
543 else
544 {
545 TRACE("count:%d - %s already neighbor of ", count, nodeAddr.GetHostString());
546 TRACE("%s\n", nbrAddr.GetHostString());
547 nbrList.Remove(*nbrIface);
548 }
549 }
550 else
551 {
552 // Disconnect any former neighbors that were no longer in range
553 if (!nbrList.IsEmpty())
554 {
555 MyGraph::Interface::SortedList::Iterator listIterator(nbrList);
556 while (NULL != (nbrIface = listIterator.GetNextInterface()))
557 {
558 graph.Disconnect(*iface, *nbrIface, true);
559 TRACE("count:%d - %s no longer neighbor of ", count, nodeAddr.GetHostString());
560 TRACE("%s\n", nbrIface->GetAddress().GetHostString());
561 printf("unlink %u,%u\n", node.GetId(), nbrIface->GetNode().GetId());
562 }
563 }
564 break;
565 }
566 } // end while (NULL != nbr)
567 } // end while (NULL != node) (graph update)
568 return true;
569 } // end UpdateGraphFromSpace()
570
571 // "relayList" is filled with the selected relays
572 int CalculateFullECDS(MyGraph& graph,
573 MyGraph::Interface::SimpleList& relayList,
574 ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool)
575 {
576 // Now that we have a fully updated "graph", perform Relay Set Selection
577 // algorithm for each node in graph
578 int numberOfRelays=0;
579 MyGraph::InterfaceIterator it(graph);
580 MyGraph::Interface* iface;
581 while (NULL != (iface = it.GetNextInterface()))
582 {
583 MyNode& node = iface->GetNode();
584 UINT8 priority = node.GetRtrPriority();
585
586 // E-CDS Steps 1,2
587 TRACE(" node:%u adjacencyCount:%u\n", node.GetId(), iface->GetAdjacencyCount());
588
589 if (iface->GetAdjacencyCount() < 2)
590 {
591 node.SetRelayStatus(false);
592 continue;
593 }
594
595 // E-CDS Step 3,4,5, & 6
596 // "nbrList" will cache the "node" 1-hop neighbors for "visited" elimination with the path search
597 MyGraph::AdjacencyIterator iteratorN1(*iface);
598 MyGraph::Interface* ifaceN1Max = NULL;
599 bool isRelay = true; // this will be set to "false" if a test fails
600 MyGraph::Interface* ifaceN1;
601 while (NULL != (ifaceN1 = iteratorN1.GetNextAdjacency()))
602 {
603 MyNode& nodeN1 = ifaceN1->GetNode();
604 nodeN1.SetVisited(false); // init for later path search
605 // Save n1_max needed for E-CDS Step 6
606 UINT8 priorityN1 = nodeN1.GetRtrPriority();
607 if (NULL == ifaceN1Max)
608 {
609 ifaceN1Max = ifaceN1;
610 }
611 else
612 {
613 MyNode& nodeN1Max = ifaceN1Max->GetNode();
614 UINT8 priorityN1Max = nodeN1Max.GetRtrPriority();
615 if ((priorityN1 > priorityN1Max) ||
616 ((priorityN1 == priorityN1Max) &&
617 (nodeN1.GetId() > nodeN1Max.GetId())))
618 {
619 ifaceN1Max = ifaceN1;
620 }
621 }
622
623 if ((priorityN1 > priority) ||
624 ((priorityN1 == priority) &&
625 (nodeN1.GetId() > node.GetId())))
626 {
627 isRelay = false; // failed test of E-CDS Step 4
628 }
629 // Check 2-hop neighbors (other neighbors of N1)
630 MyGraph::AdjacencyIterator iteratorN2(*ifaceN1);
631 MyGraph::Interface* ifaceN2;
632 while (NULL != (ifaceN2 = iteratorN2.GetNextAdjacency()))
633 {
634 if (ifaceN2 == iface) continue; // was "iface" itself
635 if (iface->HasEdgeTo(*ifaceN2)) continue; // was 1-hop neighbor of "iface"
636 MyNode& nodeN2 = ifaceN2->GetNode();
637 nodeN2.SetVisited(false); // init for later path search
638 UINT8 priorityN2 = nodeN2.GetRtrPriority();
639 if ((priorityN2 > priority) ||
640 ((priorityN2 == priority) &&
641 (nodeN2.GetId() > node.GetId())))
642 {
643 isRelay = false; // failed test of E-CDS Step 4
644 }
645 } // end while (NULL != ifaceN2)
646 } // end (while (NULL != ifaceN1)
647 if (isRelay)
648 {
649 // Passed test of E-CDS Step 4
650 node.SetRelayStatus(true);
651 numberOfRelays++;
652 TRACE("node %u is relay by rule of step 4\n", node.GetId());
653 relayList.Append(*iface);
654 continue;
655 }
656
657 // E-CDS Step 7,8 - init path search 'Q'
658 ASSERT(NULL != ifaceN1Max);
659 MyGraph::Interface::SortedList Q(sortedVerticeItemPool);
660 if (!Q.Append(*ifaceN1Max))
661 {
662 PLOG(PL_ERROR, "graphExample: error adding 'ifaceN1Max' to 'Q'\n");
663 return -1;
664 }
665 ifaceN1Max->GetNode().SetVisited(true);
666 // E-CDS Step 8 - perform path search
667 TRACE(" e-cds path search starting\n");
668 MyGraph::Interface* x;
669 while (NULL != (x = Q.RemoveHead()))
670 {
671 bool xIsInN1 = x->HasEdgeTo(*iface);
672 MyGraph::AdjacencyIterator iteratorX(*x);
673 MyGraph::Interface* n;
674 while (NULL != (n = iteratorX.GetNextAdjacency()))
675 {
676 if (n == iface) continue; // was "iface" aka "n0"
677 bool nIsInN1 = n->HasEdgeTo(*iface);
678 if (!xIsInN1 && !nIsInN1) continue; // link not in "n0" 2-hop neighborhood
679 MyNode& nodeNn = n->GetNode();
680 if (!nodeNn.WasVisited())
681 {
682 // E-CDS Step 8a - mark node as "visited"
683 nodeNn.SetVisited(true);
684 // E-CDS Step 8b - check if RtrPri(n) > RtrPri(n0)
685 UINT8 priorityNn = nodeNn.GetRtrPriority();
686 if ((priorityNn > priority) ||
687 ((priorityNn == priority) &&
688 (nodeNn.GetId() > node.GetId())))
689 {
690 if (!Q.Append(*n))
691 {
692 PLOG(PL_ERROR, "graphExample: error adding 'n' to 'Q'\n");
693 return -1;
694 }
695 }
696 }
697 } // end while (NULL != n)
698 } // end while (NULL != x)
699 TRACE(" e-cds path search completed\n");
700 // E-CDS Step 9
701 bool relayStatus = false;
702 iteratorN1.Reset();
703 while (NULL != (ifaceN1 = iteratorN1.GetNextAdjacency()))
704 {
705 if (!ifaceN1->GetNode().WasVisited())
706 {
707 relayStatus = true;
708 numberOfRelays++;
709 break;
710 }
711 }
712 if (relayStatus)
713 {
714 TRACE("node %u is relay after path search\n", node.GetId());
715 relayList.Append(*iface);
716 }
717 node.SetRelayStatus(relayStatus);
718
719 } // while (NULL != node) (relay set selection)
720 return numberOfRelays;
721 } // end CalculateFullECDS()
722
723 double CalculateDensity(MyGraph& graph)
724 {
725 int neighborCount = 0;
726 int nodeCount = 0;
727 MyGraph::InterfaceIterator it(graph);
728 MyGraph::Interface* iface;
729 while (NULL != (iface = it.GetNextInterface()))
730 {
731 MyGraph::AdjacencyIterator iteratorN1(*iface);
732 nodeCount++;
733 while (NULL != (iteratorN1.GetNextAdjacency()))
734 neighborCount++;
735 }
736 return ((double)neighborCount)/((double)nodeCount);
737 } // end CalculateDensity()
738
739
740 //////////////////////////////////////////////////////////////////////////////////////////
741 // "FastReader" implementation
742 FastReader::FastReader(FILE* filePtr)
743 : file_ptr(filePtr), savecount(0)
744 {
745 }
746
747 FastReader::Result FastReader::Read(char* buffer,
748 unsigned int* len,
749 double timeout)
750 {
751 unsigned int want = *len;
752 if (savecount)
753 {
754 unsigned int ncopy = MIN(want, savecount);
755 memcpy(buffer, saveptr, ncopy);
756 savecount -= ncopy;
757 saveptr += ncopy;
758 buffer += ncopy;
759 want -= ncopy;
760 }
761 while (want)
762 {
763 unsigned int result;
764 #ifndef WIN32 // no real-time TRPR for WIN32 yet
765 if (timeout >= 0.0)
766 {
767 int fd = fileno(file_ptr);
768 fd_set input;
769 FD_ZERO(&input);
770 struct timeval t;
771 t.tv_sec = (unsigned long)timeout;
772 t.tv_usec = (unsigned long)((1.0e+06 * (timeout - (double)t.tv_sec)) + 0.5);
773 FD_SET(fd, &input);
774 int status = select(fd+1, &input, NULL, NULL, &t);
775 switch (status)
776 {
777 case -1:
778 if (EINTR != errno)
779 {
780 perror("trpr: FastReader::Read() select() error");
781 return ERROR_;
782 }
783 else
784 {
785 continue;
786 }
787 break;
788
789 case 0:
790 return TIMEOUT;
791
792 default:
793 result = fread(savebuf, sizeof(char), 1, file_ptr);
794 break;
795 }
796 }
797 else
798 #endif // !WIN32
799 {
800 // Perform buffered read when there is no "timeout"
801 result = fread(savebuf, sizeof(char), BUFSIZE, file_ptr);
802 // This check skips NULLs that have been read on some
803 // use of trpr via tail from an NFS mounted file
804 if (!isprint(*savebuf) &&
805 ('\t' != *savebuf) &&
806 ('\n' != *savebuf) &&
807 ('\r' != *savebuf))
808 continue;
809 }
810 if (result)
811 {
812 unsigned int ncopy= MIN(want, result);
813 memcpy(buffer, savebuf, ncopy);
814 savecount = result - ncopy;
815 saveptr = savebuf + ncopy;
816 buffer += ncopy;
817 want -= ncopy;
818 }
819 else // end-of-file
820 {
821 #ifndef WIN32
822 if (ferror(file_ptr))
823 {
824 if (EINTR == errno) continue;
825 }
826 #endif // !WIN32
827 *len -= want;
828 if (*len)
829 return OK; // we read at least something
830 else
831 return DONE; // we read nothing
832 }
833 } // end while(want)
834 return OK;
835 } // end FastReader::Read()
836
837 // An OK text readline() routine (reads what will fit into buffer incl. NULL termination)
838 // if *len is unchanged on return, it means the line is bigger than the buffer and
839 // requires multiple reads
840 FastReader::Result FastReader::Readline(char* buffer,
841 unsigned int* len,
842 double timeout)
843 {
844 unsigned int count = 0;
845 unsigned int length = *len;
846 char* ptr = buffer;
847 while (count < length)
848 {
849 unsigned int one = 1;
850 switch (Read(ptr, &one, timeout))
851 {
852 case OK:
853 if (('\n' == *ptr) || ('\r' == *ptr))
854 {
855 *ptr = '\0';
856 *len = count;
857 return OK;
858 }
859 count++;
860 ptr++;
861 break;
862
863 case TIMEOUT:
864 // On timeout, save any partial line collected
865 if (count)
866 {
867 savecount = MIN(count, BUFSIZE);
868 if (count < BUFSIZE)
869 {
870 memcpy(savebuf, buffer, count);
871 savecount = count;
872 saveptr = savebuf;
873 *len = 0;
874 }
875 else
876 {
877 memcpy(savebuf, buffer+count-BUFSIZE, BUFSIZE);
878 savecount = BUFSIZE;
879 saveptr = savebuf;
880 *len = count - BUFSIZE;
881 }
882 }
883 return TIMEOUT;
884
885 case ERROR_:
886 return ERROR_;
887
888 case DONE:
889 return DONE;
890 }
891 }
892 // We've filled up the buffer provided with no end-of-line
893 return ERROR_;
894 } // end FastReader::Readline()
895
896 bool FastReader::Seek(int offset)
897 {
898 bool result = true;
899 if (offset < 0)
900 {
901 if (0 != savecount)
902 {
903 int avail = saveptr - savebuf;
904 if (avail >= abs(offset))
905 {
906 savecount += abs(offset);
907 saveptr -= abs(offset);
908 offset = 0;
909 }
910 else
911 {
912 offset -= savecount;
913 savecount = 0;
914 }
915 }
916 if (0 != offset)
917 result = (0 == fseek(file_ptr, offset, SEEK_CUR));
918 }
919 else if (offset > 0)
920 {
921 if ((unsigned int)offset < savecount)
922 {
923 savecount -= offset;
924 saveptr += offset;
925 }
926 else
927 {
928 if ((unsigned int)offset > savecount)
929 {
930 result = (0 == fseek(file_ptr, offset - savecount, SEEK_CUR));
931 }
932 savecount = 0;
933 }
934 }
935 return result;
936 } // end FastReader::Seek()