Find all paths in graph, given by task ids.

all_paths_in_graph.v

import os
import time

struct Seeker {
mut:
	graph         map[int][]int
	already_found map[int][][]int
	all_solutions [][]int
}

fn main() {
	mut seeker := Seeker{}
	lines := os.read_lines(os.resource_abs_path('example.txt'))?
	for i := 1; i < lines.len; i++ {
		line := lines[i]
		aline := line.split('\t')
		edge_from, edge_to := aline[0].int(), aline[1].int()
		// println('> i: $i | from: $edge_from to: $edge_to')
		mut existing := seeker.graph[edge_from] or { [] }
		if edge_to !in existing {
			existing << edge_to
			seeker.graph[edge_from] = existing
		}
	}
	mut n := 0
	for from_task_id, next_task_ids in seeker.graph {
		n++
		seeker.find_solutions_for_task(from_task_id, next_task_ids, n)
	}
	for idx, x in seeker.all_solutions#[0..10] {
		eprintln('first 10, idx: $idx: $x')
	}
	for idx, x in seeker.all_solutions#[-10..] {
		eprintln(' last 10, idx: $idx: $x')
	}
}

fn (mut seeker Seeker) find_solutions_for_task(from_task_id int, next_task_ids []int, n int) {
	mut solutions := [][]int{}
	for next_task_id in next_task_ids {
		seeker.chase_paths(n, mut solutions, [from_task_id], next_task_id)
	}
	seeker.already_found[from_task_id] = solutions
	seeker.all_solutions << solutions
	eprintln('>> n: ${n:6} | all_solutions.len: ${seeker.all_solutions.len:12} | found ${solutions.len:7} new solutions for task: ${from_task_id:10}')
}

fn (mut seeker Seeker) chase_paths(n int, mut solutions [][]int, path []int, current_task_id int) {
	if found := seeker.already_found[current_task_id] {
		// eprintln('> already found: $found.len continuations for $current_task_id')
		for x in found {
			mut tmp := path.clone()
			tmp << x
			solutions << tmp
		}
		return
	}

	mut tmp := path.clone()
	tmp << current_task_id
	if next := seeker.graph[current_task_id] {
		for x in next {
			if x in tmp {
				continue
			}
			seeker.chase_paths(n, mut solutions, tmp, x)
		}
	} else {
		solutions << tmp
		if solutions.len % 1000000 == 0 {
			eprintln('>>>>>> n: $n | solutions: | ${solutions.len:14} at $time.now().format_ss_milli()')
			eprintln('         tmp: $tmp')
		}
	}
}