1 //===- ListDigraph.h ------------------------------------------------------===// 2 // 3 // The MCLinker Project 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 #ifndef MCLD_ADT_GRAPHLITE_LISTDIGRAPH_H 10 #define MCLD_ADT_GRAPHLITE_LISTDIGRAPH_H 11 #include <mcld/Support/GCFactory.h> 12 13 namespace mcld { 14 namespace graph { 15 16 /** \class ListDigraph 17 * \brief ListDigraph provides an linked-list inplementation of a graph. 18 * 19 * ListDigraph is designed to get well performance for most algorithms of 20 * graph theory. 21 * 22 * Function | Complexity | Best Complexity 23 * ----------------|------------|-------------------------- 24 * Storage | V + E | 25 * Add node | O(1) | 26 * Add arc | O(1) | 27 * Remove node | O(E) | O(#(fan-in) + #(fan-out)) 28 * Remove edge | O(1) | 29 * Query adjacency | O(E) | O(#(fan-in) + #(fan-out)) 30 * 31 */ 32 class ListDigraph 33 { 34 public: 35 struct Node; 36 struct Arc; 37 38 struct Node { 39 public: 40 Node(); 41 42 public: 43 Node *prev, *next; 44 Arc *first_in, *first_out; 45 }; 46 47 struct Arc { 48 public: 49 Arc(); 50 51 public: 52 Node *target, *source; 53 Arc *prev_in, *next_in; 54 Arc *prev_out, *next_out; 55 }; 56 57 public: 58 ListDigraph(); 59 60 Node* addNode(); 61 62 Arc* addArc(Node& pU, Node& pV); 63 64 void erase(Node& pNode); 65 66 void erase(Arc& pArc); 67 68 void clear(); 69 getHead(Node * & pNode)70 void getHead(Node*& pNode) const { pNode = m_pNodeHead; } 71 72 private: 73 typedef GCFactory<Node, 0> NodeList; 74 typedef GCFactory<Arc, 0> ArcList; 75 76 private: 77 Node* m_pNodeHead; 78 Node* m_pFreeNodeHead; 79 Arc* m_pFreeArcHead; 80 81 NodeList m_NodeList; 82 ArcList m_ArcList; 83 }; 84 85 } // namespace of graph 86 } // namespace of mcld 87 88 #endif 89 90