cmComputeTargetDepends.cxx 22.3 KB
Newer Older
1
2
3
/*============================================================================
  CMake - Cross Platform Makefile Generator
  Copyright 2000-2009 Kitware, Inc., Insight Software Consortium
4

5
6
  Distributed under the OSI-approved BSD License (the "License");
  see accompanying file Copyright.txt for details.
7

8
9
10
11
  This software is distributed WITHOUT ANY WARRANTY; without even the
  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  See the License for more information.
============================================================================*/
12
13
#include "cmComputeTargetDepends.h"

14
#include "cmComputeComponentGraph.h"
15
16
17
#include "cmGlobalGenerator.h"
#include "cmLocalGenerator.h"
#include "cmMakefile.h"
18
#include "cmSourceFile.h"
19
#include "cmState.h"
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "cmSystemTools.h"
#include "cmTarget.h"
#include "cmake.h"

#include <algorithm>

#include <assert.h>

/*

This class is meant to analyze inter-target dependencies globally
during the generation step.  The goal is to produce a set of direct
dependencies for each target such that no cycles are left and the
build order is safe.

For most target types cyclic dependencies are not allowed.  However
36
STATIC libraries may depend on each other in a cyclic fashion.  In
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
general the directed dependency graph forms a directed-acyclic-graph
of strongly connected components.  All strongly connected components
should consist of only STATIC_LIBRARY targets.

In order to safely break dependency cycles we must preserve all other
dependencies passing through the corresponding strongly connected component.
The approach taken by this class is as follows:

  - Collect all targets and form the original dependency graph
  - Run Tarjan's algorithm to extract the strongly connected components
    (error if any member of a non-trivial component is not STATIC)
  - The original dependencies imply a DAG on the components.
    Use the implied DAG to construct a final safe set of dependencies.

The final dependency set is constructed as follows:

  - For each connected component targets are placed in an arbitrary
    order.  Each target depends on the target following it in the order.
    The first target is designated the head and the last target the tail.
    (most components will be just 1 target anyway)

  - Original dependencies between targets in different components are
    converted to connect the depender's component tail to the
    dependee's component head.

In most cases this will reproduce the original dependencies.  However
when there are cycles of static libraries they will be broken in a
safe manner.

For example, consider targets A0, A1, A2, B0, B1, B2, and C with these
dependencies:

  A0 -> A1 -> A2 -> A0  ,  B0 -> B1 -> B2 -> B0 -> A0  ,  C -> B0

Components may be identified as

  Component 0: A0, A1, A2
  Component 1: B0, B1, B2
  Component 2: C

Intra-component dependencies are:

  0: A0 -> A1 -> A2   , head=A0, tail=A2
  1: B0 -> B1 -> B2   , head=B0, tail=B2
  2: head=C, tail=C

The inter-component dependencies are converted as:

  B0 -> A0  is component 1->0 and becomes  B2 -> A0
  C  -> B0  is component 2->1 and becomes  C  -> B0

This leads to the final target dependencies:

  C -> B0 -> B1 -> B2 -> A0 -> A1 -> A2

These produce a safe build order since C depends directly or
transitively on all the static libraries it links.

*/

//----------------------------------------------------------------------------
cmComputeTargetDepends::cmComputeTargetDepends(cmGlobalGenerator* gg)
{
  this->GlobalGenerator = gg;
  cmake* cm = this->GlobalGenerator->GetCMakeInstance();
102
103
104
105
  this->DebugMode = cm->GetState()
                      ->GetGlobalPropertyAsBool("GLOBAL_DEPENDS_DEBUG_MODE");
  this->NoCycles = cm->GetState()
                      ->GetGlobalPropertyAsBool("GLOBAL_DEPENDS_NO_CYCLES");
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
}

//----------------------------------------------------------------------------
cmComputeTargetDepends::~cmComputeTargetDepends()
{
}

