From 0e39cdf0cc3195b77fa0effca0e2b07355fe1c0b Mon Sep 17 00:00:00 2001 From: tgdwyer Date: Mon, 13 Feb 2006 02:00:14 +0000 Subject: [PATCH] Added connector graph layout functionality --- configure.ac | 7 ++ share/icons/icons.svg | 156 +++++++++++++++++++++++-- src/Makefile.am | 2 + src/Makefile_insert | 1 + src/graphlayout/Makefile_insert | 10 ++ src/graphlayout/graphlayout.cpp | 147 +++++++++++++++++++++++ src/graphlayout/graphlayout.h | 17 +++ src/graphlayout/makefile | 17 +++ src/libavoid/connector.cpp | 4 +- src/ui/dialog/align-and-distribute.cpp | 48 ++++++++ src/ui/dialog/align-and-distribute.h | 8 +- 11 files changed, 405 insertions(+), 12 deletions(-) create mode 100644 src/graphlayout/Makefile_insert create mode 100644 src/graphlayout/graphlayout.cpp create mode 100644 src/graphlayout/graphlayout.h create mode 100644 src/graphlayout/makefile diff --git a/configure.ac b/configure.ac index b0ce823c1..17b753c6f 100644 --- a/configure.ac +++ b/configure.ac @@ -537,6 +537,13 @@ if test "$enable_osxapp" = "yes"; then AC_DEFINE(ENABLE_OSX_APP_LOCATIONS,,[Build with OSX .app data dir paths?]) fi +dnl ****************************** +dnl Boost graph library is required for graphlayout functions +dnl ****************************** +AC_CHECK_HEADER([boost/graph/adjacency_list.hpp], + [AC_DEFINE([HAVE_BOOST_GRAPH_LIB],[],[Will enable connector network layout])], + [AC_MSG_WARN([Boost graph lib not found, can't include connector network layout functionality.])]) + dnl ****************************** dnl Reported by autoscan dnl ****************************** diff --git a/share/icons/icons.svg b/share/icons/icons.svg index e2f7118a8..f29f45c76 100644 --- a/share/icons/icons.svg +++ b/share/icons/icons.svg @@ -14,7 +14,7 @@ height="320" sodipodi:docname="icons.svg" inkscape:version="0.43+devel" - sodipodi:docbase="/home/rws/inkscape/share/icons"> + sodipodi:docbase="/home/dwyer/devel/inkscape/share/icons"> width="1500" height="320" /> + + + + + + + + + + + + + + + + + + diff --git a/src/Makefile.am b/src/Makefile.am index 73e6deb36..6ac221a1a 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -43,6 +43,7 @@ include libnrtype/Makefile_insert include libavoid/Makefile_insert include livarot/Makefile_insert include removeoverlap/Makefile_insert +include graphlayout/Makefile_insert include svg/Makefile_insert include utest/Makefile_insert include widgets/Makefile_insert @@ -85,6 +86,7 @@ noinst_LIBRARIES = \ libavoid/libavoid.a \ livarot/libvarot.a \ removeoverlap/libremoveoverlap.a \ + graphlayout/libgraphlayout.a \ svg/libspsvg.a \ widgets/libspwidgets.a \ trace/libtrace.a \ diff --git a/src/Makefile_insert b/src/Makefile_insert index 3952e8cf5..302bd8089 100644 --- a/src/Makefile_insert +++ b/src/Makefile_insert @@ -259,6 +259,7 @@ inkscape_private_libs = \ ui/view/libuiview.a \ ui/libui.a \ ui/widget/libuiwidget.a \ + graphlayout/libgraphlayout.a \ removeoverlap/libremoveoverlap.a \ extension/libextension.a \ extension/implementation/libimplementation.a \ diff --git a/src/graphlayout/Makefile_insert b/src/graphlayout/Makefile_insert new file mode 100644 index 000000000..fc490743d --- /dev/null +++ b/src/graphlayout/Makefile_insert @@ -0,0 +1,10 @@ +## Makefile.am fragment sourced by src/Makefile.am. + +graphlayout/all: graphlayout/libgraphlayout.a + +graphlayout/clean: + rm -f graphlayout/libgraphlayout.a $(graphlayout_libgraphlayout_a_OBJECTS) + +graphlayout_libgraphlayout_a_SOURCES = \ + graphlayout/graphlayout.cpp \ + graphlayout/graphlayout.h diff --git a/src/graphlayout/graphlayout.cpp b/src/graphlayout/graphlayout.cpp new file mode 100644 index 000000000..9828e22fe --- /dev/null +++ b/src/graphlayout/graphlayout.cpp @@ -0,0 +1,147 @@ +/** \file + * Interface between Inkscape code (SPItem) and graphlayout functions. + */ +/* +* Authors: +* Tim Dwyer +* +* Copyright (C) 2005 Authors +* +* Released under GNU GPL. Read the file 'COPYING' for more information. +*/ +#include "graphlayout/graphlayout.h" +#include +#include + +#ifdef HAVE_BOOST_GRAPH_LIB +#include "sp-item.h" +#include "sp-item-transform.h" +#include "sp-conn-end-pair.h" +#include "conn-avoid-ref.h" +#include "libavoid/connector.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace boost; +// create a typedef for the Graph type +typedef adjacency_list > Graph; +typedef property_map::type WeightMap; +typedef graph_traits::vertex_descriptor Vertex; +typedef std::vector > PositionVec; +typedef iterator_property_map::type> PositionMap; +#endif // HAVE_BOOST_GRAPH_LIB + +/** +* Takes a list of inkscape items, extracts the graph defined by +* connectors between them, and uses graph layout techniques to find +* a nice layout +*/ +void graphlayout(GSList const *const items) { + if(!items) { + return; + } +#ifdef HAVE_BOOST_GRAPH_LIB + + + using Inkscape::Util::GSListConstIterator; + std::list selected; + selected.insert >(selected.end(), items, NULL); + if (selected.empty()) return; + int n=selected.size(); + + //Check 2 or more selected objects + if (n < 2) return; + + Graph g; + + std::cout<<"Building graph with "< nodelookup; + for (std::list::iterator it(selected.begin()); + it != selected.end(); + ++it) + { + SPItem *u=*it; + std::cout<<"id:"<id<id,"path",4)) { + nodelookup[u->id]=add_vertex(g); + } + } + WeightMap weightmap=get(edge_weight, g); + std::cout<<"Added vertices: Graph has |V|="<::iterator it(selected.begin()); + it != selected.end(); + ++it) + { + using NR::X; using NR::Y; + SPItem *itu=*it; + Vertex u=nodelookup[itu->id]; + GSList *nlist=itu->avoidRef->getAttachedConnectors(Avoid::ConnRef::runningFrom); + std::list neighbours; + neighbours.insert >(neighbours.end(),nlist,NULL); + std::cout<<" Node "<id<<" has "<::iterator ne(neighbours.begin()); + ne != neighbours.end(); + ++ne) { + + SPItem *itv=*ne; + std::cout<<"neighbour: "<id<id]; + std::cout<<" Neighbour: "<id]].x, + minY+height/2.0+position[nodelookup[u->id]].y); + sp_item_move_rel(u, NR::translate(dest - curr)); + } + } +#else + std::cout<<"Connector network layout not available! Install boost graph library and recompile to enable."< + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#ifndef SEEN_GRAPHLAYOUT_H +#define SEEN_GRAPHLAYOUT_H +#include "util/glib-list-iterators.h" + +void graphlayout(GSList const *const items); +#endif // SEEN_GRAPHLAYOUT_H diff --git a/src/graphlayout/makefile b/src/graphlayout/makefile new file mode 100644 index 000000000..5d8ac906e --- /dev/null +++ b/src/graphlayout/makefile @@ -0,0 +1,17 @@ +# Convenience stub makefile to call the real Makefile. + + + +# Explicit so that it's the default rule. +all: + cd .. && $(MAKE) graphlayout/all + +clean %.a %.o: + cd .. && $(MAKE) graphlayout/$@ + +.PHONY: all clean + +OBJEXT = o + +.SUFFIXES: +.SUFFIXES: .a .$(OBJEXT) diff --git a/src/libavoid/connector.cpp b/src/libavoid/connector.cpp index 04bf7aaad..06a0cd4aa 100644 --- a/src/libavoid/connector.cpp +++ b/src/libavoid/connector.cpp @@ -428,10 +428,10 @@ void attachedToShape(IntList &conns, const unsigned int shapeId, ConnRefList::iterator fin = connRefs.end(); for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) { if ((type & ConnRef::runningTo) && ((*i)->_dstId == shapeId)) { - conns.push_back((*i)->_id); + conns.push_back((*i)->_srcId); } else if ((type & ConnRef::runningFrom) && ((*i)->_srcId == shapeId)) { - conns.push_back((*i)->_id); + conns.push_back((*i)->_dstId); } } } diff --git a/src/ui/dialog/align-and-distribute.cpp b/src/ui/dialog/align-and-distribute.cpp index 262aa690b..35ee7b806 100644 --- a/src/ui/dialog/align-and-distribute.cpp +++ b/src/ui/dialog/align-and-distribute.cpp @@ -22,6 +22,7 @@ #include "dialogs/unclump.h" #include "removeoverlap/removeoverlap.h" +#include "graphlayout/graphlayout.h" #include @@ -487,6 +488,35 @@ private : } }; +class ActionGraphLayout : public Action { +public: + ActionGraphLayout(Glib::ustring const &id, + Glib::ustring const &tiptext, + guint row, + guint column, + AlignAndDistribute &dialog) : + Action(id, tiptext, row, column + 4, + dialog.graphLayout_table(), dialog.tooltips(), dialog) + {} + +private : + virtual void on_button_click() + { + if (!SP_ACTIVE_DESKTOP) return; + + // see comment in ActionAlign above + int saved_compensation = prefs_get_int_attribute("options.clonecompensation", "value", SP_CLONE_COMPENSATION_UNMOVED); + prefs_set_int_attribute("options.clonecompensation", "value", SP_CLONE_COMPENSATION_UNMOVED); + + graphlayout(SP_DT_SELECTION(SP_ACTIVE_DESKTOP)->itemList()); + + // restore compensation setting + prefs_set_int_attribute("options.clonecompensation", "value", saved_compensation); + + sp_document_done(SP_DT_DOCUMENT(SP_ACTIVE_DESKTOP)); + } +}; + class ActionUnclump : public Action { public : ActionUnclump(const Glib::ustring &id, @@ -717,10 +747,12 @@ AlignAndDistribute::AlignAndDistribute() _alignFrame(_("Align")), _distributeFrame(_("Distribute")), _removeOverlapFrame(_("Remove overlaps")), + _graphLayoutFrame(_("Connector network layout")), _nodesFrame(_("Nodes")), _alignTable(2, 6, true), _distributeTable(3, 6, true), _removeOverlapTable(1, 5, false), + _graphLayoutTable(1, 5, false), _nodesTable(1, 4, true), _anchorLabel(_("Relative to: ")) { @@ -814,6 +846,10 @@ AlignAndDistribute::AlignAndDistribute() addRemoveOverlapsButton("remove_overlaps", _("Move objects as little as possible so that their bounding boxes do not overlap"), 0, 0); + //Graph Layout + addGraphLayoutButton("graph_layout", + _("Nicely arrange selected connector network"), + 0, 0); //Node Mode buttons addNodeButton("node_halign", @@ -851,6 +887,7 @@ AlignAndDistribute::AlignAndDistribute() _alignFrame.add(_alignBox); _distributeFrame.add(_distributeTable); _removeOverlapFrame.add(_removeOverlapTable); + _graphLayoutFrame.add(_graphLayoutTable); _nodesFrame.add(_nodesTable); // Top level vbox @@ -862,6 +899,7 @@ AlignAndDistribute::AlignAndDistribute() vbox->pack_start(_alignFrame, true, true); vbox->pack_start(_distributeFrame, true, true); vbox->pack_start(_removeOverlapFrame, true, true); + vbox->pack_start(_graphLayoutFrame, true, true); vbox->pack_start(_nodesFrame, true, true); //Connect to the global tool change signal @@ -908,6 +946,7 @@ void AlignAndDistribute::setMode(bool nodeEdit) ((_alignFrame).*(mSel))(); ((_distributeFrame).*(mSel))(); ((_removeOverlapFrame).*(mSel))(); + ((_graphLayoutFrame).*(mSel))(); ((_nodesFrame).*(mNode))(); } @@ -950,6 +989,15 @@ void AlignAndDistribute::addRemoveOverlapsButton(const Glib::ustring &id, const ); } +void AlignAndDistribute::addGraphLayoutButton(const Glib::ustring &id, const Glib::ustring tiptext, + guint row, guint col) +{ + _actionList.push_back( + new ActionGraphLayout( + id, tiptext, row, col, *this) + ); +} + void AlignAndDistribute::addUnclumpButton(const Glib::ustring &id, const Glib::ustring tiptext, guint row, guint col) { diff --git a/src/ui/dialog/align-and-distribute.h b/src/ui/dialog/align-and-distribute.h index 35ca3c7c3..69fc17673 100644 --- a/src/ui/dialog/align-and-distribute.h +++ b/src/ui/dialog/align-and-distribute.h @@ -58,6 +58,7 @@ public: Gtk::Table &align_table(){return _alignTable;} Gtk::Table &distribute_table(){return _distributeTable;} Gtk::Table &removeOverlap_table(){return _removeOverlapTable;} + Gtk::Table &graphLayout_table(){return _graphLayoutTable;} Gtk::Table &nodes_table(){return _nodesTable;} Gtk::Tooltips &tooltips(){return _tooltips;} @@ -81,6 +82,9 @@ protected: void addRemoveOverlapsButton(const Glib::ustring &id, const Glib::ustring tiptext, guint row, guint col); + void addGraphLayoutButton(const Glib::ustring &id, + const Glib::ustring tiptext, + guint row, guint col); void addUnclumpButton(const Glib::ustring &id, const Glib::ustring tiptext, guint row, guint col); void addRandomizeButton(const Glib::ustring &id, const Glib::ustring tiptext, @@ -89,8 +93,8 @@ protected: guint row, guint col, Gtk::Table &table, NR::Dim2 orientation, bool distribute); std::list _actionList; - Gtk::Frame _alignFrame, _distributeFrame, _removeOverlapFrame, _nodesFrame; - Gtk::Table _alignTable, _distributeTable, _removeOverlapTable, _nodesTable; + Gtk::Frame _alignFrame, _distributeFrame, _removeOverlapFrame, _graphLayoutFrame, _nodesFrame; + Gtk::Table _alignTable, _distributeTable, _removeOverlapTable, _graphLayoutTable, _nodesTable; Gtk::HBox _anchorBox; Gtk::VBox _alignBox; Gtk::Label _anchorLabel; -- 2.30.2