Debian Codegraph @

protolib/include/manetGraph.h

raw
1 #ifndef _MANET_GRAPH
2 #define _MANET_GRAPH
3
4 #include "protoGraph.h"
5 #include "protoAddress.h"
6
7 /**
8 * @class NetGraph
9 *
10 * @brief This "NetGraph" stuff (incl. its embedded classes) are base classes
11 * that will be used, along with some help from a template defined afterward,
12 * for maintaining state, computing Dijkstra or other traversals, for
13 * Mobile Ad-hoc Network (MANET) routing, etc.
14 *
15 * (It is also useful for any routing, but the motivation for this is to
16 * support MANET R&D we are conducting. The "NetGraph" contains a set of
17 * "NetGraph::Interface" instances that may be connected with some associated
18 * "Cost" with "NetGraph::Link" instances (NetGraph::Link's are uni-directional,
19 * but convenience methods for bi-directional connectivity are provided).
20 * Additionally, a "ManetNode" class is provide to associate a set of
21 * interfaces together, but these associate interfaces are only considered
22 * "connected" if explicitly done.
23 */
24
25 // TBD - it may make sense to rename "NetGraph" defined here to "NetGraphBase" and
26 // keep the name "NetGraph" free or just use it for our example
27 // template usage instead of ManetGraph and actually rename this
28 // entire ".h" as "netGraph.h" instead of "manetGraph.h" and then
29 // "ManetGraph" would be available as a name.
30 //
31 // This would makes sense since "NetGraph" here essentially just adds
32 // the notion of "cost" to graph edges and provides for some
33 // cost-based traversals (e.g. Dijkstra). It also defines "Interfaces"
34 // as vertices that are identified by a ProtoAddress. Then the derived
35 // Protolib "ManetGraph" could add ProtoTimer and other elements to
36 // to links (edges) and interfaces (vertices) that are more applicable
37 // for the dynamic wireless environment that MANET strives to support.
38
39
40 class NetGraph : public ProtoGraph
41 {
42 public:
43 virtual ~NetGraph();
44
45 /**
46 * @class NetGraph::Cost
47 *
48 * @brief Base class for variants of "Cost" we can use for
49 * various graph traversals (e.g. Dyjkstra), etc
50 */
51 class Cost
52 {
53 public:
54 virtual ~Cost();
55
56 // Required overrides
57 virtual const char* GetCostKey() const = 0;
58 virtual unsigned int GetCostKeysize() const = 0; // in bits
59
60 // These methods help ProtoSortedTree when comparing keys (i.e. cost value)
61 // (Note the ProtoSortedTree does a modified lexical sort based on these)
62 virtual bool GetCostKeySigned() const = 0;
63 virtual bool GetCostKeyComplement2() const = 0;
64 virtual ProtoTree::Endian GetCostKeyEndian() const = 0;
65
66 // Copy operator
67 virtual Cost& operator=(const Cost& cost) = 0;
68
69 // Value control
70 virtual void Minimize() = 0;
71
72 // Addition operator
73 virtual void operator+=(const Cost& cost) = 0;
74
75 // Cost comparison methods
76 virtual bool operator>(const Cost& cost) const = 0;
77
78 virtual bool operator==(const Cost& cost) const = 0;
79
80 bool operator!=(const Cost& cost) const
81 {return (!(cost == *this));}
82
83 bool operator>=(const Cost& cost) const
84 {return ((*this > cost) || (*this == cost));}
85
86 bool operator<(const Cost& cost) const
87 {return ((*this >= cost) ? false : true);}
88
89 bool operator<=(const Cost& cost) const
90 {return ((*this > cost) ? false : true);}
91
92 protected:
93 Cost();
94
95 }; // end class NetGraph::Cost
96
97 /**
98 * @class NetGraph::SimpleCostTemplate
99 *
100 * @brief This wraps "double" floating point cost value. We assume
101 * IEEE754 format for the "value" member (I do have code for
102 * converting native machine floating point values to/from
103 * IEEE754 if needed)
104 *
105 * (TBD) Make "SimpleCost" a template class based upon a built-in type?
106 * (e.g., double, int, etc)
107 */
108 template <class SIMPLE_TYPE>
109 class SimpleCostTemplate : public Cost
110 {
111 public:
112 SimpleCostTemplate() : value(0) {}
113 SimpleCostTemplate(SIMPLE_TYPE theValue) : value(theValue) {}
114 virtual ~SimpleCostTemplate() {}
115
116 void SetValue(SIMPLE_TYPE theValue)
117 {value = theValue;}
118
119 SIMPLE_TYPE GetValue() const
120 {return value;}
121
122 operator SIMPLE_TYPE() const
123 {return value;}
124
125 SimpleCostTemplate& operator=(SIMPLE_TYPE theValue)
126 {
127 value = theValue;
128 return *this;
129 }
130
131 SimpleCostTemplate& operator=(const SimpleCostTemplate& cost)
132 {
133 value = cost.value;
134 return *this;
135 }
136
137 // Required overrides of pure virtual methods
138 // (These are used to help sorting by value)
139 const char* GetCostKey() const
140 {return ((char*)&value);}
141 unsigned int GetCostKeysize() const
142 {return (sizeof(SIMPLE_TYPE) << 3);}
143 virtual bool GetCostKeySigned() const
144 {return true;}
145 virtual bool GetCostKeyComplement2() const
146 {return false;}
147 virtual ProtoTree::Endian GetCostKeyEndian() const
148 {return ProtoTree::GetNativeEndian();}
149
150 Cost& operator=(const Cost& cost)
151 {
152 ASSERT(NULL != dynamic_cast<const SimpleCostTemplate*>(&cost));
153 value = static_cast<const SimpleCostTemplate&>(cost).value;
154 return *this;
155 }
156
157 void Minimize()
158 { value = 0;}
159
160 bool operator==(const Cost& cost) const
161 {
162 ASSERT(NULL != dynamic_cast<const SimpleCostTemplate*>(&cost));
163 return (value == static_cast<const SimpleCostTemplate&>(cost).value);
164 }
165
166 bool operator>(const Cost& cost) const
167 {
168 ASSERT(NULL != dynamic_cast<const SimpleCostTemplate*>(&cost));
169 return (value > static_cast<const SimpleCostTemplate&>(cost).value);
170 }
171
172 void operator+=(const Cost& cost)
173 {
174 ASSERT(NULL != dynamic_cast<const SimpleCostTemplate*>(&cost));
175 value += static_cast<const SimpleCostTemplate&>(cost).value;
176 }
177
178 protected:
179 SIMPLE_TYPE value;
180
181 }; // end class NetGraph::SimpleCostTemplate
182
183 /**
184 * @class NetGraph::SimpleCostDouble
185 *
186 * @brief This SimpleCost variant holds a "double" floating point cost value.
187 * We assume an IEEE754 format for the "value" member (I do have
188 * code for converting native machine floating point values to/from
189 * IEEE754 if needed)
190 */
191 class SimpleCostDouble : public SimpleCostTemplate<double>
192 {
193 public:
194 SimpleCostDouble() {}
195 SimpleCostDouble(double theValue) : SimpleCostTemplate<double>(theValue) {}
196 }; // end class NetGraph::SimpleCostDouble
197
198 class SimpleCostUINT32 : public SimpleCostTemplate<UINT32>
199 {
200 public:
201 SimpleCostUINT32() {}
202 SimpleCostUINT32(UINT32 theValue) : SimpleCostTemplate<UINT32>(theValue) {}
203 // Don't use the sign bit since it's "unsigned"
204 bool GetCostKeySigned() const
205 {return false;}
206 }; // end class NetGraph::SimpleCostUINT32
207
208 class SimpleCostUINT8 : public SimpleCostTemplate<UINT8>
209 {
210 public:
211 SimpleCostUINT8() {}
212 SimpleCostUINT8(UINT8 theValue) : SimpleCostTemplate<UINT8>(theValue) {}
213 // Don't use the sign bit since it's "unsigned"
214 bool GetCostKeySigned() const
215 {return false;}
216 }; // end class NetGraph::SimpleCostUINT8
217
218 class Interface;
219 class Link;
220
221 // TBD - Should the AdjacentyIterator be declared inside the Interface declaration?
222 // If we did this, the templated version could return the correct types
223 class AdjacencyIterator : public ProtoGraph::AdjacencyIterator
224 {
225 public:
226 AdjacencyIterator(Interface& iface);
227 virtual ~AdjacencyIterator();
228
229 Interface* GetNextAdjacency()
230 {return static_cast<Interface*>(ProtoGraph::AdjacencyIterator::GetNextAdjacency());}
231
232 Link* GetNextAdjacencyLink()
233 {return static_cast<Link*>(ProtoGraph::AdjacencyIterator::GetNextAdjacencyEdge());}
234
235 Interface* GetNextConnector()
236 {return static_cast<Interface*>(ProtoGraph::AdjacencyIterator::GetNextConnector());}
237
238 }; // end class NetGraph::AdjacencyIterator
239
240 /**
241 * @class NetGraph::Link
242 *
243 * @brief adds "cost" attribute to ProtoGraph::Edge
244 */
245 class Link : public Edge
246 {
247 public:
248 virtual ~Link();
249
250 // Our template below will override this for us.
251 virtual const Cost& GetCost() const = 0;
252
253 void SetCost(const Cost& cost);
254
255 Interface* GetSrc() const
256 {return static_cast<Interface*>(Edge::GetSrc());}
257
258 Interface* GetDst() const
259 {return static_cast<Interface*>(Edge::GetDst());}
260
261 // Required overrides
262 virtual const char* GetKey() const
263 {return GetCost().GetCostKey();}
264 virtual unsigned int GetKeysize() const
265 {return (GetCost().GetCostKeysize());}
266 virtual ProtoTree::Endian GetEndian() const
267 {return GetCost().GetCostKeyEndian();}
268 virtual bool UseSignBit() const
269 {return GetCost().GetCostKeySigned();}
270 virtual bool UseComplement2() const
271 {return GetCost().GetCostKeyComplement2();}
272
273 protected:
274 Link();
275 // Our template below will override this for us.
276 virtual Cost& AccessCost() = 0;
277
278 }; // end class NetGraph::Link
279
280 class Node; // a "Node" is a "super-vertice" in a NetGraph while an
281 // "Interface" is an actual vertice. The "Interfaces"
282 // associated with a "Node" may or may not be connected.
283 /**
284 * @class NetGraph::Interface
285 *
286 * @brief adds "address" identifier to ProtoGraph::Vertice and also
287 * ties "Interface" to NetGraph::Node
288 * Note the "ProtoSortedTree::Item()" aspect is for its inclusion its
289 * "node" iface_list only
290 */
291 class Interface : public ProtoGraph::Vertice, public ProtoSortedTree::Item
292 {
293 friend class NetGraph;
294 public:
295 Interface(Node& theNode, const ProtoAddress& addr);
296 Interface(Node& theNode);
297 virtual ~Interface();
298
299 const ProtoAddress& GetAddress() const
300 {return default_addr_item.GetAddress();}
301 const ProtoAddress& GetAnyAddress() const
302 {return GetAddress();}
303 ProtoAddressList& GetAddressList()
304 {return addr_list;}
305
306 bool SetName(const char* theName);
307 const char* GetName() const
308 {return name_ptr;}
309 void ClearName(); // nullifies name
310
311 // Use to add additional "extra" addresses
312 // Note: Any graphs currently containing this interface get be updated as well
313 bool AddAddress(const ProtoAddress& theAddress);
314 bool RemoveAddress(const ProtoAddress& theAddress);
315
316 bool Contains(const ProtoAddress& theAddress) const
317 {return addr_list.Contains(theAddress);}
318
319 const ProtoAddress& GetDefaultAddress() const
320 {return default_addr_item.GetAddress();}
321
322 //void SetAddress(const ProtoAddress& theAddress)
323 // {address = theAddress;}
324
325 Node& GetNode() const
326 {return *node;}
327
328 const Node* GetNodePtr() const
329 {return node;}
330
331 bool ChangeNode(Node& theNode);
332
333 bool HasLinkTo(const Interface& dstIface) const
334 {return ProtoGraph::Vertice::HasEdgeTo(dstIface);}
335
336 Link* GetLinkTo(const Interface& dstIface) const
337 {return static_cast<Link*>(ProtoGraph::Vertice::GetEdgeTo(dstIface));}
338
339 // This maintains a simple, unsorted (non-indexed) list of Interfaces
340 class SimpleList : public Vertice::SimpleList
341 {
342 public:
343 SimpleList(ItemPool* itemPool = NULL);
344 virtual ~SimpleList();
345
346 Interface* GetHead() const
347 {return static_cast<Interface*>(Vertice::SimpleList::GetHead());}
348
349 Interface* RemoveHead()
350 {return static_cast<Interface*>(Vertice::SimpleList::RemoveHead());}
351
352 class Iterator : public Vertice::SimpleList::Iterator
353 {
354 public:
355 Iterator(const SimpleList& theList);
356 virtual ~Iterator();
357
358 Interface* GetNextInterface()
359 {return static_cast<Interface*>(GetNextVertice());}
360
361 }; // end class NetGraph::Interface::SimpleList::Iterator
362
363 }; // end class NetGraph::Interface::SimpleList
364
365 // This maintains a list of Interfaces, sorted by their "key", etc
366 class SortedList : public Vertice::SortedList
367 {
368 public:
369 SortedList(ItemPool* itemPool = NULL);
370 virtual ~SortedList();
371
372 Interface* FindInterface(const ProtoAddress& addr) const
373 {return static_cast<Interface*>(FindVertice(addr.GetRawHostAddress(), addr.GetLength() << 3));}
374
375 Interface* GetHead() const
376 {return static_cast<Interface*>(Vertice::SortedList::GetHead());}
377
378 Interface* RemoveHead()
379 {return static_cast<Interface*>(Vertice::SortedList::RemoveHead());}
380
381 class Iterator : public Vertice::SortedList::Iterator
382 {
383 public:
384 Iterator(SortedList& theList);
385 virtual ~Iterator();
386
387 Interface* GetNextInterface()
388 {return static_cast<Interface*>(GetNextVertice());}
389
390 }; // end class NetGraph::Interface::SortedList::Iterator
391
392 }; // end class NetGraph::Interface::SortedList
393
394 // PriorityQueue class to use for traversal purposes
395 // This sorts by "Cost" associated with the interface
396 class PriorityQueue : public Vertice::SortedList
397 {
398 public:
399 class ItemFactory;
400
401 PriorityQueue(ItemFactory& itemFactory);
402 virtual ~PriorityQueue();
403
404 bool Insert(Interface& iface, const Cost& cost);
405
406 void Remove(Interface& iface)
407 {SortedList::Remove(iface);}
408
409 Interface* RemoveHead()
410 {return static_cast<Interface*>(SortedList::RemoveHead());}
411
412 bool IsEmpty() const
413 {return iface_list.IsEmpty();}
414
415 Interface* GetHead() const
416 {return static_cast<Interface*>(SortedList::GetHead());}
417
418 const Cost* GetCost(const Interface& iface) const
419 {
420 Item* item = static_cast<Item*>(GetQueueState(iface));
421 return ((NULL != item) ? &(item->GetCost()) : NULL);
422 }
423
424 // Move vertice from this PriorityQueue to another
425 void TransferInterface(Interface& iface, PriorityQueue& dstQueue)
426 {SortedList::TransferVertice(iface, dstQueue);}
427
428 void TransferItem(Item& item, PriorityQueue& dstQueue)
429 {SortedList::TransferItem(item, dstQueue);}
430
431 // These are used to query enqueued interfaces post-Dijkstra
432 Interface* GetNextHop(const Interface& iface) const
433 {
434 Item* item = static_cast<Item*>(GetQueueState(iface));
435 return ((NULL != item) ? item->GetNextHop() : NULL);
436 }
437 Link* GetNextHopLink(const Interface& iface) const
438 {
439 Item* item = static_cast<Item*>(GetQueueState(iface));
440 return ((NULL != item) ? item->GetNextHopLink() : NULL);
441 }
442 Interface* GetPrevHop(const Interface& iface) const
443 {
444 Item* item = static_cast<Item*>(GetQueueState(iface));
445 return ((NULL != item) ? item->GetPrevHop() : NULL);
446 }
447 void SetRouteInfo(Interface& iface, Link* nextHopLink, Interface* prevHop)
448 {
449 Item* item = static_cast<Item*>(GetQueueState(iface));
450 ASSERT(NULL != item);
451 item->SetNextHopLink(nextHopLink);
452 item->SetPrevHop(prevHop);
453 }
454
455 void Adjust(Interface& iface, const Cost& newCost);
456 bool AdjustDownward(Interface& iface, const Cost& newCost,const Interface* newPrevHop = NULL);
457 bool AdjustUpward(Interface& iface, const Cost& newCost);
458
459 // Note use of this method does not maintain priority queue sorting order!
460 bool Append(Interface& iface); // used for Dijkstra "tree walking" only
461
462 class Item : public SortedList::Item
463 {
464 public:
465 virtual ~Item();
466
467 // Our subclass templates will override these
468 virtual const Cost& GetCost() const = 0;
469 virtual void SetCost(const Cost& cost) = 0;
470
471 // "ProtoGraph::Vertice::SortedList::Item" overrides
472 // (We sort our PriorityQueue items by "cost")
473 const char* GetKey() const
474 {return GetCost().GetCostKey();}
475 unsigned int GetKeysize() const
476 {return GetCost().GetCostKeysize();}
477 virtual ProtoTree::Endian GetEndian() const
478 {return GetCost().GetCostKeyEndian();}
479 virtual bool UseSignBit() const
480 {return GetCost().GetCostKeySigned();}
481 virtual bool UseComplement2() const
482 {return GetCost().GetCostKeyComplement2();}
483
484 Interface* GetInterface() const
485 {return static_cast<Interface*>(GetVertice());}
486
487 // These are useful post-Djikstra completion
488 void SetPrevHop(Interface* prevHop)
489 {prev_hop = prevHop;}
490 Interface* GetPrevHop() const
491 {return prev_hop;}
492
493 void SetNextHopLink(Link* nextHopLink)
494 {next_hop_link = nextHopLink;}
495 Link* GetNextHopLink() const
496 {return next_hop_link;}
497 Interface* GetNextHop() const
498 {return ((NULL != next_hop_link) ? next_hop_link->GetDst() : NULL);}
499
500 protected:
501 Item();
502 // Our subclass templates will override this
503 virtual Cost& AccessCost() = 0;
504
505 private:
506 Interface* prev_hop; // reverse path towards srcIFace
507 Link* next_hop_link; // forward path from srcIface to here
508
509 }; // end class NetGraph::Interface::PriorityQueue::Item
510
511 class ItemFactory
512 {
513 public:
514 virtual ~ItemFactory();
515
516 void Destroy()
517 {item_pool.Destroy();}
518
519 Item* GetItem();
520
521 void PutItem(Item& item)
522 {item_pool.PutItem(item);}
523
524 protected:
525 ItemFactory();
526 virtual Item* CreateItem() const = 0;
527
528 // Member variables
529 SortedList::ItemPool item_pool;
530
531 }; // end class NetGraph::Interface::PriorityQueue::ItemFactory
532
533 class Iterator : public SortedList::Iterator
534 {
535 public:
536 Iterator(PriorityQueue& priorityQueue);
537 virtual ~Iterator();
538
539 Interface* GetNextInterface()
540 {return static_cast<Interface*>(SortedList::Iterator::GetNextVertice());}
541
542 Item* GetNextItem()
543 {return static_cast<Item*>(SortedList::Iterator::GetNextItem());}
544
545 }; // end NetGraph::Interface::PriorityQueue::Iterator
546
547 protected:
548 // Member variables
549 ProtoSortedTree iface_list; // sorted by "Cost" value
550 ItemFactory& item_factory;
551
552 private:
553 using Vertice::SortedList::Remove; // gets rid of hidden overloaded virtual function warning
554
555 }; // end NetGraph::Interface::PriorityQueue
556
557 protected:
558 // Overrides for interfaces with "key" based on address
559 // ProtoGraph::Vertice parent class overrides
560 // Subclasses _may_ want to override these methods
561 // (These are used for default sorting of
562 // of the Vertice::SortedList if used)
563 // _BUT_ if these are overridden, the derived
564 // class destructor _MUST_ call Vertice::Cleanup() so
565 // that these _are_ not indirectly called in the Vertice
566 // destructor!!!
567
568 // These affect the Interface's sorting criteria
569 // in the ProtoGraph::vertice_list and any Interface::SortedList
570 // membership.
571 virtual const char* GetVerticeKey() const;
572 virtual unsigned int GetVerticeKeysize() const;
573
574 private:
575 // ProtoSortedTree::Item parent class overrides
576 virtual const char* GetKey() const
577 {return GetVerticeKey();}
578 virtual unsigned int GetKeysize() const
579 {return GetVerticeKeysize();}
580
581 Node* node;
582 NetGraph* graph;
583 ProtoAddressList addr_list;
584 ProtoAddressList::Item default_addr_item;
585 char* name_ptr;
586 }; // end class NetGraph::Interface
587
588 // The "Node" class associates multiple interfaces together even if they
589 // are not connected in a ManetGraph. A "Node" reference is required in
590 // the "Interface" constructor. Note that when a "Node" is deleted, it
591 // deletes any Interfaces contained in its "iface_list"
592 class Node
593 {
594 public:
595 Node();
596 virtual ~Node();
597
598 void Consume(Node& foodNode);
599
600 Interface* FindInterface(const ProtoAddress& addr) const;
601 // {return static_cast<Interface*>(iface_list.Find(addr.GetRawHostAddress(), addr.GetLength() << 3));}
602 // {return reinterpret_cast<Interface*>((void*)addr_list.GetUserData(addr));}
603 Interface* FindInterfaceByName(const char* theName);
604
605 Interface* FindInterfaceByString(const char* theString); //looks for it as both a name and address
606
607 bool AddInterface(Interface& iface, bool makeDefault = false);
608
609 void RemoveInterface(Interface& iface);
610
611 // Note "AppendInterface() should be deprecated
612 bool AppendInterface(Interface& iface, bool makeDefault = false)
613 {return AddInterface(iface, makeDefault);}
614
615 bool Contains(const Interface& iface) const
616 {return (iface.GetNodePtr() == this);}
617
618 Interface* GetAnyInterface() const
619 {return static_cast<Interface*>(iface_list.GetRoot());}
620 Interface* GetDefaultInterface() const
621 {return static_cast<Interface*>(default_interface_ptr);}
622
623 bool IsSymmetricNeighbor(Node& node);
624
625 class InterfaceIterator : public ProtoSortedTree::Iterator
626 {
627 public:
628 InterfaceIterator(Node& theNode);
629 virtual ~InterfaceIterator();
630
631 bool HasEmptyList()
632 {return HasEmptyTree();}
633
634 void Reset()
635 {ProtoSortedTree::Iterator::Reset();}
636
637 Interface* GetNextInterface()
638 {return static_cast<Interface*>(GetNextItem());}
639
640 }; // end class NetGraph::Node::InterfaceIterator
641
642 friend class InterfaceIterator;
643 friend class NetGraph::Interface;
644
645 // Iterate over all _neighboring_ interfaces
646 class NeighborIterator
647 {
648 public:
649 NeighborIterator(Node& theNode);
650 virtual ~NeighborIterator();
651
652 void Reset();
653
654 Interface* GetNextNeighborInterface();
655
656 Link* GetNextNeighborLink();
657
658 private:
659 InterfaceIterator iface_iterator;
660 AdjacencyIterator adj_iterator;
661 }; // end class NetGraph::Node::NeighborIterator
662
663 protected:
664
665 ProtoSortedTree iface_list;
666 ProtoAddressList extra_addr_list; // contains list of ifaces' "extra" addresses
667
668 private:
669 bool AddExtraInterfaceAddress(const Interface& iface,const ProtoAddress& addr)
670 {return extra_addr_list.Insert(addr, &iface);}
671 void RemoveExtraInterfaceAddress(const ProtoAddress& addr)
672 {extra_addr_list.Remove(addr);}
673 bool SetDefaultInterface(Interface& iface);
674
675 Interface* default_interface_ptr;
676 }; // end class NetGraph::Node
677
678 // NetGraph control/query methods
679 bool InsertNode(Node& node, Interface* iface = NULL); //this function will be removed in upcoming releases
680 bool InsertInterface(Interface& iface); // this function should be used instead of InsertNode()
681 void RemoveNode(Node& node, Interface* iface = NULL);
682 void RemoveInterface(Interface& iface); // This removes the interface _and_ its links
683
684 Interface* FindInterface(const ProtoAddress& addr) const
685 {return ((Interface*)addr_list.GetUserData(addr));}
686
687 Node* FindNode(const ProtoAddress& theAddress)
688 {
689 Interface* iface = FindInterface(theAddress);
690 return ((NULL != iface) ? &iface->GetNode() : NULL);
691 }
692
693 Interface* FindInterfaceByName(const char *theName);
694
695 Interface* FindInterfaceByString(const char *theString); // finds the interface both by name and address
696
697 Node* FindNodeByName(const char *theName)
698 {
699 Interface* iface = FindInterfaceByName(theName);
700 return ((NULL != iface) ? &iface->GetNode() : NULL);
701 }
702
703 Node* FindNodeByString(const char* theString)
704 {
705 Interface* iface = FindInterfaceByString(theString);
706 return ((NULL != iface) ? &iface->GetNode() : NULL);
707 }
708
709 class InterfaceIterator : public ProtoGraph::VerticeIterator
710 {
711 public:
712 InterfaceIterator(NetGraph& theGraph);
713 virtual ~InterfaceIterator();
714
715 Interface* GetNextInterface()
716 {return static_cast<Interface*>(GetNextVertice());}
717
718 }; // end class NetGraph::InterfaceIterator
719
720
721 class SimpleTraversal : protected ProtoGraph::SimpleTraversal
722 {
723 public:
724 SimpleTraversal(const NetGraph& theGraph,
725 Interface& startIface,
726 bool traverseNodes = true,
727 bool collapseNodes = true,
728 bool depthFirst = false);
729
730 virtual ~SimpleTraversal();
731
732 bool Reset()
733 {return Reset(false);}
734
735 Interface* GetNextInterface(unsigned int* level = NULL);
736
737 protected:
738 // Override this method to filter which edges are included in traversal
739 // (return "false" to disallow specific edges)
740 // Note "link" will be NULL is src/dst are on same node
741 virtual bool AllowLink(const Interface& srcIface, const Interface& dstIface, Link* link)
742 {return true;}
743
744 bool Reset(bool constructor); // arg for internal-use only
745
746 bool traverse_nodes; // traverse all node interfaces
747 bool collapse_nodes; // treat node co-interfaces as a common vertice
748
749 }; // end class NetGraph::SimpleTraversal
750
751 class DijkstraTraversal : public Interface::PriorityQueue::ItemFactory
752 {
753 public:
754 virtual ~DijkstraTraversal();
755
756 // Set to false by default; If set to true the traversal will iterate over nodes as well as interfaces.
757 void TraverseNodes(bool traverse);
758
759 bool Reset(Interface* startIface = NULL);
760
761 Interface* GetNextInterface();
762
763 bool PrevHopIsValid(Interface& currentIface);
764
765 void Update(Interface& startIface);
766
767 void Update(Interface& ifaceA, Interface& ifaceB);
768
769 // Override this method to filter which edges are included in traversal
770 // (return "false" to disallow specific links)
771 virtual bool AllowLink(const Interface& srcIface, const Link& link)
772 {return true;}
773
774 // (use these post-Dijkstra (after "GetNextInterface" returns NULL)
775 Interface* GetNextHop(const Interface& dstIface) // from "startIface" towards "dstIface"
776 {return (queue_visited.GetNextHop(dstIface));}
777
778 Interface* GetPrevHop(const Interface& dstIface) // back towards "startIface"
779 {return (queue_visited.GetPrevHop(dstIface));}
780
781 const Cost* GetCost(const Interface& dstIface) const
782 {return (queue_visited.GetCost(dstIface));}
783
784 // BFS traversal of routing tree ("tree walk")
785 bool TreeWalkReset();
786 Interface* TreeWalkNext(unsigned int* level = NULL);
787
788 protected:
789 DijkstraTraversal(NetGraph& theGraph,
790 Interface* startIface);
791
792 DijkstraTraversal(NetGraph& theGraph,
793 Node& startNode,
794 Interface* startIface = NULL);
795
796 // Note: The template subclass provides the "ItemFactory::CreateItem()" method
797
798 // Our templates below override this one
799 virtual Cost& AccessCostTemp() = 0;
800
801 NetGraph& manet_graph;
802 Interface* start_iface;
803 Interface::PriorityQueue queue_pending;
804 Interface::PriorityQueue queue_visited;
805
806 // These two members support the "tree walk" BFS
807 Interface* trans_iface;
808 unsigned int current_level;
809
810 bool dijkstra_completed;
811 bool in_update;
812 bool traverse_nodes;
813 bool reset_required;
814 }; // end class NetGraph::DijkstraTraversal
815
816
817 // These Link and Interface Template definitions may be used by developers along
818 // with the NetGraphTemplate definition below to build custom link/interface/graph types.
819 template <class COST_TYPE, class IFACE_TYPE = Interface>
820 class LinkTemplate : public Link
821 {
822 public:
823 LinkTemplate() {}
824 virtual ~LinkTemplate() {}
825
826 // required override
827 const COST_TYPE& GetCost() const
828 {return cost;}
829
830 void SetCost(COST_TYPE& theCost)
831 {cost = theCost;}
832
833 IFACE_TYPE* GetSrc() const
834 {return static_cast<IFACE_TYPE*>(Edge::GetSrc());}
835
836 IFACE_TYPE* GetDst() const
837 {return static_cast<IFACE_TYPE*>(Edge::GetDst());}
838
839 private:
840 virtual Cost& AccessCost()
841 {return static_cast<Cost&>(cost);}
842 COST_TYPE cost;
843
844 }; // end class NetGraph::LinkTemplate
845
846
847 template <class COST_TYPE, class MY_TYPE, class LINK_TYPE = Link, class NODE_TYPE = Node>
848 class InterfaceTemplate : public Interface
849 {
850 public:
851 InterfaceTemplate(NODE_TYPE& theNode, const ProtoAddress& addr) : Interface(theNode, addr) {}
852 InterfaceTemplate(NODE_TYPE& theNode) : Interface(theNode) {}
853 virtual ~InterfaceTemplate() {}
854
855 LINK_TYPE* GetLinkTo(const InterfaceTemplate& dst) const
856 {return static_cast<LINK_TYPE*>(Interface::GetLinkTo(dst));}
857
858 NODE_TYPE& GetNode() const
859 {return static_cast<NODE_TYPE&>(Interface::GetNode());}
860
861 const NODE_TYPE* GetNodePtr() const
862 {return static_cast<NODE_TYPE&>(Interface::GetNodePtr());}
863
864 const COST_TYPE* GetCostTo(const InterfaceTemplate& dst) const
865 {
866 LINK_TYPE* link = GetLinkTo(dst);
867 return (NULL != link) ? static_cast<const COST_TYPE*>(&(link->GetCost())) : (COST_TYPE*)NULL;
868 }
869
870 static MY_TYPE* GetSrc(Link& theLink)
871 {return static_cast<MY_TYPE*>(theLink.GetSrc());}
872
873 static MY_TYPE* GetDst(Link& theLink)
874 {return static_cast<MY_TYPE*>(theLink.GetDst());}
875
876 class SimpleList : public NetGraph::Interface::SimpleList
877 {
878 public:
879 SimpleList(ItemPool* itemPool = NULL) : NetGraph::Interface::SimpleList(itemPool) {}
880 virtual ~SimpleList() {}
881
882 MY_TYPE* GetHead() const
883 {return static_cast<MY_TYPE*>(NetGraph::Interface::SimpleList::GetHead());}
884
885 MY_TYPE* RemoveHead()
886 {return static_cast<MY_TYPE*>(NetGraph::Interface::SimpleList::RemoveHead());}
887
888 class Iterator : public NetGraph::Interface::SimpleList::Iterator
889 {
890 public:
891 Iterator(const SimpleList& theList) : NetGraph::Interface::SimpleList::Iterator(theList) {}
892 virtual ~Iterator() {}
893
894 MY_TYPE* GetNextInterface()
895 {return static_cast<MY_TYPE*>(NetGraph::Interface::SimpleList::Iterator::GetNextInterface());}
896
897 }; // end class NetGraph::InterfaceTemplate::SimpleList::Iterator
898
899 }; // end class NetGraph::InterfaceTemplate::SimpleList
900
901 class SortedList : public NetGraph::Interface::SortedList
902 {
903 public:
904 SortedList(ItemPool* itemPool = NULL) : NetGraph::Interface::SortedList(itemPool) {}
905 virtual ~SortedList() {}
906
907
908 MY_TYPE* FindInterface(const ProtoAddress& addr) const
909 {return static_cast<MY_TYPE*>(FindVertice(addr.GetRawHostAddress(), addr.GetLength() << 3));}
910
911 MY_TYPE* FindInterfaceByName(const char* name)
912 {return static_cast<MY_TYPE*>(FindVertice(name,(strlen(name) & 0x01) ? (strlen(name) << 3) : ((strlen(name)+1) << 3)));}
913
914 MY_TYPE* GetHead() const
915 {return static_cast<MY_TYPE*>(Vertice::SortedList::GetHead());}
916
917 MY_TYPE* RemoveHead()
918 {return static_cast<MY_TYPE*>(Vertice::SortedList::RemoveHead());}
919
920 class Iterator : public NetGraph::Interface::SortedList::Iterator
921 {
922 public:
923 Iterator(SortedList& theList) : NetGraph::Interface::SortedList::Iterator(theList) {}
924 virtual ~Iterator() {}
925
926 MY_TYPE* GetNextInterface()
927 {return static_cast<MY_TYPE*>(NetGraph::Interface::SortedList::Iterator::GetNextInterface());}
928
929 }; // end class NetGraph::InterfaceTemplate::SortedList::Iterator
930
931 }; // end class NetGraph::InterfaceTemplate::SortedList
932
933 class PriorityQueue : public NetGraph::Interface::PriorityQueue
934 {
935 public:
936 PriorityQueue() : NetGraph::Interface::PriorityQueue(builtin_item_factory) {}
937 PriorityQueue(ItemFactory& itemFactory) : NetGraph::Interface::PriorityQueue(itemFactory) {}
938 virtual ~PriorityQueue() {}
939
940 class Item : public NetGraph::Interface::PriorityQueue::Item
941 {
942 public:
943 Item() {}
944 virtual ~Item() {}
945
946 const Cost& GetCost() const
947 {return static_cast<const Cost&>(cost);}
948
949 void SetCost(const Cost& theCost)
950 {cost = static_cast<const COST_TYPE&>(theCost);}
951
952 private:
953 virtual Cost& AccessCost()
954 {return static_cast<Cost&>(cost);}
955 COST_TYPE cost;
956 }; // end class NetGraph::PriorityQueue::Item
957
958 class ItemFactory : public NetGraph::Interface::PriorityQueue::ItemFactory
959 {
960 public:
961 ItemFactory() {}
962 virtual ~ItemFactory() {}
963
964 protected:
965 NetGraph::Interface::PriorityQueue::Item* CreateItem() const
966 {return static_cast<NetGraph::Interface::PriorityQueue:: Item*>(new Item);} // creates new templated "Item"
967
968 }; // end class NetGraph::InterfaceTemplate::PriorityQueue::ItemFactory()
969
970 private:
971 ItemFactory builtin_item_factory;
972
973 }; // end class NetGraph::InterfaceTemplate::PriorityQueue
974
975 }; // end class NetGraph::InterfaceTemplate
976
977 template <class COST_TYPE, class NODE_TYPE = NetGraph::Node>
978 class DefaultInterfaceTemplate : public InterfaceTemplate<COST_TYPE, NODE_TYPE, DefaultInterfaceTemplate<COST_TYPE> >
979 {
980 public:
981 DefaultInterfaceTemplate(NODE_TYPE& theNode, const ProtoAddress& addr)
982 : InterfaceTemplate<COST_TYPE, NODE_TYPE, DefaultInterfaceTemplate>(theNode, addr) {}
983 virtual ~DefaultInterfaceTemplate() {}
984 }; // end class NetGraph::DefaultInterfaceTemplate
985
986
987 template <class IFACE_TYPE = Interface, class LINK_TYPE = Link>
988 class NodeTemplate : public Node
989 {
990 public:
991 NodeTemplate() {}
992 virtual ~NodeTemplate() {}
993
994 IFACE_TYPE* FindInterface(const ProtoAddress& addr) const
995 {return static_cast<IFACE_TYPE*>(NetGraph::Node::FindInterface(addr));}
996
997 IFACE_TYPE* FindInterfaceByName(const char* theName)
998 {return static_cast<IFACE_TYPE*>(NetGraph::Node::FindInterfaceByName(theName));}
999
1000 IFACE_TYPE* GetDefaultInterface() const
1001 {return static_cast<IFACE_TYPE*>(NetGraph::Node::GetDefaultInterface());}
1002
1003 class InterfaceIterator : public NetGraph::Node::InterfaceIterator
1004 {
1005 public:
1006 InterfaceIterator(Node& node) : NetGraph::Node::InterfaceIterator(node) {}
1007 virtual ~InterfaceIterator() {}
1008
1009 IFACE_TYPE* GetNextInterface()
1010 {return static_cast<IFACE_TYPE*>(NetGraph::Node::InterfaceIterator::GetNextInterface());}
1011
1012 }; // end class NetGraphTemplate::Node::InterfaceIterator
1013 class NeighborIterator : public NetGraph::Node::NeighborIterator
1014 {
1015 public:
1016 NeighborIterator(Node& node) : NetGraph::Node::NeighborIterator(node) {}
1017 virtual ~NeighborIterator() {}
1018
1019 IFACE_TYPE* GetNextNeighborInterface()
1020 {return static_cast<IFACE_TYPE*>(NetGraph::Node::NeighborIterator::GetNextNeighborInterface());}
1021
1022 LINK_TYPE* GetNextNeighborLink()
1023 {return static_cast<LINK_TYPE*>(NetGraph::Node::NeighborIterator::GetNextNeighborLink());}
1024 }; // end class NetGraph::NodeTemplate::NeighborIterator
1025
1026 }; // end class NetGraph::NodeTemplate
1027
1028
1029 protected:
1030 NetGraph();
1031
1032 // Netgraph::Interface calls these when adding or removing addresses
1033 bool AddInterfaceAddress(const Interface& iface, const ProtoAddress& addr)
1034 {return addr_list.Insert(addr, &iface);}
1035 void RemoveInterfaceAddress(const ProtoAddress& addr)
1036 {addr_list.Remove(addr);}
1037 void SuspendInterface(Interface& iface)
1038 {vertice_list.Remove(iface);}
1039 bool ResumeInterface(Interface& iface)
1040 {return vertice_list.Insert(iface);}
1041
1042 // Our template provides a type-safe "public" override of this
1043 Link* Connect(Interface& srcIface, Interface& dstIface, const Cost& cost);
1044 bool Connect(Interface& srcIface, Interface& dstIface, const Cost& cost, bool duplex);
1045
1046 Link* Reconnect(Interface& srcIface, Interface& dstIface, const Cost& cost);
1047 bool Reconnect(Interface& srcIface, Interface& dstIface, const Cost& cost, bool duplex);
1048
1049 private:
1050 ProtoAddressList addr_list; // list of _all_ addresses of all contained interfaces
1051
1052 }; // end class NetGraph
1053
1054
1055 // The "NetGraph" stuff declared above are the base (interface) classes for
1056 // actual subclasses we will derive and use. The following provides a template
1057 // class based on the "Cost" type. This lets us easily derive different types
1058 // of "Cost" subclasses and then derive a "NetGraph" subclass that uses that
1059 // new "Cost" subclass for its Dijkstra, etc. Cool!, huh?
1060 //
1061 // Note that further below we declare a "ManetGraph" subclass as an example
1062 // that uses the "NetGraph::SimpleCost" that was declared above.
1063
1064 template <class COST_TYPE = NetGraph::SimpleCostDouble,
1065 class IFACE_TYPE = NetGraph::DefaultInterfaceTemplate<COST_TYPE>,
1066 class LINK_TYPE = NetGraph::LinkTemplate<COST_TYPE, IFACE_TYPE>,
1067 class NODE_TYPE = NetGraph::NodeTemplate<IFACE_TYPE> >
1068 class NetGraphTemplate : public NetGraph
1069 {
1070 public:
1071 NetGraphTemplate() {}
1072 virtual ~NetGraphTemplate() {}
1073
1074 // These typedefs let us use DerivedGraph::Interface and DerivedGraph::Link types that
1075 // are synonomous with passed-in template interface/link types
1076 typedef COST_TYPE Cost;
1077 typedef IFACE_TYPE Interface;
1078 typedef LINK_TYPE Link;
1079 typedef NODE_TYPE Node;
1080
1081 NODE_TYPE* FindNode(const ProtoAddress& theAddress)
1082 {return static_cast<NODE_TYPE*>(NetGraph::FindNode(theAddress));}
1083
1084 IFACE_TYPE* FindInterface(const ProtoAddress& addr) const
1085 {return static_cast<IFACE_TYPE*>(NetGraph::FindInterface(addr));}
1086
1087 IFACE_TYPE* FindInterfaceByName(const char* name)
1088 {return static_cast<IFACE_TYPE*>(NetGraph::FindInterfaceByName(name));}
1089
1090 IFACE_TYPE* FindInterfaceByString(const char* theString)
1091 {return static_cast<IFACE_TYPE*>(NetGraph::FindInterfaceByString(theString));}
1092
1093 // Note for the "SimpleTypeTemplate" and its derivatives for "double", "int", etc
1094 // have casting/conversion operators defined that allow direct use of the
1095 // corresponding "simple" type (i.e. "double", etc) for the "cost" argument here.
1096 LINK_TYPE* Connect(IFACE_TYPE& srcIface, IFACE_TYPE& dstIface, const COST_TYPE& cost)
1097 {return static_cast<LINK_TYPE*>(NetGraph::Connect(srcIface, dstIface, cost));}
1098
1099 bool Connect(IFACE_TYPE& srcIface, IFACE_TYPE& dstIface, const COST_TYPE& cost, bool duplex)
1100 {return NetGraph::Connect(srcIface, dstIface, cost, duplex);}
1101
1102 LINK_TYPE* Reconnect(Interface& srcIface, Interface& dstIface, const Cost& cost)
1103 {return static_cast<LINK_TYPE*>(NetGraph::Reconnect(srcIface, dstIface, cost));}
1104
1105 bool Reconnect(IFACE_TYPE& srcIface, IFACE_TYPE& dstIface, const COST_TYPE& cost, bool duplex)
1106 {return NetGraph::Reconnect(srcIface, dstIface, cost, duplex);}
1107
1108 // TBD - provide a GetLinkList() to get list of links from "srcIface" to "dstIface"
1109 LINK_TYPE* GetLink(IFACE_TYPE& srcIface, IFACE_TYPE& dstIface)
1110 {return static_cast<LINK_TYPE*>(srcIface.GetLinkTo(dstIface));}
1111
1112
1113 class AdjacencyIterator : public NetGraph::AdjacencyIterator
1114 {
1115 public:
1116 AdjacencyIterator(IFACE_TYPE& iface) : NetGraph::AdjacencyIterator(iface) {}
1117 virtual ~AdjacencyIterator() {}
1118
1119 IFACE_TYPE* GetNextAdjacency()
1120 {return static_cast<IFACE_TYPE*>(NetGraph::AdjacencyIterator::GetNextAdjacency());}
1121
1122 LINK_TYPE* GetNextAdjacencyLink()
1123 {return static_cast<LINK_TYPE*>(NetGraph::AdjacencyIterator::GetNextAdjacencyLink());}
1124
1125 IFACE_TYPE* GetNextConnector()
1126 {return static_cast<IFACE_TYPE*>(NetGraph::AdjacencyIterator::GetNextConnector());}
1127
1128 }; // end class NetGraphTemplate::AdjacencyIterator
1129
1130 class InterfaceIterator : public NetGraph::InterfaceIterator
1131 {
1132 public:
1133 InterfaceIterator(NetGraphTemplate& theGraph) : NetGraph::InterfaceIterator(theGraph) {}
1134 virtual ~InterfaceIterator() {}
1135
1136 IFACE_TYPE* GetNextInterface()
1137 {return static_cast<IFACE_TYPE*>(NetGraph::InterfaceIterator::GetNextVertice());}
1138
1139 }; // end class NetGraphTemplate::InterfaceIterator
1140
1141 class SimpleTraversal : public NetGraph::SimpleTraversal
1142 {
1143 public:
1144 SimpleTraversal(const NetGraphTemplate& theGraph,
1145 IFACE_TYPE& startIface,
1146 bool traverseNodes = true,
1147 bool collapseNodes = true,
1148 bool depthFirst = false)
1149 : NetGraph::SimpleTraversal(theGraph, startIface, traverseNodes, collapseNodes, depthFirst) {}
1150 virtual ~SimpleTraversal() {}
1151
1152 IFACE_TYPE* GetNextInterface(unsigned int* level = NULL)
1153 {return static_cast<IFACE_TYPE*>(NetGraph::SimpleTraversal::GetNextInterface(level));}
1154
1155 }; // end class NetGraphTemplate::SimpleTraversal
1156
1157 class DijkstraTraversal : public NetGraph::DijkstraTraversal
1158 {
1159 public:
1160 DijkstraTraversal(NetGraphTemplate& theGraph,
1161 Node& startNode,
1162 IFACE_TYPE* startIface = NULL)
1163 : NetGraph::DijkstraTraversal(theGraph, startNode, startIface)
1164 {
1165 Reset();
1166 }
1167
1168 virtual ~DijkstraTraversal() {}
1169
1170 IFACE_TYPE* GetNextInterface()
1171 {return static_cast<IFACE_TYPE*>(NetGraph::DijkstraTraversal::GetNextInterface());}
1172
1173 // (use these post-Dijkstra (i.e., after "GetNextInterface" returns NULL)
1174 const COST_TYPE* GetCost(const IFACE_TYPE& iface) const
1175 {return static_cast<const COST_TYPE*>(NetGraph::DijkstraTraversal::GetCost(iface));}
1176
1177 IFACE_TYPE* GetNextHop(const IFACE_TYPE& dstIface) // from "startIface" towards "dstIface"
1178 {return static_cast<IFACE_TYPE*>(queue_visited.GetNextHop(dstIface));}
1179
1180 IFACE_TYPE* GetPrevHop(const IFACE_TYPE& dstIface) // back towards "startIface"
1181 {return static_cast<IFACE_TYPE*>(queue_visited.GetPrevHop(dstIface));}
1182
1183 // BFS traversal of routing tree ("tree walk")
1184 IFACE_TYPE* TreeWalkNext(unsigned int* level = NULL)
1185 {return static_cast<IFACE_TYPE*>(NetGraph::DijkstraTraversal::TreeWalkNext(level));}
1186
1187 protected:
1188 Cost& AccessCostTemp()
1189 {return static_cast<Cost&>(cost_temp);}
1190
1191 // Required override of NetGraph::Interface::PriorityQueue::ItemFactory::CreateItem()
1192 NetGraph::Interface::PriorityQueue::Item* CreateItem() const
1193 {return static_cast<NetGraph::Interface::PriorityQueue::Item*>(new typename IFACE_TYPE::PriorityQueue::Item);}
1194
1195 COST_TYPE cost_temp;
1196
1197 }; // end class NetGraphTemplate::DijkstraTraversal
1198
1199 protected:
1200 // Override of ProtoGraph::CreateEdge()
1201 virtual Edge* CreateEdge() const
1202 {return static_cast<Edge*>(new LINK_TYPE);}
1203
1204 }; // end class NetGraphTemplate
1205
1206 // TBD - Rename the above "NetGraphTemplate" -> "NetGraphBase" and then declare
1207 // a new "NetGraphTemplate" here (using NetGraphBase) that allows users to
1208 // provide their own Node (and Link?) derivatives as well as Cost type
1209 // so that the proper return types are automatically provided from
1210 // Iterators, etc ... need to think about this a little ... i.e. the "Node"
1211 // is not a problem, but the templating of the COST_TYPE member of Link
1212 // is problematic ... A trick might be to have Dijkstra Traversal keep
1213 // a Link just for cost storage ... i.e. to contain the templating on
1214 // the COST_TYPE contained in the Link?? more thought needed!
1215
1216
1217 // And finally, here we use our "NetGraph" base class and "NetGraphTemplate"
1218 // to generate an _example_ (but usable) "ManetGraph" class that uses the
1219 // "NetGraph::SimpleCostDouble" type as its "cost" metric for Dijkstra, etc
1220 /**
1221 * @class ManetGraph
1222 *
1223 * @brief Derived from NetGraphTemplate using "SimpleCostDouble" as its COST_TYPE.
1224 * Hopefully a suitable graph structure for keeping and exploring multi-hop network state.
1225 * Supports a notion of multiple interfaces per node, etc.
1226 */
1227
1228
1229 class ManetInterface; // predeclared so it can be passed to templated ManetLink definition below
1230 class ManetNode; // predeclared so it can be passed to templated ManetInterface definition below
1231
1232 // Define a ManetLink type that uses the "SimpleCostDouble" as its cost metric
1233 class ManetLink : public NetGraph::LinkTemplate<NetGraph::SimpleCostDouble, ManetInterface> {};
1234
1235 // Define a ManetInterface type to help "wire up" our example templated ManetGraph below
1236 class ManetInterface : public NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, ManetInterface, ManetLink, ManetNode>
1237 {
1238 public:
1239 ManetInterface(ManetNode& theNode, const ProtoAddress& addr)
1240 : NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, ManetInterface, ManetLink, ManetNode>(theNode, addr) {}
1241 ManetInterface(ManetNode& theNode)
1242 : NetGraph::InterfaceTemplate<NetGraph::SimpleCostDouble, ManetInterface, ManetLink, ManetNode>(theNode) {}
1243 }; // end class ManetInterface
1244
1245 // Define a "ManetNode" type that has the ManetInterface thpye
1246 class ManetNode : public NetGraph::NodeTemplate<ManetInterface> {};
1247
1248 // Finally, declare a ManetGraph from our NetGraphTemplate
1249 // Note this also creates ManetGraph::Interface and ManetGraph::Link typedef
1250 // equivalents to ManetInterface/ManetLink
1251 class ManetGraph : public NetGraphTemplate<NetGraph::SimpleCostDouble, ManetInterface, ManetLink, ManetNode> {};
1252
1253
1254 // Note that the following equivalent types are "nested in the ManetGraph namespace via typedef
1255 // ManetGraph::Node == ManetNode
1256 // ManetGraph::Interface == ManetInterface
1257 // ManetGraph::Link == ManetLink
1258
1259
1260 // This simple definition gives you the same sort of "default" ManetGraph
1261 // (the above steps illustrate how to create an opportunity for custom Interface and Link classes)
1262 // class ManetGraph : public NetGraphTemplate<> {};
1263
1264
1265 //
1266 // Also, this could have been similarly (and perhaps more elegantly) done with a namespace as follows:
1267 //
1268 // namespace Manet
1269 // {
1270 // typedef NetGraph::SimpleCostDouble Cost;
1271 // class Interface;
1272 // class Node;
1273 // class Link : public NetGraph::LinkTemplate<Cost, Interface> {};
1274 // class Interface : public NetGraph::InterfaceTemplate<Cost, Node, Interface, Link> {};
1275 // class Graph : public NetGraphTemplate<Cost, Node, Interface, Link> {};
1276 // }; // end namespace Manet
1277 //
1278 // This would result in Maent::Node, Manet::Interface, Manet::Link, and Manet::Graph classes
1279 // (And equivalent Manet::Graph::Node, Manet::Graph::Interface and Manet::Graph::Link class names.
1280 // Other elements (e.g., enums, classed, etc) could be also added to the namespace as needed)
1281
1282 // To summarize, one can define their own custom "Cost", "Node", "Interface", and/or "Link" subclasses
1283 // and then use the template to define your own custom "Graph" class made up of these elements.
1284 // Alternatively, one could subclass from "NetGraph" directly, but the templates provide the convenience
1285 // of iterators, etc that return proper typenames (so arduous casting is not needed)
1286
1287
1288 #endif // _MANET_GRAPH