1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libavoid - Fast, Incremental, Object-avoiding Line Router
*
* Copyright (C) 2011-2013 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_MTST_H
#define AVOID_MTST_H
#include <cstdio>
#include <set>
#include <list>
#include <utility>
#include "libavoid/vertices.h"
#include "libavoid/hyperedgetree.h"
namespace Avoid {
class VertInf;
class Router;
class ConnRef;
class EdgeInf;
typedef std::list<VertexSet> VertexSetList;
typedef std::pair<EdgeInf *, VertInf *> LayeredOrthogonalEdge;
typedef std::list<LayeredOrthogonalEdge> LayeredOrthogonalEdgeList;
// Comparison for the vertex heap in the extended Dijkstra's algorithm.
struct HeapCmpVertInf
{
bool operator()(const VertInf *a, const VertInf *b) const;
};
// Comparison for the bridging edge heap in the extended Kruskal's algorithm.
struct CmpEdgeInf
{
bool operator()(const EdgeInf *a, const EdgeInf *b) const;
};
// This class is not intended for public use.
// It is used by the hyperedge routing code to build a minimum terminal
// spanning tree for a set of terminal vertices.
class MinimumTerminalSpanningTree
{
public:
MinimumTerminalSpanningTree(Router *router,
std::set<VertInf *> terminals,
JunctionHyperedgeTreeNodeMap *hyperedgeTreeJunctions = nullptr);
~MinimumTerminalSpanningTree();
// Uses Interleaved construction of the MTST and SPTF (heuristic 2
// from paper). This is the preferred construction approach.
void constructInterleaved(void);
// Uses Sequential construction of the MTST (heuristic 1 from paper).
void constructSequential(void);
void setDebuggingOutput(FILE *fp, unsigned int counter);
HyperedgeTreeNode *rootJunction(void) const;
private:
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);
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;
// Vertex heap for extended Dijkstra's algorithm.
std::vector<VertInf *> vHeap;
HeapCmpVertInf vHeapCompare;
// Bridging edge heap for the extended Kruskal's algorithm.
std::vector<EdgeInf *> beHeap;
CmpEdgeInf beHeapCompare;
const VertID dimensionChangeVertexID;
};
}
#endif
|
