From 799904050bdb222fd359e3c5b7e0728f95c48b36 Mon Sep 17 00:00:00 2001
From: Florian Deljarry <deljarry.florian@gmail.com>
Date: Mon, 26 Aug 2019 10:56:13 -0400
Subject: [PATCH] digraph: Add feature to get all successors and predecessors

Signed-off-by: Florian Deljarry <deljarry.florian@gmail.com>
---
 lib/graph/digraph.nit |   74 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 74 insertions(+)

diff --git a/lib/graph/digraph.nit b/lib/graph/digraph.nit
index e574dc4..fdbf351 100644
--- a/lib/graph/digraph.nit
+++ b/lib/graph/digraph.nit
@@ -862,6 +862,79 @@ abstract class MutableDigraph[V: Object]
 		end
 		return path
 	end
+
+	# Cache of all predecessors for each vertex.
+	# This attribute are lazy to compute the list use `get_all_predecessors` for each needed vertexe.
+	# Warning the cache must be invalidated after `add_arc`
+	private var cache_all_predecessors = new HashMap[V, Set[V]]
+
+	# Cache of all successors for each vertex.
+	# This attribute are lazy to compute the list use `get_all_successors` for each needed vertexe.
+	# Warning the cache must be invalidated after `add_arc`
+	private var cache_all_successors = new HashMap[V, Set[V]]
+
+	# Invalid all cache `cache_all_predecessors` and `cache_all_successors`
+	private fun invalidated_all_cache
+	do
+		if not cache_all_successors.is_empty then cache_all_successors = new HashMap[V, Set[V]]
+		if not cache_all_predecessors.is_empty then cache_all_predecessors = new HashMap[V, Set[V]]
+	end
+
+	# Returns the all predecessors of `u`.
+	#
+	# `u` is include in the returned collection
+	#
+	# Returns an empty Array is the `u` does not exist
+	# ~~~
+	# var g = new HashDigraph[Int]
+	# g.add_arc(1, 2)
+	# g.add_arc(2, 3)
+	# g.add_arc(3, 4)
+	# assert g.get_all_predecessors(4).has(4)
+	# assert g.get_all_predecessors(4).has(3)
+	# assert g.get_all_predecessors(4).has(2)
+	# assert g.get_all_predecessors(4).has(1)
+	# ~~~
+	fun get_all_predecessors(u: V): Array[V]
+	do
+		if not vertices.has(u) then return new Array[V]
+		if not cache_all_predecessors.has_key(u) then compute_all_link(u)
+		return cache_all_predecessors[u].clone.to_a
+	end
+
+	# Returns the all successors of `u`.
+	#
+	# `u` is include in the returned collection
+	#
+	# Returns an empty Array is the `u` does not exist
+	# ~~~
+	# var g = new HashDigraph[Int]
+	# g.add_arc(1, 2)
+	# g.add_arc(2, 3)
+	# g.add_arc(3, 4)
+	# assert g.get_all_successors(2).has(3)
+	# assert g.get_all_successors(2).has(4)
+	# assert g.get_all_successors(2).has(2)
+	# ~~~
+	fun get_all_successors(u: V): Array[V]
+	do
+		if not vertices.has(u) then return new Array[V]
+		if not cache_all_successors.has_key(u) then compute_all_link(u)
+		return cache_all_successors[u].clone.to_a
+	end
+
+	# Compute all succesors and all predecessors for the given `u`
+	# The result is stocked in `cache_all_predecessors` and `cache_all_predecessors`
+	private fun compute_all_link(u: V)
+	do
+		if not vertices.has(u) then return
+		if not cache_all_predecessors.has_key(u) then cache_all_predecessors[u] = new Set[V]
+		if not cache_all_successors.has_key(u) then cache_all_successors[u] = new Set[V]
+		for v in vertices do
+			if distance(v, u) != null then cache_all_predecessors[u].add(v)
+			if distance(u, v) != null then cache_all_successors[u].add(v)
+		end
+	end
 end
 # A directed graph represented by hash maps
 class HashDigraph[V: Object]
@@ -908,6 +981,7 @@ class HashDigraph[V: Object]
 		if not has_arc(u, v) then
 			incoming_vertices_map[v].add(u)
 			outgoing_vertices_map[u].add(v)
+			invalidated_all_cache
 			number_of_arcs += 1
 		end
 	end
-- 
1.7.9.5