//----------------------------------------------------------------------------
bool cmComputeTargetDepends::Compute()
{
  // Build the original graph.
  this->CollectTargets();
  this->CollectDepends();
  if(this->DebugMode)
    {
121
    this->DisplayGraph(this->InitialGraph, "initial");
122
123
124
    }

  // Identify components.
125
  cmComputeComponentGraph ccg(this->InitialGraph);
126
127
  if(this->DebugMode)
    {
128
    this->DisplayComponents(ccg);
129
    }
130
  if(!this->CheckComponents(ccg))
131
132
133
134
135
    {
    return false;
    }

  // Compute the final dependency graph.
136
137
138
139
  if(!this->ComputeFinalDepends(ccg))
    {
    return false;
    }
140
141
  if(this->DebugMode)
    {
142
    this->DisplayGraph(this->FinalGraph, "final");
143
144
145
146
147
148
149
    }

  return true;
}

//----------------------------------------------------------------------------
void
150
cmComputeTargetDepends::GetTargetDirectDepends(cmGeneratorTarget const* t,
151
                                               cmTargetDependSet& deps)
152
153
154
{
  // Lookup the index for this target.  All targets should be known by
  // this point.
155
  std::map<cmGeneratorTarget const*, int>::const_iterator tii
156
                                                  = this->TargetIndex.find(t);
157
158
159
160
  assert(tii != this->TargetIndex.end());
  int i = tii->second;

  // Get its final dependencies.
161
162
  EdgeList const& nl = this->FinalGraph[i];
  for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
163
    {
164
    cmGeneratorTarget const* dep = this->Targets[*ni];
165
166
    cmTargetDependSet::iterator di = deps.insert(dep).first;
    di->SetType(ni->IsStrong());
167
168
169
170
171
172
173
174
175
176
177
    }
}

//----------------------------------------------------------------------------
void cmComputeTargetDepends::CollectTargets()
{
  // Collect all targets from all generators.
  std::vector<cmLocalGenerator*> const& lgens =
    this->GlobalGenerator->GetLocalGenerators();
  for(unsigned int i = 0; i < lgens.size(); ++i)
    {
Stephen Kelly's avatar
Stephen Kelly committed
178
179
180
    const std::vector<cmGeneratorTarget*> targets =
        lgens[i]->GetGeneratorTargets();
    for(std::vector<cmGeneratorTarget*>::const_iterator ti = targets.begin();
181
        ti != targets.end(); ++ti)
182
      {
Stephen Kelly's avatar
Stephen Kelly committed
183
      cmGeneratorTarget* gt = *ti;
184
      int index = static_cast<int>(this->Targets.size());
185
186
      this->TargetIndex[gt] = index;
      this->Targets.push_back(gt);
187
188
189
190
191
192
193
194
      }
    }
}

//----------------------------------------------------------------------------
void cmComputeTargetDepends::CollectDepends()
{
  // Allocate the dependency graph adjacency lists.
195
  this->InitialGraph.resize(this->Targets.size());
196
197
198
199
200
201
202
203
204
205
206
207

  // Compute each dependency list.
  for(unsigned int i=0; i < this->Targets.size(); ++i)
    {
    this->CollectTargetDepends(i);
    }
}

