tarjan.cc revision 161c4a132743f15fc4757112b673085c2a7a7f29 
1// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4#include "update_engine/payload_generator/tarjan.h"
5
6#include <algorithm>
7#include <vector>
8
9#include <base/logging.h>
10
11#include "update_engine/utils.h"
12
13using std::min;
14using std::vector;
15
16namespace chromeos_update_engine {
17
18namespace {
19const vector<Vertex>::size_type kInvalidIndex = -1;
20}
21
22void TarjanAlgorithm::Execute(Vertex::Index vertex,
23                              Graph* graph,
24                              vector<Vertex::Index>* out) {
25  stack_.clear();
26  components_.clear();
27  index_ = 0;
28  for (Graph::iterator it = graph->begin(); it != graph->end(); ++it)
29    it->index = it->lowlink = kInvalidIndex;
30  required_vertex_ = vertex;
31
32  Tarjan(vertex, graph);
33  if (!components_.empty())
34    out->swap(components_[0]);
35}
36
37void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) {
38  CHECK_EQ((*graph)[vertex].index, kInvalidIndex);
39  (*graph)[vertex].index = index_;
40  (*graph)[vertex].lowlink = index_;
41  index_++;
42  stack_.push_back(vertex);
43  for (Vertex::EdgeMap::iterator it = (*graph)[vertex].out_edges.begin();
44       it != (*graph)[vertex].out_edges.end(); ++it) {
45    Vertex::Index vertex_next = it->first;
46    if ((*graph)[vertex_next].index == kInvalidIndex) {
47      Tarjan(vertex_next, graph);
48      (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
49                                     (*graph)[vertex_next].lowlink);
50    } else if (utils::VectorContainsValue(stack_, vertex_next)) {
51      (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
52                                     (*graph)[vertex_next].index);
53    }
54  }
55  if ((*graph)[vertex].lowlink == (*graph)[vertex].index) {
56    vector<Vertex::Index> component;
57    Vertex::Index other_vertex;
58    do {
59      other_vertex = stack_.back();
60      stack_.pop_back();
61      component.push_back(other_vertex);
62    } while (other_vertex != vertex && !stack_.empty());
63
64    if (utils::VectorContainsValue(component, required_vertex_)) {
65      components_.resize(components_.size() + 1);
66      component.swap(components_.back());
67    }
68  }
69}
70
71}  // namespace chromeos_update_engine
72