home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / ugraph.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-12-10  |  5.4 KB  |  163 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 12-10-1991
  4. +
  5. +
  6. +  ugraph.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef UGRAPH_H
  17. #define UGRAPH_H
  18.  
  19. #include <LEDA/graph.h>
  20.  
  21.  
  22. //-----------------------------------------------------------------------------
  23. // ugraph: base class for all undirected graphs
  24. //-----------------------------------------------------------------------------
  25.  
  26. class ugraph : public graph{
  27.  
  28. public:
  29.  
  30. edge new_edge(node,node,ent);
  31.  
  32. edge new_edge(node v, node w)
  33. { ent x; init_edge_entry(x);
  34.   return new_edge(v,w,x);
  35.  }
  36.  
  37. edge new_edge(node,node,edge,edge,ent,int=0,int=0);
  38.  
  39. edge new_edge(node v, node w, edge e1 ,edge e2, int dir1=0,int dir2=0)
  40. { ent x; init_edge_entry(x);
  41.   return new_edge(v,w,e1,e2,x,dir1,dir2);
  42.  }
  43.  
  44. /* done by graph::del_edge
  45.  
  46. void del_edge(edge e) { e->t->adj_edges.del(e->adj_loc2);
  47.                         graph::(e);
  48.                        }
  49. */
  50.  
  51. list(node) adj_nodes(node) const;
  52.  
  53. node opposite(node v, edge e)  const;
  54.  
  55. int  degree(node v)     const  { return v->adj_edges.length(); }
  56.  
  57. edge adj_succ(edge e,node v) const;
  58. edge adj_pred(edge e,node v) const;
  59. edge cyclic_adj_succ(edge e,node v) const;
  60. edge cyclic_adj_pred(edge e,node v) const;
  61.  
  62. void print_edge(edge, ostream& = cout) const;
  63.  
  64. void read(string s) { graph::read(s); make_undirected(); } 
  65.  
  66. ugraph()  { undirected = true; }
  67.  
  68. ugraph(const graph& a): graph(a) { undirected = true; make_undirected(); }
  69.  
  70. ugraph(const ugraph& a) : graph((graph&)a)  { undirected = true;  }
  71.  
  72. ~ugraph() { /* ~graph does the job */ }
  73.  
  74. //subgraph constructors
  75. ugraph(ugraph&, list(node)&, list(edge)&);
  76. ugraph(ugraph&, list(edge)&);
  77.  
  78. ugraph& operator=(const ugraph& a) 
  79.                                { return (ugraph&)graph::operator=((graph&)a); }
  80.  
  81. ugraph& operator=(const graph& a)  { graph::operator=(a); 
  82.                                      make_undirected();
  83.                                      return (ugraph&)(*this);
  84.                                     }
  85.  
  86. };
  87.  
  88.  
  89. //------------------------------------------------------------------------------
  90. // UGRAPH: generic ugraphs
  91. //------------------------------------------------------------------------------
  92.  
  93. #define UGRAPH(vtype,etype)  name3(vtype,etype,UGRAPH)
  94.  
  95. #define UGRAPHdeclare2(vtype,etype)\
  96. \
  97. class UGRAPH(vtype,etype) : public ugraph {\
  98. \
  99. void init_node_entry(ent& x) const { x = Copy(vtype(0)); }\
  100. void init_edge_entry(ent& x) const { x = Copy(etype(0)); }\
  101. \
  102. void copy_node_entry(ent& x) const { Copy(*(vtype*)&x); }\
  103. void copy_edge_entry(ent& x) const { Copy(*(etype*)&x); }\
  104. \
  105. void clear_node_entry(ent& x) const { Clear(*(vtype*)&x); }\
  106. void clear_edge_entry(ent& x) const { Clear(*(etype*)&x); }\
  107. \
  108. void read_node_entry(istream& i, ent& x)  const { Read(*(vtype*)&x,i); }\
  109. void read_edge_entry(istream& i, ent& x)  const { Read(*(etype*)&x,i); }\
  110. \
  111. void write_node_entry(ostream& o, ent& x)  const { Print(*(vtype*)&x,o); }\
  112. void write_edge_entry(ostream& o, ent& x)  const { Print(*(etype*)&x,o); }\
  113. \
  114. void print_node_entry(ostream& o, ent& x)  const\
  115.      { o << "("; Print(*(vtype*)&x,o); o << ")"; }\
  116. void print_edge_entry(ostream& o, ent& x)  const\
  117.      { o << "("; Print(*(etype*)&x,o); o << ")"; }\
  118. \
  119. public:\
  120. \
  121. int cmp_node_entry(node x, node y) const { return compare(inf(x),inf(y)); }\
  122. int cmp_edge_entry(edge x, edge y) const { return compare(inf(x),inf(y)); }\
  123. \
  124.    vtype  inf(node v)         const { return vtype(graph::inf(v)); }\
  125.    etype  inf(edge e)         const { return etype(graph::inf(e)); }\
  126.    vtype& operator[] (node v)       { return *(vtype*)&ugraph::entry(v); }\
  127.    vtype  operator[] (node v) const { return vtype(ugraph::inf(v)); }\
  128.    etype& operator[] (edge e)       { return *(etype*)&ugraph::entry(e); }\
  129.    etype  operator[] (edge e) const { return etype(ugraph::inf(e)); }\
  130.    void   assign(node v,vtype x) { graph::assign(v,Ent(x)); }\
  131.    void   assign(edge e,etype x) { graph::assign(e,Ent(x)); }\
  132.    node   new_node()          { return ugraph::new_node(); }\
  133.    node   new_node(vtype a)   { return ugraph::new_node(Copy(a)); }\
  134.    edge   new_edge(node v, node w)\
  135.                               { return ugraph::new_edge(v,w); }\
  136.    edge   new_edge(node v, node w, etype a)\
  137.                               { return ugraph::new_edge(v,w,Copy(a)); }\
  138.    edge   new_edge(node v, node w, edge e1, edge e2, int dir1, int dir2)\
  139.                        { return ugraph::new_edge(v,w,e1,e2,dir1,dir2); }\
  140.    edge   new_edge(node v,node w,edge e1,edge e2,etype a,int dir1,int dir2)\
  141.                        { return ugraph::new_edge(v,w,e1,e2,Copy(a),dir1,dir2); }\
  142.    UGRAPH(vtype,etype)& operator=(const UGRAPH(vtype,etype)& a)\
  143.        {return (UGRAPH(vtype,etype)&)(ugraph::operator=((ugraph&)a)); }\
  144. \
  145.    UGRAPH(vtype,etype)& operator=(const graph& a)\
  146.        {return (UGRAPH(vtype,etype)&)(ugraph::operator=(a)); }\
  147. \
  148.    UGRAPH(vtype,etype)()                                       { }\
  149.    UGRAPH(vtype,etype)(const UGRAPH(vtype,etype)& a): ugraph((ugraph&)a) { copy_all_entries();}\
  150.    UGRAPH(vtype,etype)(const graph& a)              : ugraph(a)         { copy_all_entries();}\
  151. \
  152.    ~UGRAPH(vtype,etype)() { clear(); }\
  153. };\
  154.  
  155.  
  156.  
  157. extern void complete_graph(ugraph&,int);
  158. extern void random_graph(ugraph&,int,int);
  159. extern void test_graph(ugraph&);
  160.  
  161.  
  162. #endif
  163.