Git commit 6aaea53ae61581032be653bff410792e9fa4981d by Caio Tonetti, on behalf of Dilson Guimarães. Committed on 20/11/2020 at 17:16. Pushed by ctonetti into branch 'master'.
Graph layout plugin added, with a force based layout algorithm. GUI: M +1 -0 libgraphtheory/editorplugins/CMakeLists.txt C +28 -4 libgraphtheory/editorplugins/graphlayout/CMakeLists.txt [from: libgraphtheory/editorplugins/CMakeLists.txt - 064% similarity] A +72 -0 libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.cpp [License: LGPL] C +28 -5 libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.h [from: libgraphtheory/logging.cpp - 061% similarity] A +16 -0 libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.json A +120 -0 libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.cpp [License: LGPL] A +75 -0 libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.h [License: GPL (v2+)] A +158 -0 libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.ui M +1 -1 libgraphtheory/logging.cpp M +299 -0 libgraphtheory/modifiers/topology.cpp M +30 -0 libgraphtheory/modifiers/topology.h https://invent.kde.org/education/rocs/commit/6aaea53ae61581032be653bff410792e9fa4981d diff --git a/libgraphtheory/editorplugins/CMakeLists.txt b/libgraphtheory/editorplugins/CMakeLists.txt index 4b099ace..eec480ba 100644 --- a/libgraphtheory/editorplugins/CMakeLists.txt +++ b/libgraphtheory/editorplugins/CMakeLists.txt @@ -24,3 +24,4 @@ ecm_optional_add_subdirectory(assignvalues) ecm_optional_add_subdirectory(generategraph) ecm_optional_add_subdirectory(transformedges) +ecm_optional_add_subdirectory(graphlayout) diff --git a/libgraphtheory/editorplugins/CMakeLists.txt b/libgraphtheory/editorplugins/graphlayout/CMakeLists.txt similarity index 64% copy from libgraphtheory/editorplugins/CMakeLists.txt copy to libgraphtheory/editorplugins/graphlayout/CMakeLists.txt index 4b099ace..6499ac0c 100644 --- a/libgraphtheory/editorplugins/CMakeLists.txt +++ b/libgraphtheory/editorplugins/graphlayout/CMakeLists.txt @@ -1,4 +1,4 @@ -# Copyright 2012-2014 Andreas Cord-Landwehr <[email protected]> +# Copyright 2020 Dilson Almeida Guimarães <[email protected]> # # Redistribution and use in source and binary forms, with or without # modification, are permitted provided that the following conditions @@ -21,6 +21,30 @@ # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -ecm_optional_add_subdirectory(assignvalues) -ecm_optional_add_subdirectory(generategraph) -ecm_optional_add_subdirectory(transformedges) +# Boost requires exceptions for this plugin +kde_enable_exceptions() + +set(graphlayout_SRCS + graphlayoutplugin.cpp + graphlayoutwidget.cpp + ../../logging.cpp +) + +#boost requires exceptions +kde_source_files_enable_exceptions(graphlayoutplugin.cpp) + +ki18n_wrap_ui(graphlayout_SRCS graphlayoutwidget.ui) +add_library(graphlayoutplugin + MODULE + ${graphlayout_SRCS} +) + +target_link_libraries(graphlayoutplugin + PUBLIC + rocsgraphtheory + KF5::Completion +) + +ecm_optional_add_subdirectory(autotests) + +install(TARGETS graphlayoutplugin DESTINATION ${PLUGIN_INSTALL_DIR}/rocs/editorplugins) diff --git a/libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.cpp b/libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.cpp new file mode 100644 index 00000000..7f586f24 --- /dev/null +++ b/libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.cpp @@ -0,0 +1,72 @@ +/* + * Copyright 2020 Dilson Almeida Guimarães <[email protected]> + * + * 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 <https://www.gnu.org/licenses/>. + */ + +#include "graphlayoutplugin.h" +#include "graphlayoutwidget.h" +#include "typenames.h" +#include "graphdocument.h" +#include "logging_p.h" +#include <KPluginFactory> +#include <QDialog> + +using namespace GraphTheory; + +K_PLUGIN_FACTORY_WITH_JSON( EditorPluginFactory, + "graphlayoutplugin.json", + registerPlugin<GraphLayoutPlugin>();) + +class GraphTheory::GraphLayoutPluginPrivate +{ +public: + GraphLayoutPluginPrivate() + : m_dialog(0) + { + } + + ~GraphLayoutPluginPrivate() + { + m_dialog->deleteLater(); + } + QDialog *m_dialog; +}; + +GraphLayoutPlugin::GraphLayoutPlugin(QObject* parent, const QList<QVariant> & /* args*/) + : EditorPluginInterface("rocs_graphlayoutplugin", parent) + , d(new GraphLayoutPluginPrivate) +{ + +} + +GraphLayoutPlugin::~GraphLayoutPlugin() +{ + +} + +void GraphLayoutPlugin::showDialog(GraphDocumentPtr document) +{ + if (!document) { + qCCritical(GRAPHTHEORY_GENERAL) << "No valid graph document given, aborting."; + } + QPointer<GraphLayoutWidget> dialog = new GraphLayoutWidget(document); + dialog->exec(); + return; +} + +#include "graphlayoutplugin.moc" diff --git a/libgraphtheory/logging.cpp b/libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.h similarity index 61% copy from libgraphtheory/logging.cpp copy to libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.h index 2e5ae80d..ee502c53 100644 --- a/libgraphtheory/logging.cpp +++ b/libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.h @@ -1,5 +1,5 @@ /* - * Copyright 2015 Andreas Cord-Landwehr <[email protected]> + * Copyright 2020 Dilson Almeida Guimarães <[email protected]> * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -18,8 +18,31 @@ * License along with this library. If not, see <https://www.gnu.org/licenses/>. */ -#include "logging_p.h" +#ifndef GRAPHLAYOUTPLUGIN_H +#define GRAPHLAYOUTPLUGIN_H -Q_LOGGING_CATEGORY(GRAPHTHEORY_FILEFORMAT, "org.kde.rocs.graphtheory.fileformat", QtWarningMsg) -Q_LOGGING_CATEGORY(GRAPHTHEORY_GENERAL, "org.kde.rocs.graphtheory.general", QtWarningMsg) -Q_LOGGING_CATEGORY(GRAPHTHEORY_KERNEL, "org.kde.rocs.graphtheory.kernel", QtWarningMsg) +#include "editorplugins/editorplugininterface.h" + +class QObject; + +namespace GraphTheory +{ + +class GraphLayoutPluginPrivate; + +class GraphLayoutPlugin : public EditorPluginInterface +{ + Q_OBJECT + +public: + GraphLayoutPlugin(QObject* parent, const QList< QVariant >&); + virtual ~GraphLayoutPlugin(); + void showDialog(GraphDocumentPtr document) Q_DECL_OVERRIDE; + +private: + const QScopedPointer<GraphLayoutPluginPrivate> d; +}; + +} + +#endif diff --git a/libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.json b/libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.json new file mode 100644 index 00000000..2e08a7bc --- /dev/null +++ b/libgraphtheory/editorplugins/graphlayout/graphlayoutplugin.json @@ -0,0 +1,16 @@ +{ + "Encoding": "UTF-8", + "KPlugin": { + "Category": "Plugins", + "Description": "This generates graph layouts automatically.", + "Description[pt_BR]": "Isto gera disposições do grafo automaticamente. ", + "Id": "rocs_graphlayoutplugin", + "License": "GPL", + "Name": "Graph Layout", + "Name[pt_BR]": "Disposição do Grafo", + "ServiceTypes": [ + "rocs/editorplugins" + ], + "Version": "0.1" + } +} diff --git a/libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.cpp b/libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.cpp new file mode 100644 index 00000000..54d92ce6 --- /dev/null +++ b/libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.cpp @@ -0,0 +1,120 @@ +/* + * Copyright 2020 Dilson Almeida Guimarães <[email protected]> + * + * 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 <https://www.gnu.org/licenses/>. + */ + +#include "graphlayoutwidget.h" + +#include "typenames.h" +#include "graphdocument.h" +#include "edge.h" +#include "modifiers/topology.h" +#include "logging_p.h" + +#include <KLocalizedString> +#include <KComboBox> + +#include <QtMath> +#include <QSlider> +#include <QList> +#include <QButtonGroup> +#include <QMessageBox> + +using namespace GraphTheory; + + +GraphLayoutWidget::GraphLayoutWidget(GraphDocumentPtr document, QWidget *parent) + : QDialog(parent) + , m_document(document) + , m_seed(1) + , m_areaFactor(50) + , m_repellingForce(50) + , m_attractionForce(50) +{ + setWindowTitle(i18nc("@title:window", "Graph Layout")); + + QVBoxLayout *mainLayout = new QVBoxLayout(this); + setLayout(mainLayout); + + QWidget *widget = new QWidget(this); + ui = new Ui::GraphLayoutWidget; + ui->setupUi(widget); + mainLayout->addWidget(widget); + + connect(ui->mainButtons, &QDialogButtonBox::accepted, this, &QDialog::accept); + connect(ui->mainButtons, &QDialogButtonBox::rejected, this, &QDialog::reject); + + connect(this, &QDialog::accepted, this, &GraphLayoutWidget::layoutGraph); + connect(ui->areaFactorSlider, &QSlider::valueChanged, this, &GraphLayoutWidget::setAreaFactor); + connect(ui->repellingForceSlider, &QSlider::valueChanged, this, &GraphLayoutWidget::setRepellingForce); + connect(ui->attractionForceSlider, &QSlider::valueChanged, this, &GraphLayoutWidget::setAttractionForce); + + // default values + ui->areaFactorSlider->setValue(50); + ui->repellingForceSlider->setValue(50); + ui->attractionForceSlider->setValue(50); +} + + +void GraphLayoutWidget::setAreaFactor(int areaFactor) { + m_areaFactor = areaFactor; +} + +void GraphLayoutWidget::setRepellingForce(int repellingForce) { + m_repellingForce = repellingForce; +} + +void GraphLayoutWidget::setAttractionForce(int attractionForce) { + m_attractionForce = attractionForce; +} + + +void GraphLayoutWidget::setSeed(int seed) +{ + m_seed = seed; +} + +void GraphLayoutWidget::layoutGraph() +{ + + //Sliders values map to parameteres with a non-linear scale + const qreal areaFactor = qPow(10, qreal(m_areaFactor - 50) / 50); + const qreal repellingForce = qPow(10, qreal(m_repellingForce - 50) / 50); + const qreal attractionForce = qPow(10, qreal(m_attractionForce - 50) / 50); + + //Creates a small margin to make the layout look nicer. + const qreal margin = 5; + + //Radius of each node. This should be equal to radius used when rendering the graph. + const qreal nodeRadius = 10; + + + const bool randomizeInitialPositions = true; + const quint32 seed = m_seed; + + Topology::applyForceBasedLayout(m_document, nodeRadius, margin, areaFactor, repellingForce, + attractionForce, randomizeInitialPositions, seed); + + close(); + deleteLater(); +} + +GraphLayoutWidget::~GraphLayoutWidget() +{ + delete ui; +} diff --git a/libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.h b/libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.h new file mode 100644 index 00000000..2badd5d7 --- /dev/null +++ b/libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.h @@ -0,0 +1,75 @@ +/* + Copyright (C) 2020 Dilson Almeida Guimarães <[email protected]> + + 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 <https://www.gnu.org/licenses/>. +*/ + +#ifndef GRAPHLAYOUTWIDGET_H +#define GRAPHLAYOUTWIDGET_H + +#include "ui_graphlayoutwidget.h" +#include "typenames.h" +#include <QWidget> +#include <QDialog> + +namespace GraphTheory { + +class GraphLayoutWidget : public QDialog +{ + Q_OBJECT + + +public: + explicit GraphLayoutWidget(GraphDocumentPtr document, QWidget *parent = 0); + ~GraphLayoutWidget(); + +public slots: + /** + * Lay out the graph. + */ + void layoutGraph(); + + /** + * Updates the seed used for generating pseudo-random numbers. + */ + void setSeed(int seed); + + /** + * Updates the area factor parameter of the layout algorithm. + */ + void setAreaFactor(int areaFactor); + + /** + * Updates the repelling force parameter of the layout algorithm. + */ + void setRepellingForce(int repellingForce); + + /** + * Updates the attraction force parameter of the layout algorithm. + */ + void setAttractionForce(int attractionForce); + +private: + + GraphDocumentPtr m_document; + int m_seed; + int m_areaFactor; + int m_repellingForce; + int m_attractionForce; + + Ui::GraphLayoutWidget *ui; +}; +} + +#endif diff --git a/libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.ui b/libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.ui new file mode 100644 index 00000000..b8eecd0f --- /dev/null +++ b/libgraphtheory/editorplugins/graphlayout/graphlayoutwidget.ui @@ -0,0 +1,158 @@ +<?xml version="1.0" encoding="UTF-8"?> +<ui version="4.0"> + <class>GraphLayoutWidget</class> + <widget class="QWidget" name="GraphLayoutWidget"> + <property name="geometry"> + <rect> + <x>0</x> + <y>0</y> + <width>306</width> + <height>161</height> + </rect> + </property> + <property name="minimumSize"> + <size> + <width>306</width> + <height>161</height> + </size> + </property> + <property name="windowTitle"> + <string>Graph Layout</string> + </property> + <widget class="QDialogButtonBox" name="mainButtons"> + <property name="geometry"> + <rect> + <x>120</x> + <y>120</y> + <width>171</width> + <height>32</height> + </rect> + </property> + <property name="minimumSize"> + <size> + <width>171</width> + <height>32</height> + </size> + </property> + <property name="orientation"> + <enum>Qt::Horizontal</enum> + </property> + <property name="standardButtons"> + <set>QDialogButtonBox::Cancel|QDialogButtonBox::Ok</set> + </property> + </widget> + <widget class="QWidget" name="formLayoutWidget"> + <property name="geometry"> + <rect> + <x>10</x> + <y>10</y> + <width>281</width> + <height>91</height> + </rect> + </property> + <layout class="QFormLayout" name="formLayout"> + <property name="horizontalSpacing"> + <number>16</number> + </property> + <property name="verticalSpacing"> + <number>16</number> + </property> + <item row="0" column="0"> + <widget class="QLabel" name="areaFactorLabel"> + <property name="text"> + <string>Area factor:</string> + </property> + </widget> + </item> + <item row="0" column="1"> + <widget class="QSlider" name="areaFactorSlider"> + <property name="minimum"> + <number>1</number> + </property> + <property name="maximum"> + <number>100</number> + </property> + <property name="orientation"> + <enum>Qt::Horizontal</enum> + </property> + </widget> + </item> + <item row="1" column="0"> + <widget class="QLabel" name="repellingForceLabel"> + <property name="text"> + <string>Repelling force:</string> + </property> + </widget> + </item> + <item row="2" column="0"> + <widget class="QLabel" name="attractionForceLabel"> + <property name="text"> + <string>Attraction force:</string> + </property> + </widget> + </item> + <item row="1" column="1"> + <widget class="QSlider" name="repellingForceSlider"> + <property name="minimum"> + <number>1</number> + </property> + <property name="maximum"> + <number>100</number> + </property> + <property name="orientation"> + <enum>Qt::Horizontal</enum> + </property> + </widget> + </item> + <item row="2" column="1"> + <widget class="QSlider" name="attractionForceSlider"> + <property name="minimum"> + <number>1</number> + </property> + <property name="maximum"> + <number>100</number> + </property> + <property name="orientation"> + <enum>Qt::Horizontal</enum> + </property> + </widget> + </item> + </layout> + </widget> + </widget> + <resources/> + <connections> + <connection> + <sender>mainButtons</sender> + <signal>accepted()</signal> + <receiver>GraphLayoutWidget</receiver> + <slot>accept()</slot> + <hints> + <hint type="sourcelabel"> + <x>248</x> + <y>254</y> + </hint> + <hint type="destinationlabel"> + <x>157</x> + <y>274</y> + </hint> + </hints> + </connection> + <connection> + <sender>mainButtons</sender> + <signal>rejected()</signal> + <receiver>GraphLayoutWidget</receiver> + <slot>reject()</slot> + <hints> + <hint type="sourcelabel"> + <x>316</x> + <y>260</y> + </hint> + <hint type="destinationlabel"> + <x>286</x> + <y>274</y> + </hint> + </hints> + </connection> + </connections> +</ui> diff --git a/libgraphtheory/logging.cpp b/libgraphtheory/logging.cpp index 2e5ae80d..28a3de31 100644 --- a/libgraphtheory/logging.cpp +++ b/libgraphtheory/logging.cpp @@ -21,5 +21,5 @@ #include "logging_p.h" Q_LOGGING_CATEGORY(GRAPHTHEORY_FILEFORMAT, "org.kde.rocs.graphtheory.fileformat", QtWarningMsg) -Q_LOGGING_CATEGORY(GRAPHTHEORY_GENERAL, "org.kde.rocs.graphtheory.general", QtWarningMsg) +Q_LOGGING_CATEGORY(GRAPHTHEORY_GENERAL, "org.kde.rocs.graphtheory.general", QtDebugMsg) Q_LOGGING_CATEGORY(GRAPHTHEORY_KERNEL, "org.kde.rocs.graphtheory.kernel", QtWarningMsg) diff --git a/libgraphtheory/modifiers/topology.cpp b/libgraphtheory/modifiers/topology.cpp index 04869b21..a22a223d 100644 --- a/libgraphtheory/modifiers/topology.cpp +++ b/libgraphtheory/modifiers/topology.cpp @@ -26,6 +26,10 @@ #include <QList> #include <QPair> #include <QVector> +#include <QVector2D> +#include <QtMath> +#include <QPointF> +#include <QRandomGenerator> #include <boost/graph/fruchterman_reingold.hpp> #include <boost/graph/circle_layout.hpp> @@ -49,6 +53,14 @@ typedef boost::iterator_property_map < PositionVec::iterator, typedef boost::graph_traits<Graph>::vertex_descriptor Vertex; typedef QPair<int, int> BoostEdge; + +typedef QPair<int, int> RemappedEdge; +struct RemappedGraph { + int numberOfNodes; + QMap<NodePtr, int> nodeToIndexMap; + QVector<RemappedEdge> edges; +}; + // handle boost exceptions namespace boost { void throw_exception(std::exception const &e) { @@ -212,3 +224,290 @@ void Topology::undirectedGraphDefaultTopology(GraphDocumentPtr document) applyCircleAlignment(document->nodes(), 300); applyMinCutTreeAlignment(document->nodes()); } + +/** @brief Calculates the size of a square in which a number of circles fit well. + * + * Given the number of circles and their radius, heuristically computes the length of the side + * of a square in which all circles can easily be placed without intersecting each other. + * Use this to figure out how big a square should be contain the drawing of graph well. + * + * By easily, understand the following: + * Consider a square with side length computed by this method. An algorithm that places circles + * at random positions inside this square, with uniform probability, should have a high chance + * of getting no intersections between the circles. For 3 circles or more, this chance is higher + * than 60%. + * + */ +qreal squareSideRandomPlacementHeuristic(const qreal radius, const int numberOfCircles) +{ + //This formula was obtained by a mix of experimentation and calculations. + return qMax(4.26 * numberOfCircles - 3.5, 2.) * radius; +} + +QMap<NodePtr, int> mapNodesToIndexes(const NodeList& nodes) +{ + int nextIndex = 0; + QMap<NodePtr, int> nodeToIndexMap; + foreach(const NodePtr node, nodes) { + nodeToIndexMap[node] = nextIndex; + nextIndex++; + } + return nodeToIndexMap; +} + +QVector<RemappedEdge> getRemappedEdges(const EdgeList& edges, + const QMap<NodePtr, int>& nodeToIndexMap) +{ + QVector<RemappedEdge> remappedEdges; + foreach(const EdgePtr edge, edges) { + const int from = nodeToIndexMap[edge->from()]; + const int to = nodeToIndexMap[edge->to()]; + remappedEdges.push_back(RemappedEdge(from, to)); + } + return remappedEdges; +} + +RemappedGraph remapGraph(const GraphDocumentPtr document) { + RemappedGraph remappedGraph; + remappedGraph.numberOfNodes = document->nodes().size(); + remappedGraph.nodeToIndexMap = mapNodesToIndexes(document->nodes()); + remappedGraph.edges = getRemappedEdges(document->edges(), remappedGraph.nodeToIndexMap); + return remappedGraph; +} + +void moveNodes(const NodeList& nodes, const QMap<NodePtr, int>& nodeToIndexMap, + const QVector<QPointF>& positions) +{ + foreach(const NodePtr node, nodes) { + const int index = nodeToIndexMap[node]; + const QPointF& position = positions[index]; + node->setX(position.x()); + node->setY(position.y()); + } +} + +QVector<QPointF> getCurrentPositions(const NodeList& nodes, + const QMap<NodePtr, int>& nodeToIndexMap) +{ + QVector<QPointF> positions(nodes.size()); + foreach(const NodePtr node, nodes) { + const int index = nodeToIndexMap[node]; + positions[index] = QPointF(node->x(), node->y()); + } + return positions; +} + + +QVector2D randomDirection(QRandomGenerator& randomGenerator) { + const qreal angle = randomGenerator.bounded(2 * M_PI); + return QVector2D(qCos(angle), qSin(angle)); +} + +QPointF projectIntoRectangle(const QPointF& point, const qreal minX, const qreal maxX, + const qreal& minY, const qreal& maxY) +{ + const qreal x = qMin(qMax(point.x(), minX), maxX); + const qreal y = qMin(qMax(point.y(), minY), maxY); + return QPointF(x, y); +} + +/** + * Lays a graph out using an adaptation of the Fruchterman-Reingold algorithm. + * + * @param graph The graph to be laid out. + * @param areaFactor A positive constant that imprecisely indicates how spread the graph should be. + * @param repellingForce A constant that controls how strong is the repelling force between nodes. + * @param attractionForce A constant that controls how strong is the attraction force between nodes + * that are neighbours. + * @param minX is the minimum x-coordinate the center of a node can have. + * @param maxX is the maximum x-coordinate the center of a node can have. + * @param minY is the minimum y-coordinate the center of a node can have. + * @param maxY is the maximum y-coordinate the center of a node can have. + * @param nodeRadius is the radius of each node. + * @param initialTemperature is the temperature to start the simulation. + * @param numberOfIterations Number of iterations to be realized in the simulation. + * @param initialPositions The initial positions of the nodes. + * @param randomGenerator The random number generator engine to be used if necessary. + * + * @return The position of the nodes after the simulation. + */ +QVector<QPointF> forceBasedLayout(const RemappedGraph& graph, const qreal areaFactor, + const qreal repellingForce, const qreal attractionForce, + const qreal minX, const qreal maxX, const qreal minY, + const qreal maxY, const qreal nodeRadius, + const qreal initialTemperature, const int numberOfIterations, + const QVector<QPointF>& initialPositions, + QRandomGenerator& randomGenerator) +{ + Q_ASSERT(maxX > minX); + Q_ASSERT(maxY > minY); + Q_ASSERT(areaFactor > 0.); + Q_ASSERT(graph.numberOfNodes > 0); + + //TODO: Take care of disconnected graphs. + + //Constant used to calculate the forces acting on each node. + const qreal area = (maxX - minX) * (maxY - minY); + const qreal k = areaFactor * qSqrt(area / graph.numberOfNodes); + + QVector<QPointF> currentPositions = initialPositions; + QVector<QVector2D> nodeForce(graph.numberOfNodes); + for (int iteration = 0; iteration < numberOfIterations; iteration++) { + //Clear forces from the previous iteration. + nodeForce.fill(QVector2D()); + + //Calculates the repelling forces. + for (int i = 0; i < graph.numberOfNodes; i++) { + for (int j = i + 1; j < graph.numberOfNodes; j++) { + QVector2D direction(currentPositions[j] - currentPositions[i]); + const qreal distance = direction.length(); + + //Adaptation of the original Fruchterman-Reingold calculation to consider the + //radius of nodes, avoiding intersection between pairs of nodes. + //Using k insted of k * k in the force calculation seems to lead to better results. + const qreal correctedDistance = qMax(distance - 2 * nodeRadius, + 1. / graph.numberOfNodes); + const qreal force = repellingForce * k / correctedDistance; + + //If the distance is too small, pick a random direction to avoid the case in + //which two nodes have the same position. + if (distance < nodeRadius) { + direction = randomDirection(randomGenerator); + } else { + direction.normalize(); + } + + nodeForce[i] -= force * direction; + nodeForce[j] += force * direction; + } + } + + //Calculates the attraction forces. + for (const RemappedEdge& edge : graph.edges) { + const int i = edge.first; + const int j = edge.second; + QVector2D direction(currentPositions[j] - currentPositions[i]); + const qreal distance = direction.length(); + + //Do not use attraction forces between nodes that are already too close. + if (distance < 2 * nodeRadius) { + continue; + } + + direction.normalize(); + const qreal force = attractionForce * distance * distance / k; + + nodeForce[i] += force * direction; + nodeForce[j] -= force * direction; + } + + //Calculates the current temperature using a liner cooling schedule. + const qreal temperature = initialTemperature * (numberOfIterations - iteration) / + numberOfIterations; + + //Moves nodes, keeping their coordinates inside the allowed ranges. + for (int i = 0; i < graph.numberOfNodes; i++) { + const qreal displacement = qMin<qreal>(nodeForce[i].length(), temperature); + const QVector2D direction = nodeForce[i].normalized(); + const QPointF target(currentPositions[i].x() + displacement * direction.x(), + currentPositions[i].y() + displacement * direction.y()); + currentPositions[i] = projectIntoRectangle(target, minX, maxX, minY, maxY); + } + + } + + return currentPositions; +} + +QVector<QPointF> randomLayout(const RemappedGraph& graph, const qreal minX, const qreal maxX, + const qreal minY, const qreal maxY, QRandomGenerator& randomGenerator) +{ + Q_ASSERT(maxX > minX); + Q_ASSERT(maxY > minY); + QVector<QPointF> positions(graph.numberOfNodes); + for (int i = 0; i < graph.numberOfNodes; i++) { + positions[i].setX(randomGenerator.bounded(maxX - minX) + minX); + positions[i].setY(randomGenerator.bounded(maxY - minY) + minY); + } + return positions; +} + +void translateGraphToUpperLeftCorner(const qreal minX, const qreal maxX, const qreal minY, + const qreal maxY, QVector<QPointF>& positions) +{ + qreal xDisplacement = maxX - minX; + qreal yDisplacement = maxY - minY; + for (const QPointF& point : positions) { + xDisplacement = qMin(xDisplacement, point.x() - minX); + yDisplacement = qMin(yDisplacement, point.y() - minY); + } + + for (QPointF& point : positions) { + point.setX(point.x() - xDisplacement); + point.setY(point.y() - yDisplacement); + } +} + +void Topology::applyForceBasedLayout(GraphDocumentPtr document, const qreal nodeRadius, + const qreal margin, const qreal areaFactor, + const qreal repellingForce, const qreal attractionForce, + const bool randomizeInitialPositions, const quint32 seed) +{ + //There is nothing to do with an empty graph. + if (document->nodes().empty()) { + return; + } + + QRandomGenerator randomGenerator(seed); + + //Gets a new representation of the graph for efficiency purposes + RemappedGraph graph = remapGraph(document); + + //Computes the square in which the center of the nodes should be placed. + //This is done heuristically so that there is enough room to move nodes around easily. + //Because the heuristic used considers only circles, one extra circle is created for each edge. + //The reasoning is that graphs with more edges need more space to drawn nicely. + const int numberOfCircles = graph.numberOfNodes; + const qreal circleRadius = 2 * nodeRadius; + const qreal side = squareSideRandomPlacementHeuristic(circleRadius, numberOfCircles); + const qreal minX = margin + nodeRadius; + const qreal maxX = minX + side; + const qreal minY = margin + nodeRadius; + const qreal maxY = minY + side; + + //Computes the initial positions. + QVector<QPointF> initialPositions; + if (randomizeInitialPositions) { + initialPositions = randomLayout(graph, minX, maxX, minY,maxY, randomGenerator); + } else { + initialPositions = getCurrentPositions(document->nodes(), graph.nodeToIndexMap); + } + + + //In order to converge properly, it makes sense that the number of iterations increases as + //the number of nodes increases. For very small graphs, a minimum number of iterations + //should be realized so the algorithm has the chance to find a nice layout. + const int numberOfIterations = qMax(graph.numberOfNodes, 100); + + //The temperature indicates how far a node can be moved in a single iteration. + //Initially, this value should be big enough to enable every node to go anywhere. + //Here, this is set so that after freeIterations each node can be anywhere. + const int freeIterations = numberOfIterations / 10 + 1; + const qreal initialTemperature = 2. * qSqrt(2.) * side * numberOfIterations / freeIterations / + (2 * numberOfIterations - freeIterations + 1); + + //Computes the layout. + QVector<QPointF> positions = forceBasedLayout(graph, areaFactor, repellingForce, + attractionForce, minX, maxX, minY, maxY, + nodeRadius, initialTemperature, + numberOfIterations, initialPositions, + randomGenerator); + + + //The generated layout may have some unused space above the graph and to the left of the graph. + translateGraphToUpperLeftCorner(minX, maxX, minY, maxY, positions); + + + //Moves nodes to their final positions. + moveNodes(document->nodes(), graph.nodeToIndexMap, positions); +} diff --git a/libgraphtheory/modifiers/topology.h b/libgraphtheory/modifiers/topology.h index 02ee6db1..6c56cbe6 100644 --- a/libgraphtheory/modifiers/topology.h +++ b/libgraphtheory/modifiers/topology.h @@ -79,6 +79,36 @@ public: * I.e., no possible present coordinates are respected. */ static void undirectedGraphDefaultTopology(GraphDocumentPtr document); + + + /** + * Applies a force based graph layout algorithm to the graph. + * + * If @p randomizeInitialPositions is @c true, the current node positions are ignored. + * Otherwise, they are used as the initial layout. + * + * Using a value of 1 for the parameters @p areaFactor, @p repellingForce and @p attractionForce + * should give a reasonable results. + * + * The control given by the parameter @p areaFactor is not precise, meaning that doubling its + * value does not necessarily mean that the final layout will use an area twice as big. + * The greater @p areaFactor is, the more the nodes tend to spread. + * + * @param document The graph document to be laid out. + * @param nodeRadius The radius of the circles that are used to represent nodes. + * @param margin The size of the top and left margins. + * @param areaFactor A constant that imprecisely controls how much area the layout will take. + * @param repellingForce The magnitude of the repelling force between nodes. + * @param attractionForce The magnitude of the attraction force between neighbouring nodes. + * @param randomizeInitialPositions Indicates whether the algorithm should start from a + * random layout. + * @param seed Seed used for generating random numbers. + */ + static void applyForceBasedLayout(GraphDocumentPtr document, const qreal nodeRadius, + const qreal margin, const qreal areaFactor, + const qreal repellingForce, const qreal attractionForce, + const bool randomizeInitialPositions, const quint32 seed); + }; }
