Timeline for FindPath with required Edges
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 13, 2021 at 22:35 | comment | added | Ben Kalziqi | @JasonB. a guy can dream, right? 😅 Derek — thanks for the thought process outlined in your answer here. I think that it's likely the best we can do here, given that (as you correctly diagnose) this is a really nontrivial problem. | |
| Aug 12, 2021 at 21:25 | history | bounty ended | Ben Kalziqi | ||
| Aug 12, 2021 at 17:59 | comment | added | Jason B. |
@BenKalziqi - I believe you are right that FindPath could be written to filter out the paths while finding them, rather than returning them all and letting you filter them. But I do not think it is written that way currently.
|
|
| Aug 12, 2021 at 11:40 | comment | added | Teabelly |
Maybe FindHamiltonianPath[] could help?
|
|
| Aug 11, 2021 at 23:20 | history | edited | Derek H | CC BY-SA 4.0 |
expanded answer based on some poster comments
|
| Aug 11, 2021 at 22:42 | comment | added | Ben Kalziqi |
Hi Derek—I don't know the details of how FindPath is working internally, but it doesn't seem completely unreasonable (caveat: I know very little about graphs) that it could have a way eliminate paths which don't traverse the required edges (e.g., there are paths you could take which, before getting to the end, would "lock you out" of being able to traverse the requested edge). Even at worse, simply discarding the paths as they're searched/collected would reduce memory usage very significantly, right? It would be double important for combinatoric cases like this. I'll try out your suggestion.
|
|
| Aug 10, 2021 at 20:53 | history | answered | Derek H | CC BY-SA 4.0 |