TransformEdgesWidget.cpp

Go to the documentation of this file.

/*
    This file is part of Rocs.
    Copyright (C) 2011 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/>.
*/

#include "TransformEdgesWidget.h"
#include "ui_TransformEdgesWidget.h"

#include <limits.h>
#include <KLocale>
#include <KDialog>
#include <KComboBox>

#include <QtGui/QDesktopWidget>
#include <QtGui/QGridLayout>
#include <QtGui/QLabel>
#include <QtGui/QLineEdit>
#include <QtGui/QPushButton>
#include <QtGui/QSpinBox>
#include <QtCore/QMap>
#include <QtCore/QPair>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topology.hpp>

#include <Document.h>
#include <DataStructure.h>
#include <DocumentManager.h>
#include "../DataStructures/Graph/GraphStructure.h"
#include <Pointer.h>
#include <Data.h>


using namespace Rocs;

class QPushButton;

TransformEdgesWidget::TransformEdgesWidget(Document* graphDoc, QWidget* parent)
    :   KDialog(parent)
{
    graphDoc_ = graphDoc;

    QWidget *widget = new QWidget(this);
    ui = new Ui::TransformEdgesWidget;
    ui->setupUi(widget);
    setMainWidget(widget);

    // other KDialog options
    setCaption(i18nc("@title:window", "Transform Edges"));
    setButtons(KDialog::Cancel | KDialog::Ok);
    KDialog::centerOnScreen(widget, -3);

    connect(this, SIGNAL(okClicked()), this, SLOT(executeTransform()));
}


TransformEdgesWidget::~TransformEdgesWidget()
{
    delete ui;
}


void TransformEdgesWidget::addDataStructures(QStringList dsNames)
{
    ui->dataStructuresCombo->insertItems(0, dsNames);
}


void TransformEdgesWidget::executeTransform()
{
    DataStructurePtr graph;
    QList< DataStructurePtr > dsList = DocumentManager::self().activeDocument()->dataStructures();

    // no graph datastructures given at document
    if (ui->dataStructuresCombo->count() == 0)
        return;

    graph = dsList[ui->dataStructuresCombo->currentIndex()];
    if (!graph)
        return;

    if (ui->radioButtonMakeComplete->isChecked())
        makeComplete(graph);
    if (ui->radioButtonEraseEdges->isChecked())
        removeAllEdges(graph);
    if (ui->radioButtonReverseEdges->isChecked())
        reverseAllEdges(graph);
    if (ui->radioButtonMakeSpanningtree->isChecked())
        makeSpanningTree(graph);
}


void TransformEdgesWidget::makeComplete(DataStructurePtr graph)
{
    bool directed = graph->document()->pointerType(0)->direction() == PointerType::Unidirectional;

    //FIXME only default pointer type considered
    foreach(PointerPtr e, graph->pointers(0)) {
        e->remove();
    }

    int size_i = graph->dataList(0).size() - 1;
    for (int i = 0; i < size_i; ++i) {
        for (int e = i + 1; e < graph->dataList(0).size(); ++e) {
            graph->createPointer(graph->dataList(0).at(i), graph->dataList(0).at(e), 0);
            if (directed) {
                graph->createPointer(graph->dataList(0).at(e), graph->dataList(0).at(i), 0);
            }
        }
    }
}


void TransformEdgesWidget::removeAllEdges(DataStructurePtr graph)
{
    if (graph) {
        //FIXME only default pointer type considered
        foreach(PointerPtr e, graph->pointers(0)) {
            e->remove();
        }
    }
}


void TransformEdgesWidget::reverseAllEdges(DataStructurePtr graph)
{
    foreach(int typeId, graph->document()->pointerTypeList()) {
        if (graph->document()->pointerType(typeId)->direction() == PointerType::Bidirectional) {
            continue;
        }
        QList< QPair< DataPtr, DataPtr > > newPointers;
        foreach(PointerPtr e, graph->pointers(typeId)) {
            newPointers << QPair< DataPtr, DataPtr >(e->to(), e->from());
            e->remove();
        }

        for (int i = 0; i < newPointers.count(); i++) {
            graph->createPointer(newPointers[i].first, newPointers[i].second, typeId);
        }
    }
}


qreal TransformEdgesWidget::makeSpanningTree(DataStructurePtr graph)
{
    boost::shared_ptr<GraphStructure>  graphDS = boost::static_pointer_cast<GraphStructure>(graph);
    if (!graphDS)
        return 0;

    QList< DataPtr > vertices = graphDS->dataList(0);
    int n = vertices.size();

    /*
     * the resulting spanning tree (MST)
     */
    QList< QPair<int, int> > 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<int, qreal> distance;
    for (int i = 0; i < vertices.size(); i++) {
        distance[i] = std::numeric_limits<unsigned int>::max();
    }

    /*
     * Indicator variable that is true if node is in tree, false otherwise.
     * Initially all nodes are marked to be not in MST.
     */
    QMap<int, bool> inTree;
    for (int i = 0; i < vertices.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<int, int>, qreal> weight;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j)   weight[QPair<int, int>(i, j)] = 0;

            PointerList out;
            out = vertices[i]->pointerList();

            for (int k = 0; k < out.size(); k++) {
                if (out[k]->to() == vertices[j]) {
                    if (!out[k]->property("value").toString().isEmpty())
                        weight[QPair<int, int>(i, j)] = out[k]->property("value").toDouble();
                    else
                        weight[QPair<int, int>(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<int, int>(0, i)] != 0) && (distance[i] > weight[QPair<int, int>(0, i)])) {
            distance[i] = weight[QPair<int, int>(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<int, int>(successor[min], min);
        inTree[min] = 1;
        total += distance[min];

        // update distances
        for (int i = 0; i < n; ++i) {
            if ((weight[QPair<int, int>(min, i)]  != 0) && (distance[i] > weight[QPair<int, int>(min, i)])) {
                distance[i] = weight[QPair<int, int>(min, i)];
                successor[i] = min;
            }
        }
    }

    // erase all graph edges
    removeAllEdges(graph);

    // refill with MST edges
    for (int i = 0; i < MST.size(); i++) {
        PointerPtr ptr = graph->createPointer(vertices[MST[i].first], vertices[MST[i].second], 0);

        if (weight[QPair<int, int>(MST[i].first, MST[i].second)] != 1) {
            QString s;
            s.setNum(weight[QPair<int, int>(MST[i].first, MST[i].second)]);
            ptr->setProperty("value", s);
        }
    }

    return total;
}