router.h

Go to the documentation of this file.

/*
 * vim: ts=4 sw=4 et tw=0 wm=0
 *
 * libavoid - Fast, Incremental, Object-avoiding Line Router
 *
 * Copyright (C) 2004-2015  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
*/



#ifndef AVOID_ROUTER_H
#define AVOID_ROUTER_H

#include <ctime>
#include <list>
#include <utility>
#include <string>

#include "libavoid/dllexport.h"
#include "libavoid/connector.h"
#include "libavoid/vertices.h"
#include "libavoid/graph.h"
#include "libavoid/timer.h"
#include "libavoid/hyperedge.h"
#include "libavoid/actioninfo.h"
#include "libavoid/hyperedgeimprover.h"


namespace Avoid {

// LineReps: Used for highlighting certain areas in debugging output.
struct LineRep
{
    Point begin;
    Point end;
};
typedef std::list<LineRep> LineReps;


typedef std::list<unsigned int> IntList;

class ShapeRef;
class JunctionRef;
class ClusterRef;
typedef std::list<ClusterRef *> ClusterRefList;
class Obstacle;
typedef std::list<Obstacle *> ObstacleList;
class DebugHandler;

enum RouterFlag
{
    PolyLineRouting = 1,
    OrthogonalRouting = 2
};


static const unsigned int runningTo = 1;
static const unsigned int runningFrom = 2;
static const unsigned int runningToAndFrom = runningTo | runningFrom;

enum RoutingParameter
{
    segmentPenalty = 0,
    
    anglePenalty,
    
    crossingPenalty,
    
    clusterCrossingPenalty,
    
    fixedSharedPathPenalty,
    
    portDirectionPenalty,
    
    shapeBufferDistance,
    
    idealNudgingDistance,

    reverseDirectionPenalty,

    // Used for determining the size of the routing parameter array.
    // This should always we the last value in the enum.
    lastRoutingParameterMarker
};

// Backwards compatibility
typedef enum RoutingParameter PenaltyType;


enum RoutingOption
{
    nudgeOrthogonalSegmentsConnectedToShapes = 0,
    
    improveHyperedgeRoutesMovingJunctions,
    
    penaliseOrthogonalSharedPathsAtConnEnds,
    
    nudgeOrthogonalTouchingColinearSegments,
    
    performUnifyingNudgingPreprocessingStep,
    
    improveHyperedgeRoutesMovingAddingAndDeletingJunctions,

    nudgeSharedPathsWithCommonEndPoint,


    // Used for determining the size of the routing options array.
    // This should always we the last value in the enum.
    lastRoutingOptionMarker
};

enum TransactionPhases 
{
    TransactionPhaseOrthogonalVisibilityGraphScanX = 1,
    TransactionPhaseOrthogonalVisibilityGraphScanY,
    TransactionPhaseRouteSearch,
    TransactionPhaseCrossingDetection,
    TransactionPhaseRerouteSearch,
    TransactionPhaseOrthogonalNudgingX,
    TransactionPhaseOrthogonalNudgingY,
    TransactionPhaseCompleted
};

// NOTE: This is an internal helper class that should not be used by the user.
//
// This class allows edges in the visibility graph to store a
// pointer to a boolean registering when a connector needs to
// reroute, while allowing connectors to be deleted without
// needing to scan and remove these references from the visibility
// graph.  Instead the bool is stored in this delegate and the
// connector is alerted later, so long as it hasn't since been
// deleted.
class ConnRerouteFlagDelegate {
    public:
        ConnRerouteFlagDelegate();
        ~ConnRerouteFlagDelegate();
        bool *addConn(ConnRef *conn);
        void removeConn(ConnRef *conn);
        void alertConns(void);
    private:
        std::list<std::pair<ConnRef *, bool> > m_mapping;
};

static const double zeroParamValue = 0;
static const double chooseSensibleParamValue = -1;

// NOTE: This is an internal helper class that should not be used by the user.
//
// It is used by libtopology to add additional functionality to libavoid
// while keeping libavoid dependency free.
class TopologyAddonInterface
{
    public:
        TopologyAddonInterface()
        {
        }
        virtual ~TopologyAddonInterface()
        {
        }
        virtual TopologyAddonInterface *clone(void) const
        {
            return new TopologyAddonInterface(*this);
        }

