Open
Graph Drawing
Framework

 v.2012.07
 

PlanRep.h
Go to the documentation of this file.
1 /*
2  * $Revision: 2583 $
3  *
4  * last checkin:
5  * $Author: gutwenger $
6  * $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012) $
7  ***************************************************************/
8 
45 //PlanRep should not know about generalizations and association,
46 //but we already set types in Attributedgraph, therefore set them
47 //in PlanRep, too
48 
49 #ifdef _MSC_VER
50 #pragma once
51 #endif
52 
53 #ifndef OGDF_PLANREP_H
54 #define OGDF_PLANREP_H
55 
56 
57 #include <ogdf/basic/GraphCopy.h>
60 #include <ogdf/basic/Layout.h>
63 
64 
65 namespace ogdf {
66 
67 
75 {
76 public:
79  {
80  Deg1RestoreInfo() : m_eOriginal(0), m_deg1Original(0), m_adjRef(0) { }
81  Deg1RestoreInfo(edge eOrig, node deg1Orig, adjEntry adjRef)
82  : m_eOriginal(eOrig), m_deg1Original(deg1Orig), m_adjRef(adjRef) { }
83 
87  };
88 
89 
90  /* @{
91  * \brief Creates a planarized representation of graph \a G.
92  */
93  PlanRep(const Graph& G);
94 
98  PlanRep(const GraphAttributes& AG);
99 
100  virtual ~PlanRep() {}
101 
102 
104 
110 
114  int numberOfCCs() const {
115  return m_nodesInCC.size();
116  }
117 
121  int currentCC() const {
122  return m_currentCC;
123  }
124 
130  const List<node> &nodesInCC(int i) const {
131  return m_nodesInCC[i];
132  }
133 
137  const List<node> &nodesInCC() const {
138  return m_nodesInCC[m_currentCC];
139  }
140 
149  void initCC(int i);
150 
151 
153 
157 
164  return m_expandAdj[v];
165  }
166 
168  return m_expandAdj[v];
169  }
170 
172 
176 
182  return m_boundaryAdj[v];
183  }
184 
190  return m_boundaryAdj[v];
191  }
192 
193  //edge on the clique boundary, adjSource
195  setEdgeTypeOf(e, edgeTypeOf(e) | cliquePattern());
196  }
198  return ((edgeTypeOf(e) & cliquePattern()) == cliquePattern());
199  }
200 
201 
203 
207 
213  return m_vType[v];
214  }
215 
221  return m_vType[v];
222  }
223 
232  inline bool isVertex(node v)
233  {
234  return ( (typeOf(v) == Graph::vertex) ||
235  (typeOf(v) == Graph::associationClass));
236  }
237 
242  nodeType nodeTypeOf(node v)
243  {
244  return m_nodeTypes[v];
245  }
246 
251  void setCrossingType(node v)
252  {
253  m_nodeTypes[v] |= ntTerCrossing << ntoTertiary;
254  }
255 
260  bool isCrossingType(node v)
261  {
262  return (m_nodeTypes[v] &= (ntTerCrossing << ntoTertiary)) != 0;
263  }
264 
266 
270 
275  EdgeType typeOf(edge e) const {
276  return m_eType[e];
277  }
278 
284  return m_eType[e];
285  }
286 
291  edgeType& oriEdgeTypes(edge e)
292  {
293  return m_oriEdgeTypes[e];
294  }
295 
300  edgeType edgeTypeOf(edge e)
301  {
302  return m_edgeTypes[e];
303  }
304 
309  edgeType& edgeTypes(edge e)
310  {
311  return m_edgeTypes[e];
312  }
313 
319  void setEdgeTypeOf(edge e, edgeType et)
320  {
321  m_edgeTypes[e] = et;
322  }
323 
332  void setType(edge e, EdgeType et)
333  {
334  m_eType[e] = et;
335  switch (et)
336  {
337  case Graph::association: m_edgeTypes[e] = etcPrimAssociation;break;
338  case Graph::generalization: m_edgeTypes[e] = etcPrimGeneralization;
339  break;
340  case Graph::dependency: m_edgeTypes[e] = etcPrimDependency; break;
341  default: break;
342  }
343  }
344 
345  //-------------------------------------------------------------------------
346  //new edge types
347  //to set or check edge types use the pattern function in the private section
348 
349  //-------------------
350  //primary level types
351 
354  bool check = (((m_edgeTypes[e] & etpPrimary) & etcPrimGeneralization) == etcPrimGeneralization);
355  return check;
356  }
357 
360  setPrimaryType(e, etcPrimGeneralization);
361 
362  //preliminary set old array too
363  m_eType[e] = generalization; //can be removed if edgetypes work properly
364  }
365 
367  bool isDependency(edge e) {
368  bool check = (((m_edgeTypes[e] & etpPrimary) & etcPrimDependency) == etcPrimDependency);
369  return check;
370  }
371 
373  void setDependency(edge e) {
374  setPrimaryType(e, etcPrimDependency);
375 
376  //preliminary set old array too
377  m_eType[e] = dependency; //can be removed if edgetypes work properly
378  }
379 
382  setPrimaryType(e, etcPrimAssociation);
383 
384  //preliminary set old array too
385  m_eType[e] = association; //can be removed if edgetypes work properly
386  }
387 
388  //------------------
389  //second level types
390 
391  //in contrast to setsecondarytype: do not delete old value
392 
394  void setExpansion(edge e) {
395  m_edgeTypes[e] |= expansionPattern();
396 
397  //preliminary set old array too
398  m_expansionEdge[e] = 1;//can be removed if edgetypes work properly
399  }
400 
402  bool isExpansion(edge e) {
403  return ((m_edgeTypes[e] & expansionPattern()) == expansionPattern());
404  }
405 
406  //should add things like cluster and clique boundaries that need rectangle shape
407 
409  bool isBoundary(edge e) {
410  return isCliqueBoundary(e); }
411 
412  //--------------
413  //tertiary types
414 
416  void setAssClass(edge e)
417  {
418  m_edgeTypes[e] |= assClassPattern();
419  }
420 
422  bool isAssClass(edge e)
423  {
424  return ((m_edgeTypes[e] & assClassPattern()) == assClassPattern());
425  }
426 
427 
428  //------------------
429  //fourth level types
430 
432  void setBrother(edge e) {
433  m_edgeTypes[e] |= brotherPattern();
434  }
435 
438  m_edgeTypes[e] |= halfBrotherPattern();
439  }
440 
442  bool isBrother(edge e) {
443  return ( (((m_edgeTypes[e] & etpFourth) & brotherPattern())>> etoFourth) == etcBrother);
444  }
445 
447  bool isHalfBrother(edge e) {
448  return ( (((m_edgeTypes[e] & etpFourth) & halfBrotherPattern())>> etoFourth) == etcHalfBrother);
449  }
450 
451  //-----------------
452  //set generic types
453 
454  edgeType edgeTypeAND(edge e, edgeType et) {m_edgeTypes[e] &= et; return m_edgeTypes[e];}
455 
456  edgeType edgeTypeOR(edge e, edgeType et) {m_edgeTypes[e] |= et; return m_edgeTypes[e];}
457 
458  //set primary edge type of edge e to primary edge type in et
459  //deletes old primary value
461  m_edgeTypes[e] &= 0xfffffff0;
462  m_edgeTypes[e] |= (etpPrimary & et);
463  }
464 
466  m_edgeTypes[e] &= 0xffffff0f;
467  m_edgeTypes[e] |= (etpSecondary & ( et << etoSecondary));
468  }
469 
470  //sets primary type to bitwise AND of et's primary value and old value
471  edgeType edgeTypePrimaryAND(edge e, edgeType et) {m_edgeTypes[e] &= (etpAll & et); return m_edgeTypes[e];}
472 
473  //sets primary type to bitwise OR of et's primary value and old value
474  edgeType edgeTypePrimaryOR(edge e, edgeType et) {m_edgeTypes[e] |= et; return m_edgeTypes[e];}
475 
476  //set user defined type locally
477  void setUserType(edge e, edgeType et)
478  {
479  OGDF_ASSERT( et < 147);
480  m_edgeTypes[e] |= (et << etoUser);
481  }
482 
483  bool isUserType(edge e, edgeType et)
484  {
485  OGDF_ASSERT( et < 147);
486  return ( (m_edgeTypes[e] & (et << etoUser)) == (et << etoUser));
487  }
488 
489  //---------------
490  //
491  // old edge types
492 
493  //this is pure nonsense, cause we have uml-edgetype and m_etype, and should be able to
494  //use them with different types, but as long as they arent used correctly (switch instead of xor),
495  //use this function to return if e is expansionedge
496  //if it is implemented correctly later, delete the array and return m_etype == Graph::expand
497  //(the whole function then is obsolete, cause you can check it directly, but for convenience...)
498  //should use genexpand, nodeexpand, dissect instead of bool
499  void setExpansionEdge(edge e, int expType) {
500  m_expansionEdge[e] = expType;
501  }
502 
503  bool isExpansionEdge(edge e) const {
504  return (m_expansionEdge[e] > 0);
505  }
506 
507  int expansionType(edge e) const { return m_expansionEdge[e]; }
508 
509  //precondition normalized
510  bool isDegreeExpansionEdge(edge e) const {
511  //return (m_eType[e] == Graph::expand);
512  return ( m_expansionEdge[e] == 2);
513  }
514 
515 
517 
523 
524 
526  const NodeArray<double> &widthOrig() const {
527  return m_pGraphAttributes->width();
528  }
529 
531  double widthOrig(node v) const {
532  return m_pGraphAttributes->width(v);
533  }
534 
536  const NodeArray<double> &heightOrig() const {
537  return m_pGraphAttributes->height();
538  }
539 
541  double heightOrig(node v) const {
542  return m_pGraphAttributes->height(v);
543  }
544 
546  EdgeType typeOrig(edge e) const {
547  return m_pGraphAttributes->type(e);
548  }
549 
552  return *m_pGraphAttributes;
553  }
554 
556 
560 
561  // Expands nodes with degree > 4 and merge nodes for generalizations
562  void expand(bool lowDegreeExpand = false);
563 
564  void expandLowDegreeVertices(OrthoRep &OR);
565 
566  void collapseVertices(const OrthoRep &OR, Layout &drawing);
567 
568  void removeCrossing(node v); //removes the crossing at node v
569 
570  //model a boundary around a star subgraph centered at center
571  //and keep external face information (outside the clique
572  void insertBoundary(node center, adjEntry& adjExternal);
573 
574 
576 
580 
582  virtual edge split(edge e);
583 
584 
585  //returns node which was expanded using v
586  node expandedNode(node v) const { return m_expandedNode[v]; }
587 
588  void setExpandedNode(node v, node w) { m_expandedNode[v] = w; }
589 
590 
592 
596 
602  node newCopy(node vOrig, Graph::NodeType vType);
603 
611  edge newCopy(node v, adjEntry adjAfter, edge eOrig);
612 
621  edge newCopy(node v, adjEntry adjAfter, edge eOrig, CombinatorialEmbedding &E);
622 
623 
625 
629 
630  // embeds current copy
631  bool embed();
632 
633  // removes all crossing nodes which are actually only two "touching" edges
634  void removePseudoCrossings();
635 
636  // re-inserts edge eOrig by "crossing" the edges in crossedEdges;
637  // splits each edge in crossedEdges
638  // Precond.: eOrig is an edge in the original graph,
639  // the edges in crossedEdges are in this graph
640  void insertEdgePath(edge eOrig, const SList<adjEntry> &crossedEdges);
641 
642  // same as insertEdgePath, but assumes that the graph is embedded
643  void insertEdgePathEmbedded(
644  edge eOrig,
646  const SList<adjEntry> &crossedEdges);
647 
648  // removes the complete edge path for edge eOrig
649  // Precond.: eOrig s an edge in the original graph
650  void removeEdgePathEmbedded(CombinatorialEmbedding &E,
651  edge eOrig,
652  FaceSetPure &newFaces) {
653  GraphCopy::removeEdgePathEmbedded(E,eOrig,newFaces);
654  }
655 
657 
671  edge insertCrossing(
672  edge &crossingEdge,
673  edge crossedEdge,
674  bool topDown);
675 
677 
682 
690  void removeDeg1Nodes(Stack<Deg1RestoreInfo> &S, const NodeArray<bool> &mark);
691 
697  void restoreDeg1Nodes(Stack<Deg1RestoreInfo> &S, List<node> &deg1s);
698 
700 
701 protected:
702 
704  int m_numCC;
705 
707 
709 
710  //------------
711  //object types
712 
713  //set the type of eCopy according to the type of eOrig
714  //should be virtual if PlanRepUML gets its own
715  void setCopyType(edge eCopy, edge eOrig);
716 
717  //helper to cope with the edge types, shifting to the right place
725 
726 
727  void removeUnnecessaryCrossing(
728  adjEntry adjA1,
729  adjEntry adjA2,
730  adjEntry adjB1,
731  adjEntry adjB2);
732 
733 //--------------------------------------------------------------------------
734 
736 
738 
741 
742  //clique handling: We save an adjEntry of the first edge of an inserted
743  //boundary around a clique at its center v
745 
746  //zusammenlegbare Typen
747  EdgeArray<int> m_expansionEdge; //1 genmerge, 2 degree (2 highdegree, 3 lowdegree)
749 
750  //m_edgeTypes stores semantic edge type information on several levels:
751  //primary type: generalization, association,...
752  //secondary type: merger,...
753  //tertiary type: vertical in hierarchy, inner, outer, ...
754  //fourth type: neighbour relation (brother, cousin in hierarchy)
755  //user types: user defined for local changes
756  EdgeArray<edgeType> m_edgeTypes; //store all type information
757 
758  //workaround fuer typsuche in insertedgepathembed
759  //speichere kopietyp auf originalen
760  //maybe it's enough to set gen/ass without extra array
762 
763  EdgeArray<edge> m_eAuxCopy; // auxiliary (GraphCopy::initByNodes())
764 
765 };//PlanRep
766 
767 } // end namespace ogdf
768 
769 
770 #endif