<commit_before>///
/// Tests `TarjanSCC`
///

use crate::mock_graph::arbitrary::{ArbVertexIn, ArbConnectedGraph};
use graphene::core::{Directed, Graph};
use graphene::algo::TarjanSCC;
use crate::mock_graph::utilities::unordered_equivalent_lists_equal;

///
/// Tests that if the graph is made up of a single component, it is found.
///
#[quickcheck]
fn finds_single_component(ArbVertexIn(graph, v): ArbVertexIn<ArbConnectedGraph<Directed>>)
	-> bool
{
	let sccs = TarjanSCC::new(&graph.0, v).collect::<Vec<_>>();
	
	sccs.len() == 1 &&
		unordered_equivalent_lists_equal( &sccs[0].all_vertices().collect(),
										  &graph.0.all_vertices().collect())
}


<commit_msg>Tested TarjanSCC.<commit_after>///
/// Tests `TarjanSCC`: Tarjan's algorithm for finding strongly connected components.
///

use graphene::{
	algo::{TarjanSCC},
	core::{
		Directed, Graph, Constrainer,
		constraint::{ConnectedGraph, Subgraph},
	},
};
use crate::mock_graph::{
	MockGraph,
	arbitrary::{ArbVertexIn},
};

///
/// Tests that no produced SCC is empty
///
#[quickcheck]
fn produces_non_empty_components(ArbVertexIn(graph, v): ArbVertexIn<MockGraph<Directed>>) -> bool
{
	for scc in TarjanSCC::new(&graph, v) {
		if scc.all_vertices().count() == 0 {
			return false;
		}
	}
	true
}

///
/// Tests that any SCC returned is actually strongly connected.
///
#[quickcheck]
fn produces_connected_components(ArbVertexIn(graph, v): ArbVertexIn<MockGraph<Directed>>) -> bool
{
	for scc in TarjanSCC::new(&graph, v) {
		if ConnectedGraph::constrain_single(scc).is_err() {
			return false
		}
	}
	true
}

///
/// Tests that for any SCC pair produced, they are not strongly connected.
///
#[quickcheck]
fn produces_disconnected_components(ArbVertexIn(graph, v): ArbVertexIn<MockGraph<Directed>>) -> bool
{
	let sccs = TarjanSCC::new(&graph, v).collect::<Vec<_>>();
	let mut scc_iter = sccs.iter();
	
	while let Some(scc) = scc_iter.next() {
		for scc2 in scc_iter.clone() {
			if scc.reaches(scc2).is_some() {
				if scc2.reaches(scc).is_some() {
					return false;
				}
			}
		}
	}
	true
}

///
/// Tests that all vertices are put inside some produced SCC.
///
#[quickcheck]
fn produces_all_vertices(ArbVertexIn(graph, v): ArbVertexIn<MockGraph<Directed>>) -> bool
{
	// We simply count the vertices since we have another test
	// for checking that no vertex is reused
	let mut vertex_count = 0;
	for scc in TarjanSCC::new(&graph, v) {
		vertex_count += scc.all_vertices().count();
	}
	vertex_count == graph.all_vertices().count()
}

///
/// Tests that all vertices in the components are from the original graph.
///
#[quickcheck]
fn produces_only_valid_vertices(ArbVertexIn(graph, v): ArbVertexIn<MockGraph<Directed>>) -> bool
{
	for scc in TarjanSCC::new(&graph, v) {
		for v in scc.all_vertices() {
			if !graph.contains_vertex(v) {
				return false;
			}
		}
	}
	true
}

///
/// Tests that no two produced SCCs share any vertices
///
#[quickcheck]
fn produces_vertex_disjoint_components(ArbVertexIn(graph, v): ArbVertexIn<MockGraph<Directed>>)
	-> bool
{
	let sccs = TarjanSCC::new(&graph, v).collect::<Vec<_>>();
	let mut scc_iter = sccs.iter();
	
	while let Some(scc) = scc_iter.next() {
		for scc2 in scc_iter.clone() {
			for v in scc.all_vertices() {
				if scc2.contains_vertex(v) {
					return false;
				}
			}
		}
	}
	true
}

///
/// Tests that the SCCs are produced in some reverse topological order.
/// This is a guarantee of Tarjan's algorithm, which means if we don't do that,
/// we are not implementing it correctly.
///
#[quickcheck]
fn produces_reverse_topological_ordering(ArbVertexIn(graph, v): ArbVertexIn<MockGraph<Directed>>) -> bool
{
	// To test the ordering, we simply check that an earlier-produced component can't reach any
	// later one.
	let sccs = TarjanSCC::new(&graph, v).collect::<Vec<_>>();
	let mut scc_iter = sccs.iter();
	
	while let Some(scc) = scc_iter.next() {
		for scc2 in scc_iter.clone() {
			if scc.reaches(scc2).is_some() {
				return false;
			}
		}
	}
	true
}
{'fraction_non_alphanumeric': 0.15268709191361124, 'fraction_numerical': 0.0032646911099949772, 'mean_word_length': 4.0226986128625475, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5253225', 'n_tokens_mistral': 1538, 'n_tokens_neox': 1445, 'n_words': 349}