← Back to branch summary

~ubuntu-branches/ubuntu/vivid/ibutils/vivid

« back to all changes in this revision

Viewing changes to ibdm/ibdm/Bipartite.cc

  • Committer: Bazaar Package Importer
  • Author(s): Benoit Mortier
  • Date: 2010-01-11 22:22:00 UTC
  • Revision ID: james.westby@ubuntu.com-20100111222200-53kum2et5nh13rv3
Tags: upstream-1.2-OFED-1.4.2
Import upstream version 1.2-OFED-1.4.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
ibdm/ibdm/Bipartite.cc
 
1
/*
 
2
 * Copyright (c) 2008 Mellanox Technologies LTD. All rights reserved.
 
3
 *
 
4
 * This software is available to you under a choice of one of two
 
5
 * licenses.  You may choose to be licensed under the terms of the GNU
 
6
 * General Public License (GPL) Version 2, available from the file
 
7
 * COPYING in the main directory of this source tree, or the
 
8
 * OpenIB.org BSD license below:
 
9
 *
 
10
 *     Redistribution and use in source and binary forms, with or
 
11
 *     without modification, are permitted provided that the following
 
12
 *     conditions are met:
 
13
 *
 
14
 *      - Redistributions of source code must retain the above
 
15
 *        copyright notice, this list of conditions and the following
 
16
 *        disclaimer.
 
17
 *
 
18
 *      - Redistributions in binary form must reproduce the above
 
19
 *        copyright notice, this list of conditions and the following
 
20
 *        disclaimer in the documentation and/or other materials
 
21
 *        provided with the distribution.
 
22
 *
 
23
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 
24
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 
25
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 
26
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 
27
 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 
28
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 
29
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 
30
 * SOFTWARE.
 
31
 *
 
32
 * $Id$
 
33
 */
 
34
 
 
35
#include "Bipartite.h"
 
36
 
 
37
//CLASS edge///////////////////////////////////
 
38
 
 
39
bool edge::isMatched() {
 
40
  vertex* ver1 = (vertex*)v1;
 
41
  vertex* ver2 = (vertex*)v2;
 
42
 
 
43
  if (((this == ver1->getPartner()) && (this != ver2->getPartner())) || ((this == ver2->getPartner()) && (this != ver1->getPartner())))
 
44
    cout << "-E- Error in edge matching" << endl;
 
45
 
 
46
  return (this == ver1->getPartner()) && (this == ver2->getPartner());
 
47
}
 
48
 
 
49
//CLASS vertex/////////////////////////////////
 
50
 
 
51
vertex::vertex(int n, side sd, int rad):id(n),s(sd),radix(rad)
 
52
{
 
53
  connections = new edge*[radix];
 
54
  pred = new edge*[radix];
 
55
  succ = new edge*[radix];
 
56
 
 
57
  partner = NULL;
 
58
  for (int i=0; i<radix; i++)
 
59
    connections[i] = pred[i] = succ[i] = NULL;
 
60
 
 
61
  predCount = succCount = 0;
 
62
  maxUsed = -1;
 
63
}
 
64
 
 
65
vertex::~vertex()
 
66
{
 
67
  delete[] connections;
 
68
  delete[] pred;
 
69
  delete[] succ;
 
70
}
 
71
 
 
72
int vertex::getID() const
 
73
{
 
74
  return id;
 
75
}
 
76
 
 
77
side vertex::getSide() const
 
78
{
 
79
  return s;
 
80
}
 
81
 
 
82
void vertex::delConnection(edge* e)
 
83
{
 
84
  int my_idx, other_idx;
 
85
  vertex* v;
 
86
 
 
87
  // Find the side we are connected at and edge index
 
88
  if (e->v1 == this) {
 
89
    my_idx = e->idx1;
 
90
    other_idx = e->idx2;
 
91
    v = (vertex*)(e->v2);
 
92
  }
 
93
  else if (e->v2 == this) {
 
94
    my_idx = e->idx2;
 
95
    other_idx = e->idx1;
 
96
    v = (vertex*)(e->v1);
 
97
  }
 
98
  else {
 
99
    cout << "-E- Edge not connected to current vertex" << endl;
 
100
    return;
 
101
  }
 
102
 
 
103
  if (my_idx >= radix || other_idx >= radix) {
 
104
    cout << "-E- Edge index illegal" << endl;
 
105
    return;
 
106
  }
 
107
 
 
108
  // Now disconnect
 
109
  connections[my_idx] = NULL;
 
110
  maxUsed--;
 
111
  v->connections[other_idx] = NULL;
 
112
  v->maxUsed--;
 
113
}
 
