1 /** \file
2 * Interface between Inkscape code (SPItem) and graphlayout functions.
3 */
4 /*
5 * Authors:
6 * Tim Dwyer <tgdwyer@gmail.com>
7 *
8 * Copyright (C) 2005 Authors
9 *
10 * Released under GNU GPL. Read the file 'COPYING' for more information.
11 */
12 #include "util/glib-list-iterators.h"
13 #include "graphlayout/graphlayout.h"
14 #include <iostream>
15 #include <config.h>
17 #ifdef HAVE_BOOST_GRAPH_LIB
18 #include "sp-path.h"
19 #include "sp-item.h"
20 #include "sp-item-transform.h"
21 #include "sp-conn-end-pair.h"
22 #include "conn-avoid-ref.h"
23 #include "libavoid/connector.h"
24 #include "libavoid/geomtypes.h"
25 #include <boost/graph/kamada_kawai_spring_layout.hpp>
26 #include <boost/graph/circle_layout.hpp>
27 #include <boost/graph/adjacency_list.hpp>
28 #include <boost/graph/graphviz.hpp>
29 #include <map>
30 #include <vector>
31 #include <algorithm>
32 #include <float.h>
34 using namespace boost;
36 // create a typedef for the Graph type
37 typedef adjacency_list<vecS, vecS, undirectedS, no_property,
38 property<edge_weight_t, double> > Graph;
39 typedef property_map<Graph, edge_weight_t>::type WeightMap;
40 typedef graph_traits<Graph>::vertex_descriptor Vertex;
41 typedef std::vector<Avoid::Point> PositionVec;
42 typedef iterator_property_map<PositionVec::iterator, property_map<Graph, vertex_index_t>::type> PositionMap;
44 /**
45 * Returns true if item is a connector
46 */
47 bool isConnector(SPItem const *const i) {
48 SPPath *path = NULL;
49 if(SP_IS_PATH(i)) {
50 path = SP_PATH(i);
51 }
52 return path && path->connEndPair.isAutoRoutingConn();
53 }
55 /**
56 * Scans the items list and places those items that are
57 * not connectors in filtered
58 */
59 void filterConnectors(GSList const *const items, std::list<SPItem *> &filtered) {
60 for(GSList *i=(GSList *)items; i!=NULL; i=i->next) {
61 SPItem *item=SP_ITEM(i->data);
62 if(!isConnector(item)) {
63 filtered.push_back(item);
64 }
65 }
66 }
67 /**
68 * Takes a list of inkscape items, extracts the graph defined by
69 * connectors between them, and uses graph layout techniques to find
70 * a nice layout
71 */
72 void graphlayout(GSList const *const items) {
73 if(!items) {
74 return;
75 }
77 using Inkscape::Util::GSListConstIterator;
78 std::list<SPItem *> selected;
79 filterConnectors(items,selected);
80 if (selected.empty()) return;
82 int n=selected.size();
83 std::cout<<"|V|="<<n<<std::endl;
85 Graph g;
87 double minX=DBL_MAX, minY=DBL_MAX, maxX=-DBL_MAX, maxY=-DBL_MAX;
89 std::map<std::string,Vertex> nodelookup;
90 for (std::list<SPItem *>::iterator i(selected.begin());
91 i != selected.end();
92 ++i)
93 {
94 SPItem *u=*i;
95 std::cout<<"Creating node for id: "<<u->id<<std::endl;
96 nodelookup[u->id]=add_vertex(g);
97 }
99 //Check 2 or more selected objects
100 if (n < 2) return;
102 WeightMap weightmap=get(edge_weight, g);
103 for (std::list<SPItem *>::iterator i(selected.begin());
104 i != selected.end();
105 ++i)
106 {
107 using NR::X; using NR::Y;
108 SPItem *iu=*i;
109 std::cout<<"Getting neighbours for id: "<<iu->id<<std::endl;
110 Vertex u=nodelookup[iu->id];
111 GSList *nlist=iu->avoidRef->getAttachedShapes(Avoid::runningFrom);
112 std::list<SPItem *> neighbours;
113 neighbours.insert<GSListConstIterator<SPItem *> >(neighbours.end(),nlist,NULL);
114 for (std::list<SPItem *>::iterator j(neighbours.begin());
115 j != neighbours.end();
116 ++j) {
118 SPItem *iv=*j;
119 Vertex v=nodelookup[iv->id];
120 Graph::edge_descriptor e; bool inserted;
121 tie(e, inserted)=add_edge(u,v,g);
122 weightmap[e]=1.0;
123 }
124 if(nlist) {
125 g_slist_free(nlist);
126 }
127 NR::Rect const item_box(sp_item_bbox_desktop(*i));
129 NR::Point ll(item_box.min());
130 minX=std::min(ll[0],minX);
131 minY=std::min(ll[1],minY);
132 NR::Point ur(item_box.max());
133 maxX=std::max(ur[0],maxX);
134 maxY=std::max(ur[1],maxY);
135 }
136 double width=maxX-minX;
137 double height=maxY-minY;
138 std::cout<<"Graph has |V|="<<num_vertices(g)<<" Width="<<width<<" Height="<<height<<std::endl;
139 PositionVec position_vec(num_vertices(g));
140 PositionMap position(position_vec.begin(), get(vertex_index, g));
141 write_graphviz(std::cout, g);
142 circle_graph_layout(g, position, width/2.0);
143 kamada_kawai_spring_layout(g, position, weightmap, side_length(width));
145 graph_traits<Graph>::vertex_iterator vi, vi_end;
146 for (std::list<SPItem *>::iterator it(selected.begin());
147 it != selected.end();
148 ++it)
149 {
150 SPItem *u=*it;
151 if(!isConnector(u)) {
152 NR::Rect const item_box(sp_item_bbox_desktop(u));
153 NR::Point const curr(item_box.midpoint());
154 NR::Point const dest(minX+width/2.0+position[nodelookup[u->id]].x,
155 minY+height/2.0+position[nodelookup[u->id]].y);
156 sp_item_move_rel(u, NR::translate(dest - curr));
157 }
158 }
159 }
160 #else
161 void graphlayout(GSList const *const items) {
162 std::cout<<"Connector network layout not available! Install boost graph library and recompile to enable."<<std::endl;
163 }
164 #endif // HAVE_BOOST_GRAPH_LIB