        virtual void improveOrthogonalTopology(Router *router)
        {
            (void)(router);  // Avoid unused parameter warning.
        }
        virtual bool outputCode(FILE *fp) const
        {
            (void)(fp);  // Avoid unused parameter warning.
            return false;
        }
        virtual bool outputDeletionCode(FILE *fp) const
        {
            (void)(fp);  // Avoid unused parameter warning.
            return false;
        }
};


//
class AVOID_EXPORT Router {
    public:
        Router(const unsigned int flags);

        virtual ~Router();

        ObstacleList m_obstacles;
        ConnRefList connRefs;
        ClusterRefList clusterRefs;
        EdgeList visGraph;
        EdgeList invisGraph;
        EdgeList visOrthogGraph;
        ContainsMap contains;
        VertInfList vertices;
        ContainsMap enclosingClusters;
        
        bool PartialTime;
        bool SimpleRouting;
        bool ClusteredRouting;

        // Poly-line routing options:
        bool IgnoreRegions;
        bool UseLeesAlgorithm;
        bool InvisibilityGrph;
       
        // General routing options:
        bool SelectiveReroute;
        
        bool PartialFeedback;
        bool RubberBandRouting;
        

        // Instrumentation:
#ifdef AVOID_PROFILE
        Timer timers;
#endif
        int st_checked_edges;

        void setTransactionUse(const bool transactions);

        bool transactionUse(void) const;

        bool processTransaction(void);

        void deleteShape(ShapeRef *shape);

        void moveShape(ShapeRef *shape, const Polygon& newPoly,
                const bool first_move = false);

        void moveShape(ShapeRef *shape, const double xDiff, const double yDiff);

        void deleteJunction(JunctionRef *junction);
        
        void deleteConnector(ConnRef *connector);

        void moveJunction(JunctionRef *junction, const Point& newPosition);

        void moveJunction(JunctionRef *junction, const double xDiff, 
                const double yDiff);
        
        void setRoutingParameter(const RoutingParameter parameter, 
                const double value = chooseSensibleParamValue);

        double routingParameter(const RoutingParameter parameter) const;

        void setRoutingOption(const RoutingOption option, const bool value);

        bool routingOption(const RoutingOption option) const;

        //          method.  See its documentation for more details.
        void setRoutingPenalty(const RoutingParameter penType, 
                const double penVal = chooseSensibleParamValue);

        HyperedgeRerouter *hyperedgeRerouter(void);

        void outputInstanceToSVG(std::string filename = std::string());

        virtual unsigned int newObjectId(void) const;

        bool objectIdIsUnused(const unsigned int id) const;
        
        virtual bool shouldContinueTransactionWithProgress(
                unsigned int elapsedTime, unsigned int phaseNumber, 
                unsigned int totalPhases, double proportion);

        HyperedgeNewAndDeletedObjectLists 
                newAndDeletedObjectListsFromHyperedgeImprovement(void) const;

        void setDebugHandler(DebugHandler *handler);
        DebugHandler *debugHandler(void) const;

        // Processes the actions list for the transaction.  You shouldn't
        // need to cal this.  Instead use processTransaction().
        void processActions(void);
        