114
 
 
115
void vertex::pushConnection(edge* e)
 
116
{
 
117
  maxUsed++;
 
118
  if (maxUsed == radix) {
 
119
    cout << "-E- Can't push connection to vertex: " << id << ", exceeding radix!" << endl;
 
120
    return;
 
121
  }
 
122
  // Mark our side
 
123
  if (e->v1 == NULL) {
 
124
    e->v1 = this;
 
125
    e->idx1 = maxUsed;
 
126
  }
 
127
  else if (e->v2 == NULL) {
 
128
    e->v2 = this;
 
129
    e->idx2 = maxUsed;
 
130
  }
 
131
  else {
 
132
    cout << "-E- Can't push connection both edges are already filled" << endl;
 
133
    return;
 
134
  }
 
135
 
 
136
  if (maxUsed >= radix) {
 
137
    cout << "-E- maxUsed illegal" << endl;
 
138
    return;
 
139
  }
 
140
 
 
141
  // Now connect
 
142
  connections[maxUsed] = e;
 
143
}
 
144
 
 
145
edge* vertex::popConnection()
 
146
{
 
147
  // Look for a connection
 
148
  int i=0;
 
149
  while ((i<radix) && !connections[i])
 
150
    i++;
 
151
  // No real connection found
 
152
  if (i == radix)
 
153
    return NULL;
 
154
 
 
155
  edge* tmp = connections[i];
 
156
 
 
157
  // Disconnect chosen edge
 
158
  connections[i] = NULL;
 
159
  if (tmp->v1 == this) {
 
160
    vertex* v = (vertex*)(tmp->v2);
 
161
    v->connections[tmp->idx2] = NULL;
 
162
  }
 
163
  else if (tmp->v2 == this) {
 
164
    vertex* v = (vertex*)(tmp->v1);
 
165
    v->connections[tmp->idx1] = NULL;
 
166
  }
 
167
  else {
 
168
    cout << "-E- Edge not connected to current vertex" << endl;
 
169
    return NULL;
 
170
  }
 
171
 
 
172
  if (tmp->idx1 >= radix || tmp->idx2 >= radix) {
 
173
    cout << "-E- Edge index illegal" << endl;
 
174
    return NULL;
 
175
  }
 
176
 
 
177
  return tmp;
 
178
}
 
179
 
 
180
// For unmacthed vertex, find an unmatched neighbor and match the pair
 
181
bool vertex::match()
 
182
{
 
183
  // Already matched
 
184
  if (partner)
 
185
    return false;
 
186
  // Look for neighbor
 
187
  for (int i=0; i<radix; i++) {
 
188
    if (connections[i]) {
 
189
      vertex* v = (vertex*)(connections[i]->otherSide(this));
 
190
      if (!v->partner) {
 
191
        // Match
 
192
        partner = connections[i];
 
193
        v->partner = connections[i];
 
194
        return true;
 
195
      }
 
196
    }
 
197
  }
 
198
  return false;
 
199
}
 
200
 
 
201
edge* vertex::getPartner() const
 
202
{
 
203
  return partner;
 
204
}
 
205
 
 
206
bool vertex::getInLayers() const
 
207
{
 
208
  return inLayers;
 
209
}
 
210
 
 
211
void vertex::setInLayers(bool b)
 
212
{
 
213
  inLayers = b;
 
214
}
 
215
 
 
216
void vertex::resetLayersInfo()
 
217
{
 
218
  inLayers = false;
 
219
  succCount = predCount = 0;
 
220
  for (int i=0; i<radix; i++)
 
221
    succ[i] = pred[i] = NULL;
 
222
}
 
