BreadthFirstPathFinder - breadth-first search along virtual structure, collecting links [OK] [1030913]

< > BotCompany Repo | #1030913 // BreadthFirstPathFinder - breadth-first search along virtual structure, collecting links [OK]

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

sclass BreadthFirstPathFinder<A> implements Steppable {
  // must set
  IF1<A, Cl<A>> getChildren;
  
  // graph representation - filled during exploration
  new MultiMap<A> links;
  
  // node queue (temporary)
  new LinkedList<A> queue;
  
  *() {}
  *(IF1<A, Cl<A>> *getChildren) {}
  *(IF1<A, Cl<A>> *getChildren, A startNode) { add(startNode); }
  
  void add(A a, A prev default null) {
    if (!links.containsKey(a)) {
      links.put(a, prev);
      queue.add(a);
    }
  }
  
  public bool step() {
    ping();
    if (empty(queue)) false;
    A a = popFirst(queue);
    fOr (A b : getChildren.get(a))
      add(b, a);
    true;
  }
  
  bool nodeReached(A a) {
    ret links.containsKey(a);
  }
  
  Cl<A> getBackLinks(A a) {
    ret links.get(a);
  }
  
  L<A> examplePath(A start, A dest) {
    new L<A> path;
    A node = dest;
    path.add(node);
    do {
      if (node == null) null; // no path found
      node = first(getBackLinks(node));
      path.add(node);
    } while (node != start);
    ret reversed(path);
  }
}

Author comment

Began life as a copy of #1021566

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

Snippet ID:

#1030913

Snippet name:

BreadthFirstPathFinder - breadth-first search along virtual structure, collecting links [OK]

Eternal ID of this version:

#1030913/15

Text MD5:

31151c97a27f9ce254ca61184aac2a04

Transpilation MD5:

8eb4c2f55213f214e172820f0d3b7c71

Author:

stefan

Category:

javax

Type:

JavaX fragment (include)

Public (visible to everyone):

Yes

Archived (hidden from active list):

Created/modified:

2022-03-21 23:29:32

Source code size:

1086 bytes / 50 lines

Pitched / IR pitched:

No / No

Views / Downloads:

226 / 485

Version history:

14 change(s)

Referenced in:

[show references]

1	sclass BreadthFirstPathFinder<A> implements Steppable {
2	// must set
3	IF1<A, Cl<A>> getChildren;
4
5	// graph representation - filled during exploration
6	new MultiMap<A> links;
7
8	// node queue (temporary)
9	new LinkedList<A> queue;
10
11	*() {}
12	(IF1<A, Cl<A>> getChildren) {}
13	(IF1<A, Cl<A>> getChildren, A startNode) { add(startNode); }
14
15	void add(A a, A prev default null) {
16	if (!links.containsKey(a)) {
17	links.put(a, prev);
18	queue.add(a);
19	}
20	}
21
22	public bool step() {
23	ping();
24	if (empty(queue)) false;
25	A a = popFirst(queue);
26	fOr (A b : getChildren.get(a))
27	add(b, a);
28	true;
29	}
30
31	bool nodeReached(A a) {
32	ret links.containsKey(a);
33	}
34
35	Cl<A> getBackLinks(A a) {
36	ret links.get(a);
37	}
38
39	L<A> examplePath(A start, A dest) {
40	new L<A> path;
41	A node = dest;
42	path.add(node);
43	do {
44	if (node == null) null; // no path found
45	node = first(getBackLinks(node));
46	path.add(node);
47	} while (node != start);
48	ret reversed(path);
49	}
50	}