//----------------------------------------------------------------------------
void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
{
  // Get the depender.
208
  cmGeneratorTarget const* depender = this->Targets[depender_index];
209
  if (depender->GetType() == cmState::INTERFACE_LIBRARY)
210
211
212
    {
    return;
    }
213

214
215
216
217
  // Loop over all targets linked directly in all configs.
  // We need to make targets depend on the union of all config-specific
  // dependencies in all targets, because the generated build-systems can't
  // deal with config-specific dependencies.
218
  {
219
  std::set<std::string> emitted;
220

221
  std::vector<std::string> configs;
222
  depender->Makefile->GetConfigurations(configs);
223
224
225
226
  if (configs.empty())
    {
    configs.push_back("");
    }
227
228
229
  for (std::vector<std::string>::const_iterator it = configs.begin();
    it != configs.end(); ++it)
    {
230
    std::vector<cmSourceFile const*> objectFiles;
231
    depender->GetExternalObjects(objectFiles, *it);
232
233
234
235
236
237
    for(std::vector<cmSourceFile const*>::const_iterator
        oi = objectFiles.begin(); oi != objectFiles.end(); ++oi)
      {
      std::string objLib = (*oi)->GetObjectLibrary();
      if (!objLib.empty() && emitted.insert(objLib).second)
        {
238
239
240
241
        if(depender->GetType() != cmState::EXECUTABLE &&
            depender->GetType() != cmState::STATIC_LIBRARY &&
            depender->GetType() != cmState::SHARED_LIBRARY &&
            depender->GetType() != cmState::MODULE_LIBRARY)
242
243
244
245
246
          {
          this->GlobalGenerator->GetCMakeInstance()
            ->IssueMessage(cmake::FATAL_ERROR,
                            "Only executables and non-OBJECT libraries may "
                            "reference target objects.",
247
                            depender->GetBacktrace());
248
249
          return;
          }
250
        const_cast<cmGeneratorTarget*>(depender)->Target->AddUtility(objLib);
251
252
        }
      }
253

254
    cmLinkImplementation const* impl = depender->GetLinkImplementation(*it);
255

256
257
    // A target should not depend on itself.
    emitted.insert(depender->GetName());
258
    for(std::vector<cmLinkImplItem>::const_iterator
259
260
          lib = impl->Libraries.begin();
        lib != impl->Libraries.end(); ++lib)
261
262
263
264
      {
      // Don't emit the same library twice for this target.
      if(emitted.insert(*lib).second)
        {
Stephen Kelly's avatar
Stephen Kelly committed
265
        this->AddTargetDepend(depender_index, *lib, true);
266
        this->AddInterfaceDepends(depender_index, *lib, emitted);
267
268
269
270
        }
      }
    }
  }
271
272

  // Loop over all utility dependencies.
273
  {
274
  std::set<cmLinkItem> const& tutils = depender->GetUtilityItems();
275
  std::set<std::string> emitted;
276
277
  // A target should not depend on itself.
  emitted.insert(depender->GetName());
278
  for(std::set<cmLinkItem>::const_iterator util = tutils.begin();
279
280
281
282
283
      util != tutils.end(); ++util)
    {
    // Don't emit the same utility twice for this target.
    if(emitted.insert(*util).second)
      {
Stephen Kelly's avatar
Stephen Kelly committed
284
      this->AddTargetDepend(depender_index, *util, false);
285
286
      }
    }
287
  }
288
289
}

290
291
//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
292
293
294
                                             const cmGeneratorTarget* dependee,
                                             const std::string& config,
                                             std::set<std::string> &emitted)
295
{
296
  cmGeneratorTarget const* depender = this->Targets[depender_index];
297
  if(cmLinkInterface const* iface =
298
                                dependee->GetLinkInterface(config,
299
                                                           depender))
300
    {
301
    for(std::vector<cmLinkItem>::const_iterator
302
303
304
305
306
307
        lib = iface->Libraries.begin();
        lib != iface->Libraries.end(); ++lib)
      {
      // Don't emit the same library twice for this target.
      if(emitted.insert(*lib).second)
        {
Stephen Kelly's avatar
Stephen Kelly committed
308
        this->AddTargetDepend(depender_index, *lib, true);
309
        this->AddInterfaceDepends(depender_index, *lib, emitted);
310
311
312
313
314
315
316
        }
      }
    }
}

//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
317
                                             cmLinkItem const& dependee_name,
318
                                             std::set<std::string> &emitted)
319
{
320
  cmGeneratorTarget const* depender = this->Targets[depender_index];
321
  cmGeneratorTarget const* dependee = dependee_name.Target;
322
323
324
  // Skip targets that will not really be linked.  This is probably a
  // name conflict between an external library and an executable
  // within the project.
325
  if(dependee &&
326
     dependee->GetType() == cmState::EXECUTABLE &&
327
     !dependee->IsExecutableWithExports())
328
329
330
331
332
333
    {
    dependee = 0;
    }

  if(dependee)
    {
334
    this->AddInterfaceDepends(depender_index, dependee, "", emitted);
335
    std::vector<std::string> configs;
336
    depender->Makefile->GetConfigurations(configs);
337
338
339
340
341
    for (std::vector<std::string>::const_iterator it = configs.begin();
      it != configs.end(); ++it)
      {
      // A target should not depend on itself.
      emitted.insert(depender->GetName());
342
      this->AddInterfaceDepends(depender_index, dependee, *it, emitted);
343
344
345
346
      }
    }
}

