1 /***********************************************************************/ 2 /* Open Visualization Data Explorer */ 3 /* (C) Copyright IBM Corp. 1989,1999 */ 4 /* ALL RIGHTS RESERVED */ 5 /* This code licensed under the */ 6 /* "IBM PUBLIC LICENSE - Open Visualization Data Explorer" */ 7 /***********************************************************************/ 8 #ifndef _GraphLayout_h 9 #define _GraphLayout_h 10 #include "../base/defines.h" 11 #include "List.h" 12 13 #include "Base.h" 14 15 // 16 // referenced classes 17 // 18 class EditorWindow; 19 class WorkSpace; 20 class Node; 21 class Ark; 22 class UIComponent; 23 class VPEAnnotator; 24 class LayoutRow; 25 class LayoutInfo; 26 27 // 28 // Class name definition: 29 // 30 #define ClassGraphLayout "GraphLayout" 31 32 #if ONLY_IN_GRAPH_LAYOUT_CODE 33 34 class NodeDistance; 35 class LayoutGroup; 36 class SlotList; 37 class GraphLayout; 38 39 // 40 // There are several classes defined in this include file that ought 41 // to be invisible to all classes other than GraphLayout. 42 // 43 #define ClassLayoutInfo "LayoutInfo" 44 45 // 46 // Store as a sort of extension record in Node. 47 // 48 class LayoutInfo : public Base { 49 private: 50 boolean initialized; 51 52 protected: 53 friend class GraphLayout; 54 // proposed new location 55 int x,y; 56 57 // the original location is used to attempt to place 58 // disconnected subgraphs relative to eachother the same 59 // way as in the original layout. 60 int orig_x, orig_y; 61 62 // are the values in x,y set? 63 boolean positioned_yet; 64 65 // was the position of the node adjusted (in some 66 // screwy way) because of a collision with another node. 67 boolean collision; 68 69 // fetched width and height stored redundantly but 70 // avoids using XtGetValues over and over. 71 int w,h; 72 LayoutInfo()73 LayoutInfo () { 74 this->x = this->y = this->w = this->h = -1; 75 this->positioned_yet = FALSE; 76 this->collision = FALSE; 77 this->initialized = FALSE; 78 } 79 80 void initialize (UIComponent* uic); 81 isInitialized()82 virtual boolean isInitialized() { return this->initialized; } 83 84 public: ~LayoutInfo()85 virtual ~LayoutInfo(){} getOriginalXYPosition(int & x,int & y)86 void getOriginalXYPosition (int& x, int& y) { 87 x = this->orig_x; 88 y = this->orig_y; 89 } getXYPosition(int & x,int & y)90 void getXYPosition (int& x, int& y) { 91 x = this->x; 92 y = this->y; 93 } getXYSize(int & w,int & h)94 void getXYSize (int& w, int& h) { 95 w = this->w; 96 h = this->h; 97 } isPositioned()98 boolean isPositioned() { return this->positioned_yet; } reposition()99 void reposition() { this->collision = this->positioned_yet = FALSE; } setProposedLocation(int x,int y)100 virtual void setProposedLocation(int x, int y) { 101 this->x = x; 102 this->y = y; 103 this->positioned_yet = TRUE; 104 } 105 106 void setCollided(boolean c=TRUE) { this->collision = c; } collided()107 boolean collided() { return this->collision; } 108 109 // 110 // Returns a pointer to the class name. 111 // getClassName()112 virtual const char* getClassName() 113 { 114 return ClassLayoutInfo; 115 } 116 }; 117 118 #define ClassNodeInfo "NodeInfo" 119 class NodeInfo : public LayoutInfo 120 { 121 private: 122 Ark* destination; 123 124 NodeInfo* straightness_destination; 125 126 Ark* straightness_opportunity; 127 boolean straightness_set; 128 int offset_for_straightness; 129 130 protected: 131 friend class GraphLayout; 132 friend class LayoutRow; 133 int hops; 134 135 LayoutGroup* group; 136 137 List* connected_nodes; 138 boolean owns_list; 139 NodeInfo()140 NodeInfo () { 141 this->hops = 0; 142 this->group = NUL(LayoutGroup*); 143 this->connected_nodes = NUL(List*); 144 this->owns_list = FALSE; 145 this->straightness_set = FALSE; 146 this->straightness_destination = NUL(NodeInfo*); 147 } 148 void initialize (Node* n, int hops); 149 setGraphDepth(int d)150 void setGraphDepth(int d) { this->hops = d; } 151 152 // for qsort 153 static int SortByHop (const void* a, const void* b); 154 155 void registerStraightArc(int offset, Ark* arc); 156 Ark* hasStraightArc(int& offset); 157 void shiftStraightArc(int dx); 158 void setStraightnessDestination (NodeInfo* dest); 159 160 public: getGraphDepth()161 int getGraphDepth() { return this->hops; } 162 setLayoutGroup(LayoutGroup * group)163 void setLayoutGroup(LayoutGroup* group) { this->group = group; } getLayoutGroup()164 LayoutGroup* getLayoutGroup() { return this->group; } 165 166 virtual ~NodeInfo(); 167 168 List* getConnectedNodes(Node* n); 169 170 static void BuildList(Node* n, List* nodes); 171 172 void setConnectedNodes(List* nodes); 173 setDestination(Ark * arc)174 void setDestination(Ark* arc) { this->destination = arc; } getDestination()175 Ark* getDestination() { return this->destination; } 176 177 int getDestinationLocation (int& hop); 178 179 virtual void setProposedLocation(int x, int y); 180 getClassName()181 virtual const char* getClassName() 182 { 183 return ClassNodeInfo; 184 } 185 }; 186 187 #define ClassAnnotationInfo "AnnotationInfo" 188 class AnnotationInfo: public LayoutInfo 189 { 190 private: 191 friend class GraphLayout; 192 193 protected: AnnotationInfo()194 AnnotationInfo() { 195 this->nearby = 0; 196 this->nearbyCnt = 0; 197 } 198 199 void initialize (VPEAnnotator* dec); 200 201 NodeDistance** nearby; 202 int nearbyCnt; 203 204 static int SortByDistance(const void* a, const void* b); 205 206 static int NextX; 207 static int NextY; 208 209 public: 210 211 virtual ~AnnotationInfo(); 212 213 void findNearestNode(Node* reflow[], int reflow_count); 214 215 void reposition(Node* reflow[], int reflow_count, List& other_decorators); 216 217 // 218 // Returns a pointer to the class name. 219 // getClassName()220 virtual const char* getClassName() 221 { 222 return ClassAnnotationInfo; 223 } 224 }; 225 226 class NodeDistance 227 { 228 private: 229 Node* node; 230 int distance; 231 int location; 232 protected: 233 public: NodeDistance(Node * n,int distance,int location)234 NodeDistance (Node* n, int distance, int location) { 235 this->node = n; 236 this->distance = distance; 237 this->location = location; 238 } getNode()239 Node* getNode() { return this->node; } getDistance()240 int getDistance() { return this->distance; } getLocation()241 int getLocation() { return this->location; } 242 }; 243 244 #define ClassLayoutGroup "LayoutGroup" 245 class LayoutGroup : public Base 246 { 247 private: 248 boolean initialized; 249 int id; 250 protected: 251 int orig_x1,orig_y1,orig_x2,orig_y2; 252 int x1,y1,x2,y2; 253 int x,y; 254 static int Comparator(const void* a, const void* b); 255 static int SortByHop(const void* a, const void* b); 256 friend class GraphLayout; 257 258 void layout(Node* node, GraphLayout* mgr, List& positioned); 259 260 boolean straightenArcs(LayoutRow* row_array[], int rows); 261 262 public: LayoutGroup(int id)263 LayoutGroup(int id) { 264 this->initialized = FALSE; 265 this->x1 = this->orig_x1 = 999999; 266 this->y1 = this->orig_y1 = 999999; 267 this->x2 = this->orig_x2 = -999999; 268 this->y2 = this->orig_y2 = -999999; 269 this->id = id; 270 } ~LayoutGroup()271 virtual ~LayoutGroup(){} 272 void initialize (List* nodes); getOriginalXYPosition(int & x,int & y)273 void getOriginalXYPosition(int& x, int& y) { 274 x = this->orig_x1; 275 y = this->orig_y1; 276 } getXYSize(int & w,int & h)277 void getXYSize(int& w, int& h) { 278 w = this->x2 - this->x1; 279 h = this->y2 - this->y1; 280 } getOriginalXYSize(int & w,int & h)281 void getOriginalXYSize(int& w, int& h) { 282 w = this->orig_x2 - this->orig_x1; 283 h = this->orig_y2 - this->orig_y1; 284 } getXYPosition(int & x,int & y)285 void getXYPosition(int& x, int& y) { 286 x = this->x1; 287 y = this->y1; 288 } getId()289 int getId() { return this->id; } setProposedLocation(int x,int y)290 void setProposedLocation (int x, int y) { 291 this->x = x; 292 this->y = y; 293 } getProposedLocation(int & x,int & y)294 void getProposedLocation (int& x, int& y) { 295 x = this->x; 296 y = this->y; 297 } getClassName()298 virtual const char* getClassName() 299 { 300 return ClassLayoutGroup; 301 } 302 }; 303 304 class Slot 305 { 306 private: 307 int min, max; 308 friend class SlotList; 309 protected: 310 public: Slot(int min,int max)311 Slot (int min, int max) { 312 this->min = min; 313 this->max = max; 314 } 315 }; 316 317 #define ClassSlotList "SlotList" 318 class SlotList : public List 319 { 320 private: 321 protected: 322 public: SlotList()323 SlotList() { 324 this->appendElement(new Slot(-999999, 999999)); 325 } 326 virtual void clear(); 327 virtual ~SlotList(); 328 int isAvailable (int x, boolean left); 329 void occupy (int x, int width); getClassName()330 virtual const char* getClassName() 331 { 332 return ClassSlotList; 333 } 334 }; 335 336 #define ClassLayoutRow "LayoutRow" 337 class LayoutRow : public Base 338 { 339 private: 340 List nodes; 341 342 SlotList slot_list; 343 344 Node** node_array; 345 346 int id; 347 348 boolean sorted_by_x; 349 boolean sorted_by_destination_x; 350 351 protected: 352 friend class LayoutGroup; 353 LayoutRow(int id)354 LayoutRow(int id) { 355 this->id = id; 356 this->sorted_by_x = FALSE; 357 this->sorted_by_destination_x = FALSE; 358 } 359 addNode(Node * n)360 void addNode(Node* n) { this->nodes.appendElement(n); } 361 362 void sort (); 363 364 void layout(GraphLayout* mgr, int& previous_id); 365 366 void layout(SlotList* slots, GraphLayout* mgr, int& previous_id); 367 368 void position (Node* n, int& left_edge, int& right_edge, 369 GraphLayout* mgr, boolean go_left, SlotList* slots, 370 int previous_rows_hop); 371 372 static int SortByDestinationX(const void* a, const void* b); 373 static int SortByX(const void* a, const void* b); 374 375 boolean favorsLeftShift (Ark* arc, GraphLayout* mgr, boolean default_value); 376 377 void straightenArcs(boolean& changes_made); 378 379 public: getSlotList()380 SlotList* getSlotList() { return &this->slot_list; } 381 getId()382 int getId() { return this->id; } 383 384 virtual ~LayoutRow(); getClassName()385 virtual const char* getClassName() 386 { 387 return ClassLayoutRow; 388 } 389 }; 390 #endif 391 392 // 393 // GraphLayout class definition: 394 // 395 class GraphLayout : public Base 396 { 397 private: 398 friend class LayoutRow; // for positionSource 399 friend class AnnotationInfo; // for CanMoveTo 400 // 401 // Private member data: 402 // 403 EditorWindow* editor; 404 405 boolean adjustHopCounts (Node* reflow[], int reflow_count, int& min); 406 void adjustAncestorHops (Node* parent, int new_hop_count, int& min); 407 void adjustDescendantHops (Node* parent, int new_hop_count); 408 int computeRequiredHopsTo (Node* n); 409 int computeRequiredHopsToSiblingsOf (Node* n); 410 void fixForTooManyReceivers(Node* n, int& min); 411 412 // 413 // Return TRUE if the node's standin can move to x,y without 414 // causing overlap with any other node in the list. 415 // 416 boolean nodeCanMoveTo (Node* n, int x, int y); 417 418 // 419 // return TRUE if the positioning was accomplished but with collision 420 // 421 boolean positionSourceOverDest(Ark* arc, int& x, int& y); 422 423 // 424 // return TRUE if the positioning was accomplished but with collision 425 // 426 boolean positionDestUnderSource(Ark* arc, int& x, int& y); 427 428 // 429 // return TRUE if the positioning was accomplished but with collision 430 // 431 boolean positionDestBesideSibling(Ark* arc, int& x, int& y, boolean prefer_left, List *unusable_nodes); 432 433 // 434 // return TRUE if the positioning was accomplished but with collision 435 // 436 boolean positionSource(Ark* arc, int x); 437 438 void repositionGroups(Node* reflow[], int reflow_count); 439 440 protected: 441 // 442 // Protected member data: 443 // 444 445 static int HeightPerLevel; 446 static int GroupSpacing; 447 static int NodeSpacing; 448 449 static const char* ErrorMessages[]; 450 451 static int ArcComparator(const void* a, const void* b); 452 453 void bottomUpTraversal (Node* visit_kids_of, int current_depth, int& min); 454 455 boolean hasConnectedInputs(Node* n); 456 boolean hasConnectedOutputs(Node* n, Node* other_than=NUL(Node*)); 457 void unmarkAllNodes(Node* reflow[], int reflow_count); 458 459 boolean computeBoundingBox (List& nodes, int& minx, int& miny, int& maxx, int& maxy); 460 boolean computeBoundingBox (Node* nodes[], int count, int& minx, int& miny, 461 int& maxx, int& maxy, List* decorators=NUL(List*)); 462 463 void repositionDecorators (List& decorators, boolean same_event_flag, Node* reflow[], int reflow_count); 464 465 void computeHopCounts (Node* reflow[], int reflow_count); 466 467 // 468 // 469 void prepareAnnotationPlacement(List& decorators, Node* reflow[], int reflow_count, 470 const List& all_decorators, WorkSpace* workSpace, int& widest, int& tallest); 471 472 List layout_groups; 473 474 // 475 // Count the connected tabs and return the number of the specified 476 // tab in the ordering of the visible tabs. i.e. The 20th input 477 // of Image might be the 2nd input tab. 478 // 479 int countConnectedInputs (Node* n, int input, int& nth_tab); 480 int countConnectedOutputs (Node* n, int output, int& nth_tab); 481 482 void repositionNewPlacements (Node* , boolean , List&); 483 484 static boolean CanMoveTo (LayoutInfo* info, int x, int y, Node* reflow[], 485 int count, List* decorators); 486 487 boolean spreadOutSpaghettiFrom (Node* n, int& min); 488 489 int countConnectionsBetween (Node* source, Node* dest, boolean count_consecutive=TRUE); 490 491 public: 492 // 493 // Constructor: 494 // GraphLayout(EditorWindow * editor)495 GraphLayout(EditorWindow *editor) { 496 this->editor = editor; 497 } 498 499 static const char* SetHeightPerLevel(int hpl); 500 static const char* SetGroupSpacing(int gs); 501 static const char* SetNodeSpacing(int ns); 502 503 boolean entireGraph(WorkSpace* workspace, const List& nodes, const List& decorators); 504 505 static Ark* IsSingleInputNoOutputNode(Node* n, boolean& shares_an_output, boolean positioned=TRUE); 506 static boolean IsSingleOutputNoInputNode(Node* n); 507 508 // 509 // Destructor: 510 // ~GraphLayout()511 ~GraphLayout() { } 512 513 boolean hasNoCloserDescendant (Node* source, Node* dest); 514 515 // 516 // append an ancestor node of root to the list if 517 // 1) it's not already in the list 518 // 2) The node doesn't have some other descents that it's 519 // 'more closely' related to. 520 // For each node appended to the list append the arc that reaches 521 // that node. 522 // 523 void getSpecialAncestorsOf (Node* root, List& ancestors, List& arcs, boolean last_call=TRUE); 524 525 // 526 // Returns a pointer to the class name. 527 // getClassName()528 const char* getClassName() 529 { 530 return ClassGraphLayout; 531 } 532 }; 533 534 535 #endif // _GraphLayout_h 536