// A is node type, B is link type

sclass BreadthFirstPathFinder_withLinkType<A, B> implements Steppable {

  new LinkedList<A> queue;

  new MultiMap<A, Pair<A, B>> links; // backwards (child -> parent)

  IF1<A, Cl<Pair<A, B>>> getChildren; // must set

  *() {}

  *(IF1<A, Cl<Pair<A, B>>> *getChildren) {}

  *(IF1<A, Cl<Pair<A, B>>> *getChildren, A startNode) { add(startNode); }

  void add(A a) {

    add(a, null, null);

  }

  void add(A a, A prev, B linkType) {

    if (!links.containsKey(a)) {

      links.put(a, prev == null ?: pair(prev, linkType));

      queue.add(a);

    }

  }

  public bool step() {

    ping();

    if (empty(queue)) false;

    A a = popFirst(queue);

    fOr (Pair<A, B> link : getChildren.get(a))

      add(link.a, a, link.b);

    true;

  }

  bool nodeReached(A a) {

    ret links.containsKey(a);

  }

  Cl<A> getBackLinks(A a) {

    ret pairsA(links.get(a));

  }

  Cl<Pair<A, B>> getBackLinksWithTypes(A a) {

    ret links.get(a);

  }

  LPair<A, B> examplePathWithTypes(A start, A dest) {

    new LPair<A, B> path;

    A node = dest;

    path.add(pair(node, null)); // dest node has no link type

    while ping (node != start) {

      Pair<A, B> link = first(getBackLinksWithTypes(node));

      ifdef BreadthFirstPathFinder_debug

        printVars_str examplePathWithTypes(+node, +link);

      endifdef

      if (link == null) null; // no path found

      path.add(link);

      node = link.a;

    }

    ret reversed(path);

  }

}