223
 
 
224
void vertex::addPartnerLayers(list<vertex*>& l)
 
225
{
 
226
  // No partner
 
227
  if (!partner)
 
228
    return;
 
229
  vertex* p = (vertex*)(partner->otherSide(this));
 
230
  // Partner already in one of the layers
 
231
  if (p->inLayers)
 
232
    return;
 
233
  // Add partner to the layer
 
234
  l.push_front(p);
 
235
  p->inLayers = true;
 
236
  // Update pred/succ relations
 
237
  if (succCount >= radix) {
 
238
    cout << "-E- More successors than radix" << endl;
 
239
    return;
 
240
  }
 
241
  succ[succCount] = partner;
 
242
  succCount++;
 
243
 
 
244
  if (p->predCount >= radix) {
 
245
    cout << "-E- More predecessors than radix" << endl;
 
246
    return;
 
247
  }
 
248
  p->pred[p->predCount] = partner;
 
249
  p->predCount++;
 
250
}
 
251
 
 
252
bool vertex::addNonPartnersLayers(list<vertex*>& l)
 
253
{
 
254
  vertex* prtn = NULL;
 
255
  bool res = false;
 
256
 
 
257
  if (partner)
 
258
    prtn = (vertex*)(partner->otherSide(this));
 
259
 
 
260
  for (int i=0; i<radix; i++) {
 
261
    vertex* v = (vertex*)(connections[i]->otherSide(this));
 
262
    if ((v != prtn) && (!v->inLayers)) {
 
263
      // free vertex found
 
264
      if (!v->partner)
 
265
        res = true;
 
266
      // Add vertex to the layer
 
267
      l.push_front(v);
 
268
      v->inLayers = true;
 
269
      // Update pred/succ relations
 
270
      if (succCount >= radix) {
 
271
        cout << "-E- More successors than radix" << endl;
 
272
        return false;
 
273
      }
 
274
      succ[succCount] = connections[i];
 
275
      succCount++;
 
276
 
 
277
      if (v->predCount >= radix) {
 
278
        cout << "-E- More predecessors than radix" << endl;
 
279
        return false;
 
280
      }
 
281
      v->pred[v->predCount] = connections[i];
 
282
      v->predCount++;
 
283
    }
 
284
  }
 
285
  return res;
 
286
}
 
287
 
 
288
vertex* vertex::getPredecessor() const
 
289
{
 
290
  vertex* v = NULL;
 
291
  // Find a valid predecessor still in layers
 
292
  for (int i=0; i<radix; i++) {
 
293
    if (pred[i]) {
 
294
      vertex* v2 = (vertex*)(pred[i]->otherSide(this));
 
295
      if (v2->inLayers) {
 
296
        v = v2;
 
297
        break;
 
298
      }
 
299
    }
 
300
  }
 
301
  return v;
 
302
}
 
303
 
 
304
// Flip edge status on augmenting path
 
305
void vertex::flipPredEdge(int idx)
 
306
{
 
307
  int i=0;
 
308
  // Find an edge to a predecessor
 
309
  for (i=0; i<radix; i++)
 
310
    if (pred[i]) {
 
311
      vertex* v1 = (vertex*)pred[i]->v1;
 
312
      vertex* v2 = (vertex*)pred[i]->v2;
 
313
      if (v1->getInLayers() && v2->getInLayers())
 
314
        break;
 
315
    }
 
316
 
 
317
  if (i == radix) {
 
318
    cout << "-E- Could find predecessor for flip" << endl;
 
319
    return;
 
320
  }
 
321
  // The predecessor vertex
 
322
  vertex* v = (vertex*) pred[i]->otherSide(this);
 
323
 
 
324
  // Unmatch edge
 
325
  if (idx)
 
326
        v->partner = NULL;
 
327
  // Match edge
 
328
  else {
 
329
    partner = pred[i];
 
330
    v->partner = pred[i];
 
331
  }
 
332
}
 
333
 
 
334
// Removing vertex from layers and updating successors/predecessors
 
