00001
00002
00003
00004
00005
00006
00007
00008
00054
00055
00056
00057
00058 #ifdef _MSC_VER
00059 #pragma once
00060 #endif
00061
00062 #ifndef OGDF_PLANREP_H
00063 #define OGDF_PLANREP_H
00064
00065
00066 #include <ogdf/basic/GraphCopy.h>
00067 #include <ogdf/planarity/EdgeTypePatterns.h>
00068 #include <ogdf/planarity/NodeTypePatterns.h>
00069 #include <ogdf/basic/Layout.h>
00070 #include <ogdf/orthogonal/OrthoRep.h>
00071 #include <ogdf/basic/GraphAttributes.h>
00072
00073
00074 namespace ogdf {
00075
00076
00083 class OGDF_EXPORT PlanRep : public GraphCopy
00084 {
00085 public:
00087 struct Deg1RestoreInfo
00088 {
00089 Deg1RestoreInfo() : m_eOriginal(0), m_deg1Original(0), m_adjRef(0) { }
00090 Deg1RestoreInfo(edge eOrig, node deg1Orig, adjEntry adjRef)
00091 : m_eOriginal(eOrig), m_deg1Original(deg1Orig), m_adjRef(adjRef) { }
00092
00093 edge m_eOriginal;
00094 node m_deg1Original;
00095 adjEntry m_adjRef;
00096 };
00097
00098
00099
00100
00101
00102 PlanRep(const Graph& G);
00103
00107 PlanRep(const GraphAttributes& AG);
00108
00109 virtual ~PlanRep() {}
00110
00111
00113
00119
00123 int numberOfCCs() const {
00124 return m_nodesInCC.size();
00125 }
00126
00130 int currentCC() const {
00131 return m_currentCC;
00132 }
00133
00139 const List<node> &nodesInCC(int i) const {
00140 return m_nodesInCC[i];
00141 }
00142
00146 const List<node> &nodesInCC() const {
00147 return m_nodesInCC[m_currentCC];
00148 }
00149
00158 void initCC(int i);
00159
00160
00162
00166
00172 adjEntry expandAdj(node v) const {
00173 return m_expandAdj[v];
00174 }
00175
00176 adjEntry& expandAdj(node v) {
00177 return m_expandAdj[v];
00178 }
00179
00181
00185
00190 adjEntry boundaryAdj(node v) const {
00191 return m_boundaryAdj[v];
00192 }
00193
00198 adjEntry& boundaryAdj(node v){
00199 return m_boundaryAdj[v];
00200 }
00201
00202
00203 void setCliqueBoundary(edge e) {
00204 setEdgeTypeOf(e, edgeTypeOf(e) | cliquePattern());
00205 }
00206 bool isCliqueBoundary(edge e) {
00207 return ((edgeTypeOf(e) & cliquePattern()) == cliquePattern());
00208 }
00209
00210
00212
00216
00221 Graph::NodeType typeOf(node v) const {
00222 return m_vType[v];
00223 }
00224
00229 Graph::NodeType& typeOf(node v) {
00230 return m_vType[v];
00231 }
00232
00241 inline bool isVertex(node v)
00242 {
00243 return ( (typeOf(v) == Graph::vertex) ||
00244 (typeOf(v) == Graph::associationClass));
00245 }
00246
00251 nodeType nodeTypeOf(node v)
00252 {
00253 return m_nodeTypes[v];
00254 }
00255
00260 void setCrossingType(node v)
00261 {
00262 m_nodeTypes[v] |= ntTerCrossing << ntoTertiary;
00263 }
00264
00269 bool isCrossingType(node v)
00270 {
00271 return (m_nodeTypes[v] &= (ntTerCrossing << ntoTertiary)) != 0;
00272 }
00273
00275
00279
00284 EdgeType typeOf(edge e) const {
00285 return m_eType[e];
00286 }
00287
00292 EdgeType& typeOf(edge e) {
00293 return m_eType[e];
00294 }
00295
00300 edgeType& oriEdgeTypes(edge e)
00301 {
00302 return m_oriEdgeTypes[e];
00303 }
00304
00309 edgeType edgeTypeOf(edge e)
00310 {
00311 return m_edgeTypes[e];
00312 }
00313
00318 edgeType& edgeTypes(edge e)
00319 {
00320 return m_edgeTypes[e];
00321 }
00322
00328 void setEdgeTypeOf(edge e, edgeType et)
00329 {
00330 m_edgeTypes[e] = et;
00331 }
00332
00341 void setType(edge e, EdgeType et)
00342 {
00343 m_eType[e] = et;
00344 switch (et)
00345 {
00346 case Graph::association: m_edgeTypes[e] = etcPrimAssociation;break;
00347 case Graph::generalization: m_edgeTypes[e] = etcPrimGeneralization;
00348 break;
00349 case Graph::dependency: m_edgeTypes[e] = etcPrimDependency; break;
00350 default: break;
00351 }
00352 }
00353
00354
00355
00356
00357
00358
00359
00360
00362 bool isGeneralization(edge e) {
00363 bool check = (((m_edgeTypes[e] & etpPrimary) & etcPrimGeneralization) == etcPrimGeneralization);
00364 return check;
00365 }
00366
00368 void setGeneralization(edge e) {
00369 setPrimaryType(e, etcPrimGeneralization);
00370
00371
00372 m_eType[e] = generalization;
00373 }
00374
00376 bool isDependency(edge e) {
00377 bool check = (((m_edgeTypes[e] & etpPrimary) & etcPrimDependency) == etcPrimDependency);
00378 return check;
00379 }
00380
00382 void setDependency(edge e) {
00383 setPrimaryType(e, etcPrimDependency);
00384
00385
00386 m_eType[e] = dependency;
00387 }
00388
00390 void setAssociation(edge e) {
00391 setPrimaryType(e, etcPrimAssociation);
00392
00393
00394 m_eType[e] = association;
00395 }
00396
00397
00398
00399
00400
00401
00403 void setExpansion(edge e) {
00404 m_edgeTypes[e] |= expansionPattern();
00405
00406
00407 m_expansionEdge[e] = 1;
00408 }
00409
00411 bool isExpansion(edge e) {
00412 return ((m_edgeTypes[e] & expansionPattern()) == expansionPattern());
00413 }
00414
00415
00416
00418 bool isBoundary(edge e) {
00419 return isCliqueBoundary(e); }
00420
00421
00422
00423
00425 void setAssClass(edge e)
00426 {
00427 m_edgeTypes[e] |= assClassPattern();
00428 }
00429
00431 bool isAssClass(edge e)
00432 {
00433 return ((m_edgeTypes[e] & assClassPattern()) == assClassPattern());
00434 }
00435
00436
00437
00438
00439
00441 void setBrother(edge e) {
00442 m_edgeTypes[e] |= brotherPattern();
00443 }
00444
00446 void setHalfBrother(edge e) {
00447 m_edgeTypes[e] |= halfBrotherPattern();
00448 }
00449
00451 bool isBrother(edge e) {
00452 return ( (((m_edgeTypes[e] & etpFourth) & brotherPattern())>> etoFourth) == etcBrother);
00453 }
00454
00456 bool isHalfBrother(edge e) {
00457 return ( (((m_edgeTypes[e] & etpFourth) & halfBrotherPattern())>> etoFourth) == etcHalfBrother);
00458 }
00459
00460
00461
00462
00463 edgeType edgeTypeAND(edge e, edgeType et) {m_edgeTypes[e] &= et; return m_edgeTypes[e];}
00464
00465 edgeType edgeTypeOR(edge e, edgeType et) {m_edgeTypes[e] |= et; return m_edgeTypes[e];}
00466
00467
00468
00469 void setPrimaryType(edge e, edgeType et) {m_edgeTypes[e] &= 0xfffffff0;
00470 m_edgeTypes[e] |= (etpPrimary & et); }
00471
00472 void setSecondaryType(edge e, edgeType et) {m_edgeTypes[e] &= 0xffffff0f;
00473 m_edgeTypes[e] |= (etpSecondary & ( et << etoSecondary)); }
00474
00475
00476 edgeType edgeTypePrimaryAND(edge e, edgeType et) {m_edgeTypes[e] &= (etpAll & et); return m_edgeTypes[e];}
00477
00478
00479 edgeType edgeTypePrimaryOR(edge e, edgeType et) {m_edgeTypes[e] |= et; return m_edgeTypes[e];}
00480
00481
00482 void setUserType(edge e, edgeType et)
00483 {
00484 OGDF_ASSERT( et < 147);
00485 m_edgeTypes[e] |= (et << etoUser);
00486 }
00487
00488 bool isUserType(edge e, edgeType et)
00489 {
00490 OGDF_ASSERT( et < 147);
00491 return ( (m_edgeTypes[e] & (et << etoUser)) == (et << etoUser));
00492 }
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504 void setExpansionEdge(edge e, int expType) {
00505 m_expansionEdge[e] = expType;
00506 }
00507
00508 bool isExpansionEdge(edge e) const {
00509 return (m_expansionEdge[e] > 0);
00510 }
00511
00512 int expansionType(edge e) const { return m_expansionEdge[e]; }
00513
00514
00515 bool isDegreeExpansionEdge(edge e) const {
00516
00517 return ( m_expansionEdge[e] == 2);
00518 }
00519
00520
00522
00528
00529
00531 const NodeArray<double> &widthOrig() const {
00532 return m_pGraphAttributes->width();
00533 }
00534
00536 double widthOrig(node v) const {
00537 return m_pGraphAttributes->width(v);
00538 }
00539
00541 const NodeArray<double> &heightOrig() const {
00542 return m_pGraphAttributes->height();
00543 }
00544
00546 double heightOrig(node v) const {
00547 return m_pGraphAttributes->height(v);
00548 }
00549
00551 EdgeType typeOrig(edge e) const {
00552 return m_pGraphAttributes->type(e);
00553 }
00554
00556 const GraphAttributes &getGraphAttributes() const {
00557 return *m_pGraphAttributes;
00558 }
00559
00561
00565
00566
00567 void expand(bool lowDegreeExpand = false);
00568
00569 void expandLowDegreeVertices(OrthoRep &OR);
00570
00571 void collapseVertices(const OrthoRep &OR, Layout &drawing);
00572
00573 void removeCrossing(node v);
00574
00575
00576
00577 void insertBoundary(node center, adjEntry& adjExternal);
00578
00579
00581
00585
00587 virtual edge split(edge e);
00588
00589
00590
00591 node expandedNode(node v) const { return m_expandedNode[v]; }
00592
00593 void setExpandedNode(node v, node w) { m_expandedNode[v] = w; }
00594
00595
00597
00601
00607 node newCopy(node vOrig, Graph::NodeType vType);
00608
00616 edge newCopy(node v, adjEntry adjAfter, edge eOrig);
00617
00626 edge newCopy(node v, adjEntry adjAfter, edge eOrig, CombinatorialEmbedding &E);
00627
00628
00630
00634
00635
00636 bool embed();
00637
00638
00639 void removePseudoCrossings();
00640
00641
00642
00643
00644
00645 void insertEdgePath(edge eOrig, const SList<adjEntry> &crossedEdges);
00646
00647
00648 void insertEdgePathEmbedded(
00649 edge eOrig,
00650 CombinatorialEmbedding &E,
00651 const SList<adjEntry> &crossedEdges);
00652
00653
00654
00655 void removeEdgePathEmbedded(CombinatorialEmbedding &E,
00656 edge eOrig,
00657 FaceSetPure &newFaces) {
00658 GraphCopy::removeEdgePathEmbedded(E,eOrig,newFaces);
00659 }
00660
00661
00662
00663
00664
00665
00666 edge insertCrossing(edge& crossingEdge,
00667 const edge crossedEdge,
00668 bool topDown);
00669
00671
00676
00684 void removeDeg1Nodes(Stack<Deg1RestoreInfo> &S, const NodeArray<bool> &mark);
00685
00691 void restoreDeg1Nodes(Stack<Deg1RestoreInfo> &S, List<node> °1s);
00692
00694
00695 protected:
00696
00697 int m_currentCC;
00698 int m_numCC;
00699
00700 Array<List<node> > m_nodesInCC;
00701
00702 const GraphAttributes* m_pGraphAttributes;
00703
00704
00705
00706
00707
00708
00709 void setCopyType(edge eCopy, edge eOrig);
00710
00711
00712 edgeType generalizationPattern() {return etcPrimGeneralization;}
00713 edgeType associationPattern() {return etcPrimAssociation;}
00714 edgeType expansionPattern() {return etcSecExpansion << etoSecondary;}
00715 edgeType assClassPattern() {return etcAssClass << etoTertiary;}
00716 edgeType brotherPattern() {return etcBrother << etoFourth;}
00717 edgeType halfBrotherPattern() {return etcHalfBrother << etoFourth;}
00718 edgeType cliquePattern() {return etcSecClique << etoSecondary;}
00719
00720
00721 void removeUnnecessaryCrossing(
00722 adjEntry adjA1,
00723 adjEntry adjA2,
00724 adjEntry adjB1,
00725 adjEntry adjB2);
00726
00727
00728
00729 NodeArray<NodeType> m_vType;
00730
00731 NodeArray<nodeType> m_nodeTypes;
00732
00733 NodeArray<node> m_expandedNode;
00734 NodeArray<adjEntry> m_expandAdj;
00735
00736
00737
00738 NodeArray<adjEntry> m_boundaryAdj;
00739
00740
00741 EdgeArray<int> m_expansionEdge;
00742 EdgeArray<EdgeType> m_eType;
00743
00744
00745
00746
00747
00748
00749
00750 EdgeArray<edgeType> m_edgeTypes;
00751
00752
00753
00754
00755 EdgeArray<edgeType> m_oriEdgeTypes;
00756
00757 EdgeArray<edge> m_eAuxCopy;
00758
00759 };
00760
00761 }
00762
00763
00764 #endif