Debian Codegraph @

protolib/examples/graphXMLExample.cpp

raw
1
2 // The purpose of this program is to illustrate use of the "MyManetGraphML" class
3 // (Note the "NetGraphTemplate" allows different graph subclasses to be
4 // created with different metric properties. The "MyManetGraphML" assumes
5 // a non-negative "double" value metric for "link cost".
6
7 #include "manetGraphML.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 <string.h>
14 #include <stdlib.h> // for rand(), srand()
15 #include <ctype.h> // for "isprint()"
16 #include <math.h> // for "sqrt()"
17
18 #include <libxml/encoding.h>
19 #include <libxml/xmlwriter.h>
20 #include <libxml/xmlreader.h>
21 //#define MY_ENCODING "ISO-8859-1"
22 #define MY_ENCODING "UTF-8"
23
24 class Commands
25 {
26 public:
27 enum FileType {NONE, GML};
28
29 Commands() : inputFilePath(NULL),inputType(NONE),outputFilePath(NULL),outputType(NONE),doPathCalc(false),doDensityCalc(false),doECDSCalc(false) {}
30 ~Commands() {delete inputFilePath; delete outputFilePath;}
31 bool ProcessCommands(int argc,char* argv[]);
32
33 char* inputFilePath;
34 FileType inputType;
35 char* outputFilePath;
36 FileType outputType;
37 bool doPathCalc;
38 bool doDensityCalc;
39 bool doECDSCalc;
40 class ECDS
41 {
42 public:
43 ECDS() : usingDensity(false) {}
44 bool usingDensity;
45 } ecds;
46 } theCommands;
47
48 class LocalAttributeKey : public ProtoSortedTree::Item
49 {
50 public:
51 bool Init(const char* theIndex,const char* theName)
52 {
53 index = new char[sizeof(theIndex)];
54 strcpy(index,theIndex);
55 name = new char[sizeof(theName)];
56 strcpy(name,theName);
57 if((NULL == index) || (NULL == name))
58 return false;
59 return true;
60 }
61 ~LocalAttributeKey()
62 {
63 delete[] index;
64 delete[] name;
65 }
66 char* index;
67 char* name;
68 private:
69 virtual const char* GetKey() const {return index;}
70 virtual unsigned int GetKeysize() const {return strlen(index);}
71 };
72 typedef ProtoSortedTreeTemplate<LocalAttributeKey> KeyList;
73
74 // "FastReader" is handy class I use for doing
75 // buffered (fast) reading of an input file.
76 class FastReader
77 {
78 public:
79 enum Result {OK, ERROR_, DONE, TIMEOUT};
80 FastReader(FILE* filePtr);
81 FastReader::Result Read(char* buffer,
82 unsigned int* len,
83 double timeout = -1.0);
84 FastReader::Result Readline(char* buffer,
85 unsigned int* len,
86 double timeout = -1.0);
87
88 bool Seek(int offset);
89
90 private:
91 enum {BUFSIZE = 2048};
92 FILE* file_ptr;
93 char savebuf[BUFSIZE];
94 char* saveptr;
95 unsigned int savecount;
96 }; // end class FastReader
97
98 void Usage()
99 {
100 fprintf(stderr, "Usage: graphExample -ifile graphml <filename> -ofile graphml <filename> <-ecds <id|density>> <-density>\n");
101 }
102
103 const unsigned int MAX_LINE = 256;
104
105 class MyCost : public ManetGraph::Cost
106 {
107 public:
108 MyCost() {};
109 MyCost(double value) : ManetGraph::Cost(value) {};
110 };
111 class MyInterface;
112 class MyLink;
113 class MyNode: public NetGraph::NodeTemplate<MyInterface>, public ProtoSpace::Node
114 {
115 public:
116 MyNode();
117 ~MyNode();
118
119 void SetRtrPriority(int value)
120 {rtr_priority = value;}
121 UINT8 GetRtrPriority() const
122 {return rtr_priority;}
123
124 void SetRelayStatus(bool state)
125 {relay_status = state;}
126 bool GetRelayStatus() const
127 {return relay_status;}
128
129 void SetVisited(bool state)
130 {visited = state;}
131 bool WasVisited() const
132 {return visited;}
133 void SetNbrs(int theNbrs)
134 {nbrs = theNbrs;}
135 int GetNbrs() const
136 {return nbrs;}
137 void SetPosition(double xPos, double yPos)
138 {
139 ordinate[0] = xPos;
140 ordinate[1] = yPos;
141 }
142 double GetOrdinateX() const
143 {return ordinate[0];}
144 double GetOrdinateY() const
145 {return ordinate[1];}
146
147 // ProtoSpace::Node required overrides
148 unsigned int GetDimensions() const
149 {return 2;}
150 double GetOrdinate(unsigned int index) const
151 {return (ordinate[index]);}
152 const double* GetOrdinatePtr() const
153 {return ordinate;}
154 private:
155 int rtr_priority;
156 bool relay_status;
157 bool visited;
158 double ordinate[2]; // x,y coordinates
159 int nbrs;
160 }; // end class Node
161 class MyInterface : public NetGraph::InterfaceTemplate<MyCost,MyInterface,MyLink,MyNode>
162 {
163 public:
164 MyInterface(MyNode& theNode, const ProtoAddress& addr)
165 : NetGraph::InterfaceTemplate<MyCost,MyInterface,MyLink,MyNode>(theNode,addr) {}
166 MyInterface(MyNode& theNode)
167 : NetGraph::InterfaceTemplate<MyCost,MyInterface,MyLink,MyNode>(theNode) {}
168 private:
169 };
170
171 class MyLink : public NetGraph::LinkTemplate<MyCost,MyInterface>
172 {
173 public:
174 private:
175 };
176
177 MyNode::MyNode()
178 : rtr_priority(0)
179 {
180 ordinate[0] = ordinate[1] = 0.0;
181 }
182
183 MyNode::~MyNode()
184 {
185 }
186 class MyManetGraphML : public ManetGraphMLTemplate<MyCost,MyInterface,MyLink,MyNode>
187 {
188 public :
189 int GetId(MyNode &node) const;
190 KeyList keys;
191 protected :
192 bool UpdateKeys(NetGraph& theGraph);
193 bool UpdateNodeAttributes(NetGraph::Node& theNode);
194 bool UpdateInterfaceAttributes(NetGraph::Interface& theInterface);
195 bool UpdateLinkAttributes(NetGraph::Link& theLink);
196 private :
197 char* FindIndex(const char* theName);
198 };
199
200 int MyManetGraphML::GetId(MyNode &node) const
201 {
202 MyManetGraphML::Interface* iface = node.GetDefaultInterface();
203 if (NULL != iface)
204 {
205 const char* addrPtr = GetString(*iface);
206 int id=0;
207 for(int i = 0;i<(int)strlen(addrPtr);i++)
208 {
209 (i % 2) ? id += ((int)addrPtr[i]) << 8 : id += addrPtr[i];
210
211 }
212 return id;
213 }
214 else
215 {
216 ASSERT(0);
217 return ((int)-1);
218 }
219 }
220 bool MyManetGraphML::UpdateKeys(NetGraph& theGraph)
221 {
222 //buuny just use theCommands and add them!
223 //AddAttribute(name,boolean|int|double|float|double|string,node|edge|port,NULL,default
224 if(theCommands.doECDSCalc)
225 AddAttributeKey("ecdsrelay","boolean","node",NULL,"false");
226 if(theCommands.doDensityCalc)
227 AddAttributeKey("prio","int","node");
228 //do link attributes
229 AddAttributeKey("weight","double","edge",NULL,"1.0");
230 return true;
231 }
232 bool MyManetGraphML::UpdateNodeAttributes(NetGraph::Node& theNode)
233 {
234 bool rv = true;
235 if(theCommands.doECDSCalc)
236 {
237 if((static_cast<MyNode&>(theNode)).GetRelayStatus())
238 {
239 rv &= AddAttribute(theNode,"ecdsrelay","true");
240 } else {
241 rv &= AddAttribute(theNode,"ecdsrelay","false");
242 }
243 }
244 if(theCommands.doDensityCalc)
245 {
246 int prio = (static_cast<MyNode&>(theNode)).GetRtrPriority();
247 char prioStr[50];
248 sprintf(prioStr,"%d",prio);
249 rv &= AddAttribute(theNode,"prio",prioStr);
250 }
251 if(!rv)
252 {
253 PLOG(PL_ERROR,"MyManetGraphML::UpdateNodeAttributes: Error updating some of the attributes\n");
254 }
255 return rv;
256 }
257 bool MyManetGraphML::UpdateInterfaceAttributes(NetGraph::Interface& iface)
258 {
259 bool rv = true;
260 return rv;
261 }
262 /*bool MyManetGraphML::WriteNodeAttributes(xmlTextWriter* writerPtr, NetGraph::Node& theNode)
263 {
264 int xmlreturn = 0;
265
266 if(theCommands.doECDSCalc)
267 {
268 char *index = FindIndex("ecdsrelay");
269 xmlreturn += xmlTextWriterStartElement(writerPtr, BAD_CAST "data");
270 xmlreturn += xmlTextWriterWriteAttribute(writerPtr, BAD_CAST "key",BAD_CAST index);
271 if((static_cast<MyNode&>(theNode)).GetRelayStatus())
272 {
273 xmlreturn = xmlTextWriterWriteString(writerPtr, BAD_CAST "true");
274 } else {
275 xmlreturn = xmlTextWriterWriteString(writerPtr, BAD_CAST "false");
276 }
277 xmlreturn += xmlTextWriterEndElement(writerPtr);
278 }
279 if(theCommands.doDensityCalc)
280 {
281 int prio = (static_cast<MyNode&>(theNode)).GetRtrPriority();
282 char prioStr[50];
283 sprintf(prioStr,"%d",prio);
284 char *index = FindIndex("nbrs");
285 xmlreturn += xmlTextWriterStartElement(writerPtr, BAD_CAST "data");
286 xmlreturn += xmlTextWriterWriteAttribute(writerPtr, BAD_CAST "key",BAD_CAST index);
287 xmlreturn = xmlTextWriterWriteString(writerPtr, BAD_CAST prioStr);
288 xmlreturn += xmlTextWriterEndElement(writerPtr);
289 }
290
291 if(xmlreturn < 0) return false;
292 return true;
293 }*/
294 /*bool MyManetGraphML::WriteInterfaceAttributes(xmlTextWriter* writerPtr, NetGraph::Interface& theInterface)
295 {
296 int xmlreturn = 0;
297 xmlreturn = xmlTextWriterWriteAttribute(writerPtr, BAD_CAST "nameExamplePort", BAD_CAST "valueExamplePort");
298 if(xmlreturn < 0)
299 return false;
300 return true;
301 }*/
302 bool MyManetGraphML::UpdateLinkAttributes(NetGraph::Link& theLink)
303 {
304 bool rv = true;
305 char value[100];
306 sprintf(value,"%f",(static_cast<MyLink&>(theLink)).GetCost().GetValue());
307 rv &= AddAttribute(theLink,"weight",value);
308 if(!rv)
309 {
310 PLOG(PL_ERROR,"MyManetGraphML::UpdateLinkAttributes: Error updating some of the attributes\n");
311 }
312 return rv;
313 }
314 /*bool MyManetGraphML::WriteLinkAttributes(xmlTextWriter* writerPtr, NetGraph::Link& theLink)
315 {
316 int xmlreturn = 0;
317 char* index = FindIndex("weight");
318 char value[100];
319 sprintf(value,"%f",(static_cast<MyLink&>(theLink)).GetCost().GetValue());
320 xmlreturn += xmlTextWriterStartElement(writerPtr, BAD_CAST "data");
321 xmlreturn += xmlTextWriterWriteAttribute(writerPtr, BAD_CAST "key",BAD_CAST index);
322 xmlreturn = xmlTextWriterWriteString(writerPtr, BAD_CAST value);
323 xmlreturn += xmlTextWriterEndElement(writerPtr);
324 if(xmlreturn < 0)
325 return false;
326 return true;
327 }*/
328 char *
329 MyManetGraphML::FindIndex(const char* theName)
330 {
331 KeyList::Iterator kit(keys);
332 LocalAttributeKey* keyPtr = kit.GetNextItem();
333 char* index = NULL;
334 while(keyPtr && (!index))
335 {
336 if(!strcmp(keyPtr->name,theName))
337 {
338 //printf("%s\n",keyPtr->index);
339 index = keyPtr->index;
340 }
341 keyPtr=kit.GetNextItem();
342 }
343 return index;
344 }
345 const double RANGE_MAX = 300.0;
346
347 inline double CalculateDistance(double x1, double y1, double x2,double y2)
348 {
349 double dx = x1 - x2;
350 double dy = y1 - y2;
351 return sqrt(dx*dx + dy*dy);
352 } // end CalculateDistance()
353
354 // This updates the graph connectivity from the "space" and using "RANGE_MAX" comms range
355 bool UpdateGraphFromSpace(MyManetGraphML& graph,
356 ProtoSpace& space,
357 ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool);
358
359 // This calculates an ECDS relay set given the "graph"
360 int CalculateFullECDS(MyManetGraphML& graph,
361 MyManetGraphML::Interface::SimpleList& relayList,
362 ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool);
363 void CalculateRouterPriority(MyManetGraphML& graph,bool usingDensity);
364 // This calculates the # of paths from 1 to 10 in the graph
365 int CalculatePaths(MyManetGraphML& graph);
366 int CountPaths(MyManetGraphML::Interface* source, MyManetGraphML::Interface* dest,int depth,int* patharray,int maxdepth); //recursive function depth first path search
367 // This calculates the nodal neighbor "density" of the given "graph"
368 double CalculateDensity(MyManetGraphML& graph);
369
370
371 // Some "hacky" scaling factors to output a "GPS" version
372 // (some other code needs to be uncommented, etc to use this)
373 double X_MIN = -77.028633;
374 double X_MAX = -77.021267;
375 double X_SCALE = (X_MAX - X_MIN) / 1600.0;
376
377 double Y_MIN = 38.828533;
378 double Y_MAX = 38.822817;
379 double Y_SCALE = (Y_MAX - Y_MIN) / 600.0;
380
381 int main(int argc, char* argv[])
382 {
383
384 // argv[1] is expected to be an ns-2 "mobility trace" file
385 // (i.e. with "setdest" commands). This program uses the
386 // "destinations" given from "setdest" commands to as node
387 // positions. It does _not_ interpolate the "setdest"
388 // locations itself. We will eventually create a more useful
389 // version of this program (likely under a different name, etc)
390 // that can use our more recently developed node location/motion
391 // XML schema (See the NRL Mobile Network Modeling Tools).
392 if(!theCommands.ProcessCommands(argc-1,argv+1))
393 {
394 Usage();
395 return -1;
396 }
397 // Create a MyManetGraphML instance that we will populate
398 // with nodes/interfaces from our "mobility trace file"
399 MyManetGraphML graph;
400
401 if(Commands::GML == theCommands.inputType)
402 {
403 printf("reading file\"%s\"\n",theCommands.inputFilePath);
404 graph.Read(theCommands.inputFilePath);
405 }
406 // This is a pool of ProtoGraph::Vertice::SortedList::Items
407 // that are used for temporary lists of MyManetGraphML::Interfaces
408 // as we adjust graph connectivity, etc. Note that the use of an
409 // "external" item pool is _optional_ for the ProtoGraph/MyManetGraphML
410 // list classes, but can boost performance by reducing memory
411 // alloc/deallocs when doing a lot of list manipulation.
412 // If a list was inited with a "pool", then it is important to
413 // keep the "pool" valid until after any associate "lists" are
414 // destroyed as "pools" do _not_ keep track of which lists are
415 // using them (yet!).
416 //TRACE("graphXMLExample: before verticeitempool decleration\n");
417 ProtoGraph::Vertice::SortedList::ItemPool sortedVerticeItemPool;
418 //TRACE("graphXMLExample: after verticeitempool decleration\n");
419 // We use the ProtoSpace to organize nodes by their position
420 // and use the ProtoSpace bounding box iterator to efficiently
421 // find adjacencies
422 ProtoSpace space;
423
424 if(theCommands.doPathCalc)
425 {
426 int paths = CalculatePaths(graph);
427 TRACE("paths = %d\n",paths);
428 }
429 MyManetGraphML::Interface::SortedList disconnectedList(&sortedVerticeItemPool);
430 MyManetGraphML::InterfaceIterator ifaceIterator(graph);
431 MyManetGraphML::Interface::SimpleList relayList;
432
433 //int relays = CalculateFullECDS(graph, relayList, &sortedVerticeItemPool);
434 //int relays = CalculateFullECDS(graph, relayList, NULL);
435 if(theCommands.doECDSCalc)
436 {
437 //TRACE("graphExample: Performing E-CDS relay set selection ===================================\n");
438
439
440 // "CalculateFullECDS" implements the ECDS relay set selection
441 // algorithm, marking selected nodes using the Node::SetRelayStatus()
442 // method. It also copies the selected nodes into the "relayList"
443 // that is passed to it. (This is mainly for illustrative purposes
444 // to demonstrate the utility of the MyManetGraphML lists, iterators, etc
445 //theCommands.ecds.usingDensity ? TRACE("true\n") : TRACE("false\n");
446 CalculateRouterPriority(graph,theCommands.ecds.usingDensity);
447 MyManetGraphML::Interface::SimpleList relayList;
448 //CalculateRouterPriority(graph);
449 int relays = CalculateFullECDS(graph, relayList, &sortedVerticeItemPool);
450 TRACE("graphXMLExample:: E-CDS relays is %d\n",relays);
451
452 // Iterate over our relay set and color the relays "blue" and their
453 // (non-relay) one-hop neighbors "green"
454 // We also build up a "disconnectedList" by first putting all nodes
455 // into it and then remove the relays and their one-hop neighbors.
456 // The disconnected nodes remaining in the list are colored "red"
457
458
459 // a) Initialize our "disconnectedList" with all ifaces in graph
460 // (note we _could_ have used the "sortedVerticeItemPool" here as
461 // well, but didn't to illustrate that it is optional. We
462 // would perform better here if did use it, though.
463 MyManetGraphML::Interface::SortedList disconnectedList(&sortedVerticeItemPool);
464 MyManetGraphML::InterfaceIterator ifaceIterator(graph);
465 MyManetGraphML::Interface* iface;
466 while (NULL != (iface = ifaceIterator.GetNextInterface()))
467 {
468 //TRACE("Example:: getting key size of %s\n",graph.GetString(*iface));
469 //TRACE("Example:: the iface pointer = %p, the iterator pointer = %p\n",iface,&ifaceIterator);
470 //iface->GetKeysize();
471 //TRACE("Example:: it crashes here with key size %d\n",iface->GetKeysize());
472 disconnectedList.Insert(*iface);
473 // TRACE("inserting %s\n",graph.GetString(*iface));
474 }
475 // b) Remove relays (and their neighbors) from the "disconnectedList"
476 // and output appropriate node colors
477 MyManetGraphML::Interface::SimpleList::Iterator relayIterator(relayList);
478 MyManetGraphML::Interface* relayIface;
479 while (NULL != (relayIface = relayIterator.GetNextInterface()))
480 {
481 // It's a relay, so remove from disconnected list
482 if(relayIface->GetAddress().IsValid())
483 {
484 if (NULL != disconnectedList.FindInterface(relayIface->GetAddress()))
485 disconnectedList.Remove(*relayIface);
486 } else {
487 if (NULL != disconnectedList.FindInterfaceByName(relayIface->GetName()))
488 disconnectedList.Remove(*relayIface);
489 }
490 //MyNode& relayNode = relayIface->GetNode();
491 //printf("node %s symbol circle,blue,3\n", graph.GetString(relayNode));
492 MyManetGraphML::AdjacencyIterator neighborIterator(*relayIface);
493 MyManetGraphML::Interface* neighborIface;
494 while (NULL != (neighborIface = neighborIterator.GetNextAdjacency()))
495 {
496 // It's a relay neighbor, so remove from disconnected list
497 if(neighborIface->GetAddress().IsValid())
498 {
499 //printf(" bunny found %s",neighborIface->GetAddress().GetHostString());
500 //printf("aka %s\n",neighborIface->GetName());
501 if (NULL != disconnectedList.FindInterface(neighborIface->GetAddress()))
502 disconnectedList.Remove(*neighborIface);
503 } else {
504 //printf(" bunny looking for%s\n",neighborIface->GetName());
505 if (NULL != disconnectedList.FindInterfaceByName(neighborIface->GetName()))
506 disconnectedList.Remove(*neighborIface);
507 }
508 MyNode& neighborNode = neighborIface->GetNode();
509 if (!neighborNode.GetRelayStatus())
510 ;//printf("node %s symbol circle,green,3\n", graph.GetString(neighborNode));
511 }
512 }
513
514 //TRACE("bunny 2 relays is %d\n",relays);
515 // c) Color any nodes remaining in "disconnectedList" red
516 MyManetGraphML::Interface::SortedList::Iterator dcIterator(disconnectedList);
517 MyManetGraphML::Interface* disconnectedIface;
518 while (NULL != (disconnectedIface = dcIterator.GetNextInterface()))
519 {
520 MyNode& disconnectedNode = disconnectedIface->GetNode();
521 printf("node %s symbol circle,red,3\n", graph.GetString(disconnectedNode));
522 }
523 // TRACE("bunny 3 relays is %d\n",relays);
524 }
525 if(theCommands.doDensityCalc)
526 {
527 double nodedensity = 0;
528 //TRACE("doing density calc...\n");
529 nodedensity = CalculateDensity(graph);
530 TRACE("density is %f\n",nodedensity);
531 //fprintf(ofile,"%f,%d\n",nodedensity,paths);
532 }
533 if(Commands::GML == theCommands.outputType)
534 {
535 graph.Write(theCommands.outputFilePath);
536 }
537 fprintf(stderr, "GraphXMLExample: Done.\n");
538 return 0;
539 } // end main()
540
541 bool
542 Commands::ProcessCommands(int argc,char* argv[])
543 {
544 for(int i=0;NULL !=argv[i];i++)
545 {
546 if(!strcmp(argv[i],"-ifile"))
547 {
548 i++;
549 if(!strcmp(argv[i],"graphml"))
550 {
551 i++;
552 inputType = GML;
553 if(NULL == argv[i])
554 {
555 PLOG(PL_ERROR,"Commands::ProcessCommands Error no input file path\n");
556 return false;
557 }
558 inputFilePath = new char[strlen(argv[i])];
559 if(NULL == inputFilePath)
560 {
561 PLOG(PL_ERROR,"Commands::ProcessCommands Error allocating space for input file path\n");
562 return false;
563 }
564 memset(inputFilePath,0,strlen(argv[i]));
565 strcpy(inputFilePath,argv[i]);
566 } else {
567 PLOG(PL_ERROR,"Commands::ProcessCommands Error unknown input file format \"%s\"\n",argv[i]);
568 return false;
569 }
570 } else if (!strcmp(argv[i],"-ofile")) {
571 i++;
572 if(!strcmp(argv[i],"graphml"))
573 {
574 i++;
575 outputType = GML;
576 if(NULL == argv[i])
577 {
578 PLOG(PL_ERROR,"Commands::ProcessCommands Error no output file path\n");
579 return false;
580 }
581 outputFilePath = new char[strlen(argv[i])];
582 if(NULL == outputFilePath)
583 {
584 PLOG(PL_ERROR,"Commands::ProcessCommands Error allocating space for output file path\n");
585 return false;
586 }
587 memset(outputFilePath,0,strlen(argv[i]));
588 strcpy(outputFilePath,argv[i]);
589 } else {
590 PLOG(PL_ERROR,"Commands::ProcessCommands Error unknown output file format \"%s\"\n",argv[i]);
591 return false;
592 }
593 } else if (!strcmp(argv[i],"-ecds")) {
594 doECDSCalc = true;
595 i++;
596 if(NULL != argv[i]){
597 if(!strcmp(argv[i],"id")) {
598 ecds.usingDensity = false;
599 } else if (!strcmp(argv[i],"density")) {
600 ecds.usingDensity = true;
601 } else {
602 i--;
603 }
604 } else {
605 i--;
606 }
607 } else if (!strcmp(argv[i],"-density")) {
608 doDensityCalc = true;
609 } else {
610 PLOG(PL_ERROR,"Commands::ProcessCommands Error Unknown command \"%s\"\n",argv[i]);
611 return false;
612 }
613 }
614 return true;
615 }
616 bool UpdateGraphFromSpace(MyManetGraphML& graph, ProtoSpace& space, ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool)
617 {
618 MyManetGraphML::InterfaceIterator it(graph);
619 MyManetGraphML::Interface* iface;
620 ;
621 unsigned int count = 0;
622 while (NULL != (iface = it.GetNextInterface()))
623 {
624 MyNode& node = iface->GetNode();
625
626 //const ProtoAddress& nodeAddr = iface->GetAddress();
627
628 // Cache list of node's current neighbors into
629 // a list we can retrieve from as we determine
630 // our "within range" nodes.
631 MyManetGraphML::Interface::SortedList nbrList(sortedVerticeItemPool);
632 MyManetGraphML::AdjacencyIterator nbrIterator(*iface);
633 MyManetGraphML::Interface* nbrIface;
634 while (NULL != (nbrIface = nbrIterator.GetNextAdjacency()))
635 {
636 if (!nbrList.Insert(*nbrIface))
637 {
638 PLOG(PL_ERROR, "graphExample: error adding neighbor to temp list\n");
639 return false;
640 }
641 }
642
643 // Iterate through our ProtoSpace from this node's location,
644 // looking for neighbor nodes within RANGE_MAX distance
645 ProtoSpace::Iterator sit(space);
646 if (!sit.Init(node.GetOrdinatePtr()))
647 {
648 PLOG(PL_ERROR, "graphExample: error initializing space iterator\n");
649 return false;
650 }
651
652 MyNode* nbr;
653 count = 0;
654 double lastDist = -1.0;
655 double distance;
656 while (NULL != (nbr = static_cast<MyNode*>(sit.GetNextNode(&distance))))
657 {
658 count++;
659
660 /*
661 TRACE("Distance from %s to ", node.GetDefaultAddress().GetHostString());
662 TRACE("%s is %lf meters (xrange:%lf yrange:%lf) (count:%d)\n",
663 nbr->GetDefaultAddress().GetHostString(), distance,
664 fabs(x - nbr->GetOrdinateX()), fabs(y - nbr->GetOrdinateY()), count);
665 */
666
667 ASSERT(lastDist <= distance);
668 lastDist = distance;
669
670 if (nbr == &node)
671 {
672 //TRACE("count:%d - %s found self\n", count, nodeAddr.GetHostString());
673 continue;
674 }
675
676 if (distance <= RANGE_MAX)
677 {
678 // Is this "nbr" already connected as a neighbor in our graph?
679 MyManetGraphML::Interface* defaultIface = nbr->GetDefaultInterface();
680 ASSERT(NULL != defaultIface);
681 const ProtoAddress& nbrAddr = defaultIface->GetAddress();
682 nbrIface = nbrList.FindInterface(nbrAddr);
683 if (NULL == nbrIface)
684 {
685 //TRACE("count:%d - connecting %s to ", count, nodeAddr.GetHostString());
686 //TRACE("%s\n", nbrAddr.GetHostString());
687 MyManetGraphML::SimpleCostDouble cost(1.0);
688 if (!graph.Connect(*iface, *defaultIface, cost, true))
689 {
690 PLOG(PL_ERROR, "graphExample error: unable to connect interfaces in graph\n");
691 return false;
692 }
693 printf("link %s,%s,green\n", graph.GetString(node), graph.GetString(*nbr));
694 }
695 else
696 {
697 //TRACE("count:%d - %s already neighbor of ", count, nodeAddr.GetHostString());
698 //TRACE("%s\n", nbrAddr.GetHostString());
699 nbrList.Remove(*nbrIface);
700 }
701 }
702 else
703 {
704 // Disconnect any former neighbors that were no longer in range
705 if (!nbrList.IsEmpty())
706 {
707 MyManetGraphML::Interface::SortedList::Iterator listIterator(nbrList);
708 while (NULL != (nbrIface = listIterator.GetNextInterface()))
709 {
710 graph.Disconnect(*iface, *nbrIface, true);
711 //TRACE("count:%d - %s no longer neighbor of ", count, nodeAddr.GetHostString());
712 //TRACE("%s\n", nbrIface->GetAddress().GetHostString());
713 //printf("unlink %u,%u\n", node.GetId(), static_cast<Node&>(nbrIface->GetNode()).GetId());
714 }
715 }
716 break;
717 }
718 } // end while (NULL != nbr)
719 } // end while (NULL != node) (graph update)
720 return true;
721 } // end UpdateGraphFromSpace()
722
723 int CalculatePaths(MyManetGraphML& graph)
724 {
725 TRACE("in calculate paths\n");
726 MyManetGraphML::InterfaceIterator it(graph);
727 MyManetGraphML::Interface* isource;
728 MyManetGraphML::Interface* idest;
729 isource = it.GetNextInterface();
730 idest = it.GetNextInterface();
731
732 MyManetGraphML::Node node;
733 it.Reset();
734 MyManetGraphML::Interface* interface;
735 while (NULL != (interface = it.GetNextInterface()))
736 {
737 MyNode& node = interface->GetNode();
738 node.SetVisited(false);
739 //TRACE(" visiting %s\n",graph.GetString(node));
740 }
741
742 MyNode& node1 = isource->GetNode();
743 //int nodeid1 = node1.GetId();
744 MyNode& node2 = idest->GetNode();
745 //int nodeid2 = node2.GetId();
746 TRACE("calculating paths from %s to",graph.GetString(node1));
747 TRACE(" %s\n",graph.GetString(node2));
748 int maxdepth = 20;
749 int* patharray = (int*) malloc (maxdepth*4);
750 memset(patharray,0,maxdepth*4);
751 int paths = CountPaths(isource,idest,0,patharray,maxdepth);
752 for(int i=0;i<maxdepth;i++)
753 {
754 TRACE("#paths at depth %d: %d\n",i,patharray[i]);
755 }
756 return paths;
757 }
758 int CountPaths(MyManetGraphML::Interface* isource,MyManetGraphML::Interface* idest,int depth,int* patharray,int maxdepth)
759 {
760 char spaces[255];
761 memset(spaces,' ',255);
762 memset(spaces+depth,0,1);
763 if(depth> maxdepth) exit(0);
764 //Node& node1 = static_cast<Node&>(isource->GetNode());
765 //int nodeid1 = node1.GetId();
766 //Node& node2 = static_cast<Node&>(idest->GetNode());
767 //int nodeid2 = node2.GetId();
768 //TRACE("%svisiting %d\n",spaces,nodeid1);
769
770 if(isource==idest)//we are at the end!
771 {
772 //TRACE("%sat the end!\n");
773 patharray[depth]+=1;
774 return 1;
775 }
776 int paths = 0;
777 MyNode& node = isource->GetNode();
778 node.SetVisited(true);
779 //iterate over adjancys and recursivly call this funciton on neighbor which haven't yet been visited
780 MyManetGraphML::AdjacencyIterator it(*isource);
781 MyManetGraphML::Interface* inbr;
782 while(NULL != (inbr = it.GetNextAdjacency()))
783 {
784 MyNode& nbrnode = inbr->GetNode();
785 //TRACE("%s%p is nbrnode\n",spaces,&nbrnode);
786 if(!nbrnode.WasVisited())
787 {
788 //TRACE("%sgoing to visit %d from %d\n",spaces,nbrnode.GetId(),nodeid1);
789 int ccount = CountPaths(inbr,idest,depth+1,patharray,maxdepth);
790 paths+= ccount;
791 //TRACE("%s%d is paths\n",spaces,paths);
792 }
793 else
794 {
795 //TRACE("%s%d was visited\n",spaces,nbrnode.GetId());
796 }
797 }
798 node.SetVisited(false);
799 //TRACE("CountPaths returning\n");
800 return paths;
801 }
802
803 double CalculateDensity(MyManetGraphML& graph)
804 {
805 int neighborCount = 0;
806 int nodeCount = 0;
807 MyManetGraphML::InterfaceIterator it(graph);
808 MyManetGraphML::Interface* iface;
809 it.Reset();
810 while (NULL != (iface = it.GetNextInterface()))
811 {
812 MyNode& node = iface->GetNode();
813 node.SetNbrs(0.0);
814 node.SetVisited(false);
815 }
816 it.Reset();
817 while (NULL != (iface = it.GetNextInterface()))
818 {
819 MyNode& node = iface->GetNode();
820 int test = node.GetNbrs()+iface->GetAdjacencyCount();
821 node.SetNbrs(test);
822 //node.SetNbrs((node.GetNbrs())+(iface->GetAdjacencyCount()));
823 neighborCount+=iface->GetAdjacencyCount();
824 if(!node.WasVisited())
825 {
826 node.SetVisited(true);
827 nodeCount++;
828 }
829 //TRACE("CalculateRouterPriority: setting adj to %d\n",iface->GetAdjacencyCount());
830 }
831 return ((double)neighborCount)/((double)nodeCount);
832 } // end CalculateDensity()
833
834 void CalculateRouterPriority(MyManetGraphML& graph,bool usingDensity)
835 {
836 if(usingDensity)
837 CalculateDensity(graph);
838 MyManetGraphML::InterfaceIterator it(graph);
839 MyManetGraphML::Interface* iface;
840 while (NULL != (iface = it.GetNextInterface()))
841 {
842 MyNode& node = iface->GetNode();
843 if(usingDensity)
844 {
845 node.SetRtrPriority(node.GetNbrs());
846 }
847 else
848 {
849 node.SetRtrPriority(0.0);
850 }
851 //TRACE("CalculateRouterPriority: setting adj to %d\n",iface->GetAdjacencyCount());
852 }
853 }
854 // "relayList" is filled with the selected relays
855 int CalculateFullECDS(MyManetGraphML& graph,
856 MyManetGraphML::Interface::SimpleList& relayList,
857 ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool)
858 {
859 // Now that we have a fully updated "graph", perform Relay Set Selection
860 // algorithm for each node in graph
861 int numberOfRelays=0;
862 MyManetGraphML::InterfaceIterator it(graph);
863 MyManetGraphML::Interface* iface;
864 while (NULL != (iface = it.GetNextInterface()))
865 {
866 MyNode& node = iface->GetNode();
867 UINT8 priority = node.GetRtrPriority();
868
869 // E-CDS Steps 1,2
870 //TRACE(" node:%s: node:%u adjacencyCount:%u\n", graph.GetString(node),graph.GetId(node), iface->GetAdjacencyCount());
871 if (iface->GetAdjacencyCount() < 2)
872 {
873 node.SetRelayStatus(false);
874 continue;
875 }
876
877 // E-CDS Step 3,4,5, & 6
878 // "nbrList" will cache the "node" 1-hop neighbors for "visited" elimination with the path search
879 MyManetGraphML::AdjacencyIterator iteratorN1(*iface);
880 MyManetGraphML::Interface* ifaceN1Max = NULL;
881 bool isRelay = true; // this will be set to "false" if a test fails
882 MyManetGraphML::Interface* ifaceN1;
883 while (NULL != (ifaceN1 = iteratorN1.GetNextAdjacency()))
884 {
885 //TRACE(" visiting adj%s: adjacencyCount %u\n",graph.GetString(*ifaceN1),ifaceN1->GetAdjacencyCount());
886 MyNode& nodeN1 = ifaceN1->GetNode();
887 //this is the place where it breaks
888 nodeN1.SetVisited(false); // init for later path search
889 // Save n1_max needed for E-CDS Step 6
890 UINT8 priorityN1 = nodeN1.GetRtrPriority();
891 if (NULL == ifaceN1Max)
892 {
893 ifaceN1Max = ifaceN1;
894 // TRACE(" %s is being set as the max with prio and id %u/%u\n",graph.GetString(*ifaceN1),priorityN1,graph.GetId(nodeN1));
895 }
896 else
897 {
898 MyNode& nodeN1Max = ifaceN1Max->GetNode();
899 UINT8 priorityN1Max = nodeN1Max.GetRtrPriority();
900 //TRACE(" priorityN1:%u/%u,priorityN1Max:%u/%u\n",priorityN1,graph.GetId(nodeN1),priorityN1Max,graph.GetId(nodeN1Max));
901 if ((priorityN1 > priorityN1Max) ||
902 ((priorityN1 == priorityN1Max) &&
903 (graph.GetId(nodeN1)>=graph.GetId(nodeN1Max))))
904 {
905 // TRACE(" %s is being set as the max with %u prio and %u id\n",graph.GetString(*ifaceN1),priorityN1,graph.GetId(nodeN1));
906 ifaceN1Max = ifaceN1;
907 }
908 }
909 if(true == isRelay)
910 {
911 if ((priorityN1 > priority) ||
912 ((priorityN1 == priority) && (graph.GetId(nodeN1)>graph.GetId(node))))
913 {
914 isRelay = false; // failed test of E-CDS Step 4
915 // TRACE(" %s is not the LARGEST\n",graph.GetString(node));
916 }
917 }
918 // Check 2-hop neighbors (other neighbors of N1)
919 MyManetGraphML::AdjacencyIterator iteratorN2(*ifaceN1);
920 //TRACE("graphExmaple:CaluculateECDS iteratorN2 pointer is %p\n",&iteratorN2);
921 MyManetGraphML::Interface* ifaceN2;
922 while (NULL != (ifaceN2 = iteratorN2.GetNextAdjacency()))
923 {
924 //TRACE(" visiting 2adj%s\n",graph.GetString(*ifaceN2));
925 if (ifaceN2 == iface) continue; // was "iface" itself
926 if (iface->HasEdgeTo(*ifaceN2)) continue; // was 1-hop neighbor of "iface"
927 MyNode& nodeN2 = ifaceN2->GetNode();
928 nodeN2.SetVisited(false); // init for later path search
929 UINT8 priorityN2 = nodeN2.GetRtrPriority();
930 if ((priorityN2 > priority) ||
931 ((priorityN2 == priority) &&
932 (graph.GetId(nodeN2)>graph.GetId(node))))
933 {
934 isRelay = false; // failed test of E-CDS Step 4
935 }
936 } // end while (NULL != ifaceN2)
937 //TRACE(" killing the iterator %s %p is the node\n",graph.GetString(node),&node);
938 } // end (while (NULL != ifaceN1)
939 if (isRelay)
940 {
941 // Passed test of E-CDS Step 4
942 node.SetRelayStatus(true);
943 numberOfRelays++;
944 //TRACE("node %s is relay by rule of step 4 %p\n", graph.GetString(node),&node);
945 relayList.Append(*iface);
946 continue;
947 }
948
949 // E-CDS Step 7,8 - init path search 'Q'
950 ASSERT(NULL != ifaceN1Max);
951 MyManetGraphML::Interface::SortedList Q(sortedVerticeItemPool);
952 if (!Q.Append(*ifaceN1Max))
953 {
954 PLOG(PL_ERROR, "graphExample: error adding 'ifaceN1Max' to 'Q'\n");
955 return -1;
956 } else {
957 //TRACE(" added %s to the Q\n",graph.GetString(*ifaceN1Max));
958 }
959 ifaceN1Max->GetNode().SetVisited(true);
960 // E-CDS Step 8 - perform path search
961 //TRACE(" e-cds path search starting\n");
962 MyManetGraphML::Interface* x;
963 while (NULL != (x = Q.RemoveHead()))
964 {
965 //TRACE(" popping %s from the Q\n",graph.GetString(*x));
966 bool xIsInN1 = x->HasEdgeTo(*iface);
967 MyManetGraphML::AdjacencyIterator iteratorX(*x);
968 MyManetGraphML::Interface* n;
969 while (NULL != (n = iteratorX.GetNextAdjacency()))
970 {
971 if (n == iface) continue; // was "iface" aka "n0"
972 bool nIsInN1 = n->HasEdgeTo(*iface);
973 if (!xIsInN1 && !nIsInN1) continue; // link not in "n0" 2-hop neighborhood
974 MyNode& nodeNn = n->GetNode();
975 if (!nodeNn.WasVisited())
976 {
977 // E-CDS Step 8a - mark node as "visited"
978 nodeNn.SetVisited(true);
979 // E-CDS Step 8b - check if RtrPri(n) > RtrPri(n0)
980 UINT8 priorityNn = nodeNn.GetRtrPriority();
981 if ((priorityNn > priority) ||
982 ((priorityNn == priority) &&
983 (graph.GetId(nodeNn)>graph.GetId(node))))
984 {
985 if (!Q.Append(*n))
986 {
987 PLOG(PL_ERROR, "graphExample: error adding 'n' to 'Q'\n");
988 return -1;
989 } else {
990 //TRACE(" adding %s to the Q\n",graph.GetString(*n));
991 }
992 }
993 }
994 } // end while (NULL != n)
995 } // end while (NULL != x)
996 //TRACE(" e-cds path search completed\n");
997 // E-CDS Step 9
998 bool relayStatus = false;
999 iteratorN1.Reset();
1000 while (NULL != (ifaceN1 = iteratorN1.GetNextAdjacency()))
1001 {
1002 if (!ifaceN1->GetNode().WasVisited())
1003 {
1004 relayStatus = true;
1005 numberOfRelays++;
1006 break;
1007 }
1008 }
1009 if (relayStatus)
1010 {
1011 //TRACE("node %u is relay after path search\n", graph.GetString(node));
1012 relayList.Append(*iface);
1013 }
1014 node.SetRelayStatus(relayStatus);
1015
1016 } // while (NULL != node) (relay set selection)
1017 return numberOfRelays;
1018 } // end CalculateFullECDS()
1019
1020
1021
1022 //////////////////////////////////////////////////////////////////////////////////////////
1023 // "FastReader" implementation
1024 FastReader::FastReader(FILE* filePtr)
1025 : file_ptr(filePtr), savecount(0)
1026 {
1027 }
1028
1029 FastReader::Result FastReader::Read(char* buffer,
1030 unsigned int* len,
1031 double timeout)
1032 {
1033 unsigned int want = *len;
1034 if (savecount)
1035 {
1036 unsigned int ncopy = MIN(want, savecount);
1037 memcpy(buffer, saveptr, ncopy);
1038 savecount -= ncopy;
1039 saveptr += ncopy;
1040 buffer += ncopy;
1041 want -= ncopy;
1042 }
1043 while (want)
1044 {
1045 unsigned int result;
1046 #ifndef WIN32 // no real-time TRPR for WIN32 yet
1047 if (timeout >= 0.0)
1048 {
1049 int fd = fileno(file_ptr);
1050 fd_set input;
1051 FD_ZERO(&input);
1052 struct timeval t;
1053 t.tv_sec = (unsigned long)timeout;
1054 t.tv_usec = (unsigned long)((1.0e+06 * (timeout - (double)t.tv_sec)) + 0.5);
1055 FD_SET(fd, &input);
1056 int status = select(fd+1, &input, NULL, NULL, &t);
1057 switch (status)
1058 {
1059 case -1:
1060 if (EINTR != errno)
1061 {
1062 perror("trpr: FastReader::Read() select() error");
1063 return ERROR_;
1064 }
1065 else
1066 {
1067 continue;
1068 }
1069 break;
1070
1071 case 0:
1072 return TIMEOUT;
1073
1074 default:
1075 result = fread(savebuf, sizeof(char), 1, file_ptr);
1076 break;
1077 }
1078 }
1079 else
1080 #endif // !WIN32
1081 {
1082 // Perform buffered read when there is no "timeout"
1083 result = fread(savebuf, sizeof(char), BUFSIZE, file_ptr);
1084 // This check skips NULLs that have been read on some
1085 // use of trpr via tail from an NFS mounted file
1086 if (!isprint(*savebuf) &&
1087 ('\t' != *savebuf) &&
1088 ('\n' != *savebuf) &&
1089 ('\r' != *savebuf))
1090 continue;
1091 }
1092 if (result)
1093 {
1094 unsigned int ncopy= MIN(want, result);
1095 memcpy(buffer, savebuf, ncopy);
1096 savecount = result - ncopy;
1097 saveptr = savebuf + ncopy;
1098 buffer += ncopy;
1099 want -= ncopy;
1100 }
1101 else // end-of-file
1102 {
1103 #ifndef WIN32
1104 if (ferror(file_ptr))
1105 {
1106 if (EINTR == errno) continue;
1107 }
1108 #endif // !WIN32
1109 *len -= want;
1110 if (*len)
1111 return OK; // we read at least something
1112 else
1113 return DONE; // we read nothing
1114 }
1115 } // end while(want)
1116 return OK;
1117 } // end FastReader::Read()
1118
1119 // An OK text readline() routine (reads what will fit into buffer incl. NULL termination)
1120 // if *len is unchanged on return, it means the line is bigger than the buffer and
1121 // requires multiple reads
1122 FastReader::Result FastReader::Readline(char* buffer,
1123 unsigned int* len,
1124 double timeout)
1125 {
1126 unsigned int count = 0;
1127 unsigned int length = *len;
1128 char* ptr = buffer;
1129 while (count < length)
1130 {
1131 unsigned int one = 1;
1132 switch (Read(ptr, &one, timeout))
1133 {
1134 case OK:
1135 if (('\n' == *ptr) || ('\r' == *ptr))
1136 {
1137 *ptr = '\0';
1138 *len = count;
1139 return OK;
1140 }
1141 count++;
1142 ptr++;
1143 break;
1144
1145 case TIMEOUT:
1146 // On timeout, save any partial line collected
1147 if (count)
1148 {
1149 savecount = MIN(count, BUFSIZE);
1150 if (count < BUFSIZE)
1151 {
1152 memcpy(savebuf, buffer, count);
1153 savecount = count;
1154 saveptr = savebuf;
1155 *len = 0;
1156 }
1157 else
1158 {
1159 memcpy(savebuf, buffer+count-BUFSIZE, BUFSIZE);
1160 savecount = BUFSIZE;
1161 saveptr = savebuf;
1162 *len = count - BUFSIZE;
1163 }
1164 }
1165 return TIMEOUT;
1166
1167 case ERROR_:
1168 return ERROR_;
1169
1170 case DONE:
1171 return DONE;
1172 }
1173 }
1174 // We've filled up the buffer provided with no end-of-line
1175 return ERROR_;
1176 } // end FastReader::Readline()
1177
1178 bool FastReader::Seek(int offset)
1179 {
1180 bool result = true;
1181 if (offset < 0)
1182 {
1183 if (0 != savecount)
1184 {
1185 int avail = saveptr - savebuf;
1186 if (avail >= abs(offset))
1187 {
1188 savecount += abs(offset);
1189 saveptr -= abs(offset);
1190 offset = 0;
1191 }
1192 else
1193 {
1194 offset -= savecount;
1195 savecount = 0;
1196 }
1197 }
1198 if (0 != offset)
1199 result = (0 == fseek(file_ptr, offset, SEEK_CUR));
1200 }
1201 else if (offset > 0)
1202 {
1203 if ((unsigned int)offset < savecount)
1204 {
1205 savecount -= offset;
1206 saveptr += offset;
1207 }
1208 else
1209 {
1210 if ((unsigned int)offset > savecount)
1211 {
1212 result = (0 == fseek(file_ptr, offset - savecount, SEEK_CUR));
1213 }
1214 savecount = 0;
1215 }
1216 }
1217 return result;
1218 } // end FastReader::Seek()
1219
1220