335
void vertex::unLink(list<vertex*>& l)
 
336
{
 
337
  inLayers = false;
 
338
  for (int i=0; i<radix; i++) {
 
339
    if (succ[i]) {
 
340
      vertex* v = (vertex*)succ[i]->otherSide(this);
 
341
      if (v->inLayers) {
 
342
        v->predCount--;
 
343
        // v has no more predecessors, schedule for removal from layers...
 
344
        if (!v->predCount)
 
345
          l.push_back(v);
 
346
        succ[i] = NULL;
 
347
      }
 
348
    }
 
349
  }
 
350
  succCount = 0;
 
351
}
 
352
 
 
353
//CLASS Bipartite
 
354
 
 
355
// C'tor
 
356
 
 
357
Bipartite::Bipartite(int s, int r):size(s),radix(r)
 
358
{
 
359
  leftSide = new vertex*[size];
 
360
  rightSide = new vertex*[size];
 
361
 
 
362
  for (int i=0; i<size; i++) {
 
363
    leftSide[i] = new vertex(i,LEFT,radix);
 
364
    rightSide[i] = new vertex(i,RIGHT,radix);
 
365
  }
 
366
}
 
367
 
 
368
///////////////////////////////////////////////////////////
 
369
 
 
370
// D'tor
 
371
 
 
372
Bipartite::~Bipartite()
 
373
{
 
374
  // Free vertices
 
375
  for (int i=0; i<size; i++) {
 
376
    delete leftSide[i];
 
377
    delete rightSide[i];
 
378
  }
 
379
  delete[] leftSide;
 
380
  delete[] rightSide;
 
381
 
 
382
  // Free edges
 
383
  while (List.size()) {
 
384
    edge* e = (edge*)(List.front());
 
385
    List.pop_front();
 
386
    delete e;
 
387
  }
 
388
}
 
389
 
 
390
////////////////////////////////////////////////////////////
 
391
 
 
392
// Get radix
 
393
 
 
394
int Bipartite::getRadix() const
 
395
{
 
396
  return radix;
 
397
}
 
398
 
 
399
////////////////////////////////////////////////////////////
 
400
 
 
401
// Set edges listt iterator to first
 
402
 
 
403
bool Bipartite::setIterFirst()
 
404
{
 
405
  it = List.begin();
 
406
  if (it == List.end())
 
407
    return false;
 
408
  return true;
 
409
}
 
410
 
 
411
///////////////////////////////////////////////////////////
 
412
 
 
413
// Set edges list iterator to next
 
414
 
 
415
bool Bipartite::setIterNext()
 
416
{
 
417
  if (it == List.end())
 
418
    return false;
 
419
  it++;
 
420
  if (it == List.end())
 
421
    return false;
 
422
  return true;
 
423
}
 
424
 
 
425
////////////////////////////////////////////////////////////
 
426
 
 
427
// Get current edge's request data
 
428
 
 
429
inputData Bipartite::getReqDat()
 
430
{
 
431
  if (it == List.end()) {
 
432
    cout << "-E- Iterator points to list end" << endl;
 
433
  }
 
434
  return ((edge*)(*it))->reqDat;
 
435
}
 
436
 
 
437
/////////////////////////////////////////////////////////////
 
438
 
 
439
// Add connection between the nodes to the graph
 
440
 
 
441
void Bipartite::connectNodes(int n1, int n2, inputData reqDat)
 
442
{
 
443
  if ((n1 >= size) || (n2 >= size)) {
 
444
    cout << "-E- Node index exceeds size" << endl;
 
445
    return;
 
446
  }
 
447
  // Create new edge
 
448
  edge* newEdge = new edge;
 
449
 
 
450
  // Init edge fields and add to it the edges list
 
451
  newEdge->it = List.insert(List.end(), newEdge);
 
452
  newEdge->reqDat = reqDat;
 
453
  newEdge->v1 = newEdge->v2 = NULL;
 
454
 
 
455
  // Connect the vertices
 
456
  leftSide[n1]->pushConnection(newEdge);
 
457
  rightSide[n2]->pushConnection(newEdge);
 
458
}
 