347
//----------------------------------------------------------------------------
348
349
350
void cmComputeTargetDepends::AddTargetDepend(
  int depender_index, cmLinkItem const& dependee_name,
  bool linking)
351
352
{
  // Get the depender.
353
  cmGeneratorTarget const* depender = this->Targets[depender_index];
354
355

  // Check the target's makefile first.
356
  cmGeneratorTarget const* dependee = dependee_name.Target;
357

358
  if(!dependee && !linking &&
359
    (depender->GetType() != cmState::GLOBAL_TARGET))
360
361
362
    {
    cmake::MessageType messageType = cmake::AUTHOR_WARNING;
    bool issueMessage = false;
363
    std::ostringstream e;
364
    switch(depender->GetPolicyStatusCMP0046())
365
366
      {
      case cmPolicies::WARN:
Stephen Kelly's avatar
Stephen Kelly committed
367
        e << cmPolicies::GetPolicyWarning(cmPolicies::CMP0046) << "\n";
368
369
370
371
372
373
374
375
376
377
378
379
        issueMessage = true;
      case cmPolicies::OLD:
        break;
      case cmPolicies::NEW:
      case cmPolicies::REQUIRED_IF_USED:
      case cmPolicies::REQUIRED_ALWAYS:
        issueMessage = true;
        messageType = cmake::FATAL_ERROR;
      }
    if(issueMessage)
      {
      cmake* cm = this->GlobalGenerator->GetCMakeInstance();
380

381
382
383
384
      e << "The dependency target \"" <<  dependee_name
        << "\" of target \"" << depender->GetName() << "\" does not exist.";

      cmListFileBacktrace const* backtrace =
385
        depender->GetUtilityBacktrace(dependee_name);
386
      if(backtrace)
387
        {
388
389
390
391
392
        cm->IssueMessage(messageType, e.str(), *backtrace);
        }
      else
        {
        cm->IssueMessage(messageType, e.str());
393
394
395
396
397
        }

      }
    }

398
399
400
401
  // Skip targets that will not really be linked.  This is probably a
  // name conflict between an external library and an executable
  // within the project.
  if(linking && dependee &&
402
     dependee->GetType() == cmState::EXECUTABLE &&
403
     !dependee->IsExecutableWithExports())
404
405
406
407
    {
    dependee = 0;
    }

408
  if(dependee)
409
    {
410
    this->AddTargetDepend(depender_index, dependee, linking);
411
    }
412
}
413

414
415
//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
416
                                             const cmGeneratorTarget* dependee,
417
418
                                             bool linking)
{
419
  if(dependee->IsImported() ||
420
     dependee->GetType() == cmState::INTERFACE_LIBRARY)
421
    {
422
423
    // Skip IMPORTED and INTERFACE targets but follow their utility
    // dependencies.
424
    std::set<cmLinkItem> const& utils = dependee->GetUtilityItems();
425
    for(std::set<cmLinkItem>::const_iterator i = utils.begin();
426
427
        i != utils.end(); ++i)
      {
428
      if(cmGeneratorTarget const* transitive_dependee = i->Target)
429
        {
430
        this->AddTargetDepend(depender_index, transitive_dependee, false);
431
        }
432
433
434
435
436
437
      }
    }
  else
    {
    // Lookup the index for this target.  All targets should be known by
    // this point.
438
    std::map<cmGeneratorTarget const*, int>::const_iterator tii =
439
440
441
442
443
444
445
446
      this->TargetIndex.find(dependee);
    assert(tii != this->TargetIndex.end());
    int dependee_index = tii->second;

    // Add this entry to the dependency graph.
    this->InitialGraph[depender_index].push_back(
      cmGraphEdge(dependee_index, !linking));
    }
447
448
449
450
}

//----------------------------------------------------------------------------
void
451
452
cmComputeTargetDepends::DisplayGraph(Graph const& graph,
                                     const std::string& name)
