Translating java DFS algorithm code to Dart

Question

I've been doing some research to find a suitable algorithm for suggesting friends. I came across DFS, but I've never implemented it in Dart before. Could someone please help me t translate it into Dart? Below is the java code:

public class SuggestFriendsDFS<T> {

    private HashMap<T, ArrayList<T>> adj = new HashMap<>(); //graph
    private List<Set<T>> groups = new ArrayList<>();


    public void addFriendship(T src, T dest) {
        adj.putIfAbsent(src, new ArrayList<T>());
        adj.get(src).add(dest);
        adj.putIfAbsent(dest, new ArrayList<T>());
        adj.get(dest).add(src);
    }


    //V is total number of people, E is number of connections
    private void findGroups() {
        Map<T, Boolean> visited = new HashMap<>();
        for (T t: adj.keySet())
            visited.put(t, false);
        for (T t:adj.keySet()) {
            if (!visited.get(t)) {
                Set<T> group = new HashSet<>();
                dfs(t, visited, group);
                groups.add(group);
            }
        }
    }

    //DFS + memoization
    private void dfs(T v, Map<T, Boolean> visited, Set<T> group ) {
        visited.put(v,true);
        group.add(v);
        for (T x : adj.get(v)) {
            if (!visited.get(x))
                dfs(x, visited, group);
        }
    }


    public Set<T> getSuggestedFriends (T a) {
        if (groups.isEmpty())
            findGroups();
        Set<T> res = new HashSet<>();
        for (Set<T> t : groups) {
            if (t.contains(a)) {
                res = t;
                break;
            }
        }
        if (res.size() > 0)
            res.remove(a);
        return res;
    }
}

I'm aware it's too much to ask, but any help will be much appreciated as I tried to translate it and ended up getting loads of errors. Thanks in advance!(: For reference, this is where I found the explanation for the java code.

Answer 1

I tried https://sma.github.io/stuff/java2dartweb/java2dartweb.html that does automatic Java to Dart conversion but it doesn't work well as soon as the code is a bit complex.

See the full conversion below, you can try it in Dartpad

import 'dart:collection';

class SuggestFriendsDFS<T> {
  final HashMap<T, List<T>> _adj = HashMap(); //graph
  final List<Set<T>> groups = [];

  //Time O(1), Space O(1)
  void addFriendship(T src, T dest) {
    _adj.putIfAbsent(src, () => <T>[]);
    _adj[src]!.add(dest);
    _adj.putIfAbsent(dest, () => <T>[]);
    _adj[dest]!.add(src);
  }

  //DFS wrapper, Time O(V+E), Space O(V)
  //V is total number of people, E is number of connections
  void findGroups() {
    Map<T, bool> visited = HashMap();

    for (T t in _adj.keys) {
      visited[t] = false;
    }

    for (T t in _adj.keys) {
      if (visited[t] == false) {
        Set<T> group = HashSet();
        _dfs(t, visited, group);
        groups.add(group);
      }
    }
  }

  //DFS + memoization, Time O(V+E), Space O(V)
  void _dfs(T v, Map<T, bool> visited, Set<T> group) {
    visited[v] = true;
    group.add(v);
    for (T x in _adj[v] ?? []) {
      if ((visited[x] ?? true) == false) _dfs(x, visited, group);
    }
  }

  //Time O(V+E), Space O(V)
  Set<T> getSuggestedFriends(T a) {
    if (groups.isEmpty) findGroups();

    var result = groups.firstWhere((element) => element.contains(a),
        orElse: () => <T>{});

    if (result.isNotEmpty) result.remove(a);

    return result;
  }
}

void main() {
  SuggestFriendsDFS<String> g = SuggestFriendsDFS();
  g.addFriendship("Ashley", "Christopher");
  g.addFriendship("Ashley", "Emily");
  g.addFriendship("Ashley", "Joshua");
  g.addFriendship("Bart", "Lisa");
  g.addFriendship("Bart", "Matthew");
  g.addFriendship("Christopher", "Andrew");
  g.addFriendship("Emily", "Joshua");
  g.addFriendship("Jacob", "Christopher");
  g.addFriendship("Jessica", "Ashley");
  g.addFriendship("JorEl", "Zod");
  g.addFriendship("KalEl", "JorEl");
  g.addFriendship("Kyle", "Lex");
  g.addFriendship("Kyle", "Zod");
  g.addFriendship("Lisa", "Marge");
  g.addFriendship("Matthew", "Lisa");
  g.addFriendship("Michael", "Christopher");
  g.addFriendship("Michael", "Joshua");
  g.addFriendship("Michael", "Jessica");
  g.addFriendship("Samantha", "Matthew");
  g.addFriendship("Samantha", "Tyler");
  g.addFriendship("Sarah", "Andrew");
  g.addFriendship("Sarah", "Christopher");
  g.addFriendship("Sarah", "Emily");
  g.addFriendship("Tyler", "Kyle");
  g.addFriendship("Stuart", "Jacob");

  g.findGroups();
  print(g.groups);

  String name = "Andrew";
  
  print("Suggestion friends of " +
      name +
      ": " +
      g.getSuggestedFriends(name).toString());
}