20 #include "ui_TransformEdgesWidget.h"
27 #include <QtGui/QDesktopWidget>
28 #include <QtGui/QGridLayout>
29 #include <QtGui/QLabel>
30 #include <QtGui/QLineEdit>
31 #include <QtGui/QPushButton>
32 #include <QtGui/QSpinBox>
33 #include <QtCore/QMap>
34 #include <QtCore/QPair>
36 #include <boost/graph/adjacency_list.hpp>
37 #include <boost/graph/topology.hpp>
40 #include <DataStructure.h>
41 #include <DocumentManager.h>
42 #include "../DataStructures/Graph/GraphStructure.h"
57 ui =
new Ui::TransformEdgesWidget;
59 setMainWidget(widget);
62 setCaption(i18nc(
"@title:window",
"Transform Edges"));
63 setButtons(KDialog::Cancel | KDialog::Ok);
64 KDialog::centerOnScreen(widget, -3);
78 ui->dataStructuresCombo->insertItems(0, dsNames);
84 DataStructurePtr graph;
85 QList< DataStructurePtr > dsList = DocumentManager::self().activeDocument()->dataStructures();
88 if (ui->dataStructuresCombo->count() == 0)
91 graph = dsList[ui->dataStructuresCombo->currentIndex()];
95 if (ui->radioButtonMakeComplete->isChecked())
97 if (ui->radioButtonEraseEdges->isChecked())
98 removeAllEdges(graph);
99 if (ui->radioButtonReverseEdges->isChecked())
100 reverseAllEdges(graph);
101 if (ui->radioButtonMakeSpanningtree->isChecked())
102 makeSpanningTree(graph);
106 void TransformEdgesWidget::makeComplete(DataStructurePtr graph)
108 bool directed = graph->document()->pointerType(0)->direction() == PointerType::Unidirectional;
111 foreach(PointerPtr e, graph->pointers(0)) {
115 int size_i = graph->dataList(0).size() - 1;
116 for (
int i = 0; i < size_i; ++i) {
117 for (
int e = i + 1; e < graph->dataList(0).size(); ++e) {
118 graph->createPointer(graph->dataList(0).at(i), graph->dataList(0).at(e), 0);
120 graph->createPointer(graph->dataList(0).at(e), graph->dataList(0).at(i), 0);
127 void TransformEdgesWidget::removeAllEdges(DataStructurePtr graph)
131 foreach(PointerPtr e, graph->pointers(0)) {
138 void TransformEdgesWidget::reverseAllEdges(DataStructurePtr graph)
140 foreach(
int typeId, graph->document()->pointerTypeList()) {
141 if (graph->document()->pointerType(typeId)->direction() == PointerType::Bidirectional) {
144 QList< QPair< DataPtr, DataPtr > > newPointers;
145 foreach(PointerPtr e, graph->pointers(typeId)) {
146 newPointers << QPair< DataPtr, DataPtr >(e->to(), e->from());
150 for (
int i = 0; i < newPointers.count(); i++) {
151 graph->createPointer(newPointers[i].first, newPointers[i].second, typeId);
157 qreal TransformEdgesWidget::makeSpanningTree(DataStructurePtr graph)
159 boost::shared_ptr<GraphStructure> graphDS = boost::static_pointer_cast<GraphStructure>(graph);
163 QList< DataPtr > vertices = graphDS->dataList(0);
164 int n = vertices.size();
169 QList< QPair<int, int> > MST;
176 QMap<int, qreal> distance;
177 for (
int i = 0; i < vertices.size(); i++) {
178 distance[i] = std::numeric_limits<unsigned int>::max();
185 QMap<int, bool> inTree;
186 for (
int i = 0; i < vertices.size(); i++) {
194 QMap< QPair<int, int>, qreal> weight;
196 for (
int i = 0; i < n; i++) {
197 for (
int j = 0; j < n; j++) {
198 if (i == j) weight[QPair<int, int>(i, j)] = 0;
201 out = vertices[i]->pointerList();
203 for (
int k = 0; k < out.size(); k++) {
204 if (out[k]->to() == vertices[j]) {
205 if (!out[k]->property(
"value").toString().isEmpty())
206 weight[QPair<int, int>(i, j)] = out[k]->property(
"value").toDouble();
208 weight[QPair<int, int>(i, j)] = 1;
219 QMap< int, int> successor;
225 for (
int i = 0; i < n; ++i) {
226 if ((weight[QPair<int, int>(0, i)] != 0) && (distance[i] > weight[QPair<int, int>(0, i)])) {
227 distance[i] = weight[QPair<int, int>(0, i)] ;
233 for (
int treeSize = 1; treeSize < n; treeSize++) {
236 for (
int i = 0; i < n; ++i) {
237 if (inTree[i] ==
false) {
238 if ((min == -1) || (distance[min] > distance[i])) {
245 MST << QPair<int, int>(successor[min], min);
247 total += distance[min];
250 for (
int i = 0; i < n; ++i) {
251 if ((weight[QPair<int, int>(min, i)] != 0) && (distance[i] > weight[QPair<int, int>(min, i)])) {
252 distance[i] = weight[QPair<int, int>(min, i)];
259 removeAllEdges(graph);
262 for (
int i = 0; i < MST.size(); i++) {
263 PointerPtr ptr = graph->createPointer(vertices[MST[i].first], vertices[MST[i].second], 0);
265 if (weight[QPair<int, int>(MST[i].first, MST[i].second)] != 1) {
267 s.setNum(weight[QPair<int, int>(MST[i].first, MST[i].second)]);
268 ptr->setProperty(
"value", s);