        void deleteCluster(ClusterRef *cluster);
        void attachedShapes(IntList &shapes, const unsigned int shapeId,
                const unsigned int type);
        void attachedConns(IntList &conns, const unsigned int shapeId,
                const unsigned int type);
        void markPolylineConnectorsNeedingReroutingForDeletedObstacle(
                Obstacle *obstacle);
        void generateContains(VertInf *pt);
        void printInfo(void);
        void regenerateStaticBuiltGraph(void);
        void destroyOrthogonalVisGraph(void);
        void setStaticGraphInvalidated(const bool invalidated);
        ConnType validConnType(const ConnType select = ConnType_None) const;
        bool isInCrossingPenaltyReroutingStage(void) const;
        void markAllObstaclesAsMoved(void);
        ShapeRef *shapeContainingPoint(const Point& point);
        void performContinuationCheck(unsigned int phaseNumber,
                size_t stepNumber, size_t totalSteps);
        void registerSettingsChange(void);

        void setTopologyAddon(TopologyAddonInterface *topologyAddon);
        void improveOrthogonalTopology(void);

        // Testing and debugging methods.
        bool existsOrthogonalSegmentOverlap(const bool atEnds = false);
        bool existsOrthogonalFixedSegmentOverlap(const bool atEnds = false);
        bool existsOrthogonalTouchingPaths(void);
        int  existsCrossings(const bool optimisedForConnectorType = false);
        bool existsInvalidOrthogonalPaths(void);

        // Outputs the current diagram.  Used for visualising individual
        // steps of various algorithms.  lineReps can be used to draw 
        // attention to specific parts of the diagram that have changed
        // between steps.
        void outputDiagramSVG(std::string instanceName = std::string(), 
                LineReps *lineReps = nullptr);

        void outputDiagramText(std::string instanceName = std::string());
        void outputDiagram(std::string instanceName = std::string());

    private:
        friend class ShapeRef;
        friend class ConnRef;
        friend class JunctionRef;
        friend class Obstacle;
        friend class ClusterRef;
        friend class ShapeConnectionPin;
        friend class MinimumTerminalSpanningTree;
        friend class ConnEnd;
        friend struct HyperedgeTreeNode;
        friend class HyperedgeRerouter;
        friend class HyperedgeImprover;

        unsigned int assignId(const unsigned int suggestedId);
        void addShape(ShapeRef *shape);
        void addJunction(JunctionRef *junction);
        void addCluster(ClusterRef *cluster);
        void modifyConnector(ConnRef *conn);
        void modifyConnector(ConnRef *conn, unsigned int type,
                const ConnEnd &connEnd, bool connPinUpdate = false);
        void modifyConnectionPin(ShapeConnectionPin *pin);

        void removeObjectFromQueuedActions(const void *object);
        void newBlockingShape(const Polygon& poly, int pid);
        void checkAllBlockedEdges(int pid);
        void checkAllMissingEdges(void);
        void adjustContainsWithAdd(const Polygon& poly, const int p_shape);
        void adjustContainsWithDel(const int p_shape);
        void adjustClustersWithAdd(const PolygonInterface& poly, 
                const int p_cluster);
        void adjustClustersWithDel(const int p_cluster);
        void rerouteAndCallbackConnectors(void);
        void improveCrossings(void);

        ActionInfoList actionList;
        unsigned int m_largest_assigned_id;
        bool m_consolidate_actions;
        bool m_currently_calling_destructors;
        double m_routing_parameters[lastRoutingParameterMarker];
        bool m_routing_options[lastRoutingOptionMarker];
        
        ConnRerouteFlagDelegate m_conn_reroute_flags;
        HyperedgeRerouter m_hyperedge_rerouter;
        
        // Progress tracking and transaction cancelling.
        clock_t m_transaction_start_time;
        bool m_abort_transaction;
        
        TopologyAddonInterface *m_topology_addon;

        // Overall modes:
        bool m_allows_polyline_routing;
        bool m_allows_orthogonal_routing;
        
        bool m_static_orthogonal_graph_invalidated;
        bool m_in_crossing_rerouting_stage;

        bool m_settings_changes;
    
        HyperedgeImprover m_hyperedge_improver;

        DebugHandler *m_debug_handler;
};


}



#endif