Inkscape
Vector Graphics Editor
•All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages Concepts
Public Member Functions | Private Member Functions | Private Attributes | List of all members
Avoid::MinimumTerminalSpanningTree Class Reference

#include <mtst.h>

Public Member Functions

 MinimumTerminalSpanningTree (Router *router, std::set< VertInf * > terminals, JunctionHyperedgeTreeNodeMap *hyperedgeTreeJunctions=nullptr)
 
 ~MinimumTerminalSpanningTree ()
 
void constructInterleaved (void)
 
void constructSequential (void)
 
void setDebuggingOutput (FILE *fp, unsigned int counter)
 
HyperedgeTreeNode * rootJunction (void) const
 

Private Member Functions

void buildHyperedgeTreeToRoot (VertInf *curr, HyperedgeTreeNode *prevNode, VertInf *prevVert, bool markEdges=false)
 
VertInf ** resetDistsForPath (VertInf *currVert, VertInf **newRootVertPtr)
 
void rewriteRestOfHyperedge (VertInf *vert, VertInf **newTreeRootPtr)
 
void drawForest (VertInf *vert, VertInf *prev)
 
void makeSet (VertInf *vertex)
 
VertexSetList::iterator findSet (VertInf *vertex)
 
void unionSets (VertexSetList::iterator s1, VertexSetList::iterator s2)
 
HyperedgeTreeNode * addNode (VertInf *vertex, HyperedgeTreeNode *prevNode)
 
void removeInvalidBridgingEdges (void)
 
void commitToBridgingEdge (EdgeInf *e)
 
bool connectsWithoutBend (VertInf *oldLeaf, VertInf *newLeaf)
 
LayeredOrthogonalEdgeList getOrthogonalEdgesFromVertex (VertInf *vert, VertInf *prev)
 
VertInf * orthogonalPartner (VertInf *vert, double penalty=0)
 
VertexPair realVerticesCountingPartners (EdgeInf *edge)
 

Private Attributes

Router * router
 
bool isOrthogonal
 
std::set< VertInf * > terminals
 
std::set< VertInf * > origTerminals
 
JunctionHyperedgeTreeNodeMap * hyperedgeTreeJunctions
 
VertexNodeMap nodes
 
HyperedgeTreeNode * m_rootJunction
 
double bendPenalty
 
VertexSetList allsets
 
std::list< VertInf * > visitedVertices
 
std::list< VertInf * > extraVertices
 
std::list< VertInf * > unusedVertices
 
std::list< VertInf ** > rootVertexPointers
 
std::vector< VertInf * > vHeap
 
HeapCmpVertInf vHeapCompare
 
std::vector< EdgeInf * > beHeap
 
CmpEdgeInf beHeapCompare
 
const VertID dimensionChangeVertexID
 

Detailed Description

Definition at line 66 of file mtst.h.

Constructor & Destructor Documentation

◆ MinimumTerminalSpanningTree()

Avoid::MinimumTerminalSpanningTree::MinimumTerminalSpanningTree ( Router *  router,
std::set< VertInf * >  terminals,
JunctionHyperedgeTreeNodeMap *  hyperedgeTreeJunctions = nullptr 
)

Definition at line 76 of file mtst.cpp.

◆ ~MinimumTerminalSpanningTree()

Avoid::MinimumTerminalSpanningTree::~MinimumTerminalSpanningTree ( )

Definition at line 89 of file mtst.cpp.

References Avoid::HyperedgeTreeNode::deleteEdgesExcept(), and m_rootJunction.

Member Function Documentation

◆ addNode()

HyperedgeTreeNode * Avoid::MinimumTerminalSpanningTree::addNode ( VertInf *  vertex,
HyperedgeTreeNode *  prevNode 
)
private

Definition at line 135 of file mtst.cpp.

References Avoid::HyperedgeTreeNode::junction, m_rootJunction, Avoid::Obstacle::makeActive(), node, nodes, Avoid::HyperedgeTreeNode::point, Avoid::VertInf::point, Avoid::Router::removeObjectFromQueuedActions(), and router.

Referenced by buildHyperedgeTreeToRoot(), commitToBridgingEdge(), and constructSequential().

◆ buildHyperedgeTreeToRoot()

void Avoid::MinimumTerminalSpanningTree::buildHyperedgeTreeToRoot ( VertInf *  curr,
HyperedgeTreeNode *  prevNode,
VertInf *  prevVert,
bool  markEdges = false 
)
private

Definition at line 182 of file mtst.cpp.

