Tulip  5.2.0
Large graphs analysis and drawing
GraphView.h
1 /*
2  *
3  * This file is part of Tulip (http://tulip.labri.fr)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef Tulip_SUPERGRAPHVIEW_H
22 #define Tulip_SUPERGRAPHVIEW_H
23 
24 #include <vector>
25 #include <tulip/GraphAbstract.h>
26 #include <tulip/GraphImpl.h>
27 #include <tulip/MutableContainer.h>
28 #include <tulip/IdManager.h>
29 
30 namespace tlp {
31 // used for node management
32 struct SGraphNodeData {
33  unsigned int outDegree;
34  unsigned int inDegree;
35  SGraphNodeData() : outDegree(0), inDegree(0) {}
36  inline void outDegreeAdd(int i) {
37  outDegree += i;
38  }
39  inline void inDegreeAdd(int i) {
40  inDegree += i;
41  }
42 };
43 
44 typedef SGraphNodeData *SGraphNodeDataPtr;
45 DECL_STORED_PTR(SGraphNodeDataPtr);
46 
47 /**
48  * This class is one of the implementation of the Graph Interface
49  * It only filters the elements of its parents.
50  */
51 class GraphView : public GraphAbstract {
52 
53  inline GraphImpl *getRootImpl() const {
54  return static_cast<GraphImpl *>(getRoot());
55  }
56 
57  friend class GraphImpl;
58 
59 public:
60  GraphView(Graph *supergraph, BooleanProperty *filter, unsigned int id);
61  ~GraphView() override;
62  //========================================================================
63  node addNode() override;
64  void addNodes(unsigned int nb) override;
65  void addNodes(unsigned int nb, std::vector<node> &addedNodes) override;
66  void addNode(const node) override;
67  void addNodes(Iterator<node> *nodes) override;
68  edge addEdge(const node n1, const node n2) override;
69  void addEdges(const std::vector<std::pair<node, node>> &edges,
70  std::vector<edge> &addedEdges) override;
71  void addEdges(const std::vector<std::pair<node, node>> &edges) override;
72  void addEdge(const edge) override;
73  void addEdges(Iterator<edge> *edges) override;
74  void delNode(const tlp::node n, bool deleteInAllGraphs = false) override;
75  void delEdge(const tlp::edge e, bool deleteInAllGraphs = false) override;
76  void setEdgeOrder(const node n, const std::vector<edge> &v) override {
77  getRootImpl()->setEdgeOrder(n, v);
78  }
79  void swapEdgeOrder(const node n, const edge e1, const edge e2) override {
80  getRootImpl()->swapEdgeOrder(n, e1, e2);
81  }
82  //=========================================================================
83  inline bool isElement(const node n) const override {
84  return _nodeData.get(n.id) != nullptr;
85  }
86  inline bool isElement(const edge e) const override {
87  return _edges.isElement(e);
88  }
89  edge existEdge(const node source, const node target, bool directed) const override;
90  inline unsigned int numberOfNodes() const override {
91  return _nodes.size();
92  }
93  inline unsigned int numberOfEdges() const override {
94  return _edges.size();
95  }
96  //=========================================================================
97  inline unsigned int deg(const node n) const override {
98  assert(isElement(n));
99  SGraphNodeData *nData = _nodeData.get(n.id);
100  return nData->inDegree + nData->outDegree;
101  }
102  inline unsigned int indeg(const node n) const override {
103  assert(isElement(n));
104  return _nodeData.get(n.id)->inDegree;
105  }
106  inline unsigned int outdeg(const node n) const override {
107  assert(isElement(n));
108  return _nodeData.get(n.id)->outDegree;
109  }
110  //=========================================================================
111  inline node source(const edge e) const override {
112  return getRootImpl()->source(e);
113  }
114  inline void setSource(const edge e, const node newSrc) override {
115  assert(isElement(e));
116  getRootImpl()->setEnds(e, newSrc, node());
117  }
118  inline node target(const edge e) const override {
119  return getRootImpl()->target(e);
120  }
121  inline void setTarget(const edge e, const node newTgt) override {
122  assert(isElement(e));
123  getRootImpl()->setEnds(e, node(), newTgt);
124  }
125  inline const std::pair<node, node> &ends(const edge e) const override {
126  return getRootImpl()->ends(e);
127  }
128  inline void setEnds(const edge e, const node newSrc, const node newTgt) override {
129  assert(isElement(e));
130  getRootImpl()->setEnds(e, newSrc, newTgt);
131  }
132  inline node opposite(const edge e, const node n) const override {
133  return getRootImpl()->opposite(e, n);
134  }
135  inline void reverse(const edge e) override {
136  assert(isElement(e));
137  getRootImpl()->reverse(e);
138  }
139  //=========================================================================
140  inline const std::vector<node> &nodes() const override {
141  return _nodes;
142  }
143  inline unsigned int nodePos(const node n) const override {
144  return _nodes.getPos(n);
145  }
146  Iterator<node> *getNodes() const override;
147  Iterator<node> *getInNodes(const node) const override;
148  Iterator<node> *getOutNodes(const node) const override;
149  Iterator<node> *getInOutNodes(const node) const override;
150  inline const std::vector<edge> &edges() const override {
151  return _edges;
152  }
153  inline unsigned int edgePos(const edge e) const override {
154  return _edges.getPos(e);
155  }
156  Iterator<edge> *getEdges() const override;
157  Iterator<edge> *getInEdges(const node) const override;
158  Iterator<edge> *getOutEdges(const node) const override;
159  Iterator<edge> *getInOutEdges(const node) const override;
160  std::vector<edge> getEdges(const node source, const node target,
161  bool directed = true) const override;
162  inline const std::vector<edge> &allEdges(const node n) const override {
163  return getRootImpl()->allEdges(n);
164  }
165  inline void sortElts() override {
166  _nodes.sort();
167  _edges.sort();
168  }
169  inline Graph *getRoot() const override {
170  // handle root destruction (see GraphAbstract destructor)
171  return id == 0 ? const_cast<GraphView *>(this) : GraphAbstract::getRoot();
172  }
173  //=========================================================================
174  // only implemented on a root graph
175  void reserveNodes(unsigned int nbNodes) override;
176  void reserveEdges(unsigned int nbEdges) override;
177  //=========================================================================
178  // updates management
179  void push(bool unpopAllowed = true,
180  std::vector<PropertyInterface *> *propertiesToPreserveOnPop = nullptr) override;
181  void pop(bool unpopAllowed = true) override;
182  void popIfNoUpdates() override;
183  void unpop() override;
184  bool canPop() override;
185  bool canUnpop() override;
186  bool canPopThenUnpop() override;
187 
188 protected:
189  // designed to reassign an id to a previously deleted elt
190  // used by GraphUpdatesRecorder
191  void restoreNode(node) override;
192  void restoreEdge(edge, node source, node target) override;
193  // designed to only update own structures
194  // used by GraphUpdatesRecorder
195  void removeNode(const node) override;
196  void removeEdge(const edge) override;
197  void removeNode(const node n, const std::vector<edge> &edges);
198  void removeEdges(const std::vector<edge> &edges);
199 
200 private:
201  MutableContainer<SGraphNodeDataPtr> _nodeData;
202  SGraphIdContainer<node> _nodes;
203  SGraphIdContainer<edge> _edges;
204  void outDegreeAdd(node n, int i);
205  void inDegreeAdd(node n, int i);
206  edge addEdgeInternal(edge);
207  void reverseInternal(const edge, const node src, const node tgt);
208  void setEndsInternal(const edge, node src, node tgt, const node newSrc, const node newTgt);
209  void addNodesInternal(unsigned int nbAdded, const std::vector<node> *nodes);
210  void addEdgesInternal(unsigned int nbAdded, const std::vector<edge> *edges,
211  const std::vector<std::pair<node, node>> &ends);
212 };
213 }
214 #endif
215 
216 ///@endcond
The edge struct represents an edge in a Graph object.
Definition: Edge.h:40
The node struct represents a node in a Graph object.
Definition: Node.h:40