[education/rocs] libgraphtheory: Graph layout plugin added, with a force based layout algorithm.
Caio Tonetti
null at kde.org
Tue Nov 24 18:27:08 GMT 2020
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 <cordlandwehr at kde.org>
+# Copyright 2020 Dilson Almeida Guimarães <dilsonguim at gmail.com>
#
# 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 <dilsonguim at gmail.com>
+ *
+ * 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 <cordlandwehr at kde.org>
+ * Copyright 2020 Dilson Almeida Guimarães <dilsonguim at gmail.com>
*
* 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 <dilsonguim at gmail.com>
+ *
+ * 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 <dilsonguim at gmail.com>
+
+ 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);
+
};
}
More information about the kde-doc-english
mailing list