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.h < prev    next >
C/C++ Source or Header  |  1998-10-05  |  6KB  |  220 lines
  1. // $Id: Graph.h,v 1.18 1998/10/05 12:21:05 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. #ifndef _DDD_Graph_h
  30. #define _DDD_Graph_h
  31.  
  32. #ifdef __GNUG__
  33. #pragma interface
  34. #endif
  35.  
  36. #include "assert.h"
  37. #include "GraphGC.h"
  38. #include "GraphNode.h"
  39. #include "GraphEdge.h"
  40. #include "Box.h"
  41. #include "TypeInfo.h"
  42.  
  43. class Graph {
  44. public:
  45.     DECLARE_TYPE_INFO
  46.  
  47. private:
  48.     GraphNode *_firstNode;    // circular list (0 if empty)
  49.     GraphEdge *_firstEdge;    // circular list (0 if empty)
  50.  
  51.     Graph& operator = (const Graph&) { assert(0); return *this; }
  52.  
  53.     void begin_color(ostream& os, const PrintGC& gc,
  54.              unsigned short red,
  55.              unsigned short green,
  56.              unsigned short blue) const;
  57.     void end_color(ostream& os, const PrintGC& gc) const;
  58.  
  59.  
  60. protected:
  61.     void addNodes(GraphNode* nodes);
  62.     void addEdges(GraphEdge* edges);
  63.     void addUsedEdges(GraphEdge* edges);
  64.  
  65.     void removeNode(GraphNode* node);
  66.     void removeEdge(GraphEdge* edge);
  67.  
  68.     bool haveNode(GraphNode* node) const { return node->graph == this; }
  69.     bool haveEdge(GraphEdge* edge) const { return edge->graph == this; }
  70.  
  71.     // Needed by copy constructor
  72.     GraphNode *getNode(GraphNode *node, const Graph& graph) const;
  73.  
  74.     // Copy constructor
  75.     Graph(const Graph& graph);
  76.  
  77. public:
  78.     // Constructors
  79.     Graph():
  80.     _firstNode(0), _firstEdge(0)
  81.     {}
  82.  
  83.     // Destructor
  84.     virtual ~Graph();
  85.   
  86.     // Duplication
  87.     virtual Graph *dup() const
  88.     {
  89.     return new Graph (*this);
  90.     }
  91.  
  92.     // Add Graph
  93.     void operator += (const Graph& g)
  94.     {
  95.     Graph *graph = g.dup();
  96.  
  97.     if (graph->_firstNode)
  98.         addNodes(graph->_firstNode);
  99.     if (graph->_firstEdge)
  100.         addEdges(graph->_firstEdge);
  101.  
  102.     graph->_firstNode = 0;
  103.     graph->_firstEdge = 0;
  104.     delete graph;
  105.     }
  106.  
  107.     // Add Node
  108.     void operator += (GraphNode *node)
  109.     {
  110.     assert(node->next == 0);    // node must not be used yet
  111.     assert(node->prev == 0);
  112.     assert(node->graph == 0);
  113.  
  114.     node->next  = node;        // now it is used
  115.     node->prev  = node;
  116.     node->graph = this;
  117.     addNodes(node);
  118.     }
  119.  
  120.     // Add Edge
  121.     void operator += (GraphEdge *edge)
  122.     {
  123.     assert(edge->next == 0);    // edge must not be used yet
  124.     assert(edge->prev == 0);
  125.     assert(edge->graph == 0);
  126.  
  127.     edge->next  = edge;        // now it is used
  128.     edge->prev  = edge;
  129.     edge->graph = this;
  130.     addEdges(edge);
  131.     }
  132.  
  133.     // Remove Node
  134.     void operator -= (GraphNode *node)
  135.     {
  136.     removeNode(node);
  137.     }
  138.  
  139.     // Remove Edge
  140.     void operator -= (GraphEdge *edge)
  141.     {
  142.     removeEdge(edge);
  143.     }
  144.  
  145.     // Iteration on all nodes and edges
  146.     // simulate a 0-terminated list
  147.     GraphNode *firstNode() const { return _firstNode; } 
  148.     GraphNode *nextNode(GraphNode *ref) const
  149.     {
  150.     return ref->next == _firstNode ? 0 : ref->next;
  151.     }
  152.  
  153.     // Same, but iterate on non-hidden nodes only
  154.     GraphNode *firstVisibleNode() const;
  155.     GraphNode *nextVisibleNode(GraphNode *ref) const;
  156.  
  157.     // Same, but iterate on edges
  158.     GraphEdge *firstEdge() const { return _firstEdge; }
  159.     GraphEdge *nextEdge(GraphEdge *ref) const
  160.     {
  161.     return ref->next == _firstEdge ? 0 : ref->next;
  162.     }
  163.  
  164.     // Same, but iterate on non-hidden edges only
  165.     GraphEdge *firstVisibleEdge() const;
  166.     GraphEdge *nextVisibleEdge(GraphEdge *ref) const;
  167.  
  168.     // Change position in node list
  169.     void makeNodeFirst(GraphNode *node);
  170.     void makeNodeLast(GraphNode *node);
  171.  
  172.     // Change position in edge list
  173.     void makeEdgeFirst(GraphEdge *edge);
  174.     void makeEdgeLast(GraphEdge *edge);
  175.  
  176.     // Drawing
  177.     void draw(Widget w, const BoxRegion& exposed, const GraphGC& gc) const;
  178.     void draw(Widget w, const BoxRegion& exposed) const
  179.     {
  180.     draw(w, exposed, GraphGC());
  181.     }
  182.     void draw(Widget w) const
  183.     {
  184.     draw(w, BoxRegion(BoxPoint(0, 0), BoxSize(INT_MAX, INT_MAX)));
  185.     }
  186.  
  187.     // Printing
  188.     void _print(ostream& os, const GraphGC& gc) const;
  189.     void _printHeader(ostream& os, const GraphGC& gc) const
  190.     {
  191.     Box::_printHeader(os, region(gc, gc.printSelectedNodesOnly), 
  192.               *gc.printGC);
  193.     }
  194.     void _printTrailer(ostream& os, const GraphGC& gc) const
  195.     {
  196.     Box::_printTrailer(os, region(gc, gc.printSelectedNodesOnly),
  197.                *gc.printGC);
  198.     }
  199.  
  200.     // Custom printing function
  201.     void print(ostream& os, const GraphGC& gc = GraphGC()) const
  202.     {
  203.     _printHeader(os, gc);
  204.     _print(os, gc);
  205.     _printTrailer(os, gc);
  206.     }
  207.  
  208.     // Total Region
  209.     BoxRegion region(const GraphGC& gc, bool selected_only = false) const;
  210.  
  211.     // Representation invariant
  212.     virtual bool OK() const;
  213. };
  214.  
  215. // I/O
  216. extern ostream& operator << (ostream& s, const Graph& g);
  217.  
  218. #endif // _DDD_Graph_h
  219. // DON'T ADD ANYTHING BEHIND THIS #endif
  220.