blob: 1a80a95d56fd9fe385091d638ce37e531facdac6 [file] [log] [blame]
// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// This is an implemenation of Tarjan's algorithm which finds all
// Strongly Connected Components in a graph.
// Note: a true Tarjan algorithm would find all strongly connected components
// in the graph. This implementation will only find the strongly connected
// component containing the vertex passed in.
#include <vector>
#include "update_engine/graph_types.h"
namespace chromeos_update_engine {
class TarjanAlgorithm {
TarjanAlgorithm() : index_(0), required_vertex_(0) {}
// 'out' is set to the result if there is one, otherwise it's untouched.
void Execute(Vertex::Index vertex,
Graph* graph,
std::vector<Vertex::Index>* out);
void Tarjan(Vertex::Index vertex, Graph* graph);
Vertex::Index index_;
Vertex::Index required_vertex_;
std::vector<Vertex::Index> stack_;
std::vector<std::vector<Vertex::Index> > components_;
} // namespace chromeos_update_engine