mcb LEDA Extension Package  0.8
mcb_approx.h
Go to the documentation of this file.
1 //
2 // This program can be freely used in an academic environment
3 // ONLY for research purposes, subject to the following restrictions:
4 //
5 // 1. The origin of this software must not be misrepresented; you must not
6 // claim that you wrote the original software. If you use this software
7 // an acknowledgment in the product documentation is required.
8 // 2. Altered source versions must be plainly marked as such, and must not be
9 // misrepresented as being the original software.
10 // 3. This notice may not be removed or altered from any source distribution.
11 //
12 // Any other use is strictly prohibited by the author, without an explicit
13 // permission.
14 //
15 // Note that this program uses the LEDA library, which is NOT free. For more
16 // details visit Algorithmic Solutions at http://www.algorithmic-solutions.com/
17 // There is also a free version of LEDA 6.0 or newer.
18 //
19 // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
20 // ! Any commercial use of this software is strictly !
21 // ! prohibited without explicit permission by the !
22 // ! author. !
23 // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
24 //
25 // This software is distributed in the hope that it will be useful,
26 // but WITHOUT ANY WARRANTY; without even the implied warranty of
27 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
28 //
29 // Copyright (C) 2004-2008 - Dimitrios Michail <dimitrios.michail@gmail.com>
30 //
31 
38 #ifndef UMCB_APPROX_H
39 #define UMCB_APPROX_H
40 
41 #include <LEP/mcb/config.h>
42 #include <LEP/mcb/umcb.h>
43 #include <LEP/mcb/spanner.h>
44 #include <LEP/mcb/ushortpath.h>
45 #include <LEP/mcb/dmcb.h>
46 
47 #ifdef LEDA_GE_V5
48 #include <LEDA/graph/edge_map.h>
49 #include <LEDA/graph/node_map.h>
50 #else
51 #include <LEDA/edge_map.h>
52 #include <LEDA/node_map.h>
53 #endif
54 
55 namespace mcb
56 {
57 
58 #if defined(LEDA_NAMESPACE)
59  using leda::node;
60  using leda::node_map;
61  using leda::edge;
62  using leda::edge_array;
63  using leda::edge_map;
64 #endif
65 
66 
67  template<typename W, class Container>
68  class mcb_approx {
69  public:
70  typedef W result_type;
71 
72  mcb_approx( const graph& g_,
73  int k_,
74  array< Container >& mcb_,
75  const mcb::edge_num& enumb_ )
76  : g(g_), k(k_), mcb(mcb_), enumb(enumb_), Tcycles(0.0), Tsubgraph(0.0)
77  {
78  }
79 
80  virtual ~mcb_approx() {}
81 
82  W run() {
83  checkGraphPreconditions();
84  checkEdgeLengthPreconditions();
85  initialize();
86 
87  constructSpanner();
88 
89  edge_num spanner_enumb( spanner );
90  array< Container > spanner_mcb;
91  constructSpannerMCB( spanner_enumb, spanner_mcb );
92 
93  constructPartialMCBfromSpanner( spanner_enumb, spanner_mcb );
94  translateSpannerMCBToGraphPartialMCB( spanner_enumb, spanner_mcb );
95 
96  return length;
97  }
98 
99  private:
100 
101  void checkGraphPreconditions() {
102 #if ! defined(LEDA_CHECKING_OFF)
103  if ( Is_Loopfree( g ) == false )
104  error_handler(999,"UMCB_APPROX: illegal graph (loops?)");
105  if ( k <= 0 )
106  error_handler(999,"UMCB_APPROX: illegal value of k, non-positive?");
107 #endif
108  }
109 
110  virtual void checkEdgeLengthPreconditions() {}
111 
112  void initialize() {
113  length = W();
114  N = enumb.dim_cycle_space();
115  mcb.resize( N );
116  }
117 
118  virtual void constructSpanner() = 0;
119 
120  virtual void constructSpannerMCB( const edge_num& spanner_enumb, array< Container >& spanner_mcb ) = 0;
121 
122  virtual void constructPartialMCBfromSpanner( const edge_num& spanner_enumb, const array< Container >& spanner_mcb ) = 0;
123 
124  virtual void translateSpannerMCBToGraphPartialMCB( const edge_num& spanner_enumb,
125  const array<Container>& spanner_mcb ) = 0;
126 
127  protected:
128  const graph& g;
129  int k;
130  array< Container >& mcb;
131  const mcb::edge_num& enumb;
132  W length;
133  int N;
134 
135  // spanner related
136  graph spanner;
137  edge_array<W> spanner_len;
138  node_map<node> node_g_to_spanner;
139  node_map<node> node_spanner_to_g;
140  edge_map<edge> edge_g_to_spanner;
141  edge_map<edge> edge_spanner_to_g;
142 
143  // statistics
144  float Tcycles, Tsubgraph, Ttemp;
145  };
146 
147 
148  // undirected case
149  template<typename W, class Container>
150  class umcb_approx : public mcb_approx< W, Container >
151  {
152  public:
153  typedef mcb_approx<W,Container> base_type;
154 
155  umcb_approx( const graph& g_,
156  int k_,
157  array< Container >& mcb_,
158  const mcb::edge_num& enumb_ )
159  : base_type( g_, k_, mcb_, enumb_ )
160  {
161  }
162 
163  ~umcb_approx() {}
164 
165  private:
166 
167  virtual void constructSpannerMCB( const edge_num& spanner_enumb, array<Container>& spanner_mcb )
168  {
169  array< Container > spanner_proof;
170 
171 #ifdef LEP_DEBUG_OUTPUT
172  std::cout << "Computing " << spanner_enumb.dim_cycle_space() << " cycles";
173  std::cout << " by the MCB of spanner..." << std::endl;
174 #endif
175 
176  length += UMCB_SVA<W,Container>( spanner, spanner_len,
177  spanner_mcb, spanner_proof, spanner_enumb );
178  }
179 
180  virtual void translateSpannerMCBToGraphPartialMCB( const edge_num& spanner_enumb,
181  const array<Container>& spanner_mcb )
182  {
183  edge e;
184  int extracycles = spanner_enumb.dim_cycle_space();
185  for( int i = 0; i < extracycles; ++i )
186  {
187  mcb[ N - extracycles + i ] = Container();
188 
189  int j = 0;
190  forall( j, spanner_mcb[ i ] )
191  {
192  // translate to numbering of original graph
193  // and add to cycle
194  e = edge_spanner_to_g[ spanner_enumb(j) ];
195  mcb[ N - extracycles + i ].insert( enumb( e ) );
196  }
197  // fix correct ordering
198  mcb[ N - extracycles + i ].sort();
199  }
200 
201 #ifdef LEP_STATS
202  Tsubgraph += leda::used_time( Ttemp );
203  std::cout << "LEP_STATS: spanner cycles time: " << Tcycles << std::endl;
204  std::cout << "LEP_STATS: subgraph MCB time : " << Tsubgraph << std::endl;
205 #endif
206  }
207 
208  using base_type::length;
209  using base_type::spanner;
210  using base_type::spanner_len;
211  using base_type::N;
212  using base_type::mcb;
213  using base_type::edge_spanner_to_g;
214  using base_type::enumb;
215  };
216 
217  // directed case
218  template<typename W>
219  class dmcb_approx : public mcb_approx<W,mcb::spvecfp>
220  {
221  public:
222  typedef mcb_approx<W,mcb::spvecfp> base_type;
223 
224  dmcb_approx( const graph& g_,
225  int k_,
226  array< mcb::spvecfp >& mcb_,
227  const mcb::edge_num& enumb_,
228  double error_
229  )
230  : base_type( g_, k_, mcb_, enumb_ ), error(error_), prime(3), minimizeErrorProb(true)
231  {
232  }
233 
234  dmcb_approx( const graph& g_,
235  int k_,
236  array< mcb::spvecfp >& mcb_,
237  const mcb::edge_num& enumb_,
238  ptype prime_
239  )
240  : base_type( g_, k_, mcb_, enumb_ ), error(0.375), prime(prime_), minimizeErrorProb(false)
241  {
242  }
243 
244  ~dmcb_approx() {}
245 
246  protected:
247 
248  ptype getPrime( const edge_num& spanner_enumb, const array<mcb::spvecfp>& spanner_mcb )
249  {
250  return ( spanner_enumb.dim_cycle_space() > 0 ) ? spanner_mcb[0].pvalue() : 3;
251  }
252 
253  private:
254 
255  virtual void constructSpannerMCB( const edge_num& spanner_enumb, array<mcb::spvecfp>& spanner_mcb )
256  {
257  array<spvecfp> spanner_proof;
258 
259 #ifdef LEP_DEBUG_OUTPUT
260  std::cout << "Computing " << spanner_enumb.dim_cycle_space() << " cycles";
261  std::cout << " by the MCB of spanner..." << std::endl;
262 #endif
263 
264  if ( minimizeErrorProb )
265  length += DMCB<W>( spanner, spanner_len,
266  spanner_mcb, spanner_proof, spanner_enumb, error );
267  else
268  length += DMCB<W>( spanner, spanner_len,
269  spanner_mcb, spanner_proof, spanner_enumb, prime );
270 
271  }
272 
273  virtual void translateSpannerMCBToGraphPartialMCB( const edge_num& spanner_enumb,
274  const array<spvecfp>& spanner_mcb )
275  {
276  edge e;
277  int extracycles = spanner_enumb.dim_cycle_space();
278  for( int i = 0; i < extracycles; ++i )
279  {
280  mcb[ N - extracycles + i] = mcb::spvecfp( getPrime( spanner_enumb, spanner_mcb ) );
281 
282  leda::list_item it = spanner_mcb[i].first();
283  while( it != nil ) {
284  e = edge_spanner_to_g[ spanner_enumb( spanner_mcb[i].index( it ) ) ];
285  mcb[ N - extracycles + i ].append( enumb(e), spanner_mcb[i].inf( it ) );
286  it = spanner_mcb[i].succ( it );
287  }
288  mcb[ N - extracycles + i ].sort(); // fix ordering
289  }
290 
291 #ifdef LEP_STATS
292  Tsubgraph += leda::used_time( Ttemp );
293  std::cout << "LEP_STATS: spanner cycles time: " << Tcycles << std::endl;
294  std::cout << "LEP_STATS: subgraph MCB time : " << Tsubgraph << std::endl;
295 #endif
296  }
297 
298  using base_type::length;
299  using base_type::spanner;
300  using base_type::spanner_len;
301  using base_type::N;
302  using base_type::mcb;
303  using base_type::edge_spanner_to_g;
304  using base_type::enumb;
305 
306  private:
307  double error;
308  ptype prime;
309  bool minimizeErrorProb;
310  };
311 
312 
313 
314 
315  // weighted undirected case
316  template<typename W, class Container>
317  class weighted_umcb_approx : public umcb_approx<W,Container>
318  {
319  public:
320  typedef umcb_approx<W,Container> base_type;
321 
322  weighted_umcb_approx( const graph& g_,
323  const edge_array<W>& len_,
324  int k_,
325  array< Container >& mcb_,
326  const mcb::edge_num& enumb_ )
327  : base_type( g_, k_, mcb_, enumb_ ), len(len_)
328  {
329  }
330 
331  weighted_umcb_approx( const graph& g_,
332  int k_,
333  array< Container >& mcb_,
334  const mcb::edge_num& enumb_ )
335  : base_type( g_, k_, mcb_, enumb_ ), len(g_,1)
336  {
337  }
338 
339  virtual ~weighted_umcb_approx() {}
340 
341  private:
342 
343  virtual void checkEdgeLengthPreconditions() {
344 #if ! defined(LEDA_CHECKING_OFF)
345  edge e;
346  forall_edges( e , g ) {
347  if ( len[e] < 0 )
348  error_handler(999,"UMCB_APPROX: illegal edge (negative weight?)");
349  }
350 #endif
351  }
352 
353  virtual void constructSpanner()
354  {
355 #ifdef LEP_STATS
356  leda::used_time( Ttemp );
357 #endif
358  mcb::detail::SPANNER( g, len, k, spanner,
359  node_g_to_spanner, node_spanner_to_g,
360  edge_g_to_spanner, edge_spanner_to_g,
361  enumb);
362 
363  // construct spanner edge lengths
364  edge e;
365  spanner_len.init( spanner );
366  forall_edges( e, spanner ) {
367  spanner_len[ e ] = len[ edge_spanner_to_g[ e ] ];
368  }
369  }
370 
371  virtual void constructPartialMCBfromSpanner( const edge_num& spanner_enumb, const array< Container >& spanner_mcb )
372  {
373  detail::ushortestpaths<W> usp( spanner, spanner_len );
374  int i = 0;
375  edge e, f;
376  forall_edges( e, g ) {
377  if ( edge_g_to_spanner[e] == nil ) {
378  mcb[i] = Container();
379 
380  // compute shortest path on spanner
381  node spanner_s = node_g_to_spanner[ g.source(e) ];
382  node spanner_t = node_g_to_spanner[ g.target(e) ];
383  usp.compute_shortest_path( spanner_s, spanner_t );
384 
385 #if ! defined(LEDA_CHECKING_OFF)
386  assert( usp.is_reachable( spanner_t ) && usp.pred( spanner_s ) == nil );
387 #endif
388 
389  // form cycle
390  W cycle_len = W();
391  node spanner_w = spanner_t;
392  while( usp.pred( spanner_w ) != nil ) {
393  f = usp.pred( spanner_w );
394  mcb[i].insert( enumb( edge_spanner_to_g[ f ] ) );
395  cycle_len += len[ edge_spanner_to_g[ f ] ];
396  spanner_w = spanner.opposite( f, spanner_w );
397  }
398  mcb[i].insert( enumb( e ) );
399  cycle_len += len[ e ];
400  mcb[i].sort(); // fix correct ordering
401 
402  // now update global cycles length
403 #if ! defined(LEDA_CHECKING_OFF)
404  if ( cycle_len < 0 )
405  error_handler(999,"UMCB_APPROX: computed cycle with negative length!");
406 #endif
407  length += cycle_len;
408 
409  i++;
410  }
411  }
412 
413 #ifdef LEP_STATS
414  Tcycles += leda::used_time( Ttemp );
415 #endif
416 #ifdef LEP_DEBUG_OUTPUT
417  std::cout << "Spanner has " << spanner.number_of_edges() << " edges..." << std::endl;
418  std::cout << "Computed " << i << " cycles fast..." << std::endl;
419 #endif
420  }
421 
422  private:
423  const edge_array<W> len;
424 
425  using base_type::g;
426  using base_type::k;
427  using base_type::length;
428  using base_type::enumb;
429  using base_type::mcb;
430  using base_type::spanner;
431  using base_type::spanner_len;
432  using base_type::node_g_to_spanner;
433  using base_type::node_spanner_to_g;
434  using base_type::edge_g_to_spanner;
435  using base_type::edge_spanner_to_g;
436  };
437 
438  // weighted directed case
439  template<typename W>
440  class weighted_dmcb_approx : public dmcb_approx<W>
441  {
442  public:
443  typedef dmcb_approx<W> base_type;
444 
445  weighted_dmcb_approx( const graph& g_,
446  const edge_array<W>& len_,
447  int k_,
448  array< spvecfp >& mcb_,
449  const mcb::edge_num& enumb_,
450  double error )
451  : base_type( g_, k_, mcb_, enumb_, error ), len(len_)
452  {
453  }
454 
455  weighted_dmcb_approx( const graph& g_,
456  int k_,
457  array< spvecfp >& mcb_,
458  const mcb::edge_num& enumb_,
459  double error )
460  : base_type( g_, k_, mcb_, enumb_, error ), len(g_,1)
461  {
462  }
463 
464  weighted_dmcb_approx( const graph& g_,
465  const edge_array<W>& len_,
466  int k_,
467  array< spvecfp >& mcb_,
468  const mcb::edge_num& enumb_,
469  ptype prime )
470  : base_type( g_, k_, mcb_, enumb_, prime ), len(len_)
471  {
472  }
473 
474  weighted_dmcb_approx( const graph& g_,
475  int k_,
476  array< spvecfp >& mcb_,
477  const mcb::edge_num& enumb_,
478  ptype prime )
479  : base_type( g_, k_, mcb_, enumb_, prime ), len(g_,1)
480  {
481  }
482 
483  virtual ~weighted_dmcb_approx() {}
484 
485  private:
486 
487  virtual void checkEdgeLengthPreconditions() {
488 #if ! defined(LEDA_CHECKING_OFF)
489  edge e;
490  forall_edges( e , g ) {
491  if ( len[e] < 0 )
492  error_handler(999,"DMCB_APPROX: illegal edge (negative weight?)");
493  }
494 #endif
495  }
496 
497  virtual void constructSpanner()
498  {
499 #ifdef LEP_STATS
500  leda::used_time( Ttemp );
501 #endif
502  mcb::detail::SPANNER( g, len, k, spanner,
503  node_g_to_spanner, node_spanner_to_g,
504  edge_g_to_spanner, edge_spanner_to_g,
505  enumb);
506 
507  // construct spanner edge lengths
508  edge e;
509  spanner_len.init( spanner );
510  forall_edges( e, spanner ) {
511  spanner_len[ e ] = len[ edge_spanner_to_g[ e ] ];
512  }
513  }
514 
515  virtual void constructPartialMCBfromSpanner( const edge_num& spanner_enumb, const array< spvecfp >& spanner_mcb )
516  {
517  detail::ushortestpaths<W> usp( spanner, spanner_len );
518  int i = 0;
519  edge e, f;
520  forall_edges( e, g ) {
521  if ( edge_g_to_spanner[e] == nil ) {
522  mcb[i] = mcb::spvecfp( base_type::getPrime( spanner_enumb, spanner_mcb ) );
523 
524  // compute shortest path on spanner
525  node spanner_s = node_g_to_spanner[ g.source(e) ];
526  node spanner_t = node_g_to_spanner[ g.target(e) ];
527  usp.compute_shortest_path( spanner_s, spanner_t );
528 
529 #if ! defined(LEDA_CHECKING_OFF)
530  assert( usp.is_reachable( spanner_t ) && usp.pred( spanner_s ) == nil );
531 #endif
532 
533  // form cycle
534  node spanner_w = spanner_t;
535  while( usp.pred( spanner_w ) != nil ) {
536  f = usp.pred( spanner_w );
537  if ( spanner_w == spanner.source(f) ) {
538  mcb[i].append( enumb( edge_spanner_to_g[ f ] ), 1 );
539  }
540  else {
541  mcb[i].append( enumb( edge_spanner_to_g[ f ] ), -1 );
542  }
543  length += len[ edge_spanner_to_g[ f ] ];
544  spanner_w = spanner.opposite( f, spanner_w );
545  }
546  mcb[i].append( enumb( e ) , 1 );
547  length += len[ e ];
548  mcb[i].sort(); // fix correct ordering
549 
550  i++;
551 
552  }
553  }
554 
555 #ifdef LEP_STATS
556  Tcycles += leda::used_time( Ttemp );
557 #endif
558 #ifdef LEP_DEBUG_OUTPUT
559  std::cout << "Spanner has " << spanner.number_of_edges() << " edges..." << std::endl;
560  std::cout << "Computed " << i << " cycles fast..." << std::endl;
561 #endif
562  }
563 
564  private:
565  const edge_array<W> len;
566 
567  using base_type::g;
568  using base_type::k;
569  using base_type::length;
570  using base_type::enumb;
571  using base_type::mcb;
572  using base_type::spanner;
573  using base_type::spanner_len;
574  using base_type::node_g_to_spanner;
575  using base_type::node_spanner_to_g;
576  using base_type::edge_g_to_spanner;
577  using base_type::edge_spanner_to_g;
578  };
579 
580 
581 
582  // unweighted undirected case
583  template<class Container>
584  class unweighted_umcb_approx : public weighted_umcb_approx<int,Container>
585  {
586  public:
587  typedef weighted_umcb_approx<int,Container> base_type;
588 
589  unweighted_umcb_approx( const graph& g_,
590  int k_,
591  array< Container >& mcb_,
592  const mcb::edge_num& enumb_ )
593  : base_type( g_, k_, mcb_, enumb_ )
594  {
595  }
596 
597  ~unweighted_umcb_approx() {}
598 
599  private:
600 
601  virtual void checkEdgeLengthPreconditions() {}
602 
603  virtual void constructPartialMCBfromSpanner( const edge_num& spanner_enumb, const array< Container >& spanner_mcb )
604  {
605  detail::ubfs usp( spanner );
606  int i = 0;
607  edge e, f;
608  forall_edges( e, g ) {
609  if ( edge_g_to_spanner[e] == nil ) {
610  mcb[i] = Container();
611 
612  // compute shortest path on spanner
613  node spanner_s = node_g_to_spanner[ g.source(e) ];
614  node spanner_t = node_g_to_spanner[ g.target(e) ];
615  usp.compute_shortest_path( spanner_s, spanner_t, 2*k-1 );
616 
617 #if ! defined(LEDA_CHECKING_OFF)
618  assert( usp.is_reachable( spanner_t ) && usp.pred( spanner_s ) == nil );
619 #endif
620 
621  // form cycle
622  node spanner_w = spanner_t;
623  while( usp.pred( spanner_w ) != nil ) {
624  f = usp.pred( spanner_w );
625  mcb[i].insert( enumb( edge_spanner_to_g[ f ] ) );
626  ++length;
627  spanner_w = spanner.opposite( f, spanner_w );
628  }
629  mcb[i].insert( enumb( e ) );
630  ++length;
631  mcb[i].sort(); // fix correct ordering
632 
633  ++i;
634  }
635  }
636 
637 #ifdef LEP_STATS
638  Tcycles += leda::used_time( Ttemp );
639 #endif
640 #ifdef LEP_DEBUG_OUTPUT
641  std::cout << "Spanner has " << spanner.number_of_edges() << " edges..." << std::endl;
642  std::cout << "Computed " << i << " cycles fast..." << std::endl;
643 #endif
644  }
645 
646  using base_type::g;
647  using base_type::enumb;
648  using base_type::mcb;
649  using base_type::k;
650  using base_type::length;
651  using base_type::spanner;
652  using base_type::edge_g_to_spanner;
653  using base_type::edge_spanner_to_g;
654  using base_type::node_g_to_spanner;
655  };
656 
689  template<class W>
690  W UMCB_APPROX( const graph& g,
691  const edge_array<W>& len,
692  const int k,
693  array< mcb::spvecgf2 >& mcb,
694  const mcb::edge_num& enumb
695  )
696  {
697  weighted_umcb_approx<W,mcb::spvecgf2> tmp( g, len, k, mcb, enumb );
698  return tmp.run();
699  }
700 
701 
729  int UMCB_APPROX( const graph& g,
730  const int k,
731  array< mcb::spvecgf2 >& mcb,
732  const mcb::edge_num& enumb
733  );
735 
736 
737 
775  template<class W>
776  W DMCB_APPROX( const graph& g,
777  const edge_array<W>& len,
778  const int k,
779  array< mcb::spvecfp >& mcb,
780  const mcb::edge_num& enumb,
781  double error = 0.375
782  )
783  {
784  weighted_dmcb_approx<W> tmp( g, len, k, mcb, enumb, error );
785  return tmp.run();
786  }
787 
818  template<class W>
819  W DMCB_APPROX( const graph& g,
820  const edge_array<W>& len,
821  const int k,
822  array< mcb::spvecfp >& mcb,
823  const mcb::edge_num& enumb,
824  mcb::ptype prime
825  )
826  {
827  weighted_dmcb_approx<W> tmp( g, len, k, mcb, enumb, prime );
828  return tmp.run();
829  }
830 
831 
833 
834 
842 
867  template<class W>
868  W UMCB( const graph& g,
869  const edge_array<W>& len,
870  array< mcb::spvecgf2 >& mcb,
871  const mcb::edge_num& enumb
872  )
873  {
874  return UMCB_APPROX<W>( g, len, 1, mcb, enumb );
875  }
876 
900  int UMCB( const graph& g,
901  array< mcb::spvecgf2 >& mcb,
902  const mcb::edge_num& enumb
903  );
905 
906 }
907 
908 #endif // UMCB_APPROX_H
909 
910 /* ex: set ts=4 sw=4 sts=4 et: */
911 
912 
mcb::UMCB_APPROX
W UMCB_APPROX(const graph &g, const edge_array< W > &len, const int k, array< mcb::spvecgf2 > &mcb, const mcb::edge_num &enumb)
Compute an undirected approximate MCB of a weighted graph.
Definition: mcb_approx.h:690
mcb::edge_num
An edge numbering class.
Definition: edge_num.h:75
mcb
The main package namespace.
umcb.h
Algorithms for undirected MCB.
mcb::DMCB_APPROX
W DMCB_APPROX(const graph &g, const edge_array< W > &len, const int k, array< mcb::spvecfp > &mcb, const mcb::edge_num &enumb, double error=0.375)
Compute a directed approximate MCB of a weighted graph.
Definition: mcb_approx.h:776
mcb::spvecfp
A sparse vector with elements in .
Definition: spvecfp.h:87
mcb::ptype
leda::integer ptype
Definition: arithm.h:58
dmcb.h
Algorithms for directed MCB.
mcb::UMCB
W UMCB(const graph &g, const edge_array< W > &len, array< mcb::spvecgf2 > &mcb, const mcb::edge_num &enumb)
Compute an MCB of an undirected graph (possible a multigraph) using the most general implementation o...
Definition: mcb_approx.h:868
Generated by   doxygen 1.8.11