Does anyone know the most optimal general purpose algorithm for checking if two points on a graph are connected? I believe a* is the best for finding the shortest path but is is the best for just getting a bool of if there is a path at all?

If they are not connected, they are not on the same graph.

Try using some algorithm to find points that are connected (modified dijkstra maybe) and then just check whether two points are in the same connected set.

What I mean is that you can scan the graph beforehand and cache the result in some hash maps and then just check whether two objects are in the same map, which should be very fast.

@iiii but is there an optimal solution for a dynamically changing graph?

@skyjoe66 depends on the kinds of the changes

@iiii ok, then ill probably just go with a*, i have to implement it for a different system anyways

I'd start at one point, put it into a "scan list" and iterate at follows:

1) If your second point is in the "scan list", abort - they are connected. If the "scan list" is empty, also abort - the points are not connected.
2) Otherwise, add all points in the "scan list" into the "included list"
3) Put all neighbours of points in the "scan list" into a "new scan list" if said neighbours aren't already in the "included list"
4) Replace the "scan list" with the "new scan list"
5) Goto 1).

@Fast-Nop sounds like a breadth first search 🤔

@iiii It is, but for doing a depth first search, you would need guidance of where to deepen, and that will not be general purpose anymore.

Also, it is not strictly breadth first because that would instead be "iterate from the first neighbour to its first neighbour" style. So it is a breadth first in each node, but depth first overall.

As a side effect, you will find how many hops you need to get from A to B - it's the number of started iterations.

@Fast-Nop yeah, I know that depth first is not very practical on a graph. And that scan was what I've had in mind for the initial sweep

lol.
how bout: you turn the image into an rgbx values array, then simply access it whenever you want to check if a pixel is part of or not.

if rgb values are = to graph line's values bob's your uncle.

you got:
one dereferencing
one condition
overhead is pretty much loading the file. its gonna be hard to beat that.

@bad-frog WTF? Image? It's about a graph, not an image.

@Fast-Nop i find that the question makes sense only if we're talking about an image.
otherwise its a collection of coordiantes and can be solved by math, if not even by checking if an element is in an array, like @iiii wrote initially...

@bad-frog Example: You have two street crossings, and there's a lot of construction working going on in the city.

Question: if you are at crossing A, can you drive to crossing B if you are in a large 40t truck?

Or: you have a computer network and have to decide whether to take out a certain routing node. If you do that, will computer A still be able to communicate with computer B?

@Fast-Nop fuck just noticed. its not about these graphs that youre talking. my bad.

for my defence english is not my first language:(

I remember studying how routers deduce the fastest route to another endpoint. It is rather efficient, change resilient and could maybe be useful in this case. I'm currently drinking though so I won't be able to find it before at least tomorrow, so I'll check tomorrow if it can be applied to your use case.

@pipe Dijkstra / modified Dijkstra was already mentioned ;)

https://en.m.wikipedia.org/wiki/...

https://en.m.wikipedia.org/wiki/...

A* means usually modified Dijkstra

(Just adding so others can maybe follow the discussion ;) )

@IntrusionCM Oh, that was just Dijkstra ? I'm disappointed now. Sorry for talking for nothing then 😅.

@pipe Depends.

There are countless algorithms in networking, but except for the older which depend on Bellman Ford, most are built upon Djikstra.

The "fun" part is that there are more names and RFCs than one can remember. XD

@IntrusionCM I'm not sure whether Dijkstra would be the optimum here, given that the question isn't about the shortest connection as per the connection weights, but just whether a connection exists at all.

@Fast-Nop Yes. I was just adding reference data not an actual solution ;)

As per Wikipedia :
"the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete."
So I'm not sure there's even some efficient solution then. So you might as well use some variation of Dijkstra.
Unless your graph is acyclic, because "However, it has a linear time solution for directed acyclic graphs", also per Wikipedia.

@Fast-Nop if you assume all weights being 0 then dijkstra will work as intended even without any modifications as any first path will be the shortest already.

@pipe it's not about longest path but just mere connectivity. Longest path is indeed a hard problem

@iiii Yes, but I was looking at the "decision version of the problem, which asks whether a path exists of at least some given length" part.

@pipe oh, in that case it is the longest path problem essentially.