References addNode(), Avoid::Router::debugHandler(), dimensionChangeVertexID, Avoid::HyperedgeTreeNode::finalVertex, Avoid::VertInf::hasNeighbour(), Avoid::VertInf::id, Avoid::VertID::isDummyPinHelper(), isOrthogonal, Avoid::HyperedgeTreeNode::isPinDummyEndpoint, Avoid::HyperedgeTreeNode::junction, Avoid::VertInf::m_orthogonalPartner, Avoid::DebugHandler::mtstCommitToEdge(), Avoid::VertInf::pathNext, router, and Avoid::EdgeInf::setHyperedgeSegment().

Referenced by commitToBridgingEdge(), and constructSequential().

◆ commitToBridgingEdge()

void Avoid::MinimumTerminalSpanningTree::commitToBridgingEdge ( EdgeInf *  e)
private

Definition at line 991 of file mtst.cpp.

References addNode(), buildHyperedgeTreeToRoot(), Avoid::Router::debugHandler(), drawForest(), hyperedgeTreeJunctions, Avoid::VertInf::makeTreeRootPointer(), Avoid::DebugHandler::mtstCommitToEdge(), origTerminals, Avoid::VertInf::pathNext, realVerticesCountingPartners(), resetDistsForPath(), rootVertexPointers, router, Avoid::EdgeInf::setHyperedgeSegment(), Avoid::VertInf::setTreeRootPointer(), terminals, Avoid::VertInf::treeRootPointer(), vHeap, and vHeapCompare.

Referenced by constructInterleaved().

◆ connectsWithoutBend()

bool Avoid::MinimumTerminalSpanningTree::connectsWithoutBend ( VertInf *  oldLeaf,
VertInf *  newLeaf 
)
private

Definition at line 832 of file mtst.cpp.

References Avoid::colinear(), isOrthogonal, Avoid::VertInf::orthogVisList, Avoid::VertInf::pathNext, Avoid::VertInf::point, Avoid::VertInf::sptfDist, and Avoid::VertInf::visList.

Referenced by constructSequential().

◆ constructInterleaved()

void Avoid::MinimumTerminalSpanningTree::constructInterleaved ( void  )

Definition at line 633 of file mtst.cpp.

References Avoid::EdgeList::begin(), Avoid::DebugHandler::beginningHyperedgeReroutingWithEndpoints(), beHeap, beHeapCompare, commitToBridgingEdge(), Avoid::VertInfList::connsBegin(), Avoid::cost(), Avoid::Router::debugHandler(), Avoid::EdgeList::end(), Avoid::VertInfList::end(), extraVertices, Avoid::EdgeInf::getDist(), getOrthogonalEdgesFromVertex(), Avoid::VertInf::id, Avoid::VertID::isDummyPinHelper(), Avoid::EdgeInf::lstNext, Avoid::VertInf::lstNext, Avoid::VertInf::makeTreeRootPointer(), Avoid::DebugHandler::mtstGrowForestWithEdge(), Avoid::DebugHandler::mtstPotentialBridgingEdge(), origTerminals, Avoid::VertInf::pathNext, realVerticesCountingPartners(), removeInvalidBridgingEdges(), rootVertexPointers, router, Avoid::EdgeInf::setMtstDist(), Avoid::VertInf::sptfDist, terminals, Avoid::tmHyperedgeAlt, Avoid::VertInf::treeRoot(), Avoid::VertInf::treeRootPointer(), Avoid::Router::vertices, vHeap, vHeapCompare, and Avoid::Router::visOrthogGraph.

Referenced by Avoid::HyperedgeRerouter::performRerouting().

◆ constructSequential()

void Avoid::MinimumTerminalSpanningTree::constructSequential ( void  )

Definition at line 282 of file mtst.cpp.

References addNode(), allsets, Avoid::DebugHandler::beginningHyperedgeReroutingWithEndpoints(), beHeap, beHeapCompare, bendPenalty, buildHyperedgeTreeToRoot(), Avoid::colinear(), connectsWithoutBend(), Avoid::VertInfList::connsBegin(), Avoid::cost(), Avoid::Router::debugHandler(), dimensionChangeVertexID, Avoid::VertInfList::end(), extraVertices, findSet(), hyperedgeTreeJunctions, Avoid::VertInf::id, Avoid::VertID::isDummyPinHelper(), isOrthogonal, Avoid::VertInf::lstNext, Avoid::EdgeInf::m_vert1, Avoid::EdgeInf::m_vert2, makeSet(), Avoid::DebugHandler::mtstCommitToEdge(), Avoid::DebugHandler::mtstGrowForestWithEdge(), Avoid::DebugHandler::mtstPotentialBridgingEdge(), nodes, Avoid::VertInf::orthogVisList, Avoid::VertInf::pathNext, Avoid::VertInf::point, router, Avoid::EdgeInf::setDist(), Avoid::VertInf::setSPTFRoot(), Avoid::VertInf::sptfDist, Avoid::VertInf::sptfRoot(), terminals, Avoid::tmHyperedgeForest, Avoid::tmHyperedgeMTST, unionSets(), Avoid::Router::vertices, vHeap, vHeapCompare, and Avoid::VertInf::visList.

