diff --git a/libgraphtheory/editorplugins/transformedges/transformedgeswidget.cpp b/libgraphtheory/editorplugins/transformedges/transformedgeswidget.cpp index 9e7619b9..7a850547 100644 --- a/libgraphtheory/editorplugins/transformedges/transformedgeswidget.cpp +++ b/libgraphtheory/editorplugins/transformedges/transformedgeswidget.cpp @@ -1,226 +1,238 @@ /* * Copyright 2011-2014 Andreas Cord-Landwehr * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) version 3, or any * later version accepted by the membership of KDE e.V. (or its * successor approved by the membership of KDE e.V.), which shall * act as a proxy defined in Section 6 of version 3 of the license. * * This library 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 * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library. If not, see . */ #include "transformedgeswidget.h" #include "typenames.h" #include "graphdocument.h" #include "edge.h" #include "modifiers/topology.h" #include #include #include #include using namespace GraphTheory; TransformEdgesWidget::TransformEdgesWidget(GraphDocumentPtr document, QWidget *parent) : QDialog(parent) , m_document(document) { setWindowTitle(i18nc("@title:window", "Transform Edges")); QVBoxLayout *mainLayout = new QVBoxLayout(this); setLayout(mainLayout); QWidget *widget = new QWidget(this); ui = new Ui::TransformEdgesWidget; ui->setupUi(widget); mainLayout->addWidget(widget); connect(ui->buttons, &QDialogButtonBox::accepted, this, &TransformEdgesWidget::accept); connect(ui->buttons, &QDialogButtonBox::rejected, this, &TransformEdgesWidget::reject); connect(this, &QDialog::accepted, this, &TransformEdgesWidget::transform); } TransformEdgesWidget::~TransformEdgesWidget() { delete ui; } void TransformEdgesWidget::transform() { if (ui->radioButtonMakeComplete->isChecked()) { makeComplete(); } if (ui->radioButtonEraseEdges->isChecked()) { removeAllEdges(); } if (ui->radioButtonReverseEdges->isChecked()) { reverseAllEdges(); } if (ui->radioButtonMakeSpanningtree->isChecked()) { makeSpanningTree(); } + if (ui->radioButtonEraseSelfEdges->isChecked()) { + removeAllSelfEdges(); + } } void TransformEdgesWidget::makeComplete() { //TODO only default edge type considered foreach(EdgePtr e, m_document->edges()) { e->destroy(); } for (int i = 0; i < m_document->nodes().size() - 1; ++i) { for (int j = i + 1; j < m_document->nodes().size(); ++j) { Edge::create(m_document->nodes().at(i), m_document->nodes().at(j)); if (m_document->edgeTypes().first()->direction() == EdgeType::Unidirectional) { Edge::create(m_document->nodes().at(j), m_document->nodes().at(i)); } } } } void TransformEdgesWidget::removeAllEdges() { //TODO only default edge type considered foreach(EdgePtr e, m_document->edges()) { e->destroy(); } } void TransformEdgesWidget::reverseAllEdges() { foreach (EdgeTypePtr type , m_document->edgeTypes()) { if (type->direction() == EdgeType::Bidirectional) { continue; } QList< QPair< NodePtr, NodePtr > > newEdges; foreach(EdgePtr e, m_document->edges(type)) { newEdges << QPair< NodePtr, NodePtr >(e->to(), e->from()); e->destroy(); } for (int i = 0; i < newEdges.count(); ++i) { EdgePtr edge = Edge::create(newEdges[i].first, newEdges[i].second); edge->setType(type); } } } qreal TransformEdgesWidget::makeSpanningTree() { NodeList nodes = m_document->nodes(); int n = nodes.size(); // the resulting spanning tree (MST) QList< QPair > MST; /* * distance[i] denotes the distance between node i and the minimum spanning * tree; initially this distance is infinity. Note that if i is already element * in MST distance[i] is only a temporary variable and its value is undefined. */ QMap distance; for (int i = 0; i < nodes.size(); i++) { distance[i] = std::numeric_limits::max(); } /* * Indicator variable that is true if node is in tree, false otherwise. * Initially all nodes are marked to be not in MST. */ QMap inTree; for (int i = 0; i < nodes.size(); i++) { inTree[i] = false; } /* weight[i][j] denotes distance between nodes i and j. If no * path is present between i and j in the previous tree the weight * must be set to 0. */ QMap< QPair, qreal> weight; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) weight[QPair(i, j)] = 0; EdgeList out; out = nodes[i]->edges(); for (int k = 0; k < out.size(); k++) { if (out[k]->to() == nodes[j]) { if (!out[k]->property("value").toString().isEmpty()) weight[QPair(i, j)] = out[k]->property("value").toDouble(); else weight[QPair(i, j)] = 1; } } } } /* * successor[i] denotes the index of the node, to which i must be * linked to in order to get distance distance[i] */ QMap< int, int> successor; // start with first graph node inTree[0] = true; // update distances for (int i = 0; i < n; ++i) { if ((weight[QPair(0, i)] != 0) && (distance[i] > weight[QPair(0, i)])) { distance[i] = weight[QPair(0, i)] ; successor[i] = 0; } } qreal total = 0; for (int treeSize = 1; treeSize < n; treeSize++) { // Find node with the smallest distance to the tree int min = -1; for (int i = 0; i < n; ++i) { if (inTree[i] == false) { if ((min == -1) || (distance[min] > distance[i])) { min = i; } } } // add node to tree MST << QPair(successor[min], min); inTree[min] = 1; total += distance[min]; // update distances for (int i = 0; i < n; ++i) { if ((weight[QPair(min, i)] != 0) && (distance[i] > weight[QPair(min, i)])) { distance[i] = weight[QPair(min, i)]; successor[i] = min; } } } removeAllEdges(); // refill with MST edges for (int i = 0; i < MST.size(); i++) { EdgePtr edge = Edge::create(nodes[MST[i].first], nodes[MST[i].second]); if (weight[QPair(MST[i].first, MST[i].second)] != 1) { QString value; value.setNum(weight[QPair(MST[i].first, MST[i].second)]); edge->setDynamicProperty("value", value); } } return total; } + +void TransformEdgesWidget::removeAllSelfEdges() +{ + foreach(EdgePtr e, m_document->edges()) { + if (e->to() == e->from()) { + e->destroy(); + } + } +} diff --git a/libgraphtheory/editorplugins/transformedges/transformedgeswidget.h b/libgraphtheory/editorplugins/transformedges/transformedgeswidget.h index 4575c8b2..7a0cfe51 100644 --- a/libgraphtheory/editorplugins/transformedges/transformedgeswidget.h +++ b/libgraphtheory/editorplugins/transformedges/transformedgeswidget.h @@ -1,72 +1,77 @@ /* * Copyright 2011-2014 Andreas Cord-Landwehr * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) version 3, or any * later version accepted by the membership of KDE e.V. (or its * successor approved by the membership of KDE e.V.), which shall * act as a proxy defined in Section 6 of version 3 of the license. * * This library 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 * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library. If not, see . */ #ifndef TRANSFORMEDGESWIDGET_H #define TRANSFORMEDGESWIDGET_H #include "ui_transformedgeswidget.h" #include "typenames.h" #include namespace GraphTheory { class TransformEdgesWidget : public QDialog { Q_OBJECT public: explicit TransformEdgesWidget(GraphDocumentPtr document, QWidget *parent = 0); ~TransformEdgesWidget(); public Q_SLOTS: void transform(); private: /** * Create edges between all nodes. */ void makeComplete(); /** * Remove all edges. */ void removeAllEdges(); /** * Reverse all existing edges. */ void reverseAllEdges(); /** * Transform given graph to a spanning tree by executing Prim's minimum spanning tree (MST) * algorithm. All edges are assumed to have weight 1 if no weights are given. Otherwise, * with given weights the specified values are used. * * \return total weight of MST */ qreal makeSpanningTree(); + /** + * Remove all self-edges. + */ + void removeAllSelfEdges(); + GraphDocumentPtr m_document; Ui::TransformEdgesWidget *ui; }; } #endif diff --git a/libgraphtheory/editorplugins/transformedges/transformedgeswidget.ui b/libgraphtheory/editorplugins/transformedges/transformedgeswidget.ui index 6d39299a..8b996323 100644 --- a/libgraphtheory/editorplugins/transformedges/transformedgeswidget.ui +++ b/libgraphtheory/editorplugins/transformedges/transformedgeswidget.ui @@ -1,79 +1,86 @@ TransformEdgesWidget 0 0 307 218 Transform Edges This option connects all nodes of the given graph. The new edges do not have any preset weights. Complete Graph true This option removes all edges from the given graph. Remove all Edges This option reverses all edges of a directed graph. Note that this does not apply to undirected graphs. Reverse all Edges <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0//EN" "http://www.w3.org/TR/REC-html40/strict.dtd"> <html><head><meta name="qrichtext" content="1" /><style type="text/css"> p, li { white-space: pre-wrap; } </style></head><body style=" font-family:'DejaVu Sans'; font-size:9pt; font-weight:400; font-style:normal;"> <p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px;">This option executes <span style=" font-style:italic;">Prim's Minimal Spanning Tree Algorithm</span> at the graph. All edges without given weights are assumed to have weights equals 1. Directed and undirected graphs are processed accordingly.</p></body></html> Spanning Tree Transformation + + + + Remove all Self Edges + + + QDialogButtonBox::Cancel|QDialogButtonBox::Ok