The dart_types from osaxma

The transitiveReduction algorithm is inaccurate and slow

Currently we generate the matrix as follow:

Lines 63 to 82 in 9ff7f0c

 static Map<DartType, List<DartType>> _createTypeMatrix( 

 List<DartType> types, 

 TypeSystem typeSystem, 

 ) { 

 logger.trace('_createTypeMatrix start (types length: ${types.length})'); 

 final matrix = <DartType, List<DartType> /* subtypes */ >{}; 

 for (var t in types) { 

 final edges = types 

 .where((element) => element != t && typeSystem.isSubtypeOf(element, t)) 

 .toSet() 

 .toList(); 

 matrix[t] = edges; 

 } 

 logger.trace('_createTypeMatrix end: (matrix length = ${matrix.length})'); 

 return matrix; 

 }

Then we generate the transitive reduction of the graph as follow:

dart_types/lib/src/util.dart

Lines 44 to 65 in 5654ae7

 Map<T, Set<T>> transitiveReduction<T>(Map<T, Iterable<T>> graph) { 

 logger.trace('transitiveReduction start (graph length: ${graph.length})'); 

 var result = <T, Set<T>>{}; 

 graph.forEach((vertex, edges) { 

 result[vertex] = Set<T>.from(edges.where((element) => element != vertex)); 

 }); 

 // Lists are faster to iterate than maps, so we create a list since we're 

 // iterating repeatedly. 

 var keys = graph.keys.toList(); 

 for (var vertex1 in keys) { 

 for (var vertex2 in keys) { 

 for (var vertex3 in keys) { 

 if (result[vertex1]!.contains(vertex2) && result[vertex2]!.contains(vertex3)) { 

 result[vertex1]!.remove(vertex3); 

 } 

 } 

 } 

 } 

 logger.trace('transitiveReduction end: (result length = ${result.length})'); 

 return result; 

 }

The transitiveReduction has two issues:

It doesn't remove edges accurately when there are more than two edges in a path
- e.g. A -> B -> C -> D; A -> C; A-> D -- it won't remove A->D here.
- I think because we sort all the types by subtypes, we reduced this issue
It's slow! Running the all_types.dart example without selecting a type or applying filters, won't even complete on my machine before the laptop gets extremely hot and the fan gets quite noisy.

I think there should be a better way to generate the transitive reduction of the graph directly and more efficiently.

osaxma / dart_types Goto Github PK

dart_types's People

Contributors

Stargazers

Watchers

dart_types's Issues

The transitiveReduction algorithm is inaccurate and slow

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent

	static Map<DartType, List<DartType>> _createTypeMatrix(
	List<DartType> types,
	TypeSystem typeSystem,
	) {
	logger.trace('_createTypeMatrix start (types length: ${types.length})');

	final matrix = <DartType, List<DartType> /* subtypes */ >{};

	for (var t in types) {
	final edges = types
	.where((element) => element != t && typeSystem.isSubtypeOf(element, t))
	.toSet()
	.toList();
	matrix[t] = edges;
	}

	logger.trace('_createTypeMatrix end: (matrix length = ${matrix.length})');

	return matrix;
	}

	Map<T, Set<T>> transitiveReduction<T>(Map<T, Iterable<T>> graph) {
	logger.trace('transitiveReduction start (graph length: ${graph.length})');
	var result = <T, Set<T>>{};
	graph.forEach((vertex, edges) {
	result[vertex] = Set<T>.from(edges.where((element) => element != vertex));
	});

	// Lists are faster to iterate than maps, so we create a list since we're
	// iterating repeatedly.
	var keys = graph.keys.toList();
	for (var vertex1 in keys) {
	for (var vertex2 in keys) {
	for (var vertex3 in keys) {
	if (result[vertex1]!.contains(vertex2) && result[vertex2]!.contains(vertex3)) {
	result[vertex1]!.remove(vertex3);
	}
	}
	}
	}
	logger.trace('transitiveReduction end: (result length = ${result.length})');
	return result;
	}