◆ drawForest()

void Avoid::MinimumTerminalSpanningTree::drawForest ( VertInf *  vert,
VertInf *  prev 
)
private

Definition at line 913 of file mtst.cpp.

References Avoid::Router::debugHandler(), drawForest(), getOrthogonalEdgesFromVertex(), Avoid::DebugHandler::mtstGrowForestWithEdge(), Avoid::VertInf::point, router, Avoid::VertInf::treeRoot(), and Avoid::VertInf::treeRootPointer().

Referenced by commitToBridgingEdge(), and drawForest().

◆ findSet()

VertexSetList::iterator Avoid::MinimumTerminalSpanningTree::findSet ( VertInf *  vertex)
private

Definition at line 111 of file mtst.cpp.

References allsets.

Referenced by constructSequential().

◆ getOrthogonalEdgesFromVertex()

LayeredOrthogonalEdgeList Avoid::MinimumTerminalSpanningTree::getOrthogonalEdgesFromVertex ( VertInf *  vert,
VertInf *  prev 
)
private

Definition at line 577 of file mtst.cpp.

References dimensionChangeVertexID, Avoid::VertInf::id, isOrthogonal, orthogonalPartner(), Avoid::VertInf::orthogVisList, Avoid::VertInf::point, Avoid::VertInf::visList, Avoid::Point::x, and Avoid::Point::y.

Referenced by constructInterleaved(), drawForest(), and rewriteRestOfHyperedge().

◆ makeSet()

void Avoid::MinimumTerminalSpanningTree::makeSet ( VertInf *  vertex)
private

Definition at line 104 of file mtst.cpp.

References allsets.

Referenced by constructSequential().

◆ orthogonalPartner()

VertInf * Avoid::MinimumTerminalSpanningTree::orthogonalPartner ( VertInf *  vert,
double  penalty = 0 
)
private

Definition at line 523 of file mtst.cpp.

References bendPenalty, dimensionChangeVertexID, extraVertices, isOrthogonal, Avoid::VertInf::m_orthogonalPartner, Avoid::VertInf::point, router, and Avoid::EdgeInf::setDist().

Referenced by getOrthogonalEdgesFromVertex().

◆ realVerticesCountingPartners()

VertexPair Avoid::MinimumTerminalSpanningTree::realVerticesCountingPartners ( EdgeInf *  edge)
private

Definition at line 964 of file mtst.cpp.

References dimensionChangeVertexID, Avoid::VertInf::id, Avoid::VertInf::m_orthogonalPartner, Avoid::EdgeInf::m_vert1, Avoid::EdgeInf::m_vert2, Avoid::VertInf::point, and Avoid::Point::x.

Referenced by commitToBridgingEdge(), constructInterleaved(), and removeInvalidBridgingEdges().

◆ removeInvalidBridgingEdges()

void Avoid::MinimumTerminalSpanningTree::removeInvalidBridgingEdges ( void  )
private

Definition at line 543 of file mtst.cpp.

References beHeap, beHeapCompare, origTerminals, and realVerticesCountingPartners().

Referenced by constructInterleaved().

◆ resetDistsForPath()

VertInf ** Avoid::MinimumTerminalSpanningTree::resetDistsForPath ( VertInf *  currVert,
VertInf **  newRootVertPtr 
)
private

Definition at line 252 of file mtst.cpp.

References Avoid::VertInf::pathNext, rewriteRestOfHyperedge(), Avoid::VertInf::setTreeRootPointer(), Avoid::VertInf::sptfDist, terminals, and Avoid::VertInf::treeRootPointer().

Referenced by commitToBridgingEdge().

◆ rewriteRestOfHyperedge()

void Avoid::MinimumTerminalSpanningTree::rewriteRestOfHyperedge ( VertInf *  vert,
VertInf **  newTreeRootPtr 
)
private

Definition at line 886 of file mtst.cpp.

References getOrthogonalEdgesFromVertex(), rewriteRestOfHyperedge(), and Avoid::VertInf::setTreeRootPointer().

Referenced by resetDistsForPath(), and rewriteRestOfHyperedge().

◆ rootJunction()

HyperedgeTreeNode * Avoid::MinimumTerminalSpanningTree::rootJunction ( void  ) const

Definition at line 98 of file mtst.cpp.

References m_rootJunction.

Referenced by Avoid::HyperedgeRerouter::performRerouting().

◆ setDebuggingOutput()

void Avoid::MinimumTerminalSpanningTree::setDebuggingOutput ( FILE *  fp,
unsigned int  counter 
)

◆ unionSets()

