1 files changed, 388 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libavoid/hyperedge.cpp b/src/3rdparty/adaptagrams/libavoid/hyperedge.cpp
new file mode 100644
index 0000000..d6f2a40
--- /dev/null
+++ b/src/3rdparty/adaptagrams/libavoid/hyperedge.cpp
@@ -0,0 +1,388 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ *
+ * Copyright (C) 2011-2014  Monash University
+ *
+ * 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) any later version.
+ * See the file LICENSE.LGPL distributed with the library.
+ *
+ * Licensees holding a valid commercial license may use this file in
+ * accordance with the commercial license agreement provided with the 
+ * library.
+ *
+ * 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.  
+ *
+ * Author(s):  Michael Wybrow
+*/
+
+#include "libavoid/hyperedge.h"
+#include "libavoid/hyperedgetree.h"
+#include "libavoid/mtst.h"
+#include "libavoid/junction.h"
+#include "libavoid/connector.h"
+#include "libavoid/vertices.h"
+#include "libavoid/connend.h"
+#include "libavoid/shape.h"
+#include "libavoid/router.h"
+#include "libavoid/assertions.h"
+#include "libavoid/debughandler.h"
+#include "libavoid/debug.h"
+
+
+namespace Avoid {
+
+HyperedgeRerouter::HyperedgeRerouter()
+    : m_router(nullptr)
+{
+}
+
+void HyperedgeRerouter::setRouter(Router *router)
+{
+    m_router = router;
+}
+
+size_t HyperedgeRerouter::registerHyperedgeForRerouting(
+        ConnEndList terminals)
+{
+    m_terminals_vector.push_back(terminals);
+    m_root_junction_vector.push_back(nullptr);
+
+    return m_terminals_vector.size() - 1;
+}
+
+size_t HyperedgeRerouter::registerHyperedgeForRerouting(
+        JunctionRef *junction)
+{
+    m_terminals_vector.push_back(ConnEndList());
+    m_root_junction_vector.push_back(junction);
+
+    return m_terminals_vector.size() - 1;
+}
+
+size_t HyperedgeRerouter::count(void) const
+{
+    return m_terminals_vector.size();
+}
+
+HyperedgeNewAndDeletedObjectLists HyperedgeRerouter::newAndDeletedObjectLists(
+        size_t index) const
+{
+    COLA_ASSERT(index <= count());
+
+    HyperedgeNewAndDeletedObjectLists result;
+
+    result.newJunctionList = m_new_junctions_vector[index];
+    result.deletedJunctionList = m_deleted_junctions_vector[index];
+    result.newConnectorList = m_new_connectors_vector[index];
+    result.deletedConnectorList = m_deleted_connectors_vector[index];
+
+    return result;
+}
+
+
+void HyperedgeRerouter::outputInstanceToSVG(FILE *fp)
+{
+    if (count() == 0)
+    {
+        return;
+    }
+
+    fprintf(fp, "    HyperedgeRerouter *hyperedgeRerouter = router->hyperedgeRerouter();\n");
+    const size_t num_hyperedges = count();
+    for (size_t i = 0; i < num_hyperedges; ++i)
+    {
+        if (m_root_junction_vector[i])
+        {
+            fprintf(fp, "    hyperedgeRerouter->registerHyperedgeForRerouting(junctionRef%u);\n",
+                    m_root_junction_vector[i]->id());
+        }
+        else
+        {
+            fprintf(fp, "    ConnEndList heConnList%u;\n", (unsigned int) i);
+            for (ConnEndList::const_iterator it = m_terminals_vector[i].begin();
+                    it != m_terminals_vector[i].end(); ++it)
+            {
+                (*it).outputCode(fp, "heEnd");
+                fprintf(fp, "    heConnList%u.push_back(heEndPt);\n",
+                        (unsigned int) i);
+            }
+            fprintf(fp, "    hyperedgeRerouter->registerHyperedgeForRerouting(heConnList%u);\n",
+                    (unsigned int) i);
+
+        }
+    }
+    fprintf(fp, "\n");
+}
+
+
+// Follow connected junctions and connectors from the given connector to
+// determine the hyperedge topology, saving objects to the deleted-objects
+// vectors as we go.
+bool HyperedgeRerouter::findAttachedObjects(size_t index,
+        ConnRef *connector, JunctionRef *ignore, ConnRefSet& hyperedgeConns)
+{
+    bool validHyperedge = false;
+
+    connector->assignConnectionPinVisibility(true);
+
+    m_deleted_connectors_vector[index].push_back(connector);
+    hyperedgeConns.insert(connector);
+
+    std::pair<Obstacle *, Obstacle *> anchors = connector->endpointAnchors();
+    JunctionRef *jFirst = dynamic_cast<JunctionRef *> (anchors.first);
+    JunctionRef *jSecond = dynamic_cast<JunctionRef *> (anchors.second);
+
+    if (jFirst)
+    {
+        // If attached to a junction and not one we've explored, then continue.
+        if (jFirst != ignore)
+        {
+            validHyperedge |= findAttachedObjects(index, jFirst, connector, hyperedgeConns);
+        }
+    }
+    else
+    {
+        // If its an endpoint, then record the vertex for this endpoint.
+        COLA_ASSERT(connector->m_src_vert);
+        m_terminal_vertices_vector[index].insert(connector->m_src_vert);
+    }
+
+    if (jSecond)
+    {
+        // If attached to a junction and not one we've explored, then continue.
+        if (jSecond != ignore)
+        {
+            validHyperedge |= findAttachedObjects(index, jSecond, connector, hyperedgeConns);
+        }
+    }
+    else
+    {
+        // If its an endpoint, then record the vertex for this endpoint.
+        COLA_ASSERT(connector->m_dst_vert);
+        m_terminal_vertices_vector[index].insert(connector->m_dst_vert);
+    }
+    return validHyperedge;
+}
+
+
+// Follow connected junctions and connectors from the given junction to
+// determine the hyperedge topology, saving objects to the deleted-objects
+// vectors as we go.
+bool HyperedgeRerouter::findAttachedObjects(size_t index,
+        JunctionRef *junction, ConnRef *ignore, ConnRefSet& hyperedgeConns)
+{
+    bool validHyperedge = false;
+
+    m_deleted_junctions_vector[index].push_back(junction);
+
+    ConnRefList connectors = junction->attachedConnectors();
+
+    if (connectors.size() > 2)
+    {
+        // A valid hyperedge must have at least one junction with three
+        // connectors attached, i.e., more than two endpoints.
+        validHyperedge |= true;
+    }
+
+    for (ConnRefList::iterator curr  = connectors.begin();
+            curr != connectors.end(); ++curr)
+    {
+        if (*curr == ignore)
+        {
+            continue;
+        }
+
+        COLA_ASSERT(*curr != nullptr);
+        validHyperedge |= findAttachedObjects(index, (*curr), junction, hyperedgeConns);
+    }
+    return validHyperedge;
+}
+
+
+// Populate the deleted-object vectors with all the connectors and junctions
+// that form the registered hyperedges.  Then return the set of all these
+// connectors so they can be ignored for individual rerouting.
+ConnRefSet HyperedgeRerouter::calcHyperedgeConnectors(void)
+{
+    COLA_ASSERT(m_router != nullptr);
+
+    ConnRefSet allRegisteredHyperedgeConns;
+
+    // Clear the deleted-object vectors.  We populate them here if necessary.
+    m_deleted_junctions_vector.clear();
+    m_deleted_junctions_vector.resize(count());
+    m_deleted_connectors_vector.clear();
+    m_deleted_connectors_vector.resize(count());
+
+    m_terminal_vertices_vector.clear();
+    m_terminal_vertices_vector.resize(count());
+    m_added_vertices.clear();
+
+    // Populate the deleted-object vectors.
+    const size_t num_hyperedges = count();
+    for (size_t i = 0; i < num_hyperedges; ++i)
+    {
+        if (m_root_junction_vector[i])
+        {
+            // Follow objects attached to junction to find the hyperedge.
+            bool valid = findAttachedObjects(i, m_root_junction_vector[i], nullptr,
+                    allRegisteredHyperedgeConns);
+            if (!valid)
+            {
+                err_printf("Warning: Hyperedge %d registered with "
+                           "HyperedgeRerouter is invalid and will be "
+                           "ignored.\n", (int) i);
+                // Hyperedge is invalid.  Clear the terminals and other info
+                // so it will be ignored, and rerouted as a normal set of 
+                // connectors.
+                m_terminals_vector[i].clear();
+                m_terminal_vertices_vector[i].clear();
+                m_deleted_junctions_vector[i].clear();
+                m_deleted_connectors_vector[i].clear();
+            }
+            continue;
+        }
+
+        // Alternatively, we have a set of ConnEnds, so store the
+        // corresponding terminals
+        std::pair<bool, VertInf *> maybeNewVertex;
+        for (ConnEndList::const_iterator it = m_terminals_vector[i].begin();
+                it != m_terminals_vector[i].end(); ++it)
+        {
+            maybeNewVertex = it->getHyperedgeVertex(m_router);
+            COLA_ASSERT(maybeNewVertex.second != nullptr);
+            m_terminal_vertices_vector[i].insert(maybeNewVertex.second);
+
+            if (maybeNewVertex.first)
+            {
+                // This is a newly created vertex.  Remember it so we can
+                // free it and it's visibility edges later.
+                m_added_vertices.push_back(maybeNewVertex.second);
+            }
+        }
+    }
+
+    // Return these connectors that don't require rerouting.
+    return allRegisteredHyperedgeConns;
+}
+
+
+void HyperedgeRerouter::performRerouting(void)
+{
+    COLA_ASSERT(m_router != nullptr);
+
+    m_new_junctions_vector.clear();
+    m_new_junctions_vector.resize(count());
+    m_new_connectors_vector.clear();
+    m_new_connectors_vector.resize(count());
+
+#ifdef DEBUGHANDLER
+    if (m_router->debugHandler())
+    {
+        std::vector<Box> obstacleBoxes;
+        ObstacleList::iterator obstacleIt = m_router->m_obstacles.begin();
+        while (obstacleIt != m_router->m_obstacles.end())
+        {
+            Obstacle *obstacle = *obstacleIt;
+            JunctionRef *junction = dynamic_cast<JunctionRef *> (obstacle);
+            if (junction && ! junction->positionFixed())
+            {
+                // Junctions that are free to move are not treated as obstacles.
+                ++obstacleIt;
+                continue;
+            }
+            Box bbox = obstacle->routingBox();
+            obstacleBoxes.push_back(bbox);
+            ++obstacleIt;
+        }
+        m_router->debugHandler()->updateObstacleBoxes(obstacleBoxes);
+    }
+#endif
+
+    // For each hyperedge...
+    const size_t num_hyperedges = count();
+    for (size_t i = 0; i < num_hyperedges; ++i)
+    {
+        if (m_terminal_vertices_vector[i].empty())
+        {
+            // Invalid hyperedge, ignore.
+            continue;
+        }
+
+        // Execute the MTST method to find good junction positions and an
+        // initial path.  A hyperedge tree will be built for the new route.
+        JunctionHyperedgeTreeNodeMap hyperedgeTreeJunctions;
+        MinimumTerminalSpanningTree mtst(m_router, 
+                m_terminal_vertices_vector[i], &hyperedgeTreeJunctions);
+
+        // The older MTST construction method (faster, worse results).
+        //mtst.constructSequential();
+        
+        // The preferred MTST construction method.
+        // Slightly slower, better quality results.
+        mtst.constructInterleaved();
+
+        HyperedgeTreeNode *treeRoot = mtst.rootJunction();
+        COLA_ASSERT(treeRoot);
+        
+        // Fill in connector information and join them to junctions of endpoints
+        // of original connectors.
+        treeRoot->addConns(nullptr, m_router, 
+                m_deleted_connectors_vector[i], nullptr);
+
+        // Output the list of new junctions and connectors from hyperedge tree.
+        treeRoot->listJunctionsAndConnectors(nullptr, m_new_junctions_vector[i],
+                m_new_connectors_vector[i]);
+
+        // Write paths from the hyperedge tree back into individual
+        // connector routes.
+        for (size_t pass = 0; pass < 2; ++pass)
+        {
+            treeRoot->writeEdgesToConns(nullptr, pass);
+        }
+
+        // Tell the router that we are deleting the objects used for the
+        // previous path for the hyperedge.
+        for (ConnRefList::iterator curr = 
+                m_deleted_connectors_vector[i].begin();
+                curr != m_deleted_connectors_vector[i].end(); ++curr)
+        {
+            // Clear visibility assigned for connection pins.
+            (*curr)->assignConnectionPinVisibility(false);
+
+            m_router->deleteConnector(*curr);
+        }
+        for (JunctionRefList::iterator curr = 
+                m_deleted_junctions_vector[i].begin();
+                curr != m_deleted_junctions_vector[i].end(); ++curr)
+        {
+            m_router->deleteJunction(*curr);
+        }
+    }
+
+    // Clear the input to this class, so that new objects can be registered
+    // for rerouting for the next time that transaction that is processed.
+    m_terminals_vector.clear();
+    m_root_junction_vector.clear();
+
+    // Free temporarily added vertices.
+    for (VertexList::iterator curr = m_added_vertices.begin();
+            curr != m_added_vertices.end(); ++curr)
+    {
+        (*curr)->removeFromGraph();
+        m_router->vertices.removeVertex(*curr);
+        delete *curr;
+    }
+    m_added_vertices.clear();
+}
+
+
+}
+