30template <
typename IntQueue>
31inline void PopTop(IntQueue* q,
int* top) {
36template <
typename C,
typename F>
37void PopTop(std::priority_queue<int, C, F>* q,
int* top) {
43template <
bool stable_sort>
45 CHECK(!TraversalStarted()) <<
"Cannot add nodes after starting traversal";
46 CHECK_GE(node_index, 0) <<
"Index must not be negative";
48 if (
static_cast<std::size_t
>(node_index) >= adjacency_lists_.size()) {
49 adjacency_lists_.resize(node_index + 1);
63template <
bool stable_sort>
65 CHECK(!TraversalStarted()) <<
"Cannot add edges after starting traversal";
70 const uint32 adj_list_size = adj_list.size();
72 for (AdjacencyList::const_iterator it = adj_list.begin();
73 it != adj_list.end(); ++it) {
78 adj_list.push_back(to);
81 adj_list.push_back(to);
82 if (++num_edges_added_since_last_duplicate_removal_ > ++num_edges_ / 2) {
83 num_edges_added_since_last_duplicate_removal_ = 0;
88 num_edges_ -= RemoveDuplicates(&adjacency_lists_,
94template <
bool stable_sort>
96 int* next_node_index,
bool* cyclic, std::vector<int>* output_cycle_nodes) {
97 if (!TraversalStarted()) {
102 if (num_nodes_left_ == 0) {
105 if (nodes_with_zero_indegree_.empty()) {
106 VLOG(2) <<
"Not all nodes have been visited (" << num_nodes_left_
107 <<
" nodes left), but there aren't any zero-indegree nodes"
108 <<
" available. This graph is cyclic! Use ExtractCycle() for"
109 <<
" more information.";
111 if (output_cycle_nodes != NULL) {
112 ExtractCycle(output_cycle_nodes);
119 PopTop(&nodes_with_zero_indegree_, next_node_index);
124 adj_list.swap(adjacency_lists_[*next_node_index]);
127 for (std::size_t i = 0; i < adj_list.size(); ++i) {
128 if (--indegree_[adj_list[i]] == 0) {
129 nodes_with_zero_indegree_.push(adj_list[i]);
135template <
bool stable_sort>
137 if (TraversalStarted()) {
141 const int num_nodes = adjacency_lists_.size();
142 indegree_.assign(num_nodes, 0);
148 for (
int from = 0; from < num_nodes; ++from) {
150 for (AdjacencyList::const_iterator it = adj_list.begin();
151 it != adj_list.end(); ++it) {
157 for (
int node = 0; node < num_nodes; ++node) {
158 if (indegree_[node] == 0) {
159 nodes_with_zero_indegree_.push(node);
163 num_nodes_left_ = num_nodes;
164 traversal_started_ =
true;
168template <
bool stable_sort>
170 std::vector<AdjacencyList>* lists,
int skip_lists_smaller_than) {
172 if (skip_lists_smaller_than < 2) {
173 skip_lists_smaller_than = 2;
175 const int n = lists->size();
176 std::vector<bool> visited(n,
false);
177 int num_duplicates_removed = 0;
178 for (std::vector<AdjacencyList>::iterator list = lists->begin();
179 list != lists->end(); ++list) {
180 if (list->size() <
static_cast<std::size_t
>(skip_lists_smaller_than)) {
183 num_duplicates_removed += list->size();
187 AdjacencyList::iterator it = list->begin();
188 DCHECK(it != list->end());
189 while (!visited[*it]) {
190 visited[*(it++)] =
true;
191 if (it == list->end()) {
196 if (it != list->end()) {
197 AdjacencyList::iterator it2 = it;
198 while (++it != list->end()) {
204 list->erase(it2, list->end());
206 for (it = list->begin(); it != list->end(); ++it) {
207 visited[*it] =
false;
209 num_duplicates_removed -= list->size();
211 return num_duplicates_removed;
218template <
bool stable_sort>
220 std::vector<int>* cycle_nodes)
const {
221 const int num_nodes = adjacency_lists_.size();
222 cycle_nodes->clear();
227 std::vector<bool> no_cycle_reachable_from(num_nodes,
false);
233 std::size_t adj_list_index;
234 explicit DfsState(
int _node) : node(_node), adj_list_index(0) {}
236 std::vector<DfsState> dfs_stack;
237 std::vector<bool> in_cur_stack(num_nodes,
false);
238 for (
int start_node = 0; start_node < num_nodes; ++start_node) {
239 if (no_cycle_reachable_from[start_node]) {
243 dfs_stack.push_back(DfsState(start_node));
244 in_cur_stack[start_node] =
true;
245 while (!dfs_stack.empty()) {
246 DfsState* cur_state = &dfs_stack.back();
247 if (cur_state->adj_list_index >=
248 adjacency_lists_[cur_state->node].size()) {
249 no_cycle_reachable_from[cur_state->node] =
true;
250 in_cur_stack[cur_state->node] =
false;
251 dfs_stack.pop_back();
257 adjacency_lists_[cur_state->node][cur_state->adj_list_index];
258 ++(cur_state->adj_list_index);
259 if (no_cycle_reachable_from[child]) {
262 if (in_cur_stack[child]) {
265 cycle_nodes->push_back(dfs_stack.back().node);
266 if (dfs_stack.back().node == child) {
267 std::reverse(cycle_nodes->begin(), cycle_nodes->end());
270 dfs_stack.pop_back();
274 dfs_stack.push_back(DfsState(child));
275 in_cur_stack[child] =
true;
291 int num_nodes,
const std::vector<std::pair<int, int>>& arcs) {
292 std::vector<int> cycle;
297 for (
const auto& arc : arcs) {
298 sorter.
AddEdge(arc.first, arc.second);
#define CHECK_GE(val1, val2)
#define DCHECK(condition)
#define VLOG(verboselevel)
void ExtractCycle(std::vector< int > *cycle_nodes) const
void AddEdge(int from, int to)
void AddNode(int node_index)
std::vector< int > AdjacencyList
static const int kLazyDuplicateDetectionSizeThreshold
std::vector< int > FindCycleInDenseIntGraph(int num_nodes, const std::vector< std::pair< int, int > > &arcs)