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.

CodePudding user response：

You can try https://sma.github.io/stuff/java2dartweb/java2dartweb.html to help you translate the syntax, block by block.

Otherwise show us what you have translated and which error you get and someone may help you.

CodePudding user response：

Here's a quick convert, not tested but syntax error free:

import 'dart:collection';

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

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

  //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
  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.containsValue(x)) _dfs(x, visited, group);
    }
  }

  Set<T> getSuggestedFriends(T a) {
    if (_groups.isEmpty) _findGroups();
    Set<T> res = HashSet();
    for (Set<T> t in _groups) {
      if (t.contains(a)) {
        res = t;
        break;
      }
    }
    if (res.isNotEmpty) res.remove(a);
    return res;
  }
}