[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-i18n-doc
Subject:    [rocs] RocsCore/DataStructures/Graph: Fix distance computation for unconnected nodes.
From:       Andreas Cord-Landwehr <cola () uni-paderborn ! de>
Date:       2013-06-11 18:28:30
Message-ID: 20130611182830.C18F4A605A () git ! kde ! org
[Download RAW message or body]

Git commit 06c79f18fc9b43d0ff5a3c2a6a98cd86ce54a609 by Andreas Cord-Landwehr, on \
behalf of Matthew Mellott. Committed on 11/06/2013 at 11:41.
Pushed by cordlandwehr into branch 'master'.

Fix distance computation for unconnected nodes.

If a path does not exist between any two vertices in a graph, the
distance between those vertices is defined to be infinity. The
GraphStructure::distances method was returning zero in this situation
and so this was a bug. A fix for this bug was implemented, a test case
was added to verify these changes, and related documentation was
updated.

Introducing two new strings, as requested at i18n list.

REVIEW: 110822
CCMAIL: kde-i18n-doc@kde.org

M  +13   -5    RocsCore/DataStructures/Graph/GraphStructure.cpp
M  +4    -2    RocsCore/DataStructures/Graph/GraphStructure.h
M  +14   -0    RocsCore/DataStructures/Graph/GraphStructure.xml
M  +31   -0    RocsCore/DataStructures/Graph/Tests/TestGraphStructureAlgorithms.cpp
M  +1    -0    RocsCore/DataStructures/Graph/Tests/TestGraphStructureAlgorithms.h

http://commits.kde.org/rocs/06c79f18fc9b43d0ff5a3c2a6a98cd86ce54a609

diff --git a/RocsCore/DataStructures/Graph/GraphStructure.cpp \
b/RocsCore/DataStructures/Graph/GraphStructure.cpp index a3de72a..01630f5 100644
--- a/RocsCore/DataStructures/Graph/GraphStructure.cpp
+++ b/RocsCore/DataStructures/Graph/GraphStructure.cpp
@@ -39,6 +39,8 @@
 #include <KLocale>
 #include <QString>
 
+#include <cmath>
+
 DataStructurePtr Rocs::GraphStructure::create(Document *parent)
 {
     return DataStructure::create<GraphStructure>(parent);
@@ -268,13 +270,19 @@ QScriptValue Rocs::GraphStructure::distances(Data* fromRaw)
     QScriptValue distances = engine()->newArray();
     foreach (DataPtr target, dataListAll()) {
         qreal length = 0;
-        foreach (PointerPtr edge, shortestPaths[target]) {
-            if (!edge->property("value").toString().isEmpty()) {
-                length += edge->property("value").toDouble();
-            } else {
-                length += 1;
+
+        if (shortestPaths[target].isEmpty() && from != target) {
+            length = INFINITY;
+        } else {
+            foreach (PointerPtr edge, shortestPaths[target]) {
+                if (!edge->property("value").toString().isEmpty()) {
+                    length += edge->property("value").toDouble();
+                } else {
+                    length += 1;
+                }
             }
         }
+
         distances.property("push").call(
             distances,
             QScriptValueList() << length
diff --git a/RocsCore/DataStructures/Graph/GraphStructure.h \
b/RocsCore/DataStructures/Graph/GraphStructure.h index 7754cd0..66b0c20 100644
--- a/RocsCore/DataStructures/Graph/GraphStructure.h
+++ b/RocsCore/DataStructures/Graph/GraphStructure.h
@@ -254,8 +254,10 @@ public slots:
     /**
      * Computes the Dijkstra's shortest path algorithm to compute
      * all shortest path distances from \p from. If edge has value 0, the edge value
-     * is set to 1. Note: this shortest path algorithm works only for graphs with \
                all
-     * edges values non-negative. For undirected graphs reverse edges are add \
automatically. +     * is set to 1. Infinity is returned when there is no path
+     * between \p from and another node in the graph. Note: this shortest path
+     * algorithm works only for graphs with all edges values non-negative. For
+     * undirected graphs reverse edges are added automatically.
      * The algorithm has time complexity O(V log V + E).
      *
      * \param from the node from which the computation starts
diff --git a/RocsCore/DataStructures/Graph/GraphStructure.xml \
b/RocsCore/DataStructures/Graph/GraphStructure.xml index a814a25..16308f5 100644
--- a/RocsCore/DataStructures/Graph/GraphStructure.xml
+++ b/RocsCore/DataStructures/Graph/GraphStructure.xml
@@ -120,5 +120,19 @@ A graph objects holds the information of a data structure of \
type "Graph".  </parameter>
     </parameters>
 </method>
+<method>
+    <name>distances(from)</name>
+    <description>
+        <para>Returns an array of shortest path lengths from this node to every \
other node in the graph.</para> +    </description>
+    <returnType>Array</returnType>
+    <parameters>
+        <parameter>
+            <name>from</name>
+            <type>GraphNode</type>
+            <info>Source node for distance computations.</info>
+        </parameter>
+    </parameters>
+</method>
 </methods>
 </object>
diff --git a/RocsCore/DataStructures/Graph/Tests/TestGraphStructureAlgorithms.cpp \
b/RocsCore/DataStructures/Graph/Tests/TestGraphStructureAlgorithms.cpp index \
                340f5d9..93e835b 100644
--- a/RocsCore/DataStructures/Graph/Tests/TestGraphStructureAlgorithms.cpp
+++ b/RocsCore/DataStructures/Graph/Tests/TestGraphStructureAlgorithms.cpp
@@ -31,6 +31,8 @@
 #include <DataStructureBackendManager.h>
 #include <DocumentManager.h>
 
+#include <cmath>
+
 TestGraphStructureAlgorithms::TestGraphStructureAlgorithms()
 {
     QVERIFY(DataStructureBackendManager::self().backends().count() > 0);
@@ -49,6 +51,35 @@ void TestGraphStructureAlgorithms::cleanupTestCase()
     DocumentManager::self().removeDocument(DocumentManager::self().activeDocument());
  }
 
+void TestGraphStructureAlgorithms::testDistances()
+{
+    Document *document = DocumentManager::self().activeDocument();
+    DataList dataList;
+
+    document->pointerType(0)->setDirection(PointerType::Bidirectional);
+
+    DataStructurePtr ds = document->addDataStructure("Dijkstra");
+    boost::shared_ptr<Rocs::GraphStructure> graph = \
boost::static_pointer_cast<Rocs::GraphStructure>(ds); +
+    // need to set engine because GraphStructure::distances calls \
QScriptEngine::newArray +    ds->setEngine(new QScriptEngine(this));
+
+    // create 3 nodes connected as follows:
+    // x-x x
+    int nodes = 3;
+    dataList.clear();
+    for (int i = 0; i < nodes; ++i) {
+        dataList.append(graph->createData(QString(i), 0));
+    }
+    dataList[0]->createPointer(dataList[1]);
+
+    // test distances from 0 to all others
+    QScriptValue distances = graph->distances(dataList[0].get());
+    QVERIFY2(distances.property(0).equals(QScriptValue(0)), "ERROR: distance is \
wrong"); +    QVERIFY2(distances.property(1).equals(QScriptValue(1)), "ERROR: \
distance is wrong"); +    \
QVERIFY2(distances.property(2).equals(QScriptValue(INFINITY)), "ERROR: distance is \
wrong"); +}
+
 void TestGraphStructureAlgorithms::testDijkstraBidirectional()
 {
     Document *document = DocumentManager::self().activeDocument();
diff --git a/RocsCore/DataStructures/Graph/Tests/TestGraphStructureAlgorithms.h \
b/RocsCore/DataStructures/Graph/Tests/TestGraphStructureAlgorithms.h index \
                abac132..e563fd0 100644
--- a/RocsCore/DataStructures/Graph/Tests/TestGraphStructureAlgorithms.h
+++ b/RocsCore/DataStructures/Graph/Tests/TestGraphStructureAlgorithms.h
@@ -35,6 +35,7 @@ public:
 private slots:
     void init();
     void cleanupTestCase();
+    void testDistances();
     void testDijkstraBidirectional();
     void testDijkstraUnidirectional();
 


[prev in list] [next in list] [prev in thread] [next in thread]