void Avoid::MinimumTerminalSpanningTree::unionSets ( VertexSetList::iterator  s1,
VertexSetList::iterator  s2 
)
private

Definition at line 124 of file mtst.cpp.

References allsets.

Referenced by constructSequential().

Member Data Documentation

◆ allsets

VertexSetList Avoid::MinimumTerminalSpanningTree::allsets
private

Definition at line 114 of file mtst.h.

Referenced by constructSequential(), findSet(), makeSet(), and unionSets().

◆ beHeap

std::vector<EdgeInf *> Avoid::MinimumTerminalSpanningTree::beHeap
private

Definition at line 125 of file mtst.h.

Referenced by constructInterleaved(), constructSequential(), and removeInvalidBridgingEdges().

◆ beHeapCompare

CmpEdgeInf Avoid::MinimumTerminalSpanningTree::beHeapCompare
private

Definition at line 126 of file mtst.h.

Referenced by constructInterleaved(), constructSequential(), and removeInvalidBridgingEdges().

◆ bendPenalty

double Avoid::MinimumTerminalSpanningTree::bendPenalty
private

Definition at line 113 of file mtst.h.

Referenced by constructSequential(), and orthogonalPartner().

◆ dimensionChangeVertexID

const VertID Avoid::MinimumTerminalSpanningTree::dimensionChangeVertexID
private

Definition at line 128 of file mtst.h.

Referenced by buildHyperedgeTreeToRoot(), constructSequential(), getOrthogonalEdgesFromVertex(), orthogonalPartner(), and realVerticesCountingPartners().

◆ extraVertices

std::list<VertInf *> Avoid::MinimumTerminalSpanningTree::extraVertices
private

Definition at line 116 of file mtst.h.

Referenced by constructInterleaved(), constructSequential(), and orthogonalPartner().

◆ hyperedgeTreeJunctions

JunctionHyperedgeTreeNodeMap* Avoid::MinimumTerminalSpanningTree::hyperedgeTreeJunctions
private

Definition at line 109 of file mtst.h.

Referenced by commitToBridgingEdge(), and constructSequential().

◆ isOrthogonal

bool Avoid::MinimumTerminalSpanningTree::isOrthogonal
private

Definition at line 106 of file mtst.h.

Referenced by buildHyperedgeTreeToRoot(), connectsWithoutBend(), constructSequential(), getOrthogonalEdgesFromVertex(), and orthogonalPartner().

◆ m_rootJunction

HyperedgeTreeNode* Avoid::MinimumTerminalSpanningTree::m_rootJunction
private

Definition at line 112 of file mtst.h.

Referenced by addNode(), rootJunction(), and ~MinimumTerminalSpanningTree().

◆ nodes

VertexNodeMap Avoid::MinimumTerminalSpanningTree::nodes
private

Definition at line 111 of file mtst.h.

Referenced by addNode(), and constructSequential().

◆ origTerminals

std::set<VertInf *> Avoid::MinimumTerminalSpanningTree::origTerminals
private

Definition at line 108 of file mtst.h.

Referenced by commitToBridgingEdge(), constructInterleaved(), and removeInvalidBridgingEdges().

◆ rootVertexPointers

std::list<VertInf **> Avoid::MinimumTerminalSpanningTree::rootVertexPointers
private

Definition at line 118 of file mtst.h.

Referenced by commitToBridgingEdge(), and constructInterleaved().

◆ router

Router* Avoid::MinimumTerminalSpanningTree::router
private

Definition at line 105 of file mtst.h.

Referenced by addNode(), buildHyperedgeTreeToRoot(), commitToBridgingEdge(), constructInterleaved(), constructSequential(), drawForest(), and orthogonalPartner().

◆ terminals

std::set<VertInf *> Avoid::MinimumTerminalSpanningTree::terminals
private

Definition at line 107 of file mtst.h.

Referenced by commitToBridgingEdge(), constructInterleaved(), constructSequential(), and resetDistsForPath().

◆ unusedVertices

std::list<VertInf *> Avoid::MinimumTerminalSpanningTree::unusedVertices
private

Definition at line 117 of file mtst.h.

◆ vHeap

std::vector<VertInf *> Avoid::MinimumTerminalSpanningTree::vHeap
private

Definition at line 121 of file mtst.h.

Referenced by commitToBridgingEdge(), constructInterleaved(), and constructSequential().

◆ vHeapCompare

HeapCmpVertInf Avoid::MinimumTerminalSpanningTree::vHeapCompare
private

Definition at line 122 of file mtst.h.

Referenced by commitToBridgingEdge(), constructInterleaved(), and constructSequential().

◆ visitedVertices

std::list<VertInf *> Avoid::MinimumTerminalSpanningTree::visitedVertices
private

Definition at line 115 of file mtst.h.

The documentation for this class was generated from the following files: