From 6931de4f317866a8d4874fa7f08926b91f55debf Mon Sep 17 00:00:00 2001 From: tgdwyer Date: Sun, 16 Jul 2006 13:48:42 +0000 Subject: [PATCH] Layout algorithm is now applied to each connected component in the selection separately. Previously, behaviour of layout on disconnected graphs was... undefined! --- src/graphlayout/graphlayout.cpp | 29 +++--- src/libcola/Makefile_insert | 3 +- src/libcola/cola.h | 21 ++++- src/libcola/connected_components.cpp | 67 ++++++++++++++ src/libcola/cycle_detector.cpp | 133 ++++++++++++++++----------- src/libcola/cycle_detector.h | 39 ++++---- 6 files changed, 201 insertions(+), 91 deletions(-) create mode 100644 src/libcola/connected_components.cpp diff --git a/src/graphlayout/graphlayout.cpp b/src/graphlayout/graphlayout.cpp index 403145636..72c47d9bf 100644 --- a/src/graphlayout/graphlayout.cpp +++ b/src/graphlayout/graphlayout.cpp @@ -76,8 +76,6 @@ void graphlayout(GSList const *const items) { //Check 2 or more selected objects if (n < 2) return; - double minX=DBL_MAX, minY=DBL_MAX, maxX=-DBL_MAX, maxY=-DBL_MAX; - map nodelookup; vector rs; vector es; @@ -89,8 +87,6 @@ void graphlayout(GSList const *const items) { 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); nodelookup[u->id]=rs.size(); rs.push_back(new Rectangle(ll[0],ur[0],ll[1],ur[1])); } @@ -140,7 +136,7 @@ void graphlayout(GSList const *const items) { map::iterator v_pair=nodelookup.find(iv->id); if(v_pair!=nodelookup.end()) { unsigned v=v_pair->second; - //cout << "Edge: (" << u <<","<style->marker[SP_MARKER_LOC_END].set) { if(directed && strcmp(conn->style->marker[SP_MARKER_LOC_END].value,"none")) { @@ -154,16 +150,25 @@ void graphlayout(GSList const *const items) { g_slist_free(nlist); } } - //double width=maxX-minX; - //double height=maxY-minY; const unsigned E = es.size(); double eweights[E]; fill(eweights,eweights+E,1); - - ConstrainedMajorizationLayout alg(rs,es,eweights,ideal_connector_length); - alg.setupConstraints(NULL,NULL,avoid_overlaps, - NULL,NULL,NULL,&scy,NULL,NULL); - alg.run(); + vector cs; + connectedComponents(rs,es,cs); + for(unsigned i=0;iedges.size();j++) { + Edge& e=c->edges[j]; + printf("(%d,%d) ",e.first,e.second); + } + if(c->edges.size()<2) continue; + cout << endl; + ConstrainedMajorizationLayout alg(c->rects,c->edges,eweights,ideal_connector_length); + alg.setupConstraints(NULL,NULL,avoid_overlaps, + NULL,NULL,NULL,&scy,NULL,NULL); + alg.run(); + } for (list::iterator it(selected.begin()); it != selected.end(); diff --git a/src/libcola/Makefile_insert b/src/libcola/Makefile_insert index f8f9de20c..dc032a289 100644 --- a/src/libcola/Makefile_insert +++ b/src/libcola/Makefile_insert @@ -14,4 +14,5 @@ libcola_libcola_a_SOURCES = libcola/cola.h\ libcola/shortest_paths.cpp\ libcola/shortest_paths.h\ libcola/straightener.h\ - libcola/straightener.cpp + libcola/straightener.cpp\ + libcola/connected_components.cpp diff --git a/src/libcola/cola.h b/src/libcola/cola.h index cc99515bf..e0cf1257c 100644 --- a/src/libcola/cola.h +++ b/src/libcola/cola.h @@ -17,9 +17,24 @@ typedef vector Cluster; typedef vector Clusters; +using vpsc::Rectangle; + namespace cola { typedef pair Edge; + // a graph component with a list of node_ids giving indices for some larger list of nodes + // for the nodes in this component, and a list of edges - node indices relative to this component + struct Component { + vector node_ids; + vector rects; + vector edges; + }; + // for a graph of n nodes, return connected components + void connectedComponents( + vector &rs, + vector &es, + vector &components); + // defines references to three variables for which the goal function // will be altered to prefer points u-b-v are in a linear arrangement // such that b is placed at u+t(v-u). @@ -121,7 +136,7 @@ namespace cola { class ConstrainedMajorizationLayout { public: ConstrainedMajorizationLayout( - vector& rs, + vector& rs, vector& es, double* eweights, double idealLength, @@ -141,7 +156,7 @@ namespace cola { straightenEdges(NULL) { assert(rs.size()==n); - boundingBoxes = new vpsc::Rectangle*[rs.size()]; + boundingBoxes = new Rectangle*[rs.size()]; copy(rs.begin(),rs.end(),boundingBoxes); double** D=new double*[n]; @@ -229,7 +244,7 @@ namespace cola { double** Dij; double tol; TestConvergence& done; - vpsc::Rectangle** boundingBoxes; + Rectangle** boundingBoxes; double *X, *Y; Clusters* clusters; double edge_length; diff --git a/src/libcola/connected_components.cpp b/src/libcola/connected_components.cpp new file mode 100644 index 000000000..8450e4874 --- /dev/null +++ b/src/libcola/connected_components.cpp @@ -0,0 +1,67 @@ +#include +#include "cola.h" +using namespace std; + +namespace cola { + namespace ccomponents { + struct Node { + unsigned id; + bool visited; + vector neighbours; + Rectangle* r; + }; + // Depth first search traversal of graph to find connected component + void dfs(Node* v, + set& remaining, + Component* component, + map > &cmap) { + v->visited=true; + remaining.erase(v); + cmap[v->id]=make_pair(component,component->node_ids.size()); + component->node_ids.push_back(v->id); + component->rects.push_back(v->r); + for(unsigned i=0;ineighbours.size();i++) { + Node* u=v->neighbours[i]; + if(!u->visited) { + dfs(u,remaining,component,cmap); + } + } + } + } + + using namespace ccomponents; + + // for a graph of n nodes, return connected components + void connectedComponents( + vector &rs, + vector &es, + vector &components) { + unsigned n=rs.size(); + vector vs(n); + set remaining; + for(unsigned i=0;i::iterator e=es.begin();e!=es.end();e++) { + vs[e->first].neighbours.push_back(&vs[e->second]); + vs[e->second].neighbours.push_back(&vs[e->first]); + } + map > cmap; + while(!remaining.empty()) { + Component* component=new Component; + Node* v=*remaining.begin(); + dfs(v,remaining,component,cmap); + components.push_back(component); + } + for(vector::iterator e=es.begin();e!=es.end();e++) { + pair u=cmap[e->first], + v=cmap[e->second]; + assert(u.first==v.first); + u.first->edges.push_back(make_pair(u.second,v.second)); + } + } +} +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 diff --git a/src/libcola/cycle_detector.cpp b/src/libcola/cycle_detector.cpp index ddc056e4d..89a2ccaae 100644 --- a/src/libcola/cycle_detector.cpp +++ b/src/libcola/cycle_detector.cpp @@ -9,6 +9,7 @@ #include #include +#define VISIT_DEBUG #define RUN_DEBUG using namespace std; @@ -20,14 +21,18 @@ TimeStamp Time; CycleDetector::CycleDetector(unsigned numVertices, Edges *edges) { this->V = numVertices; this->edges = edges; + nodes = NULL; // make the adjacency matrix this->make_matrix(); - assert(nodes.size() == this->V); + assert(nodes->size() == this->V); } CycleDetector::~CycleDetector() { - if (!nodes.empty()) { for (unsigned i = 0; i < nodes.size(); i++) { delete nodes[i]; } } + if (nodes != NULL) { + for (unsigned i = 0; i < nodes->size(); i++) { if ((*nodes)[i] != NULL) { delete (*nodes)[i]; } } + delete nodes; + } } void CycleDetector::make_matrix() { @@ -35,12 +40,16 @@ void CycleDetector::make_matrix() { Edge anEdge; Node *newNode; - if (!nodes.empty()) { for (map::iterator ni = nodes.begin(); ni != nodes.end(); ni++) { delete nodes[ni->first]; } } - nodes.clear(); + if (nodes != NULL) { + for (unsigned i = 0; i < nodes->size(); i++) { if ((*nodes)[i] != NULL) { delete (*nodes)[i]; } } + delete nodes; + } + + nodes = new vector(this->V, NULL); traverse.clear(); - // we should have no nodes in the list - assert(nodes.empty()); + // we should not have an empty array + assert(!nodes->empty()); assert(traverse.empty()); // from the edges passed, fill the adjacency matrix @@ -53,37 +62,37 @@ void CycleDetector::make_matrix() { #ifdef ADJMAKE_DEBUG cout << "vertex1: " << anEdge.first << ", vertex2: " << anEdge.second << endl; #endif - if (nodes.find(anEdge.first) == nodes.end()) { + if (!find_node(nodes, anEdge.first)) { #ifdef ADJMAKE_DEBUG cout << "Making a new vector indexed at: " << anEdge.first << endl; #endif newNode = new Node(anEdge.first); newNode->dests.push_back(anEdge.second); - nodes[anEdge.first] = newNode; + (*nodes)[anEdge.first] = newNode; } else { - nodes[anEdge.first]->dests.push_back(anEdge.second); + (*nodes)[anEdge.first]->dests.push_back(anEdge.second); } // check if the destination vertex exists in the nodes map - if (nodes.find(anEdge.second) == nodes.end()) { + if (!find_node(nodes, anEdge.second)) { #ifdef ADJMAKE_DEBUG cerr << "Making a new vector indexed at: " << anEdge.second << endl; #endif newNode = new Node(anEdge.second); - nodes[anEdge.second] = newNode; + (*nodes)[anEdge.second] = newNode; } } - assert(!nodes.empty()); + assert(!nodes->empty()); // the following block is code to print out // the adjacency matrix. #ifdef ADJMAKE_DEBUG - for (map::iterator ni = nodes.begin(); ni != nodes.end(); ni++) { - Node *node = ni->second; + for (unsigned i = 0; i < nodes->size(); i++) { + Node *node = (*nodes)[i]; cout << "nodes[" << node->id << "]: "; if (isSink(node)) { cout << "SINK"; } @@ -96,26 +105,23 @@ void CycleDetector::make_matrix() { } vector *CycleDetector::detect_cycles() { - vector *cyclicEdgesMapping = NULL; + cyclicEdgesMapping = new vector(edges->size(), false); - assert(!nodes.empty()); + assert(!nodes->empty()); assert(!edges->empty()); // make a copy of the graph to ensure that we have visited all // vertices traverse.clear(); assert(traverse.empty()); - for (unsigned i = 0; i < V; i++) { traverse[i] = false; } + for (unsigned i = 0; i < V; i++) { traverse.push_back(i); } #ifdef SETUP_DEBUG - for (map::iterator ivi = traverse.begin(); ivi != traverse.end(); ivi++) { - cout << "traverse{" << ivi->first << "}: " << ivi->second << endl; + for (unsigned i = 0; i < traverse.size(); i++) { + cout << "traverse{" << i << "}: " << traverse[i] << endl; } #endif - // set up the mapping between the edges and their cyclic truth - for(unsigned i = 0; i < edges->size(); i++) { cyclicEdges[(*edges)[i]] = false; } - // find the cycles - assert(nodes.size() > 1); + assert(nodes->size() > 1); // while we still have vertices to visit, visit. while (!traverse.empty()) { @@ -126,19 +132,19 @@ vector *CycleDetector::detect_cycles() { #ifdef RUN_DEBUG cout << "Marking vertex(" << v << ") as CLOSED" << endl; #endif - nodes[v]->status = Node::DoneVisiting; + (*nodes)[v]->status = Node::DoneVisiting; } assert(seenInRun.empty()); #ifdef VISIT_DEBUG - cout << "begining search at vertex(" << traverse.begin()->first << ")" << endl; + cout << "begining search at vertex(" << traverse[0] << ")" << endl; #endif Time = 0; // go go go - visit(traverse.begin()->first); + visit(traverse[0]); } // clean up @@ -146,17 +152,6 @@ vector *CycleDetector::detect_cycles() { assert(seenInRun.empty()); assert(traverse.empty()); - cyclicEdgesMapping = new vector(edges->size(), false); - - for (unsigned i = 0; i < edges->size(); i++) { - if (cyclicEdges[(*edges)[i]]) { - (*cyclicEdgesMapping)[i] = true; - #ifdef OUTPUT_DEBUG - cout << "Setting cyclicEdgesMapping[" << i << "] to true" << endl; - #endif - } - } - return cyclicEdgesMapping; } @@ -165,60 +160,68 @@ void CycleDetector::mod_graph(unsigned numVertices, Edges *edges) { this->edges = edges; // remake the adjaceny matrix this->make_matrix(); - assert(nodes.size() == this->V); + assert(nodes->size() == this->V); } void CycleDetector::visit(unsigned k) { unsigned cycleOpen; + Node *thisNode = (*nodes)[k]; // state that we have seen this vertex - if (traverse.find(k) != traverse.end()) { + pair< bool, vector::iterator > haveSeen = find_node(traverse, k); + if (haveSeen.first) { #ifdef VISIT_DEBUG cout << "Visiting vertex(" << k << ") for the first time" << endl; #endif - traverse.erase(k); + traverse.erase(haveSeen.second); } seenInRun.push(k); // set up this node as being visited. - nodes[k]->stamp = ++Time; - nodes[k]->status = Node::BeingVisited; + thisNode->stamp = ++Time; + thisNode->status = Node::BeingVisited; // traverse to all the vertices adjacent to this vertex. - for (unsigned n = 0; n < nodes[k]->dests.size(); n++) { - unsigned v = nodes[k]->dests[n]; + for (unsigned n = 0; n < thisNode->dests.size(); n++) { + Node *otherNode = (*nodes)[thisNode->dests[n]]; - if (nodes[v]->status != Node::DoneVisiting) { - if (nodes[v]->status == Node::NotVisited) { + if (otherNode->status != Node::DoneVisiting) { + if (otherNode->status == Node::NotVisited) { // visit this node #ifdef VISIT_DEBUG - cout << "traversing from vertex(" << k << ") to vertex(" << v << ")" << endl; + cout << "traversing from vertex(" << k << ") to vertex(" << otherNode->id << ")" << endl; #endif - visit(v); + visit(otherNode->id); } // if we are part of a cycle get the timestamp of the ancestor - if (nodes[v]->cyclicAncestor != NULL) { cycleOpen = nodes[v]->cyclicAncestor->stamp; } + if (otherNode->cyclicAncestor != NULL) { cycleOpen = otherNode->cyclicAncestor->stamp; } // else just get the timestamp of the node we just visited - else { cycleOpen = nodes[v]->stamp; } + else { cycleOpen = otherNode->stamp; } // compare the stamp of the traversal with our stamp - if (cycleOpen <= nodes[k]->stamp) { - if (nodes[v]->cyclicAncestor == NULL) { nodes[v]->cyclicAncestor = nodes[v]; } + if (cycleOpen <= thisNode->stamp) { + if (otherNode->cyclicAncestor == NULL) { otherNode->cyclicAncestor = otherNode; } + // store the cycle - cyclicEdges[Edge(k,v)] = true; + for (unsigned i = 0; i < edges->size(); i++) { + if ((*edges)[i] == Edge(k, otherNode->id)) { (*cyclicEdgesMapping)[i] = true; } + #ifdef OUTPUT_DEBUG + cout << "Setting cyclicEdgesMapping[" << i << "] to true" << endl; + #endif + } + // this node is part of a cycle - if (nodes[k]->cyclicAncestor == NULL) { nodes[k]->cyclicAncestor = nodes[v]->cyclicAncestor; } + if (thisNode->cyclicAncestor == NULL) { thisNode->cyclicAncestor = otherNode->cyclicAncestor; } // see if we are part of a cycle with a cyclicAncestor that possesses a lower timestamp - if (nodes[v]->cyclicAncestor->stamp < nodes[k]->cyclicAncestor->stamp) { nodes[k]->cyclicAncestor = nodes[v]->cyclicAncestor; } + if (otherNode->cyclicAncestor->stamp < thisNode->cyclicAncestor->stamp) { thisNode->cyclicAncestor = otherNode->cyclicAncestor; } } } } } - // determines whether or not a vertex is a sink bool CycleDetector::isSink(Node *node) { // a vertex is a sink if it has no outgoing edges, @@ -226,3 +229,21 @@ bool CycleDetector::isSink(Node *node) { if (node->dests.empty()) { return true; } else { return false; } } + +bool CycleDetector::find_node(std::vector *& list, unsigned k) { + for (unsigned i = 0; i < this->V; i++) { + if ((*list)[i] != NULL) { + if ((*list)[i]->id == k) { return true; } + } + } + + return false; +} + +pair< bool, vector::iterator > CycleDetector::find_node(std::vector& list, unsigned k) { + for (vector::iterator ti = traverse.begin(); ti != traverse.end(); ti++) { + if (*ti == k) { return pair< bool, vector::iterator >(true, ti); } + } + + return pair< bool, vector::iterator >(false, traverse.end()); +} diff --git a/src/libcola/cycle_detector.h b/src/libcola/cycle_detector.h index 5cd52e324..fcb8722fe 100644 --- a/src/libcola/cycle_detector.h +++ b/src/libcola/cycle_detector.h @@ -4,12 +4,25 @@ #include #include #include -#include "cola.h" +#include typedef unsigned TimeStamp; typedef std::vector Edges; typedef std::vector CyclicEdges; -class Node; + +class Node { + public: + enum StatusType { NotVisited, BeingVisited, DoneVisiting }; + + unsigned id; + TimeStamp stamp; + Node *cyclicAncestor; + std::vector dests; + StatusType status; + + Node(unsigned id) { this->id = id; cyclicAncestor = NULL; status = NotVisited; } + ~Node() {} +}; class CycleDetector { public: @@ -26,29 +39,17 @@ class CycleDetector { Edges *edges; // internally used variables. - std::map nodes; // the nodes in the graph - std::map cyclicEdges; // the cyclic edges in the graph. - std::map traverse; // nodes still left to visit in the graph + std::vector *nodes; // the nodes in the graph + std::vector *cyclicEdgesMapping; // the cyclic edges in the graph. + std::vector traverse; // nodes still left to visit in the graph std::stack seenInRun; // nodes visited in a single pass. // internally used methods void make_matrix(); void visit(unsigned k); bool isSink(Node *node); -}; - -class Node { - public: - enum StatusType { NotVisited, BeingVisited, DoneVisiting }; - - unsigned id; - TimeStamp stamp; - Node *cyclicAncestor; - vector dests; - StatusType status; - - Node(unsigned id) { this->id = id; cyclicAncestor = NULL; status = NotVisited; } - ~Node() {} + bool find_node(std::vector *& list, unsigned k); + std::pair< bool, std::vector::iterator > find_node(std::vector& list, unsigned k); }; #endif -- 2.30.2