Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

58
LINES

< > BotCompany Repo | #1030919 // BreadthFirstPathFinder_withLinkType [OK]

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (3388L/19K).

// 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);
  }
}

Author comment

Began life as a copy of #1030913

download  show line numbers  debug dex  old transpilations   

Travelled to 4 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, vouqrxazstgt

No comments. add comment

Snippet ID: #1030919
Snippet name: BreadthFirstPathFinder_withLinkType [OK]
Eternal ID of this version: #1030919/11
Text MD5: dc284d7f93830e632d208dd9f6c71bda
Transpilation MD5: d348672b39afc4ebe3b0371594064aef
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2021-04-10 19:23:55
Source code size: 1533 bytes / 58 lines
Pitched / IR pitched: No / No
Views / Downloads: 142 / 341
Version history: 10 change(s)
Referenced in: [show references]