Function LongestPathTree

src/algorithms/longest_path.c:83–98

Finds the longest path in an acyclic graph.

// Finds the longest path in an acyclic graph.
QGNode *LongestPathTree(const QueryGraph *g, int *level) {
	int l = BFS_LOWEST_LEVEL;
	QGNode **leafs = BFS(g->nodes[0], &l);
	QGNode *leaf = leafs[0];
	array_free(leafs);

	l = BFS_LOWEST_LEVEL;
	leafs = BFS(leaf, &l);

	ASSERT(array_len(leafs) > 0 && l >= 0);
	QGNode *n = leafs[0];
	array_free(leafs);

	*level = l;
	return n;
}