453
{
454
  fprintf(stderr, "The %s target dependency graph is:\n", name.c_str());
455
456
457
  int n = static_cast<int>(graph.size());
  for(int depender_index = 0; depender_index < n; ++depender_index)
    {
458
    EdgeList const& nl = graph[depender_index];
459
    cmGeneratorTarget const* depender = this->Targets[depender_index];
460
    fprintf(stderr, "target %d is [%s]\n",
461
            depender_index, depender->GetName().c_str());
462
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
463
      {
464
      int dependee_index = *ni;
465
      cmGeneratorTarget const* dependee = this->Targets[dependee_index];
466
      fprintf(stderr, "  depends on target %d [%s] (%s)\n", dependee_index,
467
              dependee->GetName().c_str(), ni->IsStrong()? "strong" : "weak");
468
469
470
471
472
473
      }
    }
  fprintf(stderr, "\n");
}

//----------------------------------------------------------------------------
474
475
476
void
cmComputeTargetDepends
::DisplayComponents(cmComputeComponentGraph const& ccg)
477
478
{
  fprintf(stderr, "The strongly connected components are:\n");
479
480
  std::vector<NodeList> const& components = ccg.GetComponents();
  int n = static_cast<int>(components.size());
481
482
  for(int c = 0; c < n; ++c)
    {
483
    NodeList const& nl = components[c];
484
    fprintf(stderr, "Component (%d):\n", c);
485
    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
486
      {
487
      int i = *ni;
488
      fprintf(stderr, "  contains target %d [%s]\n",
489
              i, this->Targets[i]->GetName().c_str());
490
491
492
493
494
495
      }
    }
  fprintf(stderr, "\n");
}

//----------------------------------------------------------------------------
496
497
498
bool
cmComputeTargetDepends
::CheckComponents(cmComputeComponentGraph const& ccg)
499
500
501
{
  // All non-trivial components should consist only of static
  // libraries.
502
503
  std::vector<NodeList> const& components = ccg.GetComponents();
  int nc = static_cast<int>(components.size());
504
505
506
  for(int c=0; c < nc; ++c)
    {
    // Get the current component.
507
    NodeList const& nl = components[c];
508
509

    // Skip trivial components.
510
    if(nl.size() < 2)
511
512
513
514
      {
      continue;
      }

515
516
517
518
519
520
521
    // Immediately complain if no cycles are allowed at all.
    if(this->NoCycles)
      {
      this->ComplainAboutBadComponent(ccg, c);
      return false;
      }

522
    // Make sure the component is all STATIC_LIBRARY targets.
523
    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
524
      {
525
      if(this->Targets[*ni]->GetType() != cmState::STATIC_LIBRARY)
526
        {
527
        this->ComplainAboutBadComponent(ccg, c);
528
529
530
531
532
533
534
535
536
        return false;
        }
      }
    }
  return true;
}

//----------------------------------------------------------------------------
void
537
cmComputeTargetDepends
538
539
::ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c,
                            bool strong)
540
541
{
  // Construct the error message.
542
  std::ostringstream e;
543
544
  e << "The inter-target dependency graph contains the following "
    << "strongly connected component (cycle):\n";
545
546
547
548
  std::vector<NodeList> const& components = ccg.GetComponents();
  std::vector<int> const& cmap = ccg.GetComponentMap();
  NodeList const& cl = components[c];
  for(NodeList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci)
549
550
551
    {
    // Get the depender.
    int i = *ci;
552
    cmGeneratorTarget const* depender = this->Targets[i];
553
554

    // Describe the depender.
555
    e << "  \"" << depender->GetName() << "\" of type "
556
      << cmState::GetTargetTypeName(depender->GetType()) << "\n";
557
558

    // List its dependencies that are inside the component.
559
560
    EdgeList const& nl = this->InitialGraph[i];
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
561
      {
562
563
      int j = *ni;
      if(cmap[j] == c)
564
        {
565
        cmGeneratorTarget const* dependee = this->Targets[j];
566
567
        e << "    depends on \"" << dependee->GetName() << "\""
          << " (" << (ni->IsStrong()? "strong" : "weak") << ")\n";
568
569
570
        }
      }
    }
571
572
573
574
575
576
577
578
579
  if(strong)
    {
    // Custom command executable dependencies cannot occur within a
    // component of static libraries.  The cycle must appear in calls
    // to add_dependencies.
    e << "The component contains at least one cycle consisting of strong "
      << "dependencies (created by add_dependencies) that cannot be broken.";
    }
  else if(this->NoCycles)
580
581
582
583
584
585
586
587
588
    {
    e << "The GLOBAL_DEPENDS_NO_CYCLES global property is enabled, so "
      << "cyclic dependencies are not allowed even among static libraries.";
    }
  else
    {
    e << "At least one of these targets is not a STATIC_LIBRARY.  "
      << "Cyclic dependencies are allowed only among static libraries.";
    }
589
590
591
592
  cmSystemTools::Error(e.str().c_str());
}

