dump.cpp

   1 // Ah... The joys graph data structures :)
   2 // A hole into which many a good computer scientist has fallen, never to be heard from again.
   3 //                                      - Andrew Sutton
   4
   5 /*
   6         Basic idea: provide concepts that define the interface(s) to different kinds of graphs so that you can do
   7         basic graph operations and algoriths without knowing exactly which kind of graph it is and keep ignorant
   8         about implementation details.
   9
  10     Basic design idea: do like the STL
  11 */
  12
  13 /*
  14 // Graph concepts (like STL containers):
  15 // Do we need them (STL doesn't make containers explicit)
  16 template<class G> concept bool Graph = false; // general graph operations
  17 template<class G> concept bool DAG = false;      // operations simplified for DAGs (any extra operations?)
  18 template<class G> concept bool Tree = false;     // operations simplified for trees (any extra operations?)
  19
  20 // accessor concepts (like STL Iterators):
  21 template<class G> concept bool Edge_ref = false;             // most general and slowest
  22 template<class G> concept bool DAG_edge_ref = false;     // operations simplified for DAGs (any extra operations?)
  23 template<class G> concept bool Tree_edge_ref = false; // operations simplified for trees (any extra operations?)
  24
  25 template<class G> concept bool Vertex_ref = false;      // most general and slowest
  26 template<class G> concept bool DAG_vertex_ref = false;  // operations simplified for DAGs (any extra operations?)
  27 template<class G> concept bool Tree_vertex_ref = false; // operations simplified for DAGs (any extra operations?)
  28
  29 // the value type (in a more general design, this would be a template parmeter):
  30 struct Val {};
  31
  32 // specific directed graphs:
  33 struct Tree {};
  34 struct Dag { };
  35 struct Dgraph {};
  36
  37 struct Node_ref {};
  38 struct Edge_ref {};     // Is an Edge an object? (if not, refer to parent node)
  39
  40 struct DAG_vertex_ref {};
  41 struct DAG_edge_ref {}; // Is an Edge an object? (if not, refer to parent node)
  42
  43 struct Gnode_ref {};
  44 struct Gedge_ref {};    // Is an Edge an object? (if not, refer to parent node)
  45
  46 // another Graph representation:
  47 struct DGN_ref {};
  48 struct DGE_ref {};      // Is an Edge an object? (if not, refer to parent node)
  49
  50 // use:
  51 template<Graph G>
  52 void traverse(G& g)
  53 {
  54         vector<???> found;      // there is a way (look up traits), lets try g::value_type
  55 }
  56
  57 */
  58
  59 /*
  60         Basic idea: provide concepts that define the interface(s) to different kinds of graphs so that you can do
  61         basic graph operations and algoriths without knowing exactly which kind of graph it is and keep ignorant
  62         about implementation details.
  63
  64     Basic design idea: do like the STL
  65 */
  66
  67 /*
  68 // Graph concepts (like STL containers):
  69 // Do we need them (STL doesn't make containers explicit)
  70 template<class G> concept bool Graph =  // general graph operations
  71         requires { typename G::value_type; };
  72 template<class G> concept bool DAG = Graph<G> && requires(G g) { tops(g); };     // operations simplified for DAGs
  73 template<class G> concept bool Tree = DAG<G> && requires(G g) { top(g); };       // operations simplified for trees
  74
  75 // accessor concepts (like STL Iterators):
  76 template<class E> concept bool Edge_ref =      // most general and slowest
  77         requires { typename E::value_type; };
  78 template<class E> concept bool DAG_edge_ref = // operations simplified for DAGs (any extra operations?)
  79         Edge_ref<E> && false;
  80 template<class E> concept bool Tree_edge_ref = // operations simplified for trees (any extra operations?)
  81         DAG_edge_ref<E> && false;
  82
  83 template<class G> concept bool Vertex_ref = true;      // most general and slowest
  84 template<class G> concept bool DAG_vertex_ref = false;  // operations simplified for DAGs (any extra operations?)
  85 template<class G> concept bool Tree_vertex_ref = false; // operations simplified for DAGs (any extra operations?)
  86
  87 // the value type (in a more general design, this would be a template parmeter):
  88 struct Val {};
  89
  90 // specific directed graphs (note: we can't assume common structure or common naming from implementation):
  91 struct Tree {
  92         using value_type = Val;
  93 };
  94
  95 struct Node_ref {};
  96 struct Edge_ref {};     // Is an Edge an object? (if not, refer to parent node)
  97
  98 void tops(Tree&);       // return vector Tree_vertex_refs
  99 Node_ref top(Tree&);
 100
 101 struct Dag {
 102         using value_type = Val;
 103 };
 104
 105 struct DAG_vertex_ref {};
 106 struct DAG_edge_ref {}; // Is an Edge an object? (if not, refer to parent node)
 107
 108 void tops(Dag&);
 109
 110 struct Dgraph {
 111         using value_type = Val;
 112 };
 113
 114
 115 struct Gnode_ref {};
 116 struct Gedge_ref {};    // Is an Edge an object? (if not, refer to parent node)
 117
 118 // another Graph representation:
 119 struct DGN_ref {};
 120 struct DGE_ref {};      // Is an Edge an object? (if not, refer to parent node)
 121
 122 // use:
 123 #include <vector>
 124 using namespace std;
 125
 126 template<Graph G, Vertex_ref R>
 127 void traverse(G& g, R r)
 128 {
 129         vector<typename G::value_type> found;   // member g::value_type (old habit: could just have used Val)
 130         // ...
 131 }
 132
 133 void use1(Tree& t, Dag& d, Dgraph& dg, Node_ref& tr, DAG_vertex_ref& dr, Gnode_ref& gr)
 134 {
 135   traverse(t,tr);
 136   traverse(d,dr);
 137   traverse(dg,gr);
 138 }
 139
 140 */
 141
 142
 143 /*
 144         Basic idea: provide concepts that define the interface(s) to different kinds of graphs so that you can do
 145         basic graph operations and algoriths without knowing exactly which kind of graph it is and keep ignorant
 146         about implementation details.
 147
 148     Basic design idea: do like the STL
 149 */
 150 /*
 151 // Graph concepts (like STL containers):
 152 // Do we need them (STL doesn't make containers explicit)
 153 template<class G> concept bool Graph =  // general graph operations
 154         requires { typename G::value_type; };
 155 template<class G> concept bool DAG = Graph<G> && requires(G g) { tops(g); };     // operations simplified for DAGs
 156 template<class G> concept bool Tree = DAG<G> && requires(G g) { top(g); };       // operations simplified for trees
 157
 158 // accessor concepts (like STL Iterators):
 159 template<class E> concept bool Edge_ref =      // most general and slowest
 160         requires(E e) {
 161                 typename E::value_type;
 162                 { *e } -> typename E::value_type;
 163                 { e.vertex } -> Vertex_ref;
 164         };
 165 template<class E> concept bool DAG_edge_ref = // operations simplified for DAGs (any extra operations?)
 166         Edge_ref<E> && false;
 167 template<class E> concept bool Tree_edge_ref = // operations simplified for trees (any extra operations?)
 168         DAG_edge_ref<E> && false;
 169
 170 template<class V> concept bool Vertex_ref =       // most general and slowest
 171   requires(V v, int i) {
 172                 typename V::value_type;
 173                 { *v } -> typename V::value_type;
 174                 { v.edge[i] } -> Edge_ref;
 175         };
 176 template<class V> concept bool DAG_vertex_ref = false;  // operations simplified for DAGs (any extra operations?)
 177 template<class V> concept bool Tree_vertex_ref = false; // operations simplified for DAGs (any extra operations?)
 178
 179 // the value type (in a more general design, this would be a template parmeter):
 180 struct Val {};
 181
 182 // specific directed graphs (note: we can't assume common structure or common naming from implementation):
 183 struct Tree {
 184         using value_type = Val;
 185 };
 186
 187 struct Node_ref {};
 188 struct Edge_ref {};     // Is an Edge an object? (if not, refer to parent node)
 189
 190 void tops(Tree&);       // return vector Tree_vertex_refs
 191 Node_ref top(Tree&);
 192
 193 struct Dag {
 194         using value_type = Val;
 195 };
 196
 197 struct DAG_vertex_ref {};
 198 struct DAG_edge_ref {}; // Is an Edge an object? (if not, refer to parent node)
 199
 200 void tops(Dag&);
 201
 202 struct Dgraph {
 203         using value_type = Val;
 204 };
 205
 206
 207 struct Gnode_ref {};
 208 struct Gedge_ref {};    // Is an Edge an object? (if not, refer to parent node)
 209
 210 // another Graph representation:
 211 struct DGN_ref {};
 212 struct DGE_ref {};      // Is an Edge an object? (if not, refer to parent node)
 213
 214 // use:
 215 #include <vector>
 216 using namespace std;
 217
 218 template<Graph G, Vertex_ref R>
 219 void traverse(G& g, R r)
 220 {
 221         vector<typename G::value_type> found;   // member g::value_type (old habit: could just have used Val)
 222         // ...
 223 }
 224
 225 void use1(Tree& t, Dag& d, Dgraph& dg, Node_ref& tr, DAG_vertex_ref& dr, Gnode_ref& gr)
 226 {
 227   traverse(t,tr);
 228   traverse(d,dr);
 229   traverse(dg,gr);
 230 }