Has-Path problem for both Unidirectional and Bidirectional Graphs, dart implementation.

graph-has-path-problem.dart

/// A HAS-PATH problem, Given source and destination
/// find if there exist any path between them in the
/// acyclic/Directed/Unidirectional Graph,
/// also cyclic/undirected/bidirectional graph.

const graphDirected = {
  "f": ["g", "i"],
  "g": ["h"],
  "h": [],
  "i": ["g", "k"],
  "j": ["i"],
  "k": [],
};

const edgesUndirectedGraph = [
  ['i', 'j'],
  ['k', 'i'],
  ['m', 'k'],
  ['k', 'l'],
  ['o', 'n'],
];

void main() {
  print("Path Exist Directed : " + doesPathExist("k", "h").toString());
  print(
      "Path Exist UnDirected : " + doesPathExistUD("k", "o", Set()).toString());
}

/// Undirected

/// Creating a graph from edges
final graphUD = generateUDGraph();

bool doesPathExistUD(String src, String des, Set set) {
  if (src == des) {
    return true;
  }
  if (set.contains(src)) {
    return false;
  }
  set.add(src);

  final edge = graphUD[src]!;
  for (final neighbor in edge) {
    if (doesPathExistUD(neighbor, des, set)) {
      return true;
    }
  }
  return false;
}

/// We can remove internal loop here as relation can only contain 2 values
Map<String, List<String>> generateUDGraph() {
  final Map<String, List<String>> map = {};
  for (final relation in edgesUndirectedGraph) {
    for (final key in relation) {
      final allVerts = map[key];
      final addable = relation.toList();
      addable.removeWhere((element) => element == key);
      if (allVerts == null) {
        map[key] = addable;
      } else {
        allVerts.addAll(addable);
        map[key] = allVerts;
      }
    }
  }
  return map;
}

/// Directed
bool doesPathExist(String src, String des) {
  if (src == des) {
    return true;
  }

  final branch = graphDirected[src]!.toList();

  for (final item in branch) {
    if (doesPathExist(item, des)) {
      return true;
    } else {
      continue;
    }
  }

  return false;
}