Tulip  4.8.0
Better Visualization Through Research
 All Classes Files Functions Variables Enumerations Enumerator Properties Groups Pages
GraphImpl.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
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_SUPERGRAPHIMPL_H
22 #define Tulip_SUPERGRAPHIMPL_H
23 
24 #ifndef DOXYGEN_NOTFOR_USER
25 
26 #include <set>
27 
28 #include <vector>
29 #include <list>
30 #include <tulip/GraphAbstract.h>
31 #include <tulip/GraphStorage.h>
32 #include <tulip/IdManager.h>
33 
34 namespace tlp {
35 template<class itType >
36 struct Iterator;
37 class GraphView;
38 class GraphUpdatesRecorder;
39 
40 ///Implementation of the graph support of the Graph.
41 class TLP_SCOPE GraphImpl:public GraphAbstract {
42 
43  friend class GraphUpdatesRecorder;
44  friend class TLPExport;
45 
46 public:
47  GraphImpl();
48  ~GraphImpl();
49  void clear();
50  //=========================================================================
51  bool isElement(const node ) const;
52  bool isElement(const edge ) const;
53  edge existEdge(const node source, const node target,
54  bool directed = true) const;
55  node addNode();
56  void addNodes(unsigned int nb);
57  void addNodes(unsigned int nb, std::vector<node>& addedNodes);
58  void addNode(const node);
59  void addNodes(Iterator<node>* nodes);
60  edge addEdge(const node ,const node);
61  void addEdges(const std::vector<std::pair<node, node> >& edges);
62  void addEdges(const std::vector<std::pair<node, node> >& edges,
63  std::vector<edge>& addedEdges);
64  void addEdge(const edge);
65  void addEdges(Iterator<edge>* edges);
66  void delNode(const tlp::node n, bool deleteInAllGraphs = false);
67  void delEdge(const tlp::edge e, bool deleteInAllGraphs = false);
68  void setEdgeOrder(const node,const std::vector<edge> & );
69  void swapEdgeOrder(const node,const edge , const edge );
70  //=========================================================================
71  Iterator<node>* getNodes() const;
72  Iterator<node>* getInNodes(const node )const;
73  Iterator<node>* getOutNodes(const node )const;
74  Iterator<node>* getInOutNodes(const node )const;
75  Iterator<edge>* getEdges()const;
76  Iterator<edge>* getInEdges(const node )const;
77  Iterator<edge>* getOutEdges(const node )const;
78  Iterator<edge>* getInOutEdges(const node )const;
79  std::vector<edge> getEdges(const node source, const node target,
80  bool directed = true) const;
81  bool getEdges(const node source, const node target, bool directed,
82  std::vector<edge>& edges) const {
83  return storage.getEdges(source, target, directed, edges);
84  }
85  // to ensure that loops appear only once
86  void getInOutEdges(const node, std::vector<edge>& edges,
87  bool loopsOnlyOnce = false)const;
88  //========================================================================
89  unsigned int deg(const node ) const;
90  unsigned int indeg(const node) const;
91  unsigned int outdeg(const node) const;
92  //========================================================================
93  virtual node source(const edge) const;
94  virtual node target(const edge) const;
95  virtual node opposite(const edge, const node n) const;
96  virtual const std::pair<node, node>& ends(const edge e) const;
97  virtual void setEnds(const edge, const node, const node);
98  virtual void reverse(const edge);
99  //=======================================================================
100  unsigned int numberOfEdges()const;
101  unsigned int numberOfNodes()const;
102  //=======================================================================
103  // updates management
104  virtual void push(bool unpopAllowed = true,
105  std::vector<PropertyInterface*>* propertiesToPreserveOnPop= NULL);
106  virtual void pop(bool unpopAllowed = true);
107  virtual void unpop();
108  virtual bool canPop();
109  virtual bool canUnpop();
110  virtual bool canPopThenUnpop();
111 
112  // observer interface
113  void treatEvents(const std::vector<Event> &);
114 
115  // for subgraph id management
116  unsigned int getSubGraphId(unsigned int id);
117  void freeSubGraphId(unsigned int id);
118 
119  // to improve memory allocation
120  // attempt to reserve enough space to store nodes/edges
121  virtual void reserveNodes(unsigned int nbNodes);
122  virtual void reserveEdges(unsigned int nbEdges);
123 
124 protected:
125  // designed to reassign an id to a previously deleted elt
126  // used by GraphUpdatesRecorder
127  virtual node restoreNode(node);
128  virtual void restoreNodes(const std::vector<node>&);
129  virtual edge restoreEdge(edge, node source, node target);
130  virtual void restoreEdges(const std::vector<edge>& edges,
131  const std::vector<std::pair<node, node> >& ends);
132  // designed to only update own structures
133  // used by GraphUpdatesRecorder
134  virtual void removeNode(const node);
135  virtual void removeEdge(const edge);
136  // used by PropertyManager
137  virtual bool canDeleteProperty(Graph* g, PropertyInterface *prop);
138 
139 private :
140  GraphStorage storage;
141  IdManager graphIds;
142  std::list<GraphUpdatesRecorder*> previousRecorders;
143  std::list<Graph *> observedGraphs;
144  std::list<PropertyInterface*> observedProps;
145  std::list<GraphUpdatesRecorder*> recorders;
146 
147  void restoreAdj(node, std::vector<edge>&);
148  void observeUpdates(Graph*);
149  void unobserveUpdates();
150  void delPreviousRecorders();
151 };
152 
153 }
154 #endif
155 
156 #endif
157 ///@endcond
The edge struct represents an edge in a Graph object.
Definition: Edge.h:39
The node struct represents a node in a Graph object.
Definition: Node.h:39