Reputation
2,371
Next tag badge:
5/100 score
1/20 answers
Badges
3 14 37
Newest
 Yearling
Impact
~95k people reached

1d
awarded  Yearling
Mar
20
awarded  Curious
Sep
9
awarded  Nice Question
Sep
1
awarded  Yearling
Aug
24
answered How can I find the shortest path between two subgraphs of a larger graph?
Aug
24
comment How can I find the shortest path between two subgraphs of a larger graph?
@SJuan76 that's a good call, on making all of the nodes in one subgraph starting nodes. I don't think the other half works, though; if you stop as soon as you visit one node in the other subgraph, you may still miss out on a better path to a different node within that second subgraph.
Aug
23
comment How can I find the shortest path between two subgraphs of a larger graph?
@ratchetfreak the 0-cost idea actually is the one I was thinking about. My current implementation is... all kinds of weird. (Not blaming you for that, of course. But it does put me in the unpleasant spot of wondering if refactoring is worth it.)
Aug
23
comment How can I find the shortest path between two subgraphs of a larger graph?
@ratchetfreak ohhh, I see what you (both) mean now. Temporarily replace each subgraph with a fake node, and reassign all edges that previously touched each subgraph to touch the corresponding fake node instead. Yeah, that'll do it. Hrm, gonna be a pain to actually implement, though.
Aug
23
revised How can I find the shortest path between two subgraphs of a larger graph?
added illustration to clear up possible misunderstandings
Aug
23
comment How can I find the shortest path between two subgraphs of a larger graph?
It seems like you have the same idea as ratchet freak did in his comment under my question, which makes me think maybe I did a poor job of writing the question. The distance from one node in subgraph A to an arbitrary node N outside of subgraph A may be very different than the distance from some other node in subgraph A to node N. Thus, it's not okay to simplify away the entire subgraph in the way you suggest (or, I'm misunderstanding your approach).
Aug
23
comment How can I find the shortest path between two subgraphs of a larger graph?
It's not reasonable to simplify a subgraph that way, though; there may be multiple edges leading out of a given subgraph, with various different weights, from multiple different nodes. Using a single imaginary node as the sole entry/exit point doesn't account for that.
Aug
23
comment How can I find the shortest path between two subgraphs of a larger graph?
@ratchetfreak I'm not understanding how that would help, could you give a little more detail?
Aug
23
asked How can I find the shortest path between two subgraphs of a larger graph?
Aug
21
awarded  Nice Question
Aug
18
comment How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear
Whoops, disregard my previous comment, I misread your answer a bit. This is basically what I'm doing, although I failed to take advantage of existing graph libraries, because I foolishly didn't think to see if any existed.
Aug
15
comment How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear
I'm not really seeing how that's going to help here.
Aug
15
asked How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear
Apr
16
awarded  Popular Question
Jan
31
awarded  Popular Question
Oct
2
awarded  Nice Question