459
 
 
460
////////////////////////////////////////////////////////////////
 
461
 
 
462
// Find maximal matching
 
463
 
 
464
void Bipartite::maximalMatch()
 
465
{
 
466
  // Invoke match on left-side vertices
 
467
  for (int i=0; i<size; i++)
 
468
    leftSide[i]->match();
 
469
}
 
470
 
 
471
////////////////////////////////////////////////////////////////
 
472
 
 
473
// Find maximum matching
 
474
 
 
475
// Hopcroft-Karp algorithm
 
476
Bipartite* Bipartite::maximumMatch()
 
477
{
 
478
  // First find a maximal match
 
479
  maximalMatch();
 
480
 
 
481
  list<void*>::iterator it2 = List.begin();
 
482
  list<vertex*> l1, l2;
 
483
  list<vertex*>::iterator it;
 
484
 
 
485
  // Loop on algorithm phases
 
486
  while (1) {
 
487
    bool hardStop = false;
 
488
    // First reset layers info
 
489
    for (int i=0; i<size; i++) {
 
490
      leftSide[i]->resetLayersInfo();
 
491
      rightSide[i]->resetLayersInfo();
 
492
    }
 
493
    // Add free left-side vertices to l1 (building layer 0)
 
494
    l1.clear();
 
495
    for (int i=0; i<size; i++) {
 
496
      if (!leftSide[i]->getPartner()) {
 
497
        l1.push_front(leftSide[i]);
 
498
        leftSide[i]->setInLayers(true);
 
499
      }
 
500
    }
 
501
    // This is our termination condition
 
502
    // Maximum matching achieved
 
503
    if (l1.empty())
 
504
      break;
 
505
    // Loop on building layers
 
506
    while (1) {
 
507
      bool stop = false;
 
508
      l2.clear();
 
509
      // Add all non-partners of vertices in l1 to layers (l2)
 
510
      // We signal to stop if a free (right-side) vertex is entering l2
 
511
      for (it = l1.begin(); it != l1.end(); it++)
 
512
        if ((*it)->addNonPartnersLayers(l2))
 
513
          stop = true;
 
514
      // Found free vertex among right-side vertices
 
515
      if (stop) {
 
516
        // There are augmenting paths, apply them
 
517
        augment(l2);
 
518
        break;
 
519
      }
 
520
      // This is a terminal condition
 
521
      if (l2.empty()) {
 
522
        hardStop = true;
 
523
        break;
 
524
      }
 
525
      // Add partners of vertices in l2 to layers (l1)
 
526
      l1.clear();
 
527
      for (it = l2.begin(); it!= l2.end(); it++)
 
528
        (*it)->addPartnerLayers(l1);
 
529
      // This is a terminal condition
 
530
      if (l1.empty()) {
 
531
        hardStop = true;
 
532
        break;
 
533
      }
 
534
    }
 
535
    // Maximum matching achieved
 
536
    if (hardStop)
 
537
      break;
 
538
  }
 
539
  // Build the matching graph
 
540
  Bipartite* M = new Bipartite(size, 1);
 
541
  // Go over all edges and move matched one to the new graph
 
542
  it2 = List.begin();
 
543
  while (it2 != List.end()) {
 
544
    edge* e = (edge*)(*it2);
 
545
    if (e->isMatched()) {
 
546
      vertex* v1 = (vertex*)(e->v1);
 
547
      vertex* v2 = (vertex*)(e->v2);
 
548
      // Unlink vertices
 
549
      ((vertex*)(e->v1))->delConnection(e);
 
550
      // Update edges list
 
551
      it2 = List.erase(it2);
 
552
      // Add link to the new graph
 
553
      if (v1->getSide() == LEFT)
 
554
        M->connectNodes(v1->getID(), v2->getID(), e->reqDat);
 
555
      else
 
556
        M->connectNodes(v2->getID(), v1->getID(), e->reqDat);
 
557
      // Free memory
 
558
      delete e;
 
559
    }
 
560
    else
 
561
      it2++;
 
562
  }
 
563
  return M;
 
564
}
 
