1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
|
/*
This file is part of Rocs.
Copyright 2011 Tomaz Canabrava <tomaz.canabrava@gmail.com>
Copyright 2011 Wagner Reck <wagner.reck@gmail.com>
Copyright 2011-2012 Andreas Cord-Landwehr <cola@uni-paderborn.de>
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of
the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef GRAPHSTRUCTURE_H
#define GRAPHSTRUCTURE_H
#include "rocs_graphstructure_export.h"
#include "DataStructure.h"
namespace Rocs
{
class ROCS_GRAPHSTRUCTURE_EXPORT GraphStructure : public DataStructure
{
Q_OBJECT
Q_PROPERTY(QString name READ name WRITE setName)
public:
typedef enum {
Graph,
Multigraph
} GRAPH_TYPE;
//to avoid hide some methods
using DataStructure::remove;
using DataStructure::createPointer;
using DataStructure::createData;
static DataStructurePtr create(Document *parent);
static DataStructurePtr create(DataStructurePtr other, Document *parent);
explicit GraphStructure(Document* parent = 0);
~GraphStructure();
void importStructure(DataStructurePtr other);
/**
* Internal method to create new graph edge.
* Use \see Pointer::create(...) for creating new edges.
* \param from is the origin of the new edge
* \param to is the target of the new edge
* \param pointerType is the type of this edge, defaults to 0
* \return the created edge as PointerPtr
*/
PointerPtr createPointer(DataPtr from, DataPtr to, int pointerType);
/**
* Internal method to create new graph node.
* Use \see Data::create(...) for creating new nodes.
* \param name is the name of the node
* \param dataType is the type of this node, defaults to 0
* \return the created node as DataPtr
*/
DataPtr createData(const QString& name, int dataType);
/**
* Returns type of the graph given by enum \see GRAPH_TYPE.
* \return graph type
*/
GRAPH_TYPE graphType() const;
bool multigraph() const;
/**
* Gives a map with plugin specific properties of the data structure.
* Implementation of virtual method \see DataStructure::pluginProperties()
* \return map keys are property names, values are property values.
*/
QMap<QString, QString> pluginProperties() const;
/**
* Set plugin specific properties of data structure.
* \param identifier is the unique identifier for this property
* \param value is the to be set value for the property
*/
void setPluginProperty(const QString& identifier, const QString& property);
/**
* Computes the Dijkstra's shortest path algorithm to compute
* all shortest path distances from \p from. Note: this shortest path
* algorithm works only for graphs with all edges values non-negative.
* For undirected graphs reverse edges are add automatically.
* The algorithm has time complexity O(V log V + E).
*
* \param from the node from which the computation starts
* \return list is map with keys = target elements, values = path to target
*/
QMap<DataPtr,PointerList> dijkstraShortestPaths(DataPtr from);
/**
* Returns a list of all nodes of the graph.
* \return array containing the nodes
*/
Q_INVOKABLE QScriptValue nodes();
/**
* Returns a list of all nodes of given \p type in the graph.
* \param type is the overlay for the to created pointer
* \return array containing the nodes
*/
Q_INVOKABLE QScriptValue nodes(int type);
/**
* Returns a list of all edges of the graph.
* \return array containing the edges
*/
Q_INVOKABLE QScriptValue edges();
/**
* Returns a list of all edges of given \p type in the graph.
* \param type is the overlay for the to created pointer
* \return array containing the edges
*/
Q_INVOKABLE QScriptValue edges(int type);
/**
* Creates a new data element and return it. If the specified data type is not registered,
* no data element is created.
* \param type is the data type of the created node
* \return script value for the new node
*/
Q_INVOKABLE QScriptValue createNode(int type);
/**
* Creates a new data element and return it.
* \return script value for the new node
*/
Q_INVOKABLE QScriptValue createNode();
/**
* Creates a new edge edge from \param fromRaw to \param toRaw
* of pointer type \param type. If the specified pointer type does not exist, no pointer
* is created.
* \param fromRaw is origin of pointer
* \param toRaw is target of pointer
* \param overlay is the overlay for the to created pointer
* \return script value for the new pointer
*/
Q_INVOKABLE QScriptValue createEdge(Data* fromRaw, Data* toRaw, int type);
/**
* Creates a new edge from \param fromRaw to \param toRaw.
* \param fromRaw is origin of pointer
* \param toRaw is target of pointer
* \return script value for the new pointer
*/
Q_INVOKABLE QScriptValue createEdge(Data* fromRaw, Data* toRaw);
public slots:
/**
* Setter for graph type. No conversations are performed.
* \param type as specified by enum GRAPH_TYPE
* \return void
*/
void setGraphType(int type);
/**
* Returns a list of all nodes of the graph.
* \return array containing the nodes
* \deprecated
*/
QScriptValue list_nodes();
/**
* Returns a list of all nodes of given \p type in the graph.
* \param type is the overlay for the to created pointer
* \return array containing the nodes
* \deprecated
*/
QScriptValue list_nodes(int type);
/**
* Returns a list of all edges of the graph.
* \return array containing the edges
* \deprecated
*/
QScriptValue list_edges();
/**
* Returns a list of all edges of given \p type in the graph.
* \param type is the overlay for the to created pointer
* \return array containing the edges
* \deprecated
*/
QScriptValue list_edges(int type);
/**
* Gives array of edges of specified overlay. If overlay
* does not exist an empty array is returned.
* \param overlay integer that identifies the overlay
* \return QScriptValue array
* \deprecated
*/
QScriptValue overlay_edges(int overlay);
/**
* Creates a new node with specified \param name.
* \param name of the new node
* \return script value for the new node
* \deprecated
*/
QScriptValue add_node(const QString& name);
/**
* Creates a new overlay edge from \param fromRaw to \param toRaw
* at overlay \param overlay. If the overlay does not exist no pointer
* is created.
* \param fromRaw is origin of pointer
* \param toRaw is target of pointer
* \param overlay is the overlay for the to created pointer
* \return script value for the new pointer
* \deprecated
*/
QScriptValue add_overlay_edge(Data* fromRaw, Data* toRaw, int overlay);
/**
* Creates a new edge from \param fromRaw to \param toRaw.
* \param fromRaw is origin of pointer
* \param toRaw is target of pointer
* \return script value for the new pointer
* \deprecated
*/
QScriptValue add_edge(Data* fromRaw, Data* toRaw);
/**
* Computes the Dijkstra's shortest path algorithm to compute
* the shortes path from \param from to \param to. Note: this shortest path
* algorithm works only for graphs with all edges values non-negative.
* For undirected graphs reverse edges are add automatically.
* The algorithm has time complexity O(V log V + E).
*
* \param from the node from which the computation starts
* \param to the node to which the shortest path shall be computed
* \return the edge set of the shortest path
*/
QScriptValue dijkstra_shortest_path(Data* fromRaw, Data* toRaw);
/**
* Computes the Dijkstra's shortest path algorithm to compute
* all shortest path distances from \p from. If edge has value 0, the edge value
* is set to 1. Infinity is returned when there is no path
* between \p from and another node in the graph. Note: this shortest path
* algorithm works only for graphs with all edges values non-negative. For
* undirected graphs reverse edges are added automatically.
* The algorithm has time complexity O(V log V + E).
*
* \param from the node from which the computation starts
* \return the edge set of the shortest path
*/
QScriptValue distances(Data* fromRaw);
private:
GraphStructure::GRAPH_TYPE _type;
};
}
#endif // GRAPHSTRUCTURE_H
|