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
13namespace mcld {
14namespace 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 */
32class ListDigraph
33{
34public:
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
57public:
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
70  void getHead(Node*& pNode) const { pNode = m_pNodeHead; }
71
72private:
73  typedef GCFactory<Node, 0> NodeList;
74  typedef GCFactory<Arc, 0> ArcList;
75
76private:
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