Debian Codegraph @

protolib/include/protoGraph.h

raw
1 #ifndef _PROTO_GRAPH
2 #define _PROTO_GRAPH
3
4 #include "protoTree.h"
5 #include "protoDebug.h"
6 #include "protoDefs.h"
7
8 // TBD - this could be re-implemented using ProtoQueue classes
9 // for VerticeQueue, etc.
10
11 /**
12 * @class ProtoGraph
13 *
14 * @brief Base class for managing graph data structures.
15 */
16 class ProtoGraph
17 {
18 public:
19 ProtoGraph();
20 virtual ~ProtoGraph();
21
22 /**
23 * @class Vertice
24 *
25 * @brief A basic ProtoGraph element, the "vertice"
26 */
27 class Vertice;
28 /**
29 * @class Edge
30 *
31 * @brief A basic ProtoGraph element, the "edge"
32 */
33 class Edge;
34
35 // (TBD) We should probably give the ProtoGraph
36 // a "VerticeFactory" and require vertices be
37 // managed _under_ the graph (no Insert/Remove) since
38 // our Vertice class only has one AdjacencyQueue
39 // member. Otherwise we would need to give the Vertice
40 // a "GraphList" with each GraphList::Item having
41 // the "AdjacencyQueue" for that corresponding graph?
42
43 bool InsertVertice(Vertice& vertice);
44
45 void RemoveVertice(Vertice& vertice); // associated links are removed with vertice
46
47 Vertice* FindVertice(const char* key, unsigned int keysize) const
48 {return vertice_list.FindVertice(key, keysize);}
49
50 bool IsInGraph(const Vertice& vertice) const
51 {return (vertice.IsInQueue(vertice_list));}
52
53
54 // "Connect()" creates a directed edge from "src" to "dst"
55 Edge* Connect(Vertice& src, Vertice& dst);
56
57 void Reconnect(Vertice& src, Vertice& dst, Edge& edge);
58
59 void Disconnect(Vertice& src, Vertice& dst, bool duplex = false);
60
61 bool IsEmpty() const
62 {return vertice_list.IsEmpty();}
63
64 // Disconnect and remove any inserted vertices
65 // (does not delete the vertices)
66 void Empty();
67
68
69 /**
70 * @class ProtoGraph::AdjacencyIterator
71 */
72 class AdjacencyIterator
73 {
74 public:
75 AdjacencyIterator(Vertice& vertice);
76 virtual ~AdjacencyIterator();
77
78 // TBD - provide some iteration options here. For example,
79 // iterate conjointly over "adjacencies" and "connectors"
80
81 // @brief Returns next vertice _to_ which there is connection
82 Vertice* GetNextAdjacency();
83
84 // @brief Returns next edge _to_ which there is connection
85 Edge* GetNextAdjacencyEdge()
86 {return static_cast<Edge*>(adj_iterator.GetNextItem());}
87
88 // @brief Returns next vertice _from_ which there is connection
89 // (note can use Vertice::GetEdgeTo(vertice) to get that edge if desired)
90 Vertice* GetNextConnector();
91
92 void Reset()
93 {
94 adj_iterator.Reset();
95 con_iterator.Reset();
96 }
97
98 private:
99 ProtoSortedTree::Iterator adj_iterator;
100 ProtoSortedTree::Iterator con_iterator;
101
102 }; // end class ProtoGraph::Vertice::AdjacencyIterator
103
104 /**
105 * @class VerticeQueue
106 *
107 * @brief Base class for Queues that wish to contain Vertices. Note that
108 * the VerticeQueue does _not_ itself implement any form of list or tree, etc
109 * but instead leaves the specific form of data structure to derived
110 * subclasses so that VerticeQueues may be implemented in different ways. The
111 * VerticeQueue really just provides a base means for Vertices to keep track
112 * of which lists they are in and the pure virtual VerticeQueue::Remove() method
113 * is where a Vertice should get disassociated from the given VerticeQueue derivative
114 */
115
116 class VerticeQueue
117 {
118 public:
119 virtual ~VerticeQueue();
120
121 virtual void Remove(Vertice& vertice) = 0;
122
123 virtual void Empty() = 0; // MUST remove all items from queue
124
125 bool Contains(const Vertice& vertice)
126 {return (NULL != vertice.GetQueueState(*this));}
127
128 class QueueStatePool;
129 /**
130 * @class QueueState
131 *
132 * @brief The "ProtoGraph::VerticeQueue::QueueState"
133 * class is a base class that enables
134 * the "Vertice" class to keep track of the
135 * VerticeQueues to which it belongs. Additionally,
136 * those VerticeQueue subclasses can extend
137 * the VerticeQueue::QueueState class to contain
138 * additional state that is associated with the
139 * given vertice in the context of that VerticeQueue
140 */
141 class QueueState
142 {
143 friend class VerticeQueue;
144 friend class Vertice;
145 friend class QueueStatePool;
146
147 public:
148 virtual ~QueueState();
149
150 Vertice* GetVertice() const
151 {return vertice;}
152 VerticeQueue* GetQueue() const
153 {return queue;}
154
155 protected:
156 QueueState();
157
158 // IMPORTANT: Any derived QueueState classes MUST call
159 // cleanup in their destructor to avoid possible indirect
160 // calls to virtual functions in the ~QueueState() destructor
161 void Cleanup();
162
163 void Associate(Vertice& theVertice, VerticeQueue& theQueue)
164 {
165 vertice = &theVertice;
166 queue = &theQueue;
167 }
168 void Disassociate()
169 {
170 vertice = NULL;
171 queue = NULL;
172 }
173
174 void SetQueue(VerticeQueue& theQueue)
175 {queue = &theQueue;}
176
177 /**
178 * @class Entry
179 *
180 * @brief Container used by Vertices to keep
181 * their lists of VerticeQueueState
182 */
183 class Entry : public ProtoTree::Item
184 {
185 public:
186 Entry(QueueState& queueState);
187 QueueState& GetQueueState() const
188 {return queue_state;}
189
190 const char* GetKey() const
191 {return ((const char*)queue_state.GetQueueHandle());}
192 unsigned int GetKeysize() const
193 {return (sizeof(VerticeQueue*) << 3);}
194
195 private:
196 QueueState& queue_state; // "parent" VerticeQueueState
197 }; // end class ProtoGraph::Vertice::Queue::QueueState::Entry
198
199 Entry& AccessEntry() {return entry;}
200
201 const VerticeQueue** GetQueueHandle() const
202 {return ((const VerticeQueue**)&queue);}
203
204 private:
205 Vertice* vertice;
206 VerticeQueue* queue; // "parent" VerticeQueue
207 Entry entry;
208
209 }; // end class ProtoGraph::VerticeQueue::QueueState
210 /**
211 * @class ProtoGraph::VerticeQueue::QueueStatePool
212 *
213 * @brief QueueState repository. Note that a QueueStatePool
214 * should ony be used to cache a single (i.e. homogeneous) type
215 * of QueueState (i.e. QueueState subclass) otherwise one
216 * may not "Get()" what one expects from the pool!
217 */
218 class QueueStatePool : public ProtoTree::ItemPool
219 {
220 public:
221 QueueStatePool();
222 virtual ~QueueStatePool();
223
224 void Destroy();
225
226 QueueState* Get()
227 {
228 QueueState::Entry* entry = static_cast<QueueState::Entry*>(ProtoTree::ItemPool::Get());
229 return ((NULL != entry) ? &(entry->GetQueueState()) : NULL);
230 }
231
232 void Put(QueueState& theState)
233 {ProtoTree::ItemPool::Put(theState.AccessEntry());}
234
235 }; // end class ProtoGraph::VerticeQueue::QueueStatePool
236
237 protected:
238 VerticeQueue();
239
240 void TransferQueueState(QueueState& queueState, VerticeQueue& dstQueue)
241 {
242 Vertice* vertice = queueState.GetVertice();
243 ASSERT(NULL != vertice);
244 vertice->Dereference(queueState);
245 queueState.SetQueue(dstQueue);
246 vertice->Reference(queueState);
247 }
248
249 QueueState* GetQueueState(const Vertice& vertice) const
250 {return vertice.GetQueueState(*this);}
251
252 void Associate(Vertice& vertice, QueueState& queueState);
253 void Disassociate(Vertice& vertice, QueueState& queueState);
254
255 }; // end class VerticeQueue
256
257
258 class EdgePool;
259 /**
260 * @class AdjacencyQueue
261 *
262 * @brief List of Vertices adjacent, sorted by Edge "key"
263 * (i.e. instead of Vertice "key" as in case of SortedList)
264 */
265 class AdjacencyQueue : public VerticeQueue
266 {
267 friend class Vertice;
268 friend class Edge;
269 friend class AdjacencyIterator;
270
271 protected:
272 AdjacencyQueue(Vertice& srcVertice);
273 virtual ~AdjacencyQueue();
274
275 // Connect to "dstVertice" with "edge"
276 void Connect(Vertice& dstVertice,
277 Edge& edge);
278 // Same as connect but doesn't call OnConnect
279 void Reconnect(Vertice& dstVertice,
280 Edge& edge);
281
282 // Remove all edges to "dstVertice"
283 void Disconnect(Vertice& dstVertice,
284 EdgePool* edgePool = NULL);
285
286 // Remove a specific edge (and pool or delete it)
287 void RemoveEdge(Vertice& dstVertice,
288 Edge& edge,
289 EdgePool* edgePool = NULL);
290
291 // Remove a specific edge (but don't delete it)
292 void SuspendEdge(Vertice& dstVertice,
293 Edge& edge);
294
295 Vertice& GetSrc() const
296 {return src_vertice;}
297
298 // Note this count currently only reflects edges _to_ other Vertices
299 unsigned int GetCount() const
300 {return adjacency_count;}
301
302 // Methods used to manage connector_tree
303 // TBD - keep a "connector_count" ???
304 void AddConnector(Edge& edge);
305 void RemoveConnector(Edge& edge);
306
307 private:
308 void Remove(Vertice& dstVertice)
309 {Disconnect(dstVertice, NULL);}
310
311 void Empty();
312
313 Vertice& src_vertice;
314 ProtoSortedTree adjacency_tree; // list of dst vertices I am connected _to_
315 unsigned int adjacency_count;
316 ProtoSortedTree connector_tree; // sorted list edges connected _to_ me
317
318 }; // end class ProtoGraph::AdjacencyQueue
319
320
321 /**
322 * @class ProtoGraph::Edge
323 *
324 * @brief The ProtoGraph::Edge inherits from "VerticeQueue::QueueState" so
325 * for the Edge's src Vertice "adjacency_queue" that derives from VerticeQueue.
326 * It inherits from ProtoSortedTree::Item since the AdjacencyQueue is implemented
327 * as a ProtoSortedTree (sorted on the Edge key). Finally, the Edge contains
328 * a "tracker" member that is used by the Edge's dst Vertice to "track" which
329 * edges are pointing towards that given Vertice. A "connector_list" is an element
330 * of the Vertice "adjacency_queue"
331 *
332 */
333 class Edge : public VerticeQueue::QueueState, public ProtoSortedTree::Item
334 {
335 friend class AdjacencyQueue;
336 friend class AdjacencyIterator;
337
338 public:
339 Edge();
340
341 virtual ~Edge();
342
343 virtual void OnConnect();
344 virtual void OnDisconnect();
345
346 Vertice* GetDst() const
347 {return GetVertice();}
348
349 Vertice* GetSrc() const;
350
351 // Subclasses should override these to provide
352 // a sorting criteria (if desired) for the
353 // "AdjacencyQueue" defined above
354 virtual const char* GetKey() const;
355 virtual unsigned int GetKeysize() const;
356 virtual ProtoTree::Endian GetEndian() const;
357 virtual bool UseSignBit() const;
358 virtual bool UseComplement2() const;
359
360 private:
361 class Tracker : public ProtoSortedTree::Item
362 {
363 public:
364 Tracker(const Edge& edge);
365
366 const Edge& GetEdge() const
367 {return edge;}
368
369 private:
370 virtual const char* GetKey() const
371 {return edge.GetKey();}
372 virtual unsigned int GetKeysize() const
373 {return edge.GetKeysize();}
374 virtual ProtoTree::Endian GetEndian() const
375 {return edge.GetEndian();}
376 virtual bool UseSignBit() const
377 {return edge.UseSignBit();}
378 virtual bool UseComplement2() const
379 {return edge.UseComplement2();}
380
381 const Edge& edge;
382
383 }; // end class ProtoGraph::Edge::Tracker
384
385 // Only the AdjacencyQueue should invoke this method.
386 Tracker& AccessTracker()
387 {return tracker;}
388
389 Tracker tracker; // used by dst vertices to "track" edges _from_ src vertices
390 // (Whenever an Edge is added to a src vertice "adjacency_queue",
391 // the Edge::tracker is added to the dst vertice
392 // "adjacency_queue::connector_tree"
393
394 }; // end class ProtoGraph::Edge
395
396 class EdgePool : public VerticeQueue::QueueStatePool
397 {
398 public:
399 EdgePool();
400 virtual ~EdgePool();
401
402 Edge* GetEdge()
403 {return static_cast<Edge*>(VerticeQueue::QueueStatePool::Get());}
404
405 void PutEdge(Edge& edge)
406 {VerticeQueue::QueueStatePool::Put(edge);}
407
408 }; // end class ProtoGraph::EdgePool
409
410
411 /**
412 * @class Vertice
413 *
414 */
415 class Vertice
416 {
417 friend class ProtoGraph;
418 friend class VerticeQueue;
419
420 public:
421 virtual ~Vertice();
422
423 // Subclasses _may_ want to override these methods
424 // (These are used for default sorting of
425 // of the Vertice::SortedList if used)
426 // _BUT_ if these are overridden, the derived
427 // class destructor _MUST_ call Vertice::Cleanup() so
428 // that these _are_ not indirectly called in the Vertice
429 // destructor!!!
430 virtual const char* GetVerticeKey() const = 0;
431 virtual unsigned int GetVerticeKeysize() const = 0;
432 virtual ProtoTree::Endian GetVerticeKeyEndian() const;
433 virtual bool GetVerticeKeySigned() const;
434 virtual bool GetVerticeKeyComplement2() const;
435
436 void Cleanup(); // see comment immediately above
437
438 bool IsInQueue(const VerticeQueue& queue) const
439 {return (NULL != GetQueueState(queue));}
440
441 // This tests for "this" _to_ "dst" connection (unidirectional check)
442 bool HasEdgeTo(const Vertice& dst) const
443 {return dst.IsInQueue(adjacency_queue);}
444
445 Edge* GetEdgeTo(const Vertice& dst) const
446 {return static_cast<Edge*>(dst.GetQueueState(adjacency_queue));}
447
448 unsigned int GetAdjacencyCount() const
449 {return adjacency_queue.GetCount();}
450
451 /**
452 * @class ProtoGraph::Vertice::SimpleList
453 *
454 * @brief Simple unsorted, doubly linked-list class used for
455 * traversals and other purposes
456 */
457 class SimpleList : public VerticeQueue
458 {
459 public:
460 class ItemPool;
461
462 SimpleList(SimpleList::ItemPool* itemPool = NULL);
463 virtual ~SimpleList();
464
465 // required override
466 virtual void Remove(Vertice& vertice);
467
468 bool Prepend(Vertice& vertice);
469 bool Append(Vertice& vertice);
470
471 bool IsEmpty() const
472 {return (NULL == head);}
473
474 // Note "Empty()" does not delete Vertices, but does
475 // delete or pool the queue state "Items"
476 void Empty();
477
478 Vertice* GetHead() const
479 {return ((NULL != head) ? head->GetVertice() : NULL);}
480
481 Vertice* RemoveHead();
482
483 class Iterator;
484
485 /**
486 * @class ProtoGraph::Vertice::SimpleList::Item
487 *
488 */
489 class Item : public QueueState
490 {
491 friend class SimpleList;
492 friend class ItemPool;
493 friend class Iterator;
494
495 public:
496 Item();
497 virtual ~Item();
498
499 protected:
500 void Prepend(Item* theItem)
501 {prev = theItem;}
502 void Append(Item* theItem)
503 {next = theItem;}
504
505 Item* GetPrev() const
506 {return prev;}
507 Item* GetNext() const
508 {return next;}
509
510 private:
511 Item* prev;
512 Item* next;
513 }; // end class ProtoGraph::Vertice::SimpleList::Item
514
515 // Move vertice from this SimpleList to another
516 void TransferVertice(Vertice& vertice, SimpleList& dstSimpleList)
517 {
518 Item* item = static_cast<Item*>(vertice.GetQueueState(*this));
519 ASSERT(NULL != item);
520 TransferItem(*item, dstSimpleList);
521 }
522
523 void TransferItem(Item& item, SimpleList& dstSimpleList)
524 {
525 Vertice* vertice = item.GetVertice();
526 ASSERT(NULL != vertice);
527 RemoveItem(item);
528 TransferQueueState(item, dstSimpleList);
529 dstSimpleList.AppendItem(item);
530 }
531
532 /**
533 * @class ProtoGraph::Vertice::SimpleList::ItemPool
534 *
535 * @brief Container class for Items
536 */
537 class ItemPool : public VerticeQueue::QueueStatePool
538 {
539 public:
540 ItemPool();
541 virtual ~ItemPool();
542
543 Item* GetItem();
544
545 void PutItem(Item& item)
546 {VerticeQueue::QueueStatePool::Put(item);}
547
548 }; // end class ProtoGraph::Vertice::SimpleList::ItemPool
549
550 /**
551 * @class ProtoGraph::Vertice::SimpleList::Iterator
552 */
553 class Iterator
554 {
555 public:
556 Iterator(const SimpleList& theSimpleList, bool reverse = false);
557 virtual ~Iterator();
558
559 void Reset();
560 Vertice* GetNextVertice();
561
562 private:
563 const SimpleList& list;
564 Item* next_item;
565 bool forward;
566
567 }; // end class ProtoGraph::Vertice::SimpleList::Iterator
568 friend class Iterator;
569
570 protected:
571 Item* GetNewItem()
572 {return ((NULL != item_pool) ? item_pool->GetItem() : new Item);}
573 void AppendItem(Item& item);
574 void PrependItem(Item& item);
575 void RemoveItem(Item& item);
576
577 Item* head;
578 Item* tail;
579 ItemPool* item_pool;
580
581 }; // end class ProtoGraph::Vertice::SimpleList()
582
583
584 /**
585 * @class SortedList
586 *
587 * @brief This maintains a list of Vertices,
588 * sorted by their "key", whatever that happens to be ...
589 */
590 class SortedList : public VerticeQueue
591 {
592 public:
593 class ItemPool;
594
595 SortedList(ItemPool* itemPool = NULL);
596 virtual ~SortedList();
597
598 // required override
599 virtual void Remove(Vertice& vertice);
600
601 bool Insert(Vertice& vertice);
602
603 Vertice* FindVertice(const char* key, unsigned int keysize) const
604 {
605 Item* item = static_cast<Item*>(sorted_item_tree.Find(key, keysize));
606 return (NULL != item) ? item->GetVertice() : NULL;
607 }
608
609 Vertice* GetHead() const
610 {
611 Item* headItem = static_cast<Item*>(sorted_item_tree.GetHead());
612 return ((NULL != headItem) ? headItem->GetVertice() : NULL);
613 }
614
615 Vertice* RemoveHead();
616
617 // Only use when you don't want the list sorted!
618 // (you should probably use simple list instead)
619 bool Append(Vertice& vertice);
620
621 bool IsEmpty() const
622 {return sorted_item_tree.IsEmpty();}
623
624 void Empty();
625
626 /**
627 * @class ProtoGraph::Vertice::SortedList::Item
628 *
629 * @brief "Item" is our QueueState subclass
630 * "container" for vertices in the list
631 */
632 class Item : public VerticeQueue::QueueState, public ProtoSortedTree::Item
633 {
634 public:
635 Item();
636 virtual ~Item();
637
638 // required (and optional) overrides for ProtoSortedTree::Item
639 // (these default implementations use Vertice::GetVerticeKey(), etc)
640 virtual const char* GetKey() const;
641 virtual unsigned int GetKeysize() const;
642 virtual ProtoTree::Endian GetEndian() const;
643 virtual bool UseSignBit() const;
644 virtual bool UseComplement2() const;
645 }; // end class ProtoGraph::Vertice::SortedList::Item
646
647 // Move vertice from this SortedList to another
648 void TransferVertice(Vertice& vertice, SortedList& dstList)
649 {
650 Item* item = static_cast<Item*>(vertice.GetQueueState(*this));
651 ASSERT(NULL != item);
652 TransferItem(*item, dstList);
653 }
654
655 void TransferItem(Item& item, SortedList& dstList)
656 {
657 Vertice* vertice = item.GetVertice();
658 ASSERT(NULL != vertice);
659 RemoveItem(item);
660 TransferQueueState(item, dstList);
661 dstList.InsertItem(item);
662 }
663
664 /**
665 * @class ProtoGraph::Vertice::SortedList::ItemPool
666 *
667 */
668 class ItemPool : public VerticeQueue::QueueStatePool
669 {
670 public:
671 ItemPool();
672 virtual ~ItemPool();
673
674 Item* GetItem();
675
676 void PutItem(Item& item)
677 {VerticeQueue::QueueStatePool::Put(item);}
678
679 }; // end class ProtoGraph::Vertice::SortedList::ItemPool
680
681 /**
682 * @class ProtoGraph::Vertice::SortedList::Iterator
683 */
684 class Iterator : public ProtoSortedTree::Iterator
685 {
686 public:
687 Iterator(SortedList& theList);
688 virtual ~Iterator();
689
690 Item* GetNextItem()
691 {return static_cast<Item*>(ProtoSortedTree::Iterator::GetNextItem());}
692
693 Vertice* GetNextVertice()
694 {
695 Item* nextItem = GetNextItem();
696 return ((NULL != nextItem) ? nextItem->GetVertice() : NULL);
697 }
698 }; // end class ProtoGraph::Vertice::SortedList::Iterator
699 friend class Iterator;
700
701 protected:
702 Item* GetNewItem()
703 {return ((NULL != item_pool) ? item_pool->GetItem() : new Item);}
704 void InsertItem(Item& item)
705 {
706 ASSERT(0 != item.GetKeysize());
707 sorted_item_tree.Insert(item);
708 }
709 void RemoveItem(Item& item)
710 {sorted_item_tree.Remove(item);}
711 void AppendItem(Item& item)
712 {sorted_item_tree.Append(item);}
713
714 ProtoSortedTree sorted_item_tree;
715 ItemPool* item_pool;
716
717 }; // end class ProtoGraph::Vertice::SortedList
718
719 friend class AdjacencyQueue;
720 friend class AdjacencyIterator;
721
722 protected:
723 Vertice();
724
725 // These are used by the friend class ProtoGraph. We keep these
726 // protected since the ProtoGraph instance in which the connections
727 // are made (or removed) maintains the pools of Edge and Connector
728 // instances and public access to these methods could result
729 // in mismanagement of the pooled items. I.e., the
730 // "ProtoGraph::Connect()", "ProtoGraph::Disconnect()", etc
731 // methods MUST be used instead of using these directly.
732
733 // Note here the "edge" is the connection from src->dst while
734 // the "connector" allows dst vertices to know who is connected
735 // to them.
736 void Connect(Vertice& dst, Edge& edge)
737 {adjacency_queue.Connect(dst, edge);}
738
739 void Reconnect(Vertice& dst, Edge& edge)
740 {adjacency_queue.Reconnect(dst, edge);}
741
742 void Disconnect(Vertice& dst, EdgePool* edgePool = NULL)
743 {adjacency_queue.Disconnect(dst, edgePool);}
744
745 void RemoveEdge(Vertice& dst, Edge& edge, EdgePool* edgePool = NULL)
746 {adjacency_queue.RemoveEdge(dst, edge, edgePool);}
747
748 void SuspendEdge(Vertice& dst, Edge& edge)
749 {adjacency_queue.SuspendEdge(dst, edge);}
750
751 private:
752 // These are called by a connected src Vertice::adjacency_queue
753 // so a dst Vertice can know of connections _to_ itself
754 void AddConnector(Edge& edge)
755 {adjacency_queue.AddConnector(edge);}
756 void RemoveConnector(Edge& edge)
757 {adjacency_queue.RemoveConnector(edge);}
758
759 VerticeQueue::QueueState* GetQueueState(const VerticeQueue& queue) const
760 {
761 const VerticeQueue* ptr = &queue;
762 VerticeQueue::QueueState::Entry* entry =
763 static_cast<VerticeQueue::QueueState::Entry*>(queue_state_tree.Find((const char*)&ptr, sizeof(VerticeQueue*) << 3));
764 return ((NULL != entry) ? &entry->GetQueueState() : NULL);
765 }
766 void Reference(VerticeQueue::QueueState& queueState)
767 {queue_state_tree.Insert(queueState.AccessEntry());}
768 void Dereference(VerticeQueue::QueueState& queueState)
769 {
770 ASSERT(this == queueState.GetVertice());
771 queue_state_tree.Remove(queueState.AccessEntry());
772 }
773
774 // Queue of adjacent vertices
775 // (uses "Edge" for queue state)
776 AdjacencyQueue adjacency_queue;
777
778 // These members are for use by traversals and
779 // other queue manipulations as needed
780 ProtoTree queue_state_tree;
781
782 }; // end class ProtoGraph::Vertice
783
784 /**
785 * @class ProtoGraph::VerticeIterator
786 */
787 class VerticeIterator : public Vertice::SortedList::Iterator
788 {
789 public:
790 VerticeIterator(ProtoGraph& theGraph);
791 virtual ~VerticeIterator();
792
793 // Note: Inherits the following
794 // void Reset();
795 // Vertice* GetNextVertice();
796
797 }; // end class ProtoGraph::VerticeIterator
798 friend class VerticeIterator;
799
800 /**
801 * @class ProtoGraph::SimpleTraversal
802 *
803 * @brief (TBD) We may want to make a separate "Traversal" base class
804 * that SimpleTraversal (and others) derive from so that a
805 * ProtoGraph can inform associated Traversals if the
806 * graph state changes ???
807 */
808 class SimpleTraversal
809 {
810 public:
811 SimpleTraversal(const ProtoGraph& theGraph,
812 Vertice& startVertice,
813 bool depthFirst = false);
814 virtual ~SimpleTraversal();
815 bool Reset();
816 Vertice* GetNextVertice(unsigned int* level = NULL);
817
818 // Override this method to filter which edges are included in traversal
819 // (return "false" to disallow specific edges)
820 // (Note that "edge->GetDst()" can be used to get the dst vertice)
821 virtual bool AllowEdge(const Vertice& srcVertice, const Edge& edge)
822 {return true;}
823
824 protected:
825 // Members
826 const ProtoGraph& graph;
827 Vertice& start_vertice;
828 bool depth_first; // false == breadth-first search
829 unsigned int current_level;
830 Vertice* trans_vertice; // level transition marker
831 Vertice::SimpleList queue_pending;
832 Vertice::SimpleList queue_visited;
833
834 Vertice::SimpleList::ItemPool item_pool;
835
836 }; // end class ProtoGraph::SimpleTraversal
837
838 protected:
839 // Subclasses may wish to override this if
840 // they use different Edge subclass variants
841 virtual Edge* CreateEdge() const
842 {return new Edge;}
843 // "GetEdge()" tries to get an edge from edge_pool else calls "CreateEdge()"
844 Edge* GetEdge();
845 void PutEdge(Edge& edge)
846 {edge_pool.Put(edge);}
847
848 // These let ProtoGraph subclasses control Connect() a little more specifically if desired
849 void Connect(Vertice& src, Vertice& dst, Edge& edge)
850 {src.Connect(dst, edge);}
851
852 void RemoveEdge(Vertice& src, Vertice& dst, Edge& edge)
853 {src.RemoveEdge(dst, edge, &edge_pool);}
854
855 void SuspendEdge(Vertice& src, Vertice& dst, Edge& edge)
856 {src.SuspendEdge(dst, edge);}
857
858 // Member variables
859 Vertice::SortedList vertice_list;
860
861 // Pools of vertice items and edges
862 Vertice::SortedList::ItemPool vertice_list_item_pool;
863 EdgePool edge_pool;
864
865 }; // end class ProtoGraph
866
867 #endif // _PROTO_GRAPH