diff --git a/libgraphtheory/editorplugins/generategraph/generategraphwidget.cpp b/libgraphtheory/editorplugins/generategraph/generategraphwidget.cpp index b0e16a9a..6732ce3c 100644 --- a/libgraphtheory/editorplugins/generategraph/generategraphwidget.cpp +++ b/libgraphtheory/editorplugins/generategraph/generategraphwidget.cpp @@ -1,588 +1,652 @@ -/* +/* * Copyright 2011-2014 Andreas Cord-Landwehr + * Copyright 2019 Caio Henrique Segawa Tonetti * * 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 "generategraphwidget.h" #include "typenames.h" #include "graphdocument.h" #include "edge.h" #include "modifiers/topology.h" #include "logging_p.h" #include #include #include #include #include #include #include +#include #include +#include #include #include #include #include #include #include #include #include #include using namespace GraphTheory; // typedefs used for the boost graph library typedef boost::adjacency_list < boost::listS, boost::vecS, boost::undirectedS, boost::property > Graph; typedef boost::rectangle_topology<> topology_type; typedef topology_type::point_type point_type; typedef std::vector PositionVec; typedef boost::iterator_property_map < PositionVec::iterator, boost::property_map::type > PositionMap; // handle boost exceptions namespace boost { void throw_exception(std::exception const &e) { qCCritical(GRAPHTHEORY_GENERAL) << "Exception:" << e.what(); } } GenerateGraphWidget::GenerateGraphWidget(GraphDocumentPtr document, QWidget *parent) : QDialog(parent) , m_document(document) , m_seed(1) { // setup default identifiers for the created graphs m_defaultIdentifiers.insert(MeshGraph, "MeshGraph"); m_defaultIdentifiers.insert(StarGraph, "StarGraph"); m_defaultIdentifiers.insert(CircleGraph, "CircleGraph"); m_defaultIdentifiers.insert(ErdosRenyiRandomGraph, "RandomGraph"); m_defaultIdentifiers.insert(RandomTree, "RandomTree"); + m_defaultIdentifiers.insert(RandomDag, "RandomDag"); m_defaultIdentifiers.insert(PathGraph, "PathGraph"); m_defaultIdentifiers.insert(CompleteGraph, "CompleteGraph"); m_defaultIdentifiers.insert(CompleteBipartiteGraph, "CompleteBipartite"); // set default graph m_graphGenerator = MeshGraph; setWindowTitle(i18nc("@title:window", "Generate Graph")); QVBoxLayout *mainLayout = new QVBoxLayout(this); setLayout(mainLayout); QWidget *widget = new QWidget(this); ui = new Ui::GenerateGraphWidget; ui->setupUi(widget); mainLayout->addWidget(widget); ui->buttonShowAdvanced->setIcon(QIcon::fromTheme("rocsadvancedsetup")); connect(ui->buttons, &QDialogButtonBox::accepted, this, &QDialog::accept); connect(ui->buttons, &QDialogButtonBox::rejected, this, &QDialog::reject); connect(this, &QDialog::accepted, this, &GenerateGraphWidget::generateGraph); connect(ui->comboGraphGenerator, static_cast(&QComboBox::currentIndexChanged), this, &GenerateGraphWidget::setGraphGenerator); connect(ui->nodeTypeSelector, static_cast(&QComboBox::currentIndexChanged), this, &GenerateGraphWidget::setNodeType); connect(ui->edgeTypeSelector, static_cast(&QComboBox::currentIndexChanged), this, &GenerateGraphWidget::setEdgeType); // set random seeds qint64 currentTime = QDateTime::currentMSecsSinceEpoch(); uint badRandomSeed = qHash(currentTime) % 99999; badRandomSeed = (badRandomSeed == 0) ? 1 : badRandomSeed; ui->randomGeneratorSeed->setValue(badRandomSeed); ui->GNPGeneratorSeed->setValue(badRandomSeed); ui->randomTreeGeneratorSeed->setValue(badRandomSeed); // set visibility for advanced options // TODO move to containers for easier handling ui->label_randomGeneratorSeed->setVisible(false); ui->randomGeneratorSeed->setVisible(false); ui->label_GNPGeneratorSeed->setVisible(false); ui->GNPGeneratorSeed->setVisible(false); ui->label_randomTreeGeneratorSeed->setVisible(false); ui->randomTreeGeneratorSeed->setVisible(false); for (int i = 0; i < document->edgeTypes().length(); ++i) { EdgeTypePtr type = document->edgeTypes().at(i); QString item = i18nc( "@item:inlistbox", "%1 (ID %2)", type->name(), i); ui->edgeTypeSelector->addItem(item, QVariant(i)); } ui->edgeTypeSelector->setCurrentIndex(0); for (int i = 0; i < document->nodeTypes().length(); ++i) { NodeTypePtr type = document->nodeTypes().at(i); QString item = i18nc( "@item:inlistbox", "%1 (ID %2)", type->name(), i); ui->nodeTypeSelector->addItem(item, QVariant(i)); } ui->nodeTypeSelector->setCurrentIndex(0); } void GenerateGraphWidget::setGraphGenerator(int index) { m_graphGenerator = GraphGenerator(index); if (m_defaultIdentifiers.contains(m_graphGenerator)) { ui->identifier->setText(m_defaultIdentifiers[m_graphGenerator]); } else { ui->identifier->setText("Graph"); } } void GenerateGraphWidget::setGraphIdentifier(const QString &identifier) { m_identifier = identifier; } void GenerateGraphWidget::setNodeType(int type) { if (type >= m_document->nodeTypes().length()) { qCWarning(GRAPHTHEORY_GENERAL) << "Node type " << type << " does not exist: aborting"; return; } m_nodeType = m_document->nodeTypes().at(type); } void GenerateGraphWidget::setEdgeType(int type) { if (type >= m_document->edgeTypes().length()) { qCWarning(GRAPHTHEORY_GENERAL) << "Edge type " << type << " does not exist: aborting"; return; } m_edgeType = m_document->edgeTypes().at(type); } void GenerateGraphWidget::setSeed(int seed) { m_seed = seed; } void GenerateGraphWidget::generateGraph() { setGraphIdentifier(ui->identifier->text()); switch (m_graphGenerator) { case MeshGraph: generateMesh(ui->meshRows->value(), ui->meshColumns->value()); break; case CircleGraph: generateCircle(ui->circleNodes->value()); break; case StarGraph: generateStar(ui->starSatelliteNodes->value()); break; case RandomEdgeGraph: setSeed(ui->randomGeneratorSeed->value()); generateRandomGraph( ui->randomNodes->value(), ui->randomEdges->value(), ui->randomAllowSelfedges->isTristate() ); break; case ErdosRenyiRandomGraph: setSeed(ui->randomGeneratorSeed->value()); generateErdosRenyiRandomGraph( ui->GNPNodes->value(), ui->GNPEdgeProbability->value(), ui->GNPAllowSelfedges->isTristate() ); break; case RandomTree: setSeed(ui->randomTreeGeneratorSeed->value()); generateRandomTreeGraph( ui->randomTreeNodes->value() ); break; + case RandomDag: + setSeed(ui->randomGeneratorSeed->value()); + generateRandomDagGraph( + ui->randomDagNumberOfNodes->value(), + ui->randomDagEdgeProbability->value() + ); + break; case PathGraph: generatePathGraph( ui->pathNodes->value() ); break; case CompleteGraph: generateCompleteGraph( ui->completeNodes->value() ); + break; case CompleteBipartiteGraph: generateCompleteBipartiteGraph( ui->completeBipartiteNodesLeft->value(), ui->completeBipartiteNodesRight->value() ); default: break; } close(); deleteLater(); } GenerateGraphWidget::~GenerateGraphWidget() { delete ui; } QPointF GenerateGraphWidget::documentCenter() const { QPointF center = QPointF(0, 0); qreal xSum = 0; qreal ySum = 0; int number = m_document->nodes().length(); + foreach (NodePtr node, m_document->nodes()) { xSum += node->x(); ySum += node->y(); } + if (number > 0) { center.setX(xSum / number); center.setY(ySum / number); } return center; } void GenerateGraphWidget::generateMesh(int rows, int columns) { QPointF center = documentCenter(); if (rows < 1) { rows = 1; } if (columns < 1) { columns = 1; } // create mesh of NxN points QMap, NodePtr > meshNodes; // create mesh nodes, store them in map for (int i = 0; i < columns; ++i) { for (int j = 0; j < rows; ++j) { NodePtr node = Node::create(m_document); node->setX(i * 50 - (int)25 * columns + center.x()); node->setY(j * 50 - (int)25 * rows + center.y()); node->setType(m_nodeType); meshNodes[qMakePair(i, j)] = node; } } // connect mesh nodes for (int i = 0; i < columns; ++i) { for (int j = 0; j < rows; ++j) { if (j < columns - 1) { // horizontal edges EdgePtr edge = Edge::create(meshNodes[qMakePair(i, j)], meshNodes[qMakePair(i, j + 1)]); edge->setType(m_edgeType); if (m_edgeType->direction() == EdgeType::Direction::Unidirectional) { EdgePtr edge = Edge::create(meshNodes[qMakePair(i, j + 1)], meshNodes[qMakePair(i, j)]); edge->setType(m_edgeType); } } if (i < rows - 1) { // vertical edges EdgePtr edge = Edge::create(meshNodes[qMakePair(i, j)], meshNodes[qMakePair(i + 1, j)]); edge->setType(m_edgeType); if (m_edgeType->direction() == EdgeType::Direction::Unidirectional) { EdgePtr edge = Edge::create(meshNodes[qMakePair(i + 1, j)], meshNodes[qMakePair(i, j)]); edge->setType(m_edgeType); } } } } } void GenerateGraphWidget::generateStar(int satelliteNodes) { QPointF center = documentCenter(); // compute radius such that nodes have space ~50 between each other // circle that border-length of 2*PI*radius int radius = 50 * satelliteNodes / (2 * boost::math::constants::pi()); NodeList nodes; for (int i = 1; i <= satelliteNodes; i++) { NodePtr node = Node::create(m_document); node->setX(sin(i * 2 * boost::math::constants::pi() / satelliteNodes)*radius + center.x()); node->setY(cos(i * 2 * boost::math::constants::pi() / satelliteNodes)*radius + center.y()); node->setType(m_nodeType); nodes.append(node); } // center NodePtr node = Node::create(m_document); node->setX(center.x()); node->setY(center.y()); node->setType(m_nodeType); nodes.prepend(node); // connect circle nodes for (int i = 1; i <= satelliteNodes; ++i) { EdgePtr edge = Edge::create(nodes.at(0), nodes.at(i)); edge->setType(m_edgeType); } } void GenerateGraphWidget::generateCircle(int number) { QPointF center = documentCenter(); // compute radius such that nodes have space ~50 between each other // circle that border-length of 2*PI*radius int radius = 50 * number / (2 * boost::math::constants::pi()); QList< QPair > circleNodes; // create mesh nodes, store them in map NodeList nodes; for (int i = 1; i <= number; i++) { NodePtr node = Node::create(m_document); node->setX(sin(i * 2 * boost::math::constants::pi() / number)*radius + center.x()); node->setY(cos(i * 2 * boost::math::constants::pi() / number)*radius + center.y()); node->setType(m_nodeType); nodes.append(node); } // connect circle nodes for (int i = 0; i < number - 1; i++) { EdgePtr edge = Edge::create(nodes.at(i), nodes.at(i + 1)); edge->setType(m_edgeType); } EdgePtr edge = Edge::create(nodes.at(number - 1), nodes.at(0)); edge->setType(m_edgeType); } void GenerateGraphWidget::generateRandomGraph(int nodes, int edges, bool selfEdges) { QPointF center = documentCenter(); Graph randomGraph; - boost::mt19937 gen; + std::mt19937 gen; gen.seed(static_cast(m_seed)); // generate graph - boost::generate_random_graph( + boost::generate_random_graph( randomGraph, nodes, edges, gen, selfEdges ); // generate distribution topology and apply - boost::rectangle_topology< boost::mt19937 > topology(gen, center.x() - 20 * nodes, center.y() - 20 * nodes, center.x() + 20 * nodes, center.y() + 20 * nodes); + boost::rectangle_topology< std::mt19937 > topology(gen, center.x() - 20 * nodes, center.y() - 20 * nodes, center.x() + 20 * nodes, center.y() + 20 * nodes); PositionVec position_vec(boost::num_vertices(randomGraph)); PositionMap positionMap(position_vec.begin(), get(boost::vertex_index, randomGraph)); boost::random_graph_layout(randomGraph, positionMap, topology); // minimize cuts by Fruchtman-Reingold layout algorithm - boost::fruchterman_reingold_force_directed_layout< boost::rectangle_topology< boost::mt19937 >, Graph, PositionMap > + boost::fruchterman_reingold_force_directed_layout< boost::rectangle_topology< std::mt19937 >, Graph, PositionMap > (randomGraph, positionMap, topology, boost::cooling(boost::linear_cooling(100)) ); // put nodes at whiteboard as generated QMap mapNodes; boost::graph_traits::vertex_iterator vi, vi_end; for (boost::tie(vi, vi_end) = boost::vertices(randomGraph); vi != vi_end; ++vi) { mapNodes[*vi] = Node::create(m_document); mapNodes[*vi]->setX(positionMap[*vi][0]); mapNodes[*vi]->setY(positionMap[*vi][1]); mapNodes[*vi]->setType(m_nodeType); } boost::graph_traits::edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = boost::edges(randomGraph); ei != ei_end; ++ei) { EdgePtr edge = Edge::create(mapNodes[boost::source(*ei, randomGraph)], mapNodes[boost::target(*ei, randomGraph)]); edge->setType(m_edgeType); } } void GenerateGraphWidget::generateErdosRenyiRandomGraph(int nodes, double edgeProbability, bool selfEdges) { QPointF center = documentCenter(); - boost::mt19937 gen; + std::mt19937 gen; gen.seed(static_cast(m_seed)); // generate graph - typedef boost::erdos_renyi_iterator ergen; + typedef boost::erdos_renyi_iterator ergen; Graph randomGraph(ergen(gen, nodes, edgeProbability, selfEdges), ergen(), nodes); // generate distribution topology and apply - boost::rectangle_topology< boost::mt19937 > topology(gen, center.x() - 20 * nodes, center.y() - 20 * nodes, center.x() + 20 * nodes, center.y() + 20 * nodes); + boost::rectangle_topology< std::mt19937 > topology(gen, center.x() - 20 * nodes, center.y() - 20 * nodes, center.x() + 20 * nodes, center.y() + 20 * nodes); PositionVec position_vec(boost::num_vertices(randomGraph)); PositionMap positionMap(position_vec.begin(), get(boost::vertex_index, randomGraph)); boost::random_graph_layout(randomGraph, positionMap, topology); // minimize cuts by Fruchtman-Reingold layout algorithm - boost::fruchterman_reingold_force_directed_layout< boost::rectangle_topology< boost::mt19937 >, Graph, PositionMap > + boost::fruchterman_reingold_force_directed_layout< boost::rectangle_topology< std::mt19937 >, Graph, PositionMap > (randomGraph, positionMap, topology, boost::cooling(boost::linear_cooling(100)) ); // put nodes at whiteboard as generated QMap mapNodes; boost::graph_traits::vertex_iterator vi, vi_end; for (boost::tie(vi, vi_end) = boost::vertices(randomGraph); vi != vi_end; ++vi) { mapNodes[*vi] = Node::create(m_document); mapNodes[*vi]->setX(positionMap[*vi][0]); mapNodes[*vi]->setY(positionMap[*vi][1]); mapNodes[*vi]->setType(m_nodeType); } boost::graph_traits::edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = boost::edges(randomGraph); ei != ei_end; ++ei) { EdgePtr edge = Edge::create(mapNodes[boost::source(*ei, randomGraph)], mapNodes[boost::target(*ei, randomGraph)]); edge->setType(m_edgeType); } } void GenerateGraphWidget::generateRandomTreeGraph(int number) { - boost::mt19937 gen; + + if (EdgeType::Unidirectional == m_edgeType->direction()){ + QMessageBox::critical(this, "Incorrect Edge Direction", "Edges in a Tree must be bidirectional."); + return; + } + + std::mt19937 gen; gen.seed(static_cast(m_seed)); NodeList nodes; - NodePtr node = Node::create(m_document); - node->setType(m_nodeType); - nodes.append(node); + QVector notAdded; + QVector added; - for (int i = 1; i < number; ++i) { - NodePtr thisNode = Node::create(m_document); + for (int i = 0; i < number; i++) { + NodePtr node = Node::create(m_document); node->setType(m_nodeType); - boost::random::uniform_int_distribution<> randomEarlierNodeGen(0, i-1); - int randomEarlierNode = randomEarlierNodeGen(gen); - EdgePtr edge = Edge::create(thisNode, nodes.at(randomEarlierNode)); + nodes.append(node); + + notAdded.push_back(i); + } + + // shuffle + std::shuffle(notAdded.begin(), notAdded.end(), gen); + + // add root + added.push_back(notAdded.front()); + notAdded.pop_front(); + + while (!notAdded.empty()) { + boost::random::uniform_int_distribution<> dist(0, added.size()-1); + + int randomIdx = dist(gen); + int next = notAdded.front(); + + notAdded.pop_front(); + added.push_back(next); + + EdgePtr edge = Edge::create(nodes.at(added[randomIdx]), nodes.at(next)); edge->setType(m_edgeType); - if (m_edgeType->direction() == EdgeType::Unidirectional) { - edge = Edge::create(nodes.at(randomEarlierNode), thisNode); - edge->setType(m_edgeType); + } + + Topology::directedGraphDefaultTopology(m_document); +} + +void GenerateGraphWidget::generateRandomDagGraph(int nodes, double edgeProbability) +{ + + if (EdgeType::Bidirectional == m_edgeType->direction()){ + QMessageBox::critical(this, i18n("Incorrect Edge Direction"), i18n("Edges in a Directed Acyclical Graph must be directional.")); + return; + } + + std::mt19937 gen; + gen.seed(static_cast(m_seed)); + boost::random::uniform_real_distribution dist(0, 1); + + NodeList nodes_list; + + for (int j=0; j < nodes; j++) { + NodePtr node = Node::create(m_document); + node->setType(m_nodeType); + nodes_list.append(node); + } + + // Create random edges + for (int i=0; i < nodes - 1; i++) { + for (int j=i+1; j < nodes; j++) { + if (dist(gen)< edgeProbability) { + EdgePtr edge = Edge::create(nodes_list.at(i), nodes_list.at(j)); + edge->setType(m_edgeType); + } } - nodes.append(thisNode); } - Topology topology = Topology(); - topology.directedGraphDefaultTopology(m_document); + Topology::directedGraphDefaultTopology(m_document); } void GenerateGraphWidget::generatePathGraph(int pathSize) { QPointF center = documentCenter(); QList< QPair > pathNodes; - NodeList nodes_list; for (int i = 1; i <= pathSize; i++) { NodePtr node = Node::create(m_document); node->setX(i * 50 + center.x()); node->setY(center.y()); node->setType(m_nodeType); nodes_list.append(node); } for (int i = 0; i < pathSize - 1; i++) { EdgePtr edge = Edge::create(nodes_list.at(i), nodes_list.at(i + 1)); edge->setType(m_edgeType); } } void GenerateGraphWidget::generateCompleteGraph(int nodes) { QPointF center = documentCenter(); // compute radius such that nodes have space ~100 between each other // circle that border-length of 2*PI*radius int radius = 100 * nodes / (2 * boost::math::constants::pi()); QList< QPair > circleNodes; NodeList node_list; for (int i = 1; i <= nodes; i++) { NodePtr node = Node::create(m_document); node->setX(sin(i * 2 * boost::math::constants::pi() / nodes)*radius + center.x()); node->setY(cos(i * 2 * boost::math::constants::pi() / nodes)*radius + center.y()); node->setType(m_nodeType); node_list.append(node); } for (int i = 0; i < nodes - 1; i++) { - for (int j = i + 1; j < nodes; j++){ + for (int j = i + 1; j < nodes; j++) { EdgePtr edge_lr = Edge::create(node_list.at(i), node_list.at(j)); edge_lr->setType(m_edgeType); if (m_edgeType->direction() == EdgeType::Direction::Unidirectional) { EdgePtr edge_rl = Edge::create(node_list.at(j), node_list.at(i)); edge_rl->setType(m_edgeType); } } } } void GenerateGraphWidget::generateCompleteBipartiteGraph(int nodes_left, int nodes_right) { QPointF center = documentCenter(); int separator = 100; NodeList node_list; for (int i = 0; i < nodes_left; i++) { NodePtr node = Node::create(m_document); node->setX(center.x()); node->setY(center.y() + i * 50); node->setType(m_nodeType); node_list.append(node); } for (int i = 0; i < nodes_right; i++) { NodePtr node = Node::create(m_document); node->setX(center.x() + separator); node->setY(center.y() + i * 50); node->setType(m_nodeType); node_list.append(node); } for (int i = 0; i < nodes_left; i++) { for (int j = 0; j < nodes_right; j++){ EdgePtr edge_lr = Edge::create(node_list.at(i), node_list.at(j + nodes_left)); edge_lr->setType(m_edgeType); if (m_edgeType->direction() == EdgeType::Direction::Unidirectional) { EdgePtr edge_rl = Edge::create(node_list.at(j + nodes_left), node_list.at(i)); edge_rl->setType(m_edgeType); } } } } diff --git a/libgraphtheory/editorplugins/generategraph/generategraphwidget.h b/libgraphtheory/editorplugins/generategraph/generategraphwidget.h index f1c1f6c6..aac13592 100644 --- a/libgraphtheory/editorplugins/generategraph/generategraphwidget.h +++ b/libgraphtheory/editorplugins/generategraph/generategraphwidget.h @@ -1,182 +1,191 @@ /* This file is part of Rocs. Copyright (C) 2011-2013 Andreas Cord-Landwehr 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 . */ #ifndef GENERATEGRAPHWIDGET_H #define GENERATEGRAPHWIDGET_H #include "ui_generategraphwidget.h" #include "typenames.h" #include #include namespace GraphTheory { class GenerateGraphWidget : public QDialog { Q_OBJECT enum GraphGenerator { MeshGraph, StarGraph, CircleGraph, RandomEdgeGraph, ErdosRenyiRandomGraph, RandomTree, + RandomDag, PathGraph, CompleteGraph, CompleteBipartiteGraph }; public: explicit GenerateGraphWidget(GraphDocumentPtr document, QWidget *parent = 0); ~GenerateGraphWidget(); public slots: /** * Select graph generator by its index. * * \param index the index of the graph generator */ void setGraphGenerator(int index); /** * Set seed for the internal random number generator. * * \param seed is the random number generator seed. */ void setSeed(int seed); /** * Set the type of node elements for the generator. * * \param type is the NodeType ID */ void setNodeType(int type); /** * Set the type of edges for the generator. * * \param type is the NodeType ID */ void setEdgeType(int type); /** * Set the unique graph identifier for the next generated graph. * If \p identifier is already in use, the lexicographically next identifier will be used. * * \param identifier for the next generated graph */ void setGraphIdentifier(const QString &identifier); /** * Generate the graph with the previously set configuration. */ void generateGraph(); private: QPointF documentCenter() const; /** * Generate circle graph with specified number of nodes. * * \param nodes is the number of nodes of the generated graph */ void generateCircle(int nodes); /** * Generate mesh graph with specified number of \p rows and \p columns. * * \param rows is the number of rows of the generated graph * \param columns is the number of columns of the generated graph */ void generateMesh(int rows, int columns); /** * Generate a random graph by assigning uniformly at random \p edges many edges to the set of nodes. * * \param nodes is the number of nodes of the generated graph * \param edges is the number of edges of the generated graph * \param seed is the seed for random number generator * \param selfEdges if true self edges are generated, otherwise not */ void generateRandomGraph(int nodes, int edges, bool selfEdges); /** * Generate a star graph with specified number of nodes. * * \param satelliteNodes is the number of satellite nodes of the generated graph */ void generateStar(int satelliteNodes); /** * Generate an Erdös-Renyi random graph. This graph is created by first creating a set of \p nodes * many node elements and then creating any possibly edge with probability \p edgeProbability. * * \param nodes is the number of nodes of the generated graph * \param edgeProbability is the probability for creating an arbitrary edge * \param seed is the seed for random number generator * \param selfEdges if true self edges are generated, otherwise not */ void generateErdosRenyiRandomGraph(int nodes, double edgeProbability, bool selfEdges); /** * Generate a random tree by iterating the following process: First create a root node and than * for (\p nodes - 1) rounds create for a node (selected uniformly at random) a child. * * \param nodes is number of nodes * \param seed is the seed for random number generator */ void generateRandomTreeGraph(int nodes); + /** + * Generate a random DAG by using a ranking algorithm. + * + * \param total_nodes is the number of nodes in the DAG + * \param edgeProbability is the probability of creating an edge + */ + void generateRandomDagGraph(int nodes, double edgeProbability); + /** * Generate a path graph with specified number of nodes. * * \param pathSize is the number of nodes of the generated graph */ void generatePathGraph(int pathSize); /** * Generate a complete graph with specified number of nodes. * * \param nodes is the number of nodes of the generated graph */ void generateCompleteGraph(int nodes); /** * Generate a complete bipartite graph with specified number of nodes. * * \param nodes_left is the number of nodes in the left set of the bipartite graph. * \param nodes_right is the number of nodes in the right set of the bipartite graph. */ void generateCompleteBipartiteGraph(int nodes_left, int nodes_right); GraphDocumentPtr m_document; int m_seed; NodeTypePtr m_nodeType; EdgeTypePtr m_edgeType; QString m_identifier; GraphGenerator m_graphGenerator; QHash m_defaultIdentifiers; Ui::GenerateGraphWidget *ui; }; } #endif diff --git a/libgraphtheory/editorplugins/generategraph/generategraphwidget.ui b/libgraphtheory/editorplugins/generategraph/generategraphwidget.ui index d8737788..462ed17a 100644 --- a/libgraphtheory/editorplugins/generategraph/generategraphwidget.ui +++ b/libgraphtheory/editorplugins/generategraph/generategraphwidget.ui @@ -1,685 +1,735 @@ GenerateGraphWidget 0 0 354 - 344 + 423 Generate Graph Select the graph generator. Mesh Graph Star Graph Circle Graph Random Graph Erdös-Renyi Graph Random Tree Graph + + + Random Dag Graph + + Path Graph Complete Graph Complete Bipartite 0 0 24 24 Show advanced settings. true Set the unique identifier of the generated graph. Graph The node type to create the nodes of the graph with Node type The identifier of the created graph (used for scripting) Identifier 0 QFormLayout::ExpandingFieldsGrow Number of Columns: meshColumns 1 5 Number of Rows: meshRows 1 5 Satellite Nodes: 1 999 10 Number of Nodes: 1 999 10 Nodes: 1 999 10 Edges: 20 Allow self-edges: Generator Seed: 1 999999 Nodes (n): Allow self-edges: 1 10 Edge Probability (p): Generator Seed: 1 999999 3 0.001000000000000 1.000000000000000 0.250000000000000 Nodes: 1 10 Generator Seed: 1 999999 + + + + + + + + Number of Nodes + + + + + + + 10 + + + 999 + + + + + + + Edge Probability + + + + + + + 1.000000000000000 + + + 0.100000000000000 + + + 0.500000000000000 + + + + + + + Number of Nodes: 4 Number of Nodes: 5 Left Set Nodes: 4 Right Set Nodes: 4 QDialogButtonBox::Cancel|QDialogButtonBox::Ok Select the edge type for connections of the generated graph. Qt::Horizontal The edge type to create the edges of the graph with Edge type Graph Generator Select the node type for node elements of the generated graph. KComboBox QComboBox
kcombobox.h
 buttonShowAdvanced toggled(bool) label_randomGeneratorSeed setVisible(bool) 242 21 46 158 buttonShowAdvanced toggled(bool) randomGeneratorSeed setVisible(bool) 242 21 98 158 buttonShowAdvanced toggled(bool) label_GNPGeneratorSeed setVisible(bool) 242 21 18 158 buttonShowAdvanced toggled(bool) GNPGeneratorSeed setVisible(bool) 242 21 83 158 buttonShowAdvanced toggled(bool) label_randomTreeGeneratorSeed setVisible(bool) 242 21 46 159 buttonShowAdvanced toggled(bool) randomTreeGeneratorSeed setVisible(bool) 242 21 98 159 comboGraphGenerator currentIndexChanged(int) stackedWidget setCurrentIndex(int) 169 16 146 194 diff --git a/libgraphtheory/fileformats/dot/dotfileformat.cpp b/libgraphtheory/fileformats/dot/dotfileformat.cpp index ab6c3880..d0df8eb5 100644 --- a/libgraphtheory/fileformats/dot/dotfileformat.cpp +++ b/libgraphtheory/fileformats/dot/dotfileformat.cpp @@ -1,161 +1,161 @@ /* This file is part of Rocs. Copyright 2010 Tomaz Canabrava Copyright 2010 Wagner Reck Copyright 2012-2014 Andreas Cord-Landwehr 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 . */ #include "dotfileformat.h" #include "fileformats/fileformatinterface.h" #include "modifiers/topology.h" #include "graphdocument.h" #include "node.h" #include "edge.h" #include #include #include #include #include #include #include #include "dotgrammarhelper.h" #include "dotgrammar.h" extern DotParser::DotGraphParsingHelper* phelper; using namespace GraphTheory; K_PLUGIN_FACTORY_WITH_JSON( FilePluginFactory, "dotfileformat.json", registerPlugin();) DotFileFormat::~DotFileFormat() { } DotFileFormat::DotFileFormat(QObject* parent, const QList< QVariant >&) : FileFormatInterface("rocs_dotfileformat", parent) { } const QStringList DotFileFormat::extensions() const { return QStringList() << i18n("Graphviz Format (%1)", QString("*.dot")); } void DotFileFormat::readFile() { GraphDocumentPtr document = GraphDocument::create(); setGraphDocument(document); QList < QPair > edges; QFile fileHandle(file().toLocalFile()); if (!fileHandle.open(QFile::ReadOnly)) { setError(CouldNotOpenFile, i18n("Could not open file \"%1\" in read mode: %2", file().toLocalFile(), fileHandle.errorString())); return; } QString content = fileHandle.readAll(); if (!DotParser::parse(content.toStdString(), document)) { setError(EncodingProblem, i18n("Could not parse file \"%1\".", file().toLocalFile())); return; } - Topology layouter; - layouter.directedGraphDefaultTopology(document); + + Topology::directedGraphDefaultTopology(document); setError(None); } void DotFileFormat::writeFile(GraphDocumentPtr document) { // prepare file handle for output QFile fileHandle(file().toLocalFile()); QVariantList subgraphs; if (!fileHandle.open(QFile::WriteOnly | QFile::Text)) { setError(FileIsReadOnly, i18n("Cannot open file %1 to write document. Error: %2", file().fileName(), fileHandle.errorString())); return; } QTextStream out(&fileHandle); out << "digraph {\n"; // create fast access list of already processed nodes: serialize each node only once QHash processedData; // process all data elements foreach(NodePtr node, document->nodes()) { out << processNode(node); } // process all edges for (auto const edge : document->edges()) { out << processEdge(edge); } out << "}\n"; setError(None); return; } QString DotFileFormat::processEdge(EdgePtr edge) const { QString edgeStr; edgeStr.append(QString(" %1 -> %2 ") .arg(edge->from()->id()) .arg(edge->to()->id())); // process properties if present bool firstProperty = true; if (!edge->property("name").toString().isEmpty()) { firstProperty = false; edgeStr.append("["); edgeStr.append(QString(" label = \"%2\" ").arg(edge->property("name").toString())); } foreach(const QByteArray& property, edge->dynamicPropertyNames()) { if (firstProperty == true) { firstProperty = false; edgeStr.append("["); } else { edgeStr.append(", "); } edgeStr.append(QString(" %1 = \"%2\" ").arg(QString(property)).arg(edge->property(property).toString())); } if (!firstProperty) { // at least one property was inserted edgeStr.append("]"); } return edgeStr.append(";\n"); } QString DotFileFormat::processNode(NodePtr node) const { QString nodeStr; // use identifier for unique identification, store name as argument "label" nodeStr = QString("%1").arg(node->id()); nodeStr.append(" [ "); if (!node->dynamicProperty("name").toString().isEmpty()) { nodeStr.append(QString("label=\"%1\" ").arg(node->dynamicProperty("name").toString())); } foreach(const QByteArray& property, node->dynamicPropertyNames()) { nodeStr.append(", "); nodeStr.append(QString(" %1 = \"%2\" ").arg(QString(property)).arg(node->property(property).toString())); } // at least one property was inserted nodeStr.append("]"); return nodeStr.append(";\n"); } #include "dotfileformat.moc" diff --git a/libgraphtheory/fileformats/gml/gmlfileformat.cpp b/libgraphtheory/fileformats/gml/gmlfileformat.cpp index b5e99d4c..01aa003c 100644 --- a/libgraphtheory/fileformats/gml/gmlfileformat.cpp +++ b/libgraphtheory/fileformats/gml/gmlfileformat.cpp @@ -1,148 +1,148 @@ /* This file is part of Rocs. Copyright 2010 Tomaz Canabrava Copyright 2010 Wagner Reck Copyright 2012-2014 Andreas Cord-Landwehr 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 . */ #include "gmlfileformat.h" #include "gmlgrammarhelper.h" #include "gmlgrammar.h" #include "fileformats/fileformatinterface.h" #include "modifiers/topology.h" #include "graphdocument.h" #include "node.h" #include "edge.h" #include #include #include #include #include #include using namespace GraphTheory; extern GmlParser::GmlGrammarHelper* phelper; K_PLUGIN_FACTORY_WITH_JSON( FilePluginFactory, "gmlfileformat.json", registerPlugin();) GmlFileFormat::GmlFileFormat(QObject *parent, const QList&) : FileFormatInterface("rocs_gmlfileformat", parent) { } GmlFileFormat::~GmlFileFormat() { } const QStringList GmlFileFormat::extensions() const { return QStringList() << i18n("Graph Markup Language Format (%1)", QString("*.gml")); } void GmlFileFormat::readFile() { GraphDocumentPtr document = GraphDocument::create(); setGraphDocument(document); QList < QPair > edges; QFile fileHandle(file().toLocalFile()); if (!fileHandle.open(QFile::ReadOnly)) { setError(CouldNotOpenFile, i18n("Could not open file \"%1\" in read mode: %2", file().toLocalFile(), fileHandle.errorString())); document->destroy(); return; } QString content = fileHandle.readAll(); if (!GmlParser::parse(content, document)) { //TODO change interface and pass graph structure setError(EncodingProblem, i18n("Could not parse file \"%1\".", file().toLocalFile())); document->destroy(); return; } - Topology layouter; - layouter.directedGraphDefaultTopology(document); + + Topology::directedGraphDefaultTopology(document); setGraphDocument(document); setError(None); } void GmlFileFormat::writeFile(GraphDocumentPtr document) { QFile fileHandle(file().toLocalFile()); QVariantList subgraphs; if (!fileHandle.open(QFile::WriteOnly | QFile::Text)) { setError(FileIsReadOnly, i18n("Cannot open file %1 to write document. Error: %2", file().fileName(), fileHandle.errorString())); return; } else { QTextStream out(&fileHandle); //FIXME uncommented following directed() check since this is moved to subclass //need to add toggle // out << QString("graph [\n directed %1 \n").arg(g->directed()?"1":"0"); out << QString("id \"%1\" \n").arg("graph"); //TODO support export of name foreach(NodePtr n, document->nodes()) { out << QString("node [\n id \"%1\" \n").arg(n->dynamicProperty("name").toString()); // foreach (QByteArray p, n->dynamicPropertyNames()){ // out << p << " " << n->property(p).toString() << "\n"; // } out << processNode(n); out << "]\n"; } for (auto const edge : document->edges()) { out << "edge [\n"; // foreach (QByteArray p, e->dynamicPropertyNames()){ // out << p << " " << e->property(p).toString() << "\n"; // } out << processEdge(edge); out << "]\n"; } out << "]\n"; } setError(None); return; } QString GmlFileFormat::processEdge(EdgePtr e) const { QString edge; edge.append(QString("source \"%1\"\n target \"%2\"\n").arg(e->from()->dynamicProperty("name").toString(), e->to()->dynamicProperty("name").toString())); // edge.append (QString(" color \"%1\"\n").arg(e->color())); //Problem with comments (both starts by '#') foreach(const QString &property, e->dynamicProperties()) { edge.append(QString("%1 %2\n").arg(property).arg(e->dynamicProperty(property).toString())); } return edge; } QString GmlFileFormat::processNode(NodePtr n) const { QString node; node.append(QString(" x %1 \n y %2 \n").arg(n->x()).arg(n->y())); // node.append (QString(" color \"%1\"\n").arg(n->color())); //Problem with comments (both starts by '#') foreach(const QString &property, n->dynamicProperties()) { node.append(QString("%1 %2\n").arg(property).arg(n->dynamicProperty(property).toString())); } return node; } #include "gmlfileformat.moc" diff --git a/libgraphtheory/fileformats/tgf/tgffileformat.cpp b/libgraphtheory/fileformats/tgf/tgffileformat.cpp index b401eccc..fae3f1d1 100644 --- a/libgraphtheory/fileformats/tgf/tgffileformat.cpp +++ b/libgraphtheory/fileformats/tgf/tgffileformat.cpp @@ -1,140 +1,139 @@ /* This file is part of Rocs. Copyright 2010-2011 Tomaz Canabrava Copyright 2010 Wagner Reck Copyright 2012 Andreas Cord-Landwehr 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 . */ #include "tgffileformat.h" #include "fileformats/fileformatinterface.h" #include "modifiers/topology.h" #include "graphdocument.h" #include "node.h" #include "edge.h" #include #include #include #include #include #include #include using namespace GraphTheory; K_PLUGIN_FACTORY_WITH_JSON( FilePluginFactory, "tgffileformat.json", registerPlugin();) TgfFileFormat::TgfFileFormat(QObject* parent, const QList< QVariant >&) : FileFormatInterface("rocs_tgffileformat", parent) { } TgfFileFormat::~TgfFileFormat() { } const QStringList TgfFileFormat::extensions() const { return QStringList() << i18n("Trivial Graph Format (%1)", QString("*.tgf")); } void TgfFileFormat::readFile() { GraphDocumentPtr document = GraphDocument::create(); document->nodeTypes().first()->addDynamicProperty("label"); document->edgeTypes().first()->addDynamicProperty("label"); // map node identifier from file to created data elements QMap nodeMap; QFile fileHandle(file().toLocalFile()); if (!fileHandle.open(QFile::ReadOnly)) { setError(CouldNotOpenFile, i18n("Could not open file \"%1\" in read mode: %2", file().toLocalFile(), fileHandle.errorString())); return; } ReadMode mode = Nodes; while (!fileHandle.atEnd()) { QString line = QString(fileHandle.readLine()).trimmed(); if (line.startsWith('#')) { // recognize separator before edge list mode = Edges; continue; } if (mode == Nodes) { // read node int identifier = line.section(' ', 0, 0).toInt(); QString label = line.section(' ', 1); // get label, this is everything after first space NodePtr node = Node::create(document); node->setDynamicProperty("label", label.simplified()); node->setId(identifier); if (nodeMap.contains(identifier)) { setError(EncodingProblem, i18n("Could not parse file. Identifier \"%1\" is used more than once.", identifier)); return; } nodeMap[identifier] = node; continue; } if (mode == Edges) { // node edge int from = line.section(' ', 0, 0).toInt(); int to = line.section(' ', 1, 1).toInt(); QString value = line.section(' ', 2); if (!nodeMap.contains(from) || !nodeMap.contains(to)) { setError(EncodingProblem, i18n("Could not parse file. Edge from \"%1\" to \"%2\" uses undefined nodes.", from, to)); return; } EdgePtr edge = Edge::create(nodeMap[from], nodeMap[to]); edge->setDynamicProperty("label", value.simplified()); } } - Topology layouter; - layouter.directedGraphDefaultTopology(document); + Topology::directedGraphDefaultTopology(document); setGraphDocument(document); setError(None); } void TgfFileFormat::writeFile(GraphDocumentPtr document) { QFile fileHandle(file().toLocalFile()); if (!fileHandle.open(QFile::WriteOnly | QFile::Text)) { setError(FileIsReadOnly, i18n("Could not open file \"%1\" in write mode: %2", file().fileName(), fileHandle.errorString())); return; } QTextStream out(&fileHandle); // export data elements //FIXME only default data type considered foreach(NodePtr node, document->nodes()) { out << node->id(); out << " "; out << node->dynamicProperty("label").toString(); //TODO change to selectable property out << '\n'; } out << "#\n"; // export pointers for (auto const edge : document->edges()) { out << edge->from()->id() << " " << edge->to()->id() << " " << edge->dynamicProperty("label").toString() <<'\n'; } setError(None); } #include "tgffileformat.moc" diff --git a/libgraphtheory/modifiers/topology.cpp b/libgraphtheory/modifiers/topology.cpp index fdf142f4..bf43fd9a 100644 --- a/libgraphtheory/modifiers/topology.cpp +++ b/libgraphtheory/modifiers/topology.cpp @@ -1,224 +1,214 @@ /* * 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 "topology.h" #include "graphdocument.h" #include "edge.h" #include "logging_p.h" #include #include #include #include #include #include #include #include #include #include using namespace GraphTheory; typedef boost::adjacency_list < boost::listS, boost::vecS, boost::undirectedS, boost::property > Graph; typedef boost::rectangle_topology<> topology_type; typedef topology_type::point_type point_type; typedef QVector PositionVec; typedef boost::iterator_property_map < PositionVec::iterator, boost::property_map::type > PositionMap; typedef boost::graph_traits::vertex_descriptor Vertex; typedef QPair BoostEdge; // handle boost exceptions namespace boost { void throw_exception(std::exception const &e) { qCCritical(GRAPHTHEORY_GENERAL) << "Exception:" << e.what(); } } -Topology::Topology() -{ - -} - -Topology::~Topology() -{ - -} - void Topology::applyMinCutTreeAlignment(NodeList nodes) { // nodes must be at least of length 2, and two nodes cannot have crossing edges if (nodes.count() < 3) { return; } PositionVec position_vec(nodes.count()); // set box inside which we may reposition QList xList; QList yList; foreach(NodePtr node, nodes) { xList << node->x(); yList << node->y(); } qSort(xList.begin(), xList.end()); qSort(yList.begin(), yList.end()); // do not perform algorithm if graph is very dense: // this prevents very long algorithm computations and possible threading issues if (xList.last() - xList.first() < 10 && yList.last() - yList.first() < 10 ) { qCDebug(GRAPHTHEORY_GENERAL) << "Aborting min cut alignment: nodes are already close to each other."; return; } topology_type topology(xList.first(), yList.first(), xList.last(), yList.last()); // create IDs for all nodes QMap node_mapping; QMap, EdgePtr > edge_mapping; // to map all edges back afterwards int counter = 0; foreach(NodePtr node, nodes) { node_mapping[node] = counter++; } QVector edges(nodes.first()->document()->edges().count()); counter = 0; foreach(EdgePtr edge, nodes.first()->document()->edges()) { edges[counter++] = BoostEdge(node_mapping[edge->from()], node_mapping[edge->to()]); } // setup the graph Graph graph( edges.begin(), edges.end(), nodes.count() ); PositionMap positionMap(position_vec.begin(), get(boost::vertex_index, graph)); counter = 0; foreach(NodePtr node, nodes) { positionMap[counter][0] = node->x(); positionMap[counter][1] = node->y(); counter++; } // minimize cuts by Fruchtman-Reingold layout algorithm boost::fruchterman_reingold_force_directed_layout< topology_type, Graph, PositionMap > (graph, positionMap, topology, boost::cooling(boost::linear_cooling(100)) ); // put nodes at whiteboard as generated foreach(NodePtr node, nodes) { Vertex v = boost::vertex(node_mapping[node], graph); node->setX(positionMap[v][0]); node->setY(positionMap[v][1]); } } void Topology::applyCircleAlignment(NodeList nodes, qreal radius) { if (nodes.length() == 0) { return; } PositionVec position_vec(nodes.count()); if(radius == 0) { // set box inside which we may reposition QList xList; QList yList; foreach(NodePtr node, nodes) { xList << node->x(); yList << node->y(); } qSort(xList.begin(), xList.end()); qSort(yList.begin(), yList.end()); radius = fmax(fabs(xList.first() - xList.last()), fabs(yList.first() - yList.last())) / 2; } // create IDs for all nodes QMap node_mapping; QMap, EdgePtr > edge_mapping; // to map all edges back afterwards int counter = 0; foreach(NodePtr node, nodes) { node_mapping[node] = counter++; } QVector edges(nodes.first()->document()->edges().count()); counter = 0; foreach(EdgePtr edge, nodes.first()->document()->edges()) { edges[counter++] = BoostEdge(node_mapping[edge->from()], node_mapping[edge->to()]); } // setup the graph Graph graph( edges.begin(), edges.end(), nodes.count() ); PositionMap positionMap(position_vec.begin(), get(boost::vertex_index, graph)); counter = 0; foreach(NodePtr node, nodes) { positionMap[counter][0] = node->x(); positionMap[counter][1] = node->y(); counter++; } // layout to circle boost::circle_graph_layout( graph, positionMap, radius); // put nodes at whiteboard as generated foreach(NodePtr node, nodes) { Vertex v = boost::vertex(node_mapping[node], graph); node->setX(positionMap[v][0]); node->setY(positionMap[v][1]); } } void Topology::directedGraphDefaultTopology(GraphDocumentPtr document) { //TODO: port to graphviz layout functions qCDebug(GRAPHTHEORY_GENERAL) << "Temporary implementation, should be replaced soon."; applyCircleAlignment(document->nodes(), 300); applyMinCutTreeAlignment(document->nodes()); } void Topology::undirectedGraphDefaultTopology(GraphDocumentPtr document) { //TODO: port to graphviz layout functions qCDebug(GRAPHTHEORY_GENERAL) << "Temporary implementation, should be replaced soon."; applyCircleAlignment(document->nodes(), 300); applyMinCutTreeAlignment(document->nodes()); } diff --git a/libgraphtheory/modifiers/topology.h b/libgraphtheory/modifiers/topology.h index a0fda07d..b2ec00e8 100644 --- a/libgraphtheory/modifiers/topology.h +++ b/libgraphtheory/modifiers/topology.h @@ -1,86 +1,85 @@ /* * 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 TOPOLOGY_H #define TOPOLOGY_H #include "typenames.h" #include "graphtheory_export.h" #define BOOST_MATH_DISABLE_FLOAT128 1 namespace GraphTheory { /** \brief this class provides topology modifiers for graphs * * Methods of this class either can be applied to graphs to * make unique changes or connected to specific re-format signals to * apply a given topology after every change of the structure. */ class GRAPHTHEORY_EXPORT Topology { public: - Topology(); - virtual ~Topology(); + Topology() = delete; /** \brief applies Fruchterman-Reingold cut minimization * * For the given node set this algorithm applies the Boost implementation * of the Frutherman-Reingold force directed layout algorithm to minimize * crossing edges. Data must be element of the same graph. The * crossings of all present edges contained in this graph are * minimized. This method directly modifies the node. * \param nodeList is the list of all nodes * \return void */ - void applyMinCutTreeAlignment(NodeList nodes); + static void applyMinCutTreeAlignment(NodeList nodes); /** \brief applies Circle topology to node set * * For the given node set this algorithm applies the Boost implementation * to create a circle layout. If a radius is specified, the circle will get the specified radius, * otherwise with no radius set the diameter of the minimal bounding box of all node positions * is used to determine the radius. * \param nodeList is the list of all nodes * \param radius to optionally specify target radius * \return void */ - void applyCircleAlignment(NodeList nodes, qreal radius=0); + static void applyCircleAlignment(NodeList nodes, qreal radius=0); /** \brief applies a default topology for undirected graphs * * Use this method to apply a best-fit topology to an undirected graph (though the * graph need not to be of type "Graph") only based on the node connections. * I.e., no possible present coordinates are respected. */ - void directedGraphDefaultTopology(GraphDocumentPtr document); + static void directedGraphDefaultTopology(GraphDocumentPtr document); /** \brief applies a default topology for undirected graphs * * Use this method to apply a best-fit topology to an undirected graph (though the * graph need not to be of type "Graph") only based on the node connections. * I.e., no possible present coordinates are respected. */ - void undirectedGraphDefaultTopology(GraphDocumentPtr document); + static void undirectedGraphDefaultTopology(GraphDocumentPtr document); }; } #endif