home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1999 mARCH / PCWK3A99.iso / Linux / DDD331 / DDD-3_1_.000 / DDD-3_1_ / ddd-3.1.1 / ddd / Graph.C < prev    next >
C/C++ Source or Header  |  1998-10-23  |  13KB  |  597 lines
  1. // $Id: Graph.C,v 1.20 1998/10/24 02:43:23 zeller Exp $
  2. // Graph Class
  3.  
  4. // Copyright (C) 1995 Technische Universitaet Braunschweig, Germany.
  5. // Written by Andreas Zeller <zeller@ips.cs.tu-bs.de>.
  6. // 
  7. // This file is part of DDD.
  8. // 
  9. // DDD is free software; you can redistribute it and/or
  10. // modify it under the terms of the GNU General Public
  11. // License as published by the Free Software Foundation; either
  12. // version 2 of the License, or (at your option) any later version.
  13. // 
  14. // DDD is distributed in the hope that it will be useful,
  15. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  17. // See the GNU General Public License for more details.
  18. // 
  19. // You should have received a copy of the GNU General Public
  20. // License along with DDD -- see the file COPYING.
  21. // If not, write to the Free Software Foundation, Inc.,
  22. // 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  23. // 
  24. // DDD is the data display debugger.
  25. // For details, see the DDD World-Wide-Web page, 
  26. // `http://www.cs.tu-bs.de/softech/ddd/',
  27. // or send a mail to the DDD developers <ddd@ips.cs.tu-bs.de>.
  28.  
  29. char Graph_rcsid[] = 
  30.     "$Id: Graph.C,v 1.20 1998/10/24 02:43:23 zeller Exp $";
  31.  
  32. #ifdef __GNUG__
  33. #pragma implementation
  34. #endif
  35.  
  36.  
  37. #include "Graph.h"
  38. #include "assert.h"
  39.  
  40. #include <X11/X.h>
  41. #include <X11/Xlib.h>
  42. #include <X11/Intrinsic.h>
  43.  
  44. DEFINE_TYPE_INFO_0(Graph)
  45.  
  46. // Destructor
  47. Graph::~Graph()
  48. {
  49.     GraphNode *n = firstNode();
  50.     while (n != 0)
  51.     {
  52.     GraphNode *next = nextNode(n);
  53.     delete n;
  54.     n = next;
  55.     }
  56.  
  57.     GraphEdge *e = firstEdge();
  58.     while (e != 0)
  59.     {
  60.     GraphEdge *next = nextEdge(e);
  61.     delete e;
  62.     e = next;
  63.     }
  64. }
  65.  
  66. // Copy Constructor
  67. Graph::Graph(const Graph &org_graph)
  68.     : _firstNode(0), _firstEdge(0)
  69. {
  70.     GraphNode *node, *new_node; 
  71.  
  72.     // Copy Nodes
  73.     node = org_graph._firstNode;
  74.    
  75.     if (node != 0)
  76.     {
  77.     do
  78.     {
  79.         new_node = node->dup();  // copy node
  80.         assert(new_node->next == 0);
  81.         assert(new_node->prev == 0);
  82.         assert(new_node->graph == 0);
  83.         new_node->next  = new_node;         
  84.         new_node->prev  = new_node;
  85.         new_node->graph = this;
  86.         addNodes(new_node); // add new_node to graph
  87.         node = node->next;
  88.  
  89.     } while(node != org_graph._firstNode);
  90.     }
  91.      
  92.     GraphEdge *edge, *new_edge;
  93.     
  94.     // Copy Edges
  95.     edge = org_graph._firstEdge;
  96.     
  97.     if (edge != 0)
  98.     {
  99.     do {
  100.         new_edge = edge->dup();
  101.         assert(new_edge->next == 0);    // edge must not be used yet
  102.         assert(new_edge->prev == 0);
  103.         assert(new_edge->graph == 0);
  104.         new_edge->next  = new_edge;        // now it is used
  105.         new_edge->prev  = new_edge;
  106.         new_edge->graph = this;
  107.         addUsedEdges(new_edge); // because of "enqueue" in addEdges()
  108.         edge = edge->next;
  109.  
  110.     } while(edge != org_graph._firstEdge);
  111.     }
  112.  
  113.     if (_firstEdge != 0)
  114.     {
  115.     // equal edge in original graph 
  116.     GraphEdge *org_edge = org_graph._firstEdge;
  117.         edge = _firstEdge;
  118.     GraphNode *from_node, *to_node;     
  119.      
  120.     // setup source and target of edges
  121.     do { 
  122.             // setup source node
  123.         from_node = getNode(org_edge->_from, org_graph);
  124.         edge->_from = from_node;
  125.  
  126.         // setup target node
  127.         to_node = getNode(org_edge->_to, org_graph);    
  128.         edge->_to = to_node;
  129.     
  130.         edge = edge->next;
  131.         org_edge = org_graph.nextEdge(org_edge);
  132.  
  133.     } while(edge != _firstEdge);
  134.  
  135.     // Enqueue edges
  136.     edge = _firstEdge; 
  137.  
  138.     do{
  139.         edge->enqueue();
  140.         edge = edge->next;
  141.     } while(edge != _firstEdge);
  142.     }
  143. }
  144.   
  145.  
  146.  
  147. // Add Nodes
  148. void Graph::addNodes(GraphNode *nodes)
  149. {
  150.     // Add Nodes
  151.     if (_firstNode == 0)
  152.     _firstNode = nodes;
  153.     else
  154.     {
  155.     // setup next chain
  156.     _firstNode->prev->next = nodes;
  157.     nodes->prev->next = _firstNode;
  158.  
  159.     // setup prev chain
  160.     GraphNode *old_prev = nodes->prev;
  161.     nodes->prev = _firstNode->prev;
  162.     _firstNode->prev = old_prev;
  163.     }
  164. }
  165.  
  166. // Add Edges
  167. void Graph::addEdges(GraphEdge *edges)
  168. {
  169.     // Enqueue edges
  170.     GraphEdge *e = edges; 
  171.     do {
  172.     e->enqueue();
  173.     e = e->next;
  174.     } while (e != edges);
  175.     
  176.     // Add edges
  177.     if (_firstEdge == 0)
  178.     _firstEdge = edges;
  179.     else
  180.     {
  181.     // setup next chain
  182.     _firstEdge->prev->next = edges;
  183.     edges->prev->next = _firstEdge;
  184.  
  185.     // setup prev chain
  186.     GraphEdge *old_prev = edges->prev;
  187.     edges->prev = _firstEdge->prev;
  188.     _firstEdge->prev = old_prev;
  189.     }
  190. }
  191.  
  192. // Add used Edges, i.e. add edges of a graph
  193. void Graph::addUsedEdges(GraphEdge *edges)
  194. {
  195.     // Add edges
  196.     if (_firstEdge == 0)
  197.     _firstEdge = edges;
  198.     else
  199.     {
  200.     // setup next chain
  201.     _firstEdge->prev->next = edges;
  202.     edges->prev->next = _firstEdge;
  203.  
  204.     // setup prev chain
  205.     GraphEdge *old_prev = edges->prev;
  206.     edges->prev = _firstEdge->prev;
  207.     _firstEdge->prev = old_prev;
  208.     }
  209. }
  210.  
  211. // Make NODE first node in node list
  212. void Graph::makeNodeFirst(GraphNode *node)
  213. {
  214.     if (!haveNode(node))
  215.     return;
  216.     if (node == _firstNode)
  217.     return;
  218.  
  219.     // Chain out NODE
  220.     node->prev->next = node->next;
  221.     node->next->prev = node->prev;
  222.  
  223.     // Chain in at FIRSTNODE.
  224.     node->next = _firstNode;
  225.     node->prev = _firstNode->prev;
  226.  
  227.     node->next->prev = node;
  228.     node->prev->next = node;
  229.  
  230.     // Have FIRSTNODE point at NODE.
  231.     _firstNode = node;
  232.  
  233.     assert(OK());
  234. }
  235.  
  236. // Make NODE last node in node list
  237. void Graph::makeNodeLast(GraphNode *node)
  238. {
  239.     if (!haveNode(node))
  240.     return;
  241.     if (node == _firstNode->prev)
  242.     return;
  243.  
  244.     // Chain out NODE
  245.     node->prev->next = node->next;
  246.     node->next->prev = node->prev;
  247.     if (_firstNode == node)
  248.     _firstNode = node->next;
  249.  
  250.     // Chain in at FIRSTNODE.
  251.     node->next = _firstNode;
  252.     node->prev = _firstNode->prev;
  253.  
  254.     node->next->prev = node;
  255.     node->prev->next = node;
  256.  
  257.     // Have FIRSTNODE point at NODE's successor.
  258.     _firstNode = node->next;
  259.  
  260.     assert(OK());
  261. }
  262.  
  263. // Make EDGE first edge in edge list
  264. void Graph::makeEdgeFirst(GraphEdge *edge)
  265. {
  266.     if (!haveEdge(edge))
  267.     return;
  268.     if (edge == _firstEdge)
  269.     return;
  270.  
  271.     // Chain out EDGE
  272.     edge->prev->next = edge->next;
  273.     edge->next->prev = edge->prev;
  274.  
  275.     // Chain in at FIRSTEDGE.
  276.     edge->next = _firstEdge;
  277.     edge->prev = _firstEdge->prev;
  278.  
  279.     edge->next->prev = edge;
  280.     edge->prev->next = edge;
  281.  
  282.     // Have FIRSTEDGE point at EDGE.
  283.     _firstEdge = edge;
  284.  
  285.     assert(OK());
  286. }
  287.  
  288. // Make EDGE last edge in edge list
  289. void Graph::makeEdgeLast(GraphEdge *edge)
  290. {
  291.     if (!haveEdge(edge))
  292.     return;
  293.     if (edge == _firstEdge->prev)
  294.     return;
  295.  
  296.     // Chain out EDGE
  297.     edge->prev->next = edge->next;
  298.     edge->next->prev = edge->prev;
  299.     if (_firstEdge == edge)
  300.     _firstEdge = edge->next;
  301.  
  302.     // Chain in at FIRSTEDGE.
  303.     edge->next = _firstEdge;
  304.     edge->prev = _firstEdge->prev;
  305.  
  306.     edge->next->prev = edge;
  307.     edge->prev->next = edge;
  308.  
  309.     // Have FIRSTEDGE point at EDGE's successor.
  310.     _firstEdge = edge->next;
  311.  
  312.     assert(OK());
  313. }
  314.  
  315. // Remove Node
  316. void Graph::removeNode(GraphNode *node)
  317. {
  318.     if (!haveNode(node))
  319.     return;
  320.  
  321.     GraphEdge *e;
  322.  
  323.     // Remove edges
  324.     while ((e = node->firstFrom()) != 0)
  325.     removeEdge(e);
  326.     while ((e = node->firstTo()) != 0)
  327.     removeEdge(e);
  328.  
  329.     if (node == _firstNode)
  330.     _firstNode = node->next;
  331.  
  332.     if (node == _firstNode)
  333.     {
  334.     assert(node->prev == node);
  335.     assert(node->next == node);
  336.     _firstNode = 0;
  337.     }
  338.     else
  339.     {
  340.     // remove node from next and prev chain
  341.     node->prev->next = node->next;
  342.     node->next->prev = node->prev;
  343.     }
  344.  
  345.     node->next  = 0;
  346.     node->prev  = 0;
  347.     node->graph = 0;
  348. }
  349.  
  350. // Remove Edge
  351. void Graph::removeEdge(GraphEdge *edge)
  352. {
  353.     if (!haveEdge(edge))
  354.     return;
  355.  
  356.     edge->dequeue();
  357.  
  358.     if (edge == _firstEdge)
  359.     _firstEdge = edge->next;
  360.  
  361.     if (edge == _firstEdge)
  362.     {
  363.     assert(edge->prev == edge);
  364.     assert(edge->next == edge);
  365.     _firstEdge = 0;
  366.     }
  367.     else
  368.     {
  369.     // remove edge from next and prev chain
  370.     edge->prev->next = edge->next;
  371.     edge->next->prev = edge->prev;
  372.     }
  373.  
  374.     edge->next  = 0;
  375.     edge->prev  = 0;
  376.     edge->graph = 0;
  377. }
  378.  
  379.  
  380. // Get the equal node to "org_node"
  381. // needed by the Copy-Constructor
  382. GraphNode *Graph::getNode(GraphNode *org_node, const Graph& org_graph) const
  383. {
  384.     GraphNode *search_node = org_graph._firstNode;
  385.     GraphNode *dup_node = _firstNode;
  386.      
  387.      while (search_node != org_node)
  388.      {
  389.      dup_node = dup_node->next;
  390.      search_node = search_node->next;
  391.      }
  392.  
  393.      return dup_node;
  394. }
  395.  
  396. // Draw
  397. void Graph::draw(Widget w, const BoxRegion& exposed, const GraphGC& _gc) const
  398. {
  399.     GraphGC gc(_gc);
  400.  
  401.     // get default gcs
  402.     if (gc.nodeGC   == 0)
  403.     gc.nodeGC   = DefaultGCOfScreen(XtScreen(w));
  404.     if (gc.edgeGC   == 0)
  405.     gc.edgeGC   = DefaultGCOfScreen(XtScreen(w));
  406.     if (gc.invertGC == 0)
  407.     gc.invertGC = DefaultGCOfScreen(XtScreen(w));
  408.     if (gc.clearGC  == 0)
  409.     gc.clearGC  = DefaultGCOfScreen(XtScreen(w));
  410.  
  411.     // draw all edges
  412.     for (GraphEdge *edge = firstVisibleEdge(); edge != 0; 
  413.      edge = nextVisibleEdge(edge))
  414.     edge->draw(w, exposed, gc);
  415.  
  416.     // draw all nodes
  417.     for (GraphNode *node = firstVisibleNode(); node != 0; 
  418.      node = nextVisibleNode(node))
  419.     {
  420.     if (node->redraw() || !gc.redraw)
  421.         node->draw(w, exposed, gc);
  422.     if (gc.redraw)
  423.         node->redraw() = false;
  424.     }
  425. }
  426.  
  427.  
  428. // Print
  429. void Graph::begin_color(ostream& os, const PrintGC& gc,
  430.             unsigned short red,
  431.             unsigned short green,
  432.             unsigned short blue) const
  433. {
  434.     if (gc.isPostScript())
  435.     {
  436.     const PostScriptPrintGC &ps = const_ref_cast(PostScriptPrintGC, gc);
  437.  
  438.     if (ps.color)
  439.     {
  440.         // Set edge color
  441.         os << double(red)   / 65535.0 << " "
  442.            << double(green) / 65535.0 << " "
  443.            << double(blue)  / 65535.0 << " "
  444.            << "begincolor*\n";
  445.     }
  446.     }
  447. }
  448.  
  449. void Graph::end_color(ostream& os, const PrintGC& gc) const
  450. {
  451.     if (gc.isPostScript())
  452.     {
  453.     const PostScriptPrintGC &ps = const_ref_cast(PostScriptPrintGC, gc);
  454.  
  455.     if (ps.color)
  456.         os << "endcolor*\n";
  457.     }
  458. }
  459.  
  460. void Graph::_print(ostream& os, const GraphGC& _gc) const
  461. {
  462.     // We cannot print hints, so leave them alone
  463.     GraphGC gc(_gc);
  464.     gc.drawHints = false;
  465.     gc.hintSize  = 0;
  466.  
  467.     if (firstVisibleEdge() != 0)
  468.     {
  469.     // Print all edges
  470.     begin_color(os, *gc.printGC, gc.edge_red, gc.edge_green, gc.edge_blue);
  471.  
  472.     // If printSelectedNodesOnly, print only edges between selected nodes
  473.     for (GraphEdge *edge = firstVisibleEdge(); edge != 0; 
  474.          edge = nextVisibleEdge(edge))
  475.     {
  476.         if (!gc.printSelectedNodesOnly ||
  477.         (edge->from()->selected() && edge->to()->selected()))
  478.         edge->_print(os, gc);
  479.     }
  480.  
  481.     end_color(os, *gc.printGC);
  482.     }
  483.  
  484.     if (firstVisibleNode() != 0)
  485.     {
  486.     // Print all nodes
  487.     begin_color(os, *gc.printGC, gc.node_red, gc.node_green, gc.node_blue);
  488.  
  489.     // If printSelectedNodesOnly, print only selected nodes
  490.     for (GraphNode *node = firstVisibleNode(); node != 0; 
  491.          node = nextVisibleNode(node))
  492.     {
  493.         if (!gc.printSelectedNodesOnly || node->selected())
  494.         node->_print(os, gc);
  495.     }
  496.  
  497.     end_color(os, *gc.printGC);
  498.     }
  499. }
  500.     
  501.  
  502. // Echo
  503. ostream& operator << (ostream& s, const Graph& g)
  504. {
  505.     // echo all edges
  506.     for (GraphEdge *edge = g.firstEdge(); edge != 0; edge = g.nextEdge(edge))
  507.     s << *edge << "\n";
  508.  
  509.     return s;
  510. }
  511.  
  512.  
  513. // Region occupied by graph
  514. BoxRegion Graph::region(const GraphGC& gc, bool selected_only) const
  515. {
  516.     if (firstVisibleNode() == 0)
  517.     return BoxRegion();
  518.  
  519.     BoxRegion r;
  520.     for (GraphNode *node = firstVisibleNode(); node != 0; 
  521.      node = nextVisibleNode(node))
  522.     {
  523.     if (!selected_only || node->selected())
  524.     {
  525.         r = r | node->region(gc);
  526.     }
  527.     }
  528.  
  529.     for (GraphEdge *edge = firstVisibleEdge(); edge != 0; 
  530.      edge = nextVisibleEdge(edge))
  531.     {
  532.     if (!selected_only ||
  533.         (edge->from()->selected() && edge->to()->selected()))
  534.     {
  535.         r = r | edge->region(gc);
  536.     }
  537.     }
  538.  
  539.     return r;
  540. }
  541.  
  542. // Visible nodes and edges
  543. GraphNode *Graph::firstVisibleNode() const
  544. {
  545.     GraphNode *node = firstNode();
  546.     while (node != 0 && node->hidden())
  547.     node = nextNode(node);
  548.     return node;
  549. }
  550.  
  551. GraphNode *Graph::nextVisibleNode(GraphNode *ref) const
  552. {
  553.     GraphNode *node = nextNode(ref);
  554.     while (node != 0 && node->hidden())
  555.     node = nextNode(node);
  556.     return node;
  557. }
  558.  
  559. GraphEdge *Graph::firstVisibleEdge() const
  560. {
  561.     GraphEdge *edge = firstEdge();
  562.     while (edge != 0 && (edge->hidden() 
  563.              || edge->from()->hidden() || edge->to()->hidden()))
  564.     edge = nextEdge(edge);
  565.     return edge;
  566. }
  567.  
  568. GraphEdge *Graph::nextVisibleEdge(GraphEdge *ref) const
  569. {
  570.     GraphEdge *edge = nextEdge(ref);
  571.     while (edge != 0 && (edge->hidden() 
  572.              || edge->from()->hidden() || edge->to()->hidden()))
  573.     edge = nextEdge(edge);
  574.     return edge;
  575. }
  576.  
  577. // representation invariant
  578. bool Graph::OK() const
  579. {
  580.     for (GraphNode *n = firstNode(); n != 0; n = nextNode(n))
  581.     {
  582.     assert(n->prev->next == n);
  583.     assert(n->next->prev == n);
  584.     assert(n->OK());
  585.     }
  586.  
  587.     for (GraphEdge *e = firstEdge(); e != 0; e = nextEdge(e))
  588.     {
  589.     assert(e->prev->next == e);
  590.     assert(e->next->prev == e);
  591.     assert(e->OK());
  592.     }
  593.  
  594.     return true;
  595. }
  596.  
  597.