565
 
 
566
//////////////////////////////////////////////////////////////////////
 
567
 
 
568
// Apply augmenting paths on the matching
 
569
 
 
570
void Bipartite::augment(list<vertex*>& l)
 
571
{
 
572
  // Use delQ to store vertex scheduled for the removal from layers
 
573
  list<vertex*> delQ;
 
574
  // Remove non-free vertices
 
575
  list<vertex*>::iterator it = l.begin();
 
576
  while (it != l.end()) {
 
577
    if ((*it)->getPartner()) {
 
578
      delQ.push_front((*it));
 
579
      it = l.erase(it);
 
580
    }
 
581
    else
 
582
      it++;
 
583
  }
 
584
  // Get rid of non-free vertices
 
585
  while (!delQ.empty()) {
 
586
    vertex* fr = delQ.front();
 
587
    delQ.pop_front();
 
588
    fr->unLink(delQ);
 
589
  }
 
590
 
 
591
  if (l.empty()) {
 
592
    cout << "-E- No free vertices left!" << endl;
 
593
    return;
 
594
  }
 
595
  // Augment and reset pred/succ relations
 
596
  while (!l.empty()) {
 
597
    vertex* curr = l.front();
 
598
    l.pop_front();
 
599
    int idx = 0;
 
600
    // Backtrace the path and augment
 
601
    int length=0;
 
602
    while (1) {
 
603
      delQ.push_front(curr);
 
604
      // Its either the end of a path or an error
 
605
      if (!curr->getPredecessor()) {
 
606
        if (!idx && length) {
 
607
          cout << "-E- This vertex must have predecessor" << endl;
 
608
          return;
 
609
        }
 
610
        break;
 
611
      }
 
612
      // Flip edge status
 
613
      curr->flipPredEdge(idx);
 
614
      // Move back
 
615
      curr = curr->getPredecessor();
 
616
      idx = (idx+1)%2;
 
617
      length++;
 
618
    }
 
619
    // Now clean the delQ
 
620
    while (!delQ.empty()) {
 
621
      vertex* fr = delQ.front();
 
622
      delQ.pop_front();
 
623
      fr->unLink(delQ);
 
624
    }
 
625
  }
 
626
}
 
627
 
 
628
////////////////////////////////////////////////////////////////////////
 
629
 
 
630
// Perform Euler decomposition
 
631
 
 
632
void Bipartite::decompose(Bipartite** bp1, Bipartite** bp2)
 
633
{
 
634
  if (radix < 2) {
 
635
    cout << "-E- Radix value illegal: " << radix << endl;
 
636
    return;
 
637
  }
 
638
 
 
639
  // Create new graphs
 
640
  Bipartite* arr[2];
 
641
  arr[0] = new Bipartite(size, radix/2);
 
642
  arr[1] = new Bipartite(size, radix/2);
 
643
 
 
644
  // Continue as long as unassigned edges left
 
645
  while (!List.empty()) {
 
646
    int idx = 0;
 
647
    edge* e = (edge*)List.front();
 
648
    vertex* current = (vertex*)e->v1;
 
649
    e = current->popConnection();
 
650
 
 
651
    while (e) {
 
652
      // Connect nodes in the new graphs
 
653
      vertex* v1 = (vertex*)e->v1;
 
654
      vertex* v2 = (vertex*)e->v2;
 
655
      if (v1->getSide() == LEFT)
 
656
        arr[idx]->connectNodes(v1->getID(), v2->getID(), e->reqDat);
 
657
      else
 
658
        arr[idx]->connectNodes(v2->getID(), v1->getID(), e->reqDat);
 
659
      idx = (idx+1)%2;
 
660
      // Remove edge from list
 
661
      List.erase(e->it);
 
662
      // Pick next vertex
 
663
      current = (vertex*) e->otherSide(current);
 
664
      // Free memory
 
665
      delete e;
 
666
      // Pick next edge
 
667
      e = current->popConnection();
 
668
    }
 
669
  }
 
670
  *bp1 = arr[0];
 
671
  *bp2 = arr[1];
 
672
}