Menu
▾
▴
[Scstudio-commits] SF.net SVN: scstudio:[384] trunk
|
From: <got...@us...> - 2009-09-28 13:18:53
|
Revision: 384
http://scstudio.svn.sourceforge.net/scstudio/?rev=384&view=rev
Author: gotthardp
Date: 2009-09-28 13:18:35 +0000 (Mon, 28 Sep 2009)
Log Message:
-----------
New feature: implemented experimental LayoutOptimizer based on linear programming (lp_solve library).
Modified Paths:
--------------
trunk/FindLpSolve.cmake
trunk/src/data/CMakeLists.txt
trunk/src/view/visio/addon/dllmodule.rc
trunk/src/view/visio/addon/document.cpp
trunk/src/view/visio/scstudio.nsi
Added Paths:
-----------
trunk/src/data/layout_optimizer.cpp
trunk/src/data/layout_optimizer.h
Modified: trunk/FindLpSolve.cmake
===================================================================
--- trunk/FindLpSolve.cmake 2009-09-28 12:22:49 UTC (rev 383)
+++ trunk/FindLpSolve.cmake 2009-09-28 13:18:35 UTC (rev 384)
@@ -10,9 +10,10 @@
DOC "The lp_solve library")
FIND_PATH(LPSOLVE_INCLUDE_DIR
- NAMES lpsolve/lp_lib.h
+ NAMES lp_lib.h
PATHS
${LPSOLVE_ROOT}
+ ${LPSOLVE_ROOT}/lpsolve
DOC "The lp_solve include files")
INCLUDE(FindPackageHandleStandardArgs)
Modified: trunk/src/data/CMakeLists.txt
===================================================================
--- trunk/src/data/CMakeLists.txt 2009-09-28 12:22:49 UTC (rev 383)
+++ trunk/src/data/CMakeLists.txt 2009-09-28 13:18:35 UTC (rev 384)
@@ -1,3 +1,17 @@
+OPTION(BUILD_OPTIMIZER "Enable to build the layout optimizer" OFF)
+IF(BUILD_OPTIMIZER)
+ FIND_PACKAGE(LpSolve REQUIRED)
+ INCLUDE_DIRECTORIES(${LPSOLVE_INCLUDE_DIR})
+
+ SET(OPTIMIZER_SOURCES
+ layout_optimizer.cpp
+ layout_optimizer.h
+ )
+ SET(OPTIMIZER_LIBRARIES
+ ${LPSOLVE_LIBRARY}
+ )
+ENDIF(BUILD_OPTIMIZER)
+
ADD_LIBRARY(scmsc SHARED
export.h
msc_types.cpp
@@ -32,11 +46,12 @@
hmsc_reference_checker.h
beautify.h
beautify.cpp
+ ${OPTIMIZER_SOURCES}
)
-#TARGET_LINK_LIBRARIES(scmsc
-# sctime
-#)
+TARGET_LINK_LIBRARIES(scmsc
+ ${OPTIMIZER_LIBRARIES}
+)
# build import-export formatters
ADD_SUBDIRECTORY(engmann)
Added: trunk/src/data/layout_optimizer.cpp
===================================================================
--- trunk/src/data/layout_optimizer.cpp (rev 0)
+++ trunk/src/data/layout_optimizer.cpp 2009-09-28 13:18:35 UTC (rev 384)
@@ -0,0 +1,272 @@
+/*
+ * scstudio - Sequence Chart Studio
+ * http://scstudio.sourceforge.net
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2.1, as published by the Free Software Foundation.
+ *
+ * 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. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * Copyright (c) 2009 Petr Gotthard <pet...@ce...>
+ *
+ * $Id$
+ */
+
+#include <lp_lib.h>
+
+#include "data/dfs_events_traverser.h"
+#include "data/layout_optimizer.h"
+#include "check/pseudocode/utils.h"
+
+static lprec* initialize_solver(int events_size)
+{
+ lprec *lp = make_lp(0, events_size);
+ if(lp == NULL)
+ throw std::bad_alloc();
+
+ // turn off verbose mode
+ set_verbose(lp, NEUTRAL);
+
+ // set the objective to minimize
+ set_minim(lp);
+
+ REAL* row = new REAL[events_size+1];
+ // formulate the problem
+ // note: element 0 of the array is not considered (i.e. ignored)
+ for (int i = 1; i <= events_size; i++)
+ row[i] = 0;
+ // set the objective function: sum of e[i]
+ set_obj_fn(lp, row);
+ delete[] row;
+
+ return lp;
+}
+
+// add constraint ex < ey, i.e. ex-->ey >= d
+static int add_relative_distance_constraint(lprec *lp, int ex, int ey, REAL d)
+{
+ int columns = get_Ncolumns(lp);
+ // we add new row: turn row entry mode on
+ set_add_rowmode(lp, TRUE);
+
+ REAL* row = new REAL[columns+1];
+ // initialize the vector
+ // note: element 0 of the array is not considered (i.e. ignored)
+ for (int i = 1; i <= columns; i++)
+ row[i] = 0;
+ // add the constraint: -e[x] + e[y] >= d
+ row[ex] = -1;
+ row[ey] = 1;
+ add_constraint(lp, row, GE, d);
+
+ delete[] row;
+ return 0;
+}
+
+// append new variable, i.e. new column to the matrix
+static int add_binary_variable(lprec *lp)
+{
+ int rows = get_Nrows(lp);
+ // we add new column: turn row entry mode off
+ set_add_rowmode(lp, FALSE);
+
+ REAL* column = new REAL[rows+1];
+ // initialize the vector
+ // note: element 0 of the array represents the objective value
+ for (int i = 0; i <= rows; i++)
+ column[i] = 0;
+
+ add_column(lp, column);
+ delete[] column;
+
+ // the new column is added to the model at the end
+ // current number of columns thus represents index of the new variable
+ int idx = get_Ncolumns(lp);
+
+ set_binary(lp, idx, TRUE);
+ return idx;
+}
+
+// constraint ex < ey or ex > ey, i.e. |ex<-->ey| >= d
+// see http://www.nabble.com/Absolute-value-constraint-td14841621.html
+static int add_absolute_distance_constraint(lprec *lp, int ex, int ey, REAL d)
+{
+ static const REAL max_distance = 1000; // [millimeters]
+ int z = add_binary_variable(lp);
+
+ int columns = get_Ncolumns(lp);
+ // we add new rows: turn row entry mode on
+ set_add_rowmode(lp, TRUE);
+
+ REAL* row = new REAL[columns+1];
+ // initialize the vector
+ // note: element 0 of the array is not considered (i.e. ignored)
+ for (int i = 1; i <= columns; i++)
+ row[i] = 0;
+ // set the constraint: e[x] - e[y] + z*(M+d)
+ row[ex] = 1;
+ row[ey] = -1;
+ row[z] = max_distance+d;
+ // add constraint: e[x] - e[y] + z*(M+d) <= M
+ add_constraint(lp, row, LE, max_distance);
+ // add constraint: e[x] - e[y] + z*(M+d) >= d
+ add_constraint(lp, row, GE, d);
+
+ delete[] row;
+ return 0;
+}
+
+typedef std::map<EventPtr, int> EventPtrMap;
+
+class EventIndexer: public WhiteEventFoundListener
+{
+public:
+ virtual void on_white_event_found(Event* e)
+ {
+ int index = m_events.size()+1;
+ m_events.insert(std::make_pair(e, index));
+ }
+
+ size_t get_event_count() const
+ {
+ return m_events.size();
+ }
+
+ int get_event_index(EventPtr e) const
+ {
+ EventPtrMap::const_iterator pos = m_events.find(e);
+ if(pos == m_events.end())
+ throw std::range_error("Unknown event");
+
+ return pos->second;
+ }
+
+ const EventPtrMap& get_events() const
+ {
+ return m_events;
+ }
+
+private:
+ EventPtrMap m_events;
+};
+
+class EventConstraintCreator: public EventSuccessorListener, public SendReceivePairListener
+{
+public:
+ EventConstraintCreator(lprec *lp, const EventIndexer& indexer) :
+ m_lp(lp), m_indexer(indexer) {}
+
+ float m_successor_distance;
+ float m_send_receive_distance;
+
+ virtual void on_event_successor(Event* event, Event* successor)
+ {
+ int e1, e2;
+ if(successor->get_attribute<NodeColor>("cc_color",WHITE) == GRAY)
+ {
+ // cycle detected: reverse direction
+ e1 = m_indexer.get_event_index(successor);
+ e2 = m_indexer.get_event_index(event);
+ }
+ else
+ {
+ e1 = m_indexer.get_event_index(event);
+ e2 = m_indexer.get_event_index(successor);
+ }
+
+ add_relative_distance_constraint(m_lp, e1, e2, m_successor_distance);
+ }
+
+ virtual void on_send_receive_pair(Event* send, Event* receive)
+ {
+ int e1, e2;
+ if(receive->get_attribute<NodeColor>("cc_color",WHITE) == GRAY)
+ {
+ // cycle detected: reverse direction
+ e1 = m_indexer.get_event_index(receive);
+ e2 = m_indexer.get_event_index(send);
+ }
+ else
+ {
+ e1 = m_indexer.get_event_index(send);
+ e2 = m_indexer.get_event_index(receive);
+ }
+
+ add_relative_distance_constraint(m_lp, e1, e2, m_send_receive_distance);
+ // update the objective function for matched events:
+ // minimize length and y-coordinate, i.e. 2*y(receive) - y(send)
+ set_obj(m_lp, e1, -1.0);
+ set_obj(m_lp, e2, 2.0);
+ }
+
+private:
+ lprec *m_lp;
+ const EventIndexer& m_indexer;
+};
+
+LayoutOptimizer::LayoutOptimizer()
+{
+ m_instance_head_distance = 5.0f;
+ m_successor_distance = 5.0f;
+ m_send_receive_distance = 0.0f;
+}
+
+int LayoutOptimizer::process(MscPtr msc)
+{
+ BMscPtr bmsc = boost::dynamic_pointer_cast<BMsc>(msc);
+ if(bmsc)
+ return beautify(bmsc);
+
+ return 0; // not processed
+}
+
+int LayoutOptimizer::beautify(BMscPtr bmsc)
+{
+ EventIndexer indexer;
+ DFSEventsTraverser indexing_traverser;
+ indexing_traverser.add_white_event_found_listener(&indexer);
+ indexing_traverser.traverse(bmsc.get());
+
+ lprec *lp = initialize_solver(indexer.get_event_count());
+
+ InstancePtrList::const_iterator it;
+ EventConstraintCreator constraint_creator(lp, indexer);
+ constraint_creator.m_successor_distance = m_successor_distance;
+ constraint_creator.m_send_receive_distance = m_send_receive_distance;
+
+ DFSEventsTraverser traverser("cc_color");
+ traverser.add_event_successor_listener(&constraint_creator);
+ traverser.add_send_receive_pair_listener(&constraint_creator);
+ // create the constraints
+ traverser.traverse(bmsc.get());
+
+ // (2) solve the problem
+ // before solving the problem we have to turn the row entry mode off
+ // note: don't call other API functions while in row entry mode
+ set_add_rowmode(lp, FALSE);
+
+ if(solve(lp) != 0)
+ return 0; // no solution found
+
+ int columns = get_Ncolumns(lp);
+ // process the results
+ REAL* var = new REAL[columns];
+ get_variables(lp, var);
+
+ for(EventPtrMap::const_iterator epos = indexer.get_events().begin();
+ epos != indexer.get_events().end(); epos++)
+ {
+ // note: var element 0 contains the first variable, etc.
+ epos->first->set_position(MscPoint(0, m_instance_head_distance+var[epos->second-1]));
+ }
+ delete[] var;
+
+ delete_lp(lp);
+ return 1; // success
+}
+
+// $Id$
Property changes on: trunk/src/data/layout_optimizer.cpp
___________________________________________________________________
Added: svn:keywords
+ Id
Added: svn:eol-style
+ native
Added: trunk/src/data/layout_optimizer.h
===================================================================
--- trunk/src/data/layout_optimizer.h (rev 0)
+++ trunk/src/data/layout_optimizer.h 2009-09-28 13:18:35 UTC (rev 384)
@@ -0,0 +1,36 @@
+/*
+ * scstudio - Sequence Chart Studio
+ * http://scstudio.sourceforge.net
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2.1, as published by the Free Software Foundation.
+ *
+ * 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. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * Copyright (c) 2009 Petr Gotthard <pet...@ce...>
+ *
+ * $Id$
+ */
+
+#include "data/msc.h"
+#include "data/export.h"
+
+class SCMSC_EXPORT LayoutOptimizer
+{
+public:
+ LayoutOptimizer();
+ int process(MscPtr msc);
+
+ float m_instance_head_distance;
+ float m_successor_distance;
+ float m_send_receive_distance;
+
+protected:
+ int beautify(BMscPtr bmsc);
+};
+
+// $Id$
Property changes on: trunk/src/data/layout_optimizer.h
___________________________________________________________________
Added: svn:keywords
+ Id
Added: svn:eol-style
+ native
Modified: trunk/src/view/visio/addon/dllmodule.rc
===================================================================
--- trunk/src/view/visio/addon/dllmodule.rc 2009-09-28 12:22:49 UTC (rev 383)
+++ trunk/src/view/visio/addon/dllmodule.rc 2009-09-28 13:18:35 UTC (rev 384)
@@ -89,8 +89,8 @@
//
VS_VERSION_INFO VERSIONINFO
- FILEVERSION 0,3,11,0
- PRODUCTVERSION 0,3,11,0
+ FILEVERSION 0,3,13,0
+ PRODUCTVERSION 0,3,13,0
FILEFLAGSMASK 0x3fL
#ifdef _DEBUG
FILEFLAGS 0x9L
@@ -107,13 +107,13 @@
BEGIN
VALUE "CompanyName", "Masaryk University Brno"
VALUE "FileDescription", "Microsoft Visio add-on for design and verification of Message Sequence Charts (MSC)."
- VALUE "FileVersion", "0.3.11"
+ VALUE "FileVersion", "0.3.13"
VALUE "InternalName", "scstudio.vsl"
VALUE "LegalCopyright", "(c) Petr Gotthard. All rights reserved."
VALUE "OriginalFilename", "scstudio.vsl"
VALUE "PrivateBuild", "$Revision$"
VALUE "ProductName", "Sequence Chart Studio"
- VALUE "ProductVersion", "0.3.11"
+ VALUE "ProductVersion", "0.3.13"
END
END
BLOCK "VarFileInfo"
Modified: trunk/src/view/visio/addon/document.cpp
===================================================================
--- trunk/src/view/visio/addon/document.cpp 2009-09-28 12:22:49 UTC (rev 383)
+++ trunk/src/view/visio/addon/document.cpp 2009-09-28 13:18:35 UTC (rev 384)
@@ -27,7 +27,7 @@
#include <fstream>
#include "data/msc.h"
-#include "data/beautify.h"
+#include "data/layout_optimizer.h"
// Include libraries from the Windows Template Library (WTL).
// http://wtl.sourceforge.net
@@ -1033,9 +1033,20 @@
if(msc == NULL)
return VAORC_FAILURE;
- Beautify beautify;
+ LayoutOptimizer beautify;
+ beautify.m_instance_head_distance =
+ (float)GetRegistryDWORD(SCSTUDIO_REGISTRY_ROOT, _T("InstanceHeadDistance"), 5);
+ beautify.m_successor_distance =
+ (float)GetRegistryDWORD(SCSTUDIO_REGISTRY_ROOT, _T("SuccessorDistance"), 5);
+ beautify.m_send_receive_distance =
+ (float)GetRegistryDWORD(SCSTUDIO_REGISTRY_ROOT, _T("SendReceiveDistance"), 0);
+
// generate graphical layout information
- beautify.process(msc);
+ if(!beautify.process(msc))
+ {
+ m_reportView->Print(RS_WARNING,
+ stringize() << "Optimized layout not found.");
+ }
// delete all MSC symbols, preserve ignored shapes
RemoveKnownSymbols(vsoPage);
@@ -1134,7 +1145,7 @@
}
}
- Beautify beautify;
+ LayoutOptimizer beautify;
// generate graphical layout information
beautify.process(*dpos);
Modified: trunk/src/view/visio/scstudio.nsi
===================================================================
--- trunk/src/view/visio/scstudio.nsi 2009-09-28 12:22:49 UTC (rev 383)
+++ trunk/src/view/visio/scstudio.nsi 2009-09-28 13:18:35 UTC (rev 384)
@@ -21,7 +21,7 @@
; -- General ---------------------------
-!define VERSION "0.3.12"
+!define VERSION "0.3.13"
Name "Sequence Chart Studio"
OutFile "scstudio-setup-${VERSION}.exe"
@@ -99,6 +99,7 @@
File "redistribute\atl71.dll"
File "redistribute\msvcp71.dll"
File "redistribute\msvcr71.dll"
+ File "redistribute\lpsolve55.dll"
File "redistribute\capicom.dll"
ExecWait 'regsvr32.exe /s "$INSTDIR\capicom.dll"'
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