//----------------------------------------------------------------------------
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
bool
cmComputeTargetDepends
::IntraComponent(std::vector<int> const& cmap, int c, int i, int* head,
                 std::set<int>& emitted, std::set<int>& visited)
{
  if(!visited.insert(i).second)
    {
    // Cycle in utility depends!
    return false;
    }
  if(emitted.insert(i).second)
    {
    // Honor strong intra-component edges in the final order.
    EdgeList const& el = this->InitialGraph[i];
    for(EdgeList::const_iterator ei = el.begin(); ei != el.end(); ++ei)
      {
      int j = *ei;
      if(cmap[j] == c && ei->IsStrong())
        {
612
        this->FinalGraph[i].push_back(cmGraphEdge(j, true));
613
614
615
616
617
618
619
620
621
622
        if(!this->IntraComponent(cmap, c, j, head, emitted, visited))
          {
          return false;
          }
        }
      }

    // Prepend to a linear linked-list of intra-component edges.
    if(*head >= 0)
      {
623
      this->FinalGraph[i].push_back(cmGraphEdge(*head, false));
624
625
626
627
628
629
630
631
632
633
634
635
      }
    else
      {
      this->ComponentTail[c] = i;
      }
    *head = i;
    }
  return true;
}

//----------------------------------------------------------------------------
bool
636
637
cmComputeTargetDepends
::ComputeFinalDepends(cmComputeComponentGraph const& ccg)
638
{
639
640
641
642
643
644
645
  // Get the component graph information.
  std::vector<NodeList> const& components = ccg.GetComponents();
  Graph const& cgraph = ccg.GetComponentGraph();

  // Allocate the final graph.
  this->FinalGraph.resize(0);
  this->FinalGraph.resize(this->InitialGraph.size());
646

647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
  // Choose intra-component edges to linearize dependencies.
  std::vector<int> const& cmap = ccg.GetComponentMap();
  this->ComponentHead.resize(components.size());
  this->ComponentTail.resize(components.size());
  int nc = static_cast<int>(components.size());
  for(int c=0; c < nc; ++c)
    {
    int head = -1;
    std::set<int> emitted;
    NodeList const& nl = components[c];
    for(NodeList::const_reverse_iterator ni = nl.rbegin();
        ni != nl.rend(); ++ni)
      {
      std::set<int> visited;
      if(!this->IntraComponent(cmap, c, *ni, &head, emitted, visited))
        {
        // Cycle in add_dependencies within component!
        this->ComplainAboutBadComponent(ccg, c, true);
        return false;
        }
      }
    this->ComponentHead[c] = head;
    }

671
  // Convert inter-component edges to connect component tails to heads.
672
673
  int n = static_cast<int>(cgraph.size());
  for(int depender_component=0; depender_component < n; ++depender_component)
674
    {
675
    int depender_component_tail = this->ComponentTail[depender_component];
676
677
    EdgeList const& nl = cgraph[depender_component];
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
678
      {
679
      int dependee_component = *ni;
680
      int dependee_component_head = this->ComponentHead[dependee_component];
681
      this->FinalGraph[depender_component_tail]
682
        .push_back(cmGraphEdge(dependee_component_head, ni->IsStrong()));
683
684
      }
    }
685
  return true;
686
}