From 12b21e1d27f43deaa748419919b40b80cedd0ddd Mon Sep 17 00:00:00 2001
From: Tim Dwyer <tgdwyer@gmail.com>
Date: Wed, 12 Jul 2006 00:55:58 +0000
Subject: Previously graph layout was done using the Kamada-Kawai layout
 algorithm implemented in Boost.  I am replacing this with a custom
 implementation of a constrained stress-majorization algorithm.

The stress-majorization algorithm is more robust and has better convergence
characteristics than Kamada-Kawai, and also simple constraints can be placed
on node position (for example, to enforce downward-pointing edges, non-overlap constraints, or cluster constraints).

Another big advantage is that we no longer need Boost.

I've tested the basic functionality, but I have yet to properly handle
disconnected graphs or to properly scale the resulting layout.

This commit also includes significant refactoring... the quadratic program solver - libvpsc (Variable Placement with Separation Constraints) has been moved to src/libvpsc and the actual graph layout algorithm is in libcola.

(bzr r1394)
---
 src/graphlayout/graphlayout.cpp | 99 ++++++++++++++++-------------------------
 1 file changed, 39 insertions(+), 60 deletions(-)

(limited to 'src/graphlayout/graphlayout.cpp')

diff --git a/src/graphlayout/graphlayout.cpp b/src/graphlayout/graphlayout.cpp
index 00829dac8..42b867a33 100644
--- a/src/graphlayout/graphlayout.cpp
+++ b/src/graphlayout/graphlayout.cpp
@@ -14,7 +14,6 @@
 #include <iostream>
 #include <config.h>
 
-#ifdef HAVE_BOOST_GRAPH_LIB
 #include "sp-path.h"
 #include "sp-item.h"
 #include "sp-item-transform.h"
@@ -22,24 +21,15 @@
 #include "conn-avoid-ref.h"
 #include "libavoid/connector.h"
 #include "libavoid/geomtypes.h"
-#include <boost/graph/kamada_kawai_spring_layout.hpp>
-#include <boost/graph/circle_layout.hpp>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/graphviz.hpp>
+#include "libcola/cola.h"
+#include "libvpsc/generate-constraints.h"
 #include <map>
 #include <vector>
 #include <algorithm>
 #include <float.h>
 
-using namespace boost;
-
-// create a typedef for the Graph type
-typedef adjacency_list<vecS, vecS, undirectedS, no_property, 
-	property<edge_weight_t, double> > Graph;
-typedef property_map<Graph, edge_weight_t>::type WeightMap;
-typedef graph_traits<Graph>::vertex_descriptor Vertex;
-typedef std::vector<Avoid::Point> PositionVec;
-typedef iterator_property_map<PositionVec::iterator, property_map<Graph, vertex_index_t>::type> PositionMap;
+using namespace std;
+using namespace cola;
 
 /**
  * Returns true if item is a connector
@@ -56,7 +46,7 @@ bool isConnector(SPItem const *const i) {
  * Scans the items list and places those items that are 
  * not connectors in filtered
  */
