Version: 1.1.1 (using KDE KDE 3.1.2) Installed from: Unspecified Linux OS: Linux This is an extradifficult feature. The only product which makes good automatic layouts of diagrams is Rational Rose. However, I think this is a good challenge for an open-source product.
Presumably this is after importing classes. A challenge it would be!
Subject: Re: [Uml-devel] New: Automatic layout of diagrams > This is an extradifficult feature. The only product which makes good > automatic layouts of diagrams is Rational Rose. However, I think this is a > good challenge for an open-source product. rose makes terrible layouts. there are tools that do significantly better. i think argo finally got a layout algorithm that does pretty well. there was a paper published in softvis this year describing a really nice algorithm. i can't remember who wrote it, but it did generate nice pictures. and in color too. andy
Subject: Re: [Uml-devel] Automatic layout of diagrams Jonathan Riddell <jr@jriddell.org> [031103 19:54]: > Presumably this is after importing classes. > > A challenge it would be! I like to add, that we may not need to reinvent the wheel. I've seen people using the Graphviz (http://www.research.att.com/sw/tools/graphviz/) package for this purpose. This package is already used by KCachegrind for the call map and for this Konqueror plugin showing the discspace usage. Steinchen
Subject: Re: Automatic layout of diagrams > I like to add, that we may not need to reinvent the wheel. I've seen people > using the Graphviz (http://www.research.att.com/sw/tools/graphviz/) package > for this purpose. This package is already used by KCachegrind for the call > map and for this Konqueror plugin showing the discspace usage. I used to use this package some time ago. It makes layouts of oriented acyclic graphs. Unfortunately, this is not enough for the layout of arbitrary graphs.
This would be a really kick-ass feature ! Even if dot doesn't make perfec layouts, we could try to see if umbrello couldn't propose a not perfect layout that the user would modify. This would be a first step before a really good working algorithm. Because importing a lot of classes while minimizing crossing arrows is a pain :)
An early alpha version of this is now in the 3.5 branch of SVN. It uses graphviz. It doesn't work very well yet so it might not make it into the final release.
SVN commit 442912 by okellogg: CCBUG:67059 - Fix autoconf detection of graphviz. This just shows how it would be done - IF we were doing it. To activate, remove the "dnl" from the start of the lines following the line "dnl Not GPL compatible" in configure.in.in. M +14 -4 configure.in.in M +3 -5 umbrello/Makefile.am M +3 -3 umbrello/autolayout/Makefile.am M +11 -7 umbrello/uml.cpp M +4 -2 umbrello/uml.h --- branches/KDE/3.5/kdesdk/umbrello/configure.in.in #442911:442912 @@ -9,13 +9,23 @@ fi dnl Not GPL compatible -dnl AC_CHECK_HEADER(graphviz/dot.h, +dnl AC_PATH_PROG(DOT_FOUND, dot, no) +dnl KDE_CHECK_HEADER(graphviz/pathgeom.h, dnl [kde_have_graphviz=yes], dnl [kde_have_graphviz=no]) -dnl -dnl if test "$kde_have_graphviz" = "no"; then -dnl DO_NOT_COMPILE="$DO_NOT_COMPILE umbrello" +dnl +dnl if test "$DOT_FOUND" != "no" -a "$kde_have_graphviz" = "yes"; then +dnl CXXFLAGS="$CXXFLAGS -DHAVE_DOT" +dnl GRAPHVIZ_LIB=`pkg-config --libs libgraph` +dnl AUTOLAYOUT_DIR="autolayout" +dnl AUTOLAYOUT_LIBS="autolayout/libautolayout.la $GRAPHVIZ_LIB -ldotgen -lgvc" +dnl else +dnl AUTOLAYOUT_DIR="" +dnl AUTOLAYOUT_LIBS="" dnl fi +dnl AC_SUBST(AUTOLAYOUT_DIR) +dnl AC_SUBST(AUTOLAYOUT_LIBS) + AC_LANG_RESTORE --- branches/KDE/3.5/kdesdk/umbrello/umbrello/Makefile.am #442911:442912 @@ -99,11 +99,9 @@ widget_utils.cpp \ worktoolbar.cpp -#umbrello_LDADD = ./refactoring/librefactoring.la ./classparser/libclassparser.la ./clipboard/libclipboard.la ./dialogs/libdialogs.la ./codegenerators/libcodegenerator.la ./autolayout/libautolayout.la $(LIB_KDEPRINT) $(LIB_KIO) -umbrello_LDADD = ./refactoring/librefactoring.la ./classparser/libclassparser.la ./clipboard/libclipboard.la ./dialogs/libdialogs.la ./codegenerators/libcodegenerator.la $(LIB_KDEPRINT) $(LIB_KIO) +umbrello_LDADD = ./refactoring/librefactoring.la ./classparser/libclassparser.la ./clipboard/libclipboard.la ./dialogs/libdialogs.la ./codegenerators/libcodegenerator.la $(AUTOLAYOUT_LIBS) $(LIB_KDEPRINT) $(LIB_KIO) -#SUBDIRS = classparser dialogs clipboard pics codegenerators headings refactoring autolayout -SUBDIRS = classparser dialogs clipboard pics codegenerators headings refactoring +SUBDIRS = $(AUTOLAYOUT_DIR) classparser dialogs clipboard pics codegenerators headings refactoring KDE_ICON=AUTO @@ -116,7 +114,7 @@ mime_DATA = x-umbrello.desktop #INCLUDES= -Idialogs -Irefactoring $(all_includes) -I/usr/include/graphviz/ -INCLUDES= -Idialogs -Irefactoring $(all_includes) -I/usr/include/graphviz/ +INCLUDES= -Idialogs -Irefactoring $(all_includes) METASOURCES = AUTO --- branches/KDE/3.5/kdesdk/umbrello/umbrello/autolayout/Makefile.am #442911:442912 @@ -1,8 +1,8 @@ noinst_LTLIBRARIES = libautolayout.la -INCLUDES = -I/usr/include/graphviz/ -Idialogs -Irefactoring \ +INCLUDES = -Idialogs -Irefactoring \ $(all_includes) -AM_CXXFLAGS = -I/usr/include/graphviz/ +#AM_CXXFLAGS = -I/usr/include/graphviz/ libautolayout_la_METASOURCES = AUTO #noinst_HEADERS = node.h autolayout.h autolayoutdlg.h autolayouter.h canvas.h \ @@ -14,6 +14,6 @@ graphvizgraph.cpp graphviznode.cpp dotautolayouter.cpp #libautolayout_la_LIBADD = /usr/lib/graphviz/libdotneato.la -libautolayout_la_LDFLAGS = -ldotneato -L/usr/lib/graphviz +#libautolayout_la_LDFLAGS = -ldotneato -L/usr/lib/graphviz --- branches/KDE/3.5/kdesdk/umbrello/umbrello/uml.cpp #442911:442912 @@ -59,7 +59,9 @@ #include "umllistview.h" #include "umlviewlist.h" #include "worktoolbar.h" -// #include "autolayout/autolayoutdlg.h"//dimitri +#ifdef HAVE_DOT +# include "autolayout/autolayoutdlg.h" //dimitri +#endif #include "clipboard/umlclipboard.h" #include "dialogs/classwizard.h" @@ -216,8 +218,10 @@ classDiagram = new KAction( i18n( "&Class Diagram..." ), SmallIconSet("umbrello_diagram_class"), 0, this, SLOT( slotClassDiagram() ), actionCollection(), "new_class_diagram" ); - // autolayout = new KAction(i18n("&Autolayout..."),0,0,this,SLOT(slotAutolayout()), - // actionCollection(),"autolayout"); +#if defined (HAVE_DOT) + autolayout = new KAction(i18n("&Autolayout..."),0,0,this,SLOT(slotAutolayout()), + actionCollection(),"autolayout"); +#endif sequenceDiagram= new KAction( i18n( "&Sequence Diagram..." ), SmallIconSet("umbrello_diagram_sequence"), 0, this, SLOT( slotSequenceDiagram() ), actionCollection(), "new_sequence_diagram" ); @@ -1685,12 +1689,12 @@ //m_tabWidget->moveTab( m_tabWidget->currentPageIndex(), m_tabWidget->currentPageIndex() + 1 ); } -/* void UMLApp::slotAutolayout(){ - QDialog* d = new AutolayoutDlg(getCurrentView()); - d->show(); +#ifdef HAVE_DOT + QDialog* d = new AutolayoutDlg(getCurrentView()); + d->show(); +#endif } -*/ KTabWidget* UMLApp::tabWidget() { return m_tabWidget; --- branches/KDE/3.5/kdesdk/umbrello/umbrello/uml.h #442911:442912 @@ -501,7 +501,7 @@ /** * Autolayouts the current class diagram */ - //void slotAutolayout(); + void slotAutolayout(); /** * Changes the statusbar contents for the standard label @@ -887,7 +887,9 @@ KAction* classWizard; KAction* deleteSelectedWidget; KAction* deleteDiagram; - //KAction* autolayout; +#ifdef HAVE_DOT + KAction* autolayout; +#endif KAction* changeTabLeft; KAction* changeTabRight;
OPTIMIZED DIAGRAM DRAWING: I am unfamiliar with how the mentioned layout managers work however automatically connecting classes without the associations etc. being hidden behind/going through classes. A pathfinding algorithm should be implemented so you can connect classes to enable that their connection could be followed from one class to the other without going through/behind other classes. All turns should be 90 deg unless otherwise specified. This could be achieved using the waypoints already implemented and finding a clear path from waypoint to waypoint. Also if lines have to cross each other in order to follow a shortest path to target, an OMEGA like structure should indicate that the lines are not connected. Another option should be to ask the program to sort and place so lines did not cross if at all possible. You need to implement a refresh that goes through all connections in case somebody moves classes around. Probably an automated refrest .5 seconds after release. I mention these things as they could be imperative for diagrams being acedemically acceptible in reports etc.
I saw that this autolayout stuff hasn't been added to recent umbrello code. Does anyone know what the reasons are ?
(In reply to comment #9) > I saw that this autolayout stuff hasn't been added to recent umbrello code. > Does anyone know what the reasons are ? Yes, mainly because it's not really working yet; see comment #6: > [...] > It doesn't work very well yet so it might not make it into the > final release. IMHO there is a problem with the way this is implemented, it programs directly into graphviz/dot using internal undocumented calls which may change between versions. I believe it would be cleaner to just open a pipe to the "dot" program. Further, I seem to vaguely remember Jonathan mentioning there was an issue with the license of graphviz/dot, see comment #7: > [...] > To activate, remove the "dnl" from the start of the lines following the line > "dnl Not GPL compatible" in configure.in.in.
I see, any interest in having a better implementation ?
Created attachment 68148 [details] example of a new layout generator implementation
Created attachment 68149 [details] another example
Created attachment 68150 [details] like the first example with operations and attributes
I digged a litte more into this stuff and recognized that dot would be well useable for generating non overlapping layouts. The most problematic part in using dot is that umbrello in recent state is not able to draw association lines exactly as calculated by dot. Dot uses lines, polygons, ellipses and bezier curves (b-splines) as line types, which need to be supported by umbrello for good reender results. A possible implementation road seems to me to take the related part (class AssociationLine and friends) from the soc-umbrello branch as basic idea how to implement (it is not complete mergable because of major api differences in relation to trunk umbrello) and to add support for the mentioned line types on top. This would extend the xmi file format with a line type attribute and requires a related settings attribute in the association line property dialog and/or the association line context (right-click) menu. In the case of b-splines line type, the control points will be not on the line path, which may require some changes/fixes in the line segment handling. After that implementation, adding a layout generator will be possible.
Created attachment 69318 [details] diagram auto layout for class diagrams This is my first version of a diagram auto layout implementation. Please review
Just a few notes: 1. Layouts could be choosed by a right clicking on a diagram. In the context menu there are the available layouts listed. 2. With LAYOUTGENERATOR_DEBUG set there are several files created in the background with internal informations see umbrello log output.
(In reply to comment #15) > I digged a litte more into this stuff and recognized that dot would be well > useable for generating non overlapping layouts. The most problematic part in > using dot is that umbrello in recent state is not able to draw association > lines exactly as calculated by dot. > > After that implementation, adding a layout generator will be possible. As shown in the appended patch in the first run there is no need to have bspline support in umbrello.
(In reply to comment #16) > Created attachment 69318 [details] > diagram auto layout for class diagrams > > This is my first version of a diagram auto layout implementation. Please > review For people not using git as frontend for umbrello development (which has several advantages) here is a receipt: 1. checkout kdesdk trunk with svn 2. enter kdesdk 3. rename umbrello into umbrello_ 4. run git svn clone svn://anonsvn.kde.org/home/kde/trunk/KDE/kdesdk/umbrello umbrello or when write access wanted git svn clone svn+ssh://username@svn.kde.org/home/kde/trunk/KDE/kdesdk/umbrello umbrello This will need some time. If not all the history is required one may add the -r <revision> option for example git svn clone -r 1000000 svn://anonsvn.kde.org/home/kde/trunk/KDE/kdesdk/umbrello umbrello cd umbrello git svn fetch 5. to add the appended patch enter umbrello subdir and run git am <downloaded-patch>
Created attachment 69331 [details] patch fixes a few typos in layoutgenerator.h (In reply to comment #16) > Created attachment 69318 [details] > diagram auto layout for class diagrams > > This is my first version of a diagram auto layout implementation. Please > review Super, thanks for doing this. Just some superficial observations: - layoutgenerator.h should not have execute rights. - layoutgenerator.h seems to contain the full implementation; how about shifting the bodies to a new file layoutgenerator.cpp ?
(In reply to comment #20) > Created attachment 69331 [details] > patch fixes a few typos in layoutgenerator.h > > (In reply to comment #16) > > Created attachment 69318 [details] > > diagram auto layout for class diagrams > > > > This is my first version of a diagram auto layout implementation. Please > > review > > Super, thanks for doing this. > Just some superficial observations: > - layoutgenerator.h should not have execute rights. thanks, will fix > - layoutgenerator.h seems to contain the full implementation > how about shifting the bodies to a new file layoutgenerator.cpp ? will do so, when the api has been stabilised - having header only classes in early design state makes refactoring easier, which will happens more than one time. For example: Major part of his patch (the dot file creating) could also be used as dot diagram exporter, so I'm currently thinking about a move of the related part to a class DotGenerator.
Nice work! Add it to trunk. Possible improvement: Popup menu gets very large. Why not add a sub popup menu "Layout ->" and hide all the available layouts there.
SVN commit 1284087 by habacker: Moved out dot generating code into separate class DotGenerator, which makes it able to use this code also for diagram dot export feature. A dotgenerator.h [License: GPL (v2+)] M +4 -198 layoutgenerator.h M +25 -25 layouts/class-horizontal.desktop M +27 -26 layouts/class-vertical.desktop M +18 -19 layouts/usecase-default.desktop WebSVN link: http://websvn.kde.org/?view=rev&revision=1284087
(In reply to comment #1) > Presumably this is after importing classes. > The implementation put forth by Ralf Habacker requires that a diagram was already populated with the classes etc. to rearrange. A refinement would be to allow a multiple selection of treeview objects for which to generate the diagram layout. That might be difficult to do without preexisting widgets: "dot" needs the width and height of boxes but these parameters are tightly coupled to the widgets. To get an impression of width and height calculation, see e.g. function ClassifierWidget::minimumSize().
(In reply to comment #22) > Nice work! Add it to trunk. > > Possible improvement: > Popup menu gets very large. Why not add a sub popup menu "Layout ->" and > hide all the available layouts there. I tried this already - the drawback is that because this function will be often used, there is an additional menu level to select. As far as i can see there will no more than 3 or 4 layouts for a single diagram so we can see in the future if this assumption is correct. If not a compromise may be to add say 5 layout and to add a "more layouts..." entry below containing the remaining layouts. A problem to solve will be to find the 5 top wanted layouts.
Created attachment 69475 [details] demo file for testing vertical layouts Applying vertical layout to this class diagram shows a few overlaps in the association names. Is there a way to tell dot about minimum required edge lengths?
(In reply to comment #26) > Created attachment 69475 [details] > demo file for testing vertical layouts > > Applying vertical layout to this class diagram shows a few overlaps in the > association names. > Is there a way to tell dot about minimum required edge lengths? http://www.graphviz.org/content/attrs#dminlen BTW: You may add dot attributes to the config files to get additional layouts # nodes attributes [X-UMBRELLO-Dot-Nodes] type::<widget-type>=<dot-attributes> # example type::class=shape=box # for all not defined widgets types type::default=shape=box # edge attributes [X-UMBRELLO-Dot-Edges] # for visual representation (export, temporary dot files for auto layout) visual::type::anchor=arrowhead=none,style=dashed visual::type::aggregation=arrowtail=odiamond,dir=back visual::type::composition=arrowhead=diamonds visual::type::containment=arrowtail=odottee,dir=back visual::type::dependency=arrowtail=vee,style=dashed,dir=back visual::type::uniassociation=arrowtail=vee,dir=back visual::type::association=arrowhead=none visual::type::generalization=arrowtail=normal,dir=back visual::type::realisation=arrowtail=normal,dir=back visual::type::default=arrowhead=none # for position ranking ranking::type::anchor=constraint=false ranking::type::aggregation=weight=0.001 ranking::type::association=weight=0.001 ranking::type::composition=weight=0.001 ranking::type::containment=weight=0.001 ranking::type::dependency=weight=0.001 ranking::type::generalization=weight=1.0 ranking::type::realisation=weight=0.8 ranking::type::uniassociation=weight=0.001 ranking::type::default=constraint=false # id handling (swap nodes in edge line) id::type::aggregation=swap id::type::containment=swap // other dot attributes [X-UMBRELLO-Dot-Attributes] // graph statement graph=splines=polyline,rankdir=TB,outputorder=nodesfirst,ranksep=0.5,nodesep=0.5 // main node attributes node= // main edge attributes edge= // internal settings [X-UMBRELLO-Dot-Settings] origin=50,50
(In reply to comment #27) > (In reply to comment #26) > > Created attachment 69475 [details] > > demo file for testing vertical layouts > > > > Applying vertical layout to this class diagram shows a few overlaps in the > > association names. > > Is there a way to tell dot about minimum required edge lengths? > > http://www.graphviz.org/content/attrs#dminlen minlen is for dot generator neato, which is as usable generator for state diagrams requires a len attribute on edges for example [x-UMBRELLO-Dot-Edges] ranking::type::default=len=2 [x-UMBRELLO-Dot-Attributes] graph=model=mds
SVN commit 1286041 by habacker: Use neato generator for state diagram dot export and auto layout, which gives better layouts. Related: bug 295600 M +3 -3 state-export.desktop WebSVN link: http://websvn.kde.org/?view=rev&revision=1286041
SVN commit 1286276 by habacker: Made ActivityWidget, StateWidget and SignalWidget type string accessable by dot export and layout generator config. Related: bug 295600 M +12 -3 dotgenerator.cpp M +8 -0 widgets/activitywidget.cpp M +4 -1 widgets/activitywidget.h M +8 -0 widgets/signalwidget.cpp M +4 -0 widgets/signalwidget.h M +8 -0 widgets/statewidget.cpp M +1 -6 widgets/statewidget.h WebSVN link: http://websvn.kde.org/?view=rev&revision=1286276
SVN commit 1286277 by habacker: Added id::type::default to dot export and layout generator config, which is used in case no explicit id::type::... setting is present. Related: bug 295600 M +11 -2 dotgenerator.cpp WebSVN link: http://websvn.kde.org/?view=rev&revision=1286277
SVN commit 1286278 by habacker: Added layout config for activitiy diagrams. A few widgets (box, text, region, not anchored notes) could not be placed correctly yet because off missing links. For example when placing widgets into a box, the box do not have any relation to the contained widgets. It would help if umbrello would track this "visual" containment with an (probably invisible) association. For not anchored widgets an invisible "nearest widget" assocation will help too. Related: bug 295600 A activity-export.desktop WebSVN link: http://websvn.kde.org/?view=rev&revision=1286278
SVN commit 1286822 by habacker: Use dot weight attribute for all associations in class diagrams autolayout to improve placements. M +4 -4 class-export.desktop M +4 -4 class-horizontal.desktop M +2 -2 class-vertical.desktop WebSVN link: http://websvn.kde.org/?view=rev&revision=1286822
A major problem are a few issues with activity diagrams (In reply to comment #32) > SVN commit 1286278 by habacker: > > Added layout config for activitiy diagrams. > > A few widgets (box, text, region, not anchored notes) > could not be placed correctly yet because off missing links. > text lines are often used to describe the different output lines. Currently they are not bound to the lines, which makes it hard to track position. One solution is to track the association line below the text line and add an invisible association. Another solution will be to give lines an associated text field like already available for dependencies in class diagrams.
Basic autolayout works good so far for class, state and activity diagrams. The remaining issues should be addressed in different bugs.