/*-
 * Copyright (c) 2015 Taylor R. Campbell
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>

#include "scc.h"

/*
 * Tarjan's algorithm for computing strongly connected components in a
 * directed graph in topological order, published in
 *
 * Robert Tarjan, `Depth-First Search and Linear Graph Algorithms',
 * SIAM Journal on Computing 1 (1972), pp. 146--160.
 * http://dx.doi.org/10.1137/0201010
 */

#define	MIN(A, B)	((A) < (B)? (A) : (B))

void
strongly_connected_components(void *cookie,
    struct scc_vertex *(*next_vertex)(void *, struct scc_vertex *),
    struct scc_edge *(*next_edge)(void *, struct scc_vertex *,
	struct scc_edge *),
    struct scc_vertex *(*edge_predecessor)(void *, struct scc_edge *),
    struct scc_vertex *(*edge_successor)(void *, struct scc_edge *),
    void (*emit)(void *, struct scc_vertex *))
{
	struct scc_vertex *V, *V0, *V1;
	struct scc_edge *E;
	size_t index = 1;
	struct scc_vertex *scc_stack = NULL;

	V = NULL;
	while ((V = (*next_vertex)(cookie, V)) != NULL) {
		V->sv_cycle = NULL;
		V->sv_scc_next = NULL;
		V->sv_dfs_edge = NULL;
		V->sv_index = 0;
		V->sv_lowlink = ~(size_t)0;
		V->sv_scc_stuck = false;
	}
	V = NULL;
	while ((V = (*next_vertex)(cookie, V)) != NULL) {
		if (V->sv_index)
			continue;

		/* enter connect(V) */
connect:	V->sv_index = index;
		V->sv_lowlink = index;
		index++;
		V->sv_scc_next = scc_stack;
		scc_stack = V;
		V->sv_scc_stuck = true;

		E = NULL;
		while ((E = (*next_edge)(cookie, V, E)) != NULL) {
			V1 = (*edge_successor)(cookie, E);
			if (V1->sv_index == 0) {
				assert(V1->sv_dfs_edge == NULL);
				V1->sv_dfs_edge = E;
				V = V1;
				/* recursive connect(V1) */
				goto connect;
popedge:			V->sv_lowlink = MIN(V->sv_lowlink,
				    V1->sv_lowlink);
			} else if (V1->sv_scc_stuck) {
				V->sv_lowlink = MIN(V->sv_lowlink,
				    V1->sv_index);
			}
		}

		assert(V->sv_scc_stuck);
		if (V->sv_lowlink == V->sv_index) {
			V0 = V;
			assert(scc_stack != NULL);
			while (scc_stack != NULL) {
				V1 = scc_stack;
				scc_stack = V1->sv_scc_next;
				V1->sv_scc_next = NULL;
				V1->sv_scc_stuck = false;
				V0->sv_cycle = V1;
				if (V1 == V)
					break;
				V0 = V1;
			}
			assert(V1 == V);
			(*emit)(cookie, V);
		}

		/* return from connect */
		if (V->sv_dfs_edge) {
			V1 = V;
			E = V1->sv_dfs_edge;
			V1->sv_dfs_edge = NULL;
			V = (*edge_predecessor)(cookie, E);
			goto popedge;
		}
	}
}