-void filterConnectors(GSList const *const items, std::list<SPItem *> &filtered) {
+void filterConnectors(GSList const *const items, list<SPItem *> &filtered) {
 	for(GSList *i=(GSList *)items; i!=NULL; i=i->next) {
 		SPItem *item=SP_ITEM(i->data);
 		if(!isConnector(item)) {
@@ -75,90 +65,79 @@ void graphlayout(GSList const *const items) {
 	}
 
 	using Inkscape::Util::GSListConstIterator;
-	std::list<SPItem *> selected;
+	list<SPItem *> selected;
 	filterConnectors(items,selected);
 	if (selected.empty()) return;
 
-	int n=selected.size();
-	std::cout<<"|V|="<<n<<std::endl;
-
-	Graph g;
+	const unsigned n=selected.size();
+	cout<<"|V|="<<n<<endl;
+	//Check 2 or more selected objects
+	if (n < 2) return;
 
 	double minX=DBL_MAX, minY=DBL_MAX, maxX=-DBL_MAX, maxY=-DBL_MAX;
 
-	std::map<std::string,Vertex> nodelookup;
-	for (std::list<SPItem *>::iterator i(selected.begin());
+	map<string,unsigned> nodelookup;
+	vector<Rectangle*> rs;
+	vector<Edge> es;
+	for (list<SPItem *>::iterator i(selected.begin());
 		i != selected.end();
 		++i)
 	{
 		SPItem *u=*i;
-		std::cout<<"Creating node for id: "<<u->id<<std::endl;
-		nodelookup[u->id]=add_vertex(g);
+		NR::Rect const item_box(sp_item_bbox_desktop(u));
+		NR::Point ll(item_box.min());
+		NR::Point ur(item_box.max());
+		minX=min(ll[0],minX); minY=min(ll[1],minY);
+	        maxX=max(ur[0],maxX); maxY=max(ur[1],maxY);
+		cout<<"Creating node for id: "<<u->id<<endl;
+		nodelookup[u->id]=rs.size();
+		rs.push_back(new Rectangle(ll[0],ur[0],ll[1],ur[1]));
 	}
 
-	//Check 2 or more selected objects
-	if (n < 2) return;
 
-	WeightMap weightmap=get(edge_weight, g);
-	for (std::list<SPItem *>::iterator i(selected.begin());
+	for (list<SPItem *>::iterator i(selected.begin());
 		i != selected.end();
 		++i)
 	{
-		using NR::X; using NR::Y;
 		SPItem *iu=*i;
-		std::cout<<"Getting neighbours for id: "<<iu->id<<std::endl;
-		Vertex u=nodelookup[iu->id];
+		cout<<"Getting neighbours for id: "<<iu->id<<endl;
+		unsigned u=nodelookup[iu->id];
 		GSList *nlist=iu->avoidRef->getAttachedShapes(Avoid::runningFrom);
-		std::list<SPItem *> neighbours;
+		list<SPItem *> neighbours;
 		neighbours.insert<GSListConstIterator<SPItem *> >(neighbours.end(),nlist,NULL);
-		for (std::list<SPItem *>::iterator j(neighbours.begin());
+		for (list<SPItem *>::iterator j(neighbours.begin());
 				j != neighbours.end();
 				++j) {
 			
 			SPItem *iv=*j;
-			Vertex v=nodelookup[iv->id];
-			Graph::edge_descriptor e; bool inserted;
-			tie(e, inserted)=add_edge(u,v,g);
-			weightmap[e]=1.0;
+			// What do we do if iv not in nodelookup?!?!
+			unsigned v=nodelookup[iv->id];
+			es.push_back(make_pair(u,v));
 		}
 		if(nlist) {
 			g_slist_free(nlist);
 		}
-		NR::Rect const item_box(sp_item_bbox_desktop(*i));
-			
-		NR::Point ll(item_box.min());
-		minX=std::min(ll[0],minX);
-		minY=std::min(ll[1],minY);
-		NR::Point ur(item_box.max());
-		maxX=std::max(ur[0],maxX);
-		maxY=std::max(ur[1],maxY);
 	}
 	double width=maxX-minX;
 	double height=maxY-minY;
-	std::cout<<"Graph has |V|="<<num_vertices(g)<<" Width="<<width<<" Height="<<height<<std::endl;
-  	PositionVec position_vec(num_vertices(g));
-  	PositionMap position(position_vec.begin(), get(vertex_index, g));
-  	write_graphviz(std::cout, g);
-	circle_graph_layout(g, position, width/2.0);
-	kamada_kawai_spring_layout(g, position, weightmap, side_length(width));
+	const unsigned E = es.size();
+	double eweights[E];
+	fill(eweights,eweights+E,1);
 
-	graph_traits<Graph>::vertex_iterator vi, vi_end;
-	for (std::list<SPItem *>::iterator it(selected.begin());
+	ConstrainedMajorizationLayout alg(rs,es,eweights,width/n);
+	alg.run();
+	
+	for (list<SPItem *>::iterator it(selected.begin());
 		it != selected.end();
 		++it)
 	{
 		SPItem *u=*it;
 		if(!isConnector(u)) {
+			Rectangle* r=rs[nodelookup[u->id]];
 			NR::Rect const item_box(sp_item_bbox_desktop(u));
 			NR::Point const curr(item_box.midpoint());
-			NR::Point const dest(minX+width/2.0+position[nodelookup[u->id]].x,
-				     	minY+height/2.0+position[nodelookup[u->id]].y);
+			NR::Point const dest(r->getCentreX(),r->getCentreY());
 			sp_item_move_rel(u, NR::translate(dest - curr));
 		}
 	}
 }
-#else
-void graphlayout(GSList const *const items) {
-	std::cout<<"Connector network layout not available!  Install boost graph library and recompile to enable."<<std::endl;
-}
-#endif // HAVE_BOOST_GRAPH_LIB
-- 
cgit v1.2.3