Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
edge_set.h
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 2k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

edge_set.h：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  edge_set.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_EDGE_SET_H
  14. #define LEDA_EDGE_SET_H
  16. #include <LEDA/graph.h>
  19. //------------------------------------------------------------------------------
  20. // edge_set  
  21. //------------------------------------------------------------------------------
  23. /*{Manpage {edge_set} {} {Sets of Edges} }*/
  25. class edge_set 
  26. {
  27. /*{Mdefinition
  28. An instance $S$ of the data type $edge_set$ is a subset of
  29. the edges of a graph $G$. $S$ is said to be valid for the
  30. edges of $G$.}*/
  32.   graph* g;
  33.   list<edge> L;
  34.   edge_array<list_item> A;
  36. public:
  38. /*{Mcreation S }*/
  40. edge_set(const graph& G) :A(G,nil) { g = (graph*)&G; }
  41. /*{Mcreate creates an instance $S$ of type $edge_set$ valid for all edges 
  42.             currently in graph $G$ and initializes it to the empty set.}*/ 
  46. virtual ~edge_set()  { }
  50. /*{Moperations 1.3 4 }*/
  52. void insert(edge x)  { if (A[x] == nil) A[x] = L.append(x); }
  53. /*{Mop     adds edge $x$ to $S$. }*/
  55. void del(edge x)     { if (A[x] != nil) { L.del(A[x]); A[x] = nil;} }
  56. /*{Mop       removes edge $x$ from $S$. }*/
  58. bool member(edge x)      { return (A[x] != nil); }
  59. /*{Mop       returns true if $x$ in $S$, false otherwise. }*/
  61. edge choose()  const     { return L.head(); }
  62. /*{Mop       returns an edge of $S$. }*/
  64. int  size()    const     { return L.length(); }
  65. /*{Mop       returns the size of $S$. }*/
  67. bool empty()   const     { return L.empty(); }
  68. /*{Mop       returns true iff $S$ is the empty set. }*/
  70. void clear()             { L.clear(); A.init(*g,nil); }
  71. /*{Mop       makes $S$ the empty set. }*/
  73. };
  75. /*{Mimplementation
  76. An edge set $S$ for a graph $G$ is implemented by a combination of a 
  77. list  $L$ of edges and an edge array of list_items 
  78. associating with each edge its position in $L$. All operations 
  79. take constant time, except for clear which takes time $O(|S|)$. The space 
  80. requirement is $O(n)$, where $n$ is the number of edges of $G$.}*/
  82. #endif