Open
Graph Drawing
Framework

 v.2012.05
 

UMLGraph.h
Go to the documentation of this file.
00001 /*
00002  * $Revision: 2299 $
00003  * 
00004  * last checkin:
00005  *   $Author: gutwenger $ 
00006  *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
00007  ***************************************************************/
00008  
00043 #ifdef _MSC_VER
00044 #pragma once
00045 #endif
00046 
00047 #ifndef OGDF_UML_GRAPH_H
00048 #define OGDF_UML_GRAPH_H
00049 
00050 
00051 #include <ogdf/basic/GraphAttributes.h>
00052 #include <ogdf/basic/AdjEntryArray.h>
00053 #include <ogdf/basic/SList.h>
00054 
00055 
00056 namespace ogdf {
00057 
00058 class OGDF_EXPORT UMLGraph : public GraphAttributes
00059 {
00060 public:
00061     // construction
00062 
00063     // dummy default constructor (place-holder)
00064     UMLGraph() : GraphAttributes(), m_pG(0) { }
00065 
00066     // creates UML graph in which each edge is an association
00067     explicit UMLGraph(Graph &G, long initAttributes = 0);
00068 
00069     // destruction
00070     virtual ~UMLGraph();
00071 
00072     //(re)initialization
00073     virtual void init(Graph &G, long initAttr)
00074     {
00075         m_pG = &G;
00076         GraphAttributes::init(G, initAttr);
00077         m_hierarchyParent.init(constGraph(), 0);
00078         m_upwardEdge.init(constGraph(), false);
00079     }
00080 
00081     operator const Graph &() const { return *m_pGraph; }
00082 
00083     //----------------------------------------------------------------------------
00084     //structural changes
00085     //merge generalizations at a common superclass
00086     void insertGenMergers();
00087     //insert mergers per node with given edges
00088     node doInsertMergers(node v, SList<edge> &inGens);
00089     void undoGenMergers();
00090 
00091     //replace (dense) subgraphs given in list clique by
00092     //inserting a center node connected to each node (=>star)
00093     //and deleting all edges between nodes in clique
00094     //returns center node
00095     void replaceByStar(List< List<node> > &cliques);
00096     
00097     //undo clique replacements
00098     void undoStars();
00099     //boolean switches restore of all hidden edges in single clique call
00100     void undoStar(node center, bool restoreAllEdges);
00101 
00102     //returns the size of a circular drawing for a clique around center v
00103     DRect cliqueRect(node v) 
00104     {
00105         return m_cliqueCircleSize[v];
00106     }
00107     DPoint cliquePos(node v)
00108     {
00109         return m_cliqueCirclePos[v];
00110     }
00111     
00112     //compute circle positions for all nodes around center
00113     //using the ordering given in this UMLGraph, calls 
00114     //ccP(List...)
00115     //rectMin is a temporary solution until compaction with constraints allows stretching
00116     //of rect to clique size, it gives the min(w,h) of the given fixed size rect around the clique
00117     void computeCliquePosition(node center, double rectMin);//, const adjEntry &startAdj);
00118     //compute positions for the nodes in adjNodes on a circle
00119     //tries to keep the relative placement of the nodes in the clique
00120     //rectangle (left, right,...) to avoid clique crossings of outgoing edges
00121     void computeCliquePosition(List<node> &adjNodes, node center, double rectMin = -1.0);
00122 
00123     //allow change, but should not be declared const
00124     Graph& pureGraph() const {return *m_pG;}
00125 
00126     //set status value
00127     //void setAlign(edge e, bool b) {m_alignEdge[e] = b;}
00128     //set status of edges to be specially embedded (if alignment)
00129     void setUpwards(adjEntry a, bool b) {m_upwardEdge[a] = b;}
00130     bool upwards(adjEntry a) const {return m_upwardEdge[a];}
00131 
00132     // writes attributed graph in GML format to file fileName
00133     void writeGML(const char *fileName);
00134 
00135     // writes attributed graph in GML format to output stream os
00136     void writeGML(ostream &os);
00137 
00138     //adjust the parent field for all nodes after insertion of 
00139     //mergers. If insertion is done per node via doinsert, adjust
00140     //has to be called afterwards. Otherwise, insertgenmergers calls it.
00141     void adjustHierarchyParents();
00142 
00143     //use the node position and bend position information to
00144     //derive an ordering of the edges around each node
00145     //this does not need to result in a correct combinatorial embedding
00146     void sortEdgesFromLayout();
00147 
00148     //-------------------
00149     //status retrieval
00150     //returns true if edge was inserted during clique replacement
00151     //TODO: check here how to guarantee that value is defined,
00152     //edgearray is only valid if there are cliques replaced
00153     bool isReplacement(edge e)
00154     {
00155         return m_replacementEdge[e];
00156     }
00157 
00158     const SListPure<node> &centerNodes() {return m_centerNodes;}
00159 
00160     //default size of inserted clique replacement center nodes
00161     void setDefaultCliqueCenterSize(double i) {m_cliqueCenterSize = max(i, 1.0);}
00162     double getDefaultCliqueCenterSize() {return m_cliqueCenterSize;}
00163 
00164     //-------------------------------------------------------------------------
00165     //modelling of association classes
00166     class AssociationClass {
00167     public:
00168         AssociationClass(edge e, double width = 1.0, double height = 1.0, 
00169             double x = 0.0, double y = 0.0)
00170             : m_width(width), m_height(height), m_x(x), m_y(y), m_edge(e), m_node(0)
00171         {
00172         
00173         }
00174         double m_width;
00175         double m_height;
00176         double m_x;
00177         double m_y;
00178         edge   m_edge;
00179         node   m_node;
00180     };
00181     const SListPure<AssociationClass*> &assClassList() const {return m_assClassList;}
00182 
00183     const AssociationClass*  assClass(edge e) const {return m_assClass[e];}
00184 
00185     //adds association class to edge e
00186     //void createAssociationClass(edge e, double width = 1.0, double height = 1.0)
00187     node createAssociationClass(edge e, double width = 1.0, double height = 1.0)
00188     {
00189         AssociationClass* ac = new AssociationClass(e, width, height);
00190         m_assClass[e] = ac;
00191         m_assClassList.pushBack(ac);
00192         //we already insert the node here, but not the edge
00193         //when we always insert this node here, we can remove the associationclass
00194         //class and information later on
00195         node v = m_pG->newNode();
00196         m_height[v] = ac->m_height;
00197         m_width[v]  = ac->m_width;
00198         m_associationClassModel[ac->m_edge] = v;
00199         ac->m_node = v;
00200         //guarantee correct angle at edge to edge connection
00201         if (m_attributes & GraphAttributes::nodeType)
00202         {
00203             m_vType[v] = Graph::associationClass;
00204         }
00205         return v;
00206 
00207     }
00208     //this modelling should only take place in the preprocessing steps
00209     //of the drawing algorithms?
00210     //insert representation for association class in underlying graph
00211     void modelAssociationClasses()
00212     {
00213         SListIterator<UMLGraph::AssociationClass*> it = m_assClassList.begin();
00214         while (it.valid())
00215         {
00216             modelAssociationClass((*it));
00217             it++;
00218         }//while
00219     }
00220     node modelAssociationClass(AssociationClass* ac)
00221     {
00222         node dummy = m_pG->split(ac->m_edge)->source();
00223         
00224         m_height[dummy] = 1; //just a dummy size
00225         m_width[dummy]  = 1;
00226         OGDF_ASSERT(ac->m_node)
00227         m_pG->newEdge(ac->m_node, dummy);
00228         
00229         return dummy;
00230     }
00231 
00232     void undoAssociationClasses()
00233     {
00234         SListIterator<UMLGraph::AssociationClass*> it = m_assClassList.begin();
00235         while (it.valid())
00236         {
00237             undoAssociationClass((*it));
00238             it++;
00239         }//while
00240     }
00241     //remove the modeling of the association class without removing the information
00242     void undoAssociationClass(AssociationClass* ac)
00243     {
00244         node v = m_associationClassModel[ac->m_edge];
00245         OGDF_ASSERT(v)
00246         OGDF_ASSERT(v->degree() == 1)
00247         if (v->degree() != 1) throw AlgorithmFailureException(afcLabel);
00248         //save layout information
00249         ac->m_x = x(v);
00250         ac->m_y = y(v);
00251 
00252         //remove node and unsplit edge
00253 
00254         //run around the dummy node connected to v
00255         adjEntry outAdj = v->firstAdj();
00256         adjEntry dummyAdj = outAdj->twin();
00257 
00258         node dummy = dummyAdj->theNode();
00259         OGDF_ASSERT(dummy->degree() == 3)
00260 
00261         //we do not delete the node if we already inserted it in create...
00262         //because it is a part of the graph now (in contrast to the split node)
00263         m_pG->delEdge(v->firstAdj()->theEdge());
00264         OGDF_ASSERT(v->degree() == 0)
00265 
00266         m_pG->unsplit(dummy);
00267     }//undoAssociationClass
00268 
00269 
00270 
00271 protected:
00272 
00273     node replaceByStar(List<node> &clique, NodeArray<int> &cliqueNum);
00274     DRect circularBound(node center);
00275 
00276 private:
00277 
00278     Graph *m_pG;
00279 
00280     //information about edges that are deleted in clique processing
00281     class CliqueInfo {
00282     public:
00283         CliqueInfo(node v, int i) : m_target(v), m_edgeIndex(i) {}
00284         node m_target;    //target node of deleted edge
00285         int  m_edgeIndex; //index of deleted edge, has to be restored
00286     };
00287     double m_cliqueCenterSize; //default size of inserted clique replacement center nodes
00288 
00289     SListPure<edge> m_mergeEdges;
00290     SListPure<node> m_centerNodes; //center nodes introduced at clique replacement
00291     EdgeArray<bool> m_replacementEdge; //used to mark clique replacement edges
00292                                        //may be we can join this with edge type
00293     NodeArray<DRect> m_cliqueCircleSize; //save the bounding box size of the 
00294                                          //circular drawing of the clique at center
00295     NodeArray<DPoint> m_cliqueCirclePos; //save the position of the node in the
00296                                          //circular drawing of the clique 
00297     //---------------------------------------------------
00298     //structures for association classes
00299     //may be replaced later by generic structures for different types
00300     SListPure<AssociationClass*> m_assClassList; //saves all accociation classes
00301     EdgeArray<AssociationClass*> m_assClass;     //association class for list
00302     EdgeArray<node> m_associationClassModel;     //modelled classes are stored
00303 
00304     
00305     //***************************************************
00306     //the following arrays are only set and updated in insertgenmergers
00307     //used to classify edges for embedding with alignment
00308     AdjEntryArray<bool> m_upwardEdge;
00309 
00310     //used to derive edge types for alignment in PlanRepUML
00311     //(same hierarchyparent => edge connects (half)brothers
00312     //only set during insertgenmergers to avoid the extra computation
00313     NodeArray<node> m_hierarchyParent;
00314 
00315 };
00316 
00317 
00318 } // end namespace ogdf
00319 
00320 #endif