CodeWalrus

General => Tech, Science, IT discussion & News => Topic started by: Hayleia on November 09, 2016, 11:01:40 AM

Title: A graph problem (not necessarily math-heavy)
Post by: Hayleia on November 09, 2016, 11:01:40 AM
Well, I have a graph problem. Yeah, that's the title.

Basically, imagine nodes in a plane (well, they'll be in space but let's say plane to keep things simple), without any edge for now, because the problem is exactly to find out where to put the edges. And where do we want edges? We want edges between neighbour nodes, meaning that a node will have an edge with all the closest nodes. What does that mean "closest"? There is a difference between "the 5 closest" and "the 20 closest", so yeah, my definition doesn't mean c, that's exactly my problem :P

So I'll give an example. Here are 3 nodes in line with the wanted edges. There is no edge between 1 and 3 because 2 is closer.

­1-2-3


Well, that was one stupid example. But basically, imagine more nodes, not necessarily in line. Well, imagine you're a point, moving in the plane. There is obviously a node that you're closest to, that we will call X. And a node Y would be called a "closest node to X" if your point can move from X to Y while having its closest node being always either X or Y.
In the above example, that's why 1 isn't a "closest node to 3", because whatever you do, if you try to move from 3 to 1, at some point the closest node to you will be 2.

So I have to code this, but I can't code something I didn't even define by words and rules, so does anyone have any idea how to get these rules down on paper?
Title: Re: A graph problem (not necessarily math-heavy)
Post by: kotu on November 09, 2016, 11:04:47 AM
i have no idea how to approah this

i skim-read your post because it looked difficult to understand, i doubt i could understand it if i had read it (without you explaining in person) and tbh i think you need someone trained in graph theory lol

*edit*
is it possible to make a picture of the 1-2-3 example?
Title: Re: A graph problem (not necessarily math-heavy)
Post by: Hayleia on November 09, 2016, 11:07:06 AM
I am not sure of it really. On the contrary, someone trained in graph theory or algorithms would start thinking about Dijkstra and stuff and where to apply it and then would get a biased definition with a forced Dijkstra in it even though that may be unnecessary or even false. Or they would skim-read too and answer "that's just the minimum spanning tree" even though nope, it's not, I'm sure I can get cycles in the stuff I want (just imagine 3 points at an equal distance, you want the three edges, not just 2).
Title: Re: A graph problem (not necessarily math-heavy)
Post by: p2 on November 09, 2016, 11:12:06 AM
thats some dificult to understand post you made there O.o

But for finding the next neighbors just use aa FOR loop on all other node and calculate the distance A(Xa|Ya) <--->B(Xb|Yb) by doing squareroot(Xa-Xb)^2+(Ya-Yb)^2)
but for putting it down on paper in a formula...
I dont know if thats even possible... xD

I hope that's what you ment. But it seems too easy to be the answer to your question... <_<
Title: Re: A graph problem (not necessarily math-heavy)
Post by: Hayleia on November 09, 2016, 11:15:38 AM
Quote from: p2 on November 09, 2016, 11:12:06 AM
thats some dificult to understand post you made there O.o

But for finding the next neighbors just use aa FOR loop on all other node and calculate the distance A(Xa|Ya) <--->B(Xb|Yb) by doing squareroot(Xa-Xb)^2+(Ya-Yb)^2)
but for putting it down on paper in a formula...
I dont know if thats even possible... xD

I hope that's what you ment. But it seems too easy to be the answer to your question... <_<
Nope, because that would give me the X closest nodes, not the "closest nodes" I'm looking for. They are most probably contained in some "X closest nodes" set, but which one? Especially annoying to know since X depends on the node (see the stupid example where 1 has X=1 closest nodes and 2 has X=2 closest nodes).
Title: Re: A graph problem (not necessarily math-heavy)
Post by: p2 on November 09, 2016, 11:45:57 AM
okeyyy, then to get the 5 nearest ones:

create "SMALLEST" var set to >9000
FOR loop on all nodes
  IF distance < "SMALLEST" var
  Then distance --> SMALLEST
  save node handle somewhere
EndFOR

that'd e the right code to get the smallest one.
if you need multiple results:

add an array for the node handles instead of just one single var
add if-condition in for-loop: to skip a node if it'S handle is already in the handle-array
use a for-loop to execute the previous for-loop as many times you want, eah time saving the resulting node handle in the Nth position of the array.
what you get is the node's handles, sorted by their distances to your current node. :)

is this even helpful? Or am I just repeating stuff you already know but didnt use as it was a too crappy way of doing things? ^^
Title: Re: A graph problem (not necessarily math-heavy)
Post by: Hayleia on November 09, 2016, 01:28:47 PM
It is not helpful, but not because it's a crappy way to do things (you should read my code, you'd see I don't care about crappy stuff :P), just because it is not what I want.
Title: Re: A graph problem (not necessarily math-heavy)
Post by: Hayleia on November 09, 2016, 01:53:19 PM
Kind of an update so I double post.

First, I have images, as asked by @kotu, see below.

Second, I have an almost mathematical definition of what I'm looking for.
The nodes X and Y are neighbours if there exists a path between X and Y (straight line or not) such as for all points p on that line, the closest node to p is either X or Y.

Here is the line example. You can see that there is a path between 1 and 2 such as you're always closest to 1 or 2 (on the yellow part of the path you're closest to 1, and on the red one you're closest to 2). same for 2 and 3, and there is no requirement to be a straight line. But for 1 and 3 nope, you can't find a path without a point p that will have 2 as its closest node (note, I put colors roughly where I think stuff is closest, but don't start measuring, these are just examples made in 5 minutes).
(https://tiplanet.org/forum/images/forum_uploads/6947_1478699265_582329014952f.png)

And here is a triangle example. You can see that 1 and 3 become neighbours because if we go far enough towards the bottom, we can avoid getting close to 2. And 1 and 2 are still neighbours, same for 2 and 3 but you know that.
(https://tiplanet.org/forum/images/forum_uploads/6947_1478699271_58232907b0591.png)
Title: Re: A graph problem (not necessarily math-heavy)
Post by: kotu on November 09, 2016, 02:17:33 PM
just seems like a load of calls to sqrt() * to determine 2D distances

* (if you're using C orC++)

yeah ok you can't test a path in its purest sense, as you will have to break the path down into points (pixels for example)

that would require a  formulaic solution and more processing time. the pixels based approach would probably suffice, i guess
Title: Re: A graph problem (not necessarily math-heavy)
Post by: Snektron on November 09, 2016, 02:18:50 PM
Have you tried Delaughney triangularization? Or Isosurfaces? Or voronoi-like algoritms? Im not sure, but maybe either of those might help you.
On a side note, bute force drawing it in a shader might be possible.

Also what kind of results are you supposed to get? because there are either one, infinite or zero possibilities i think (which makes me think of matrices).
Title: Re: A graph problem (not necessarily math-heavy)
Post by: Hayleia on November 09, 2016, 02:45:23 PM
Quote from: kotu on November 09, 2016, 02:17:33 PM
yeah ok you can't test a path in its purest sense, as you will have to break the path down into points (pixels for example)

that would require a  formulaic solution and more processing time. the pixels based approach would probably suffice, i guess
Nope, can't do that. Far too slow. I mean, cutting a path into discrete subpaths is possible, but combined to the fact there are quite a big number of paths to test, this is not doable.

Quote from: Snektron on November 09, 2016, 02:18:50 PM
Have you tried Delaughney triangularization? Or Isosurfaces? Or voronoi-like algoritms? Im not sure, but maybe either of those might help you.
On a side note, bute force drawing it in a shader might be possible.
No idea what isosurfaces are doing here :P
edit yeah I see what, probably has to do with the border between the "influence zones" of two nodes.
But the other two seem very related indeed. I'll check these out.

Quote from: Snektron on November 09, 2016, 02:18:50 PM
Also what kind of results are you supposed to get? because there are either one, infinite or zero possibilities i think (which makes me think of matrices).
Well I'd like to get the one result when there is one result :P
Title: Re: A graph problem (not necessarily math-heavy)
Post by: kotu on November 09, 2016, 03:33:14 PM
Are you trying to generate 2D meshes from general shape definitions? Because I played about with something like that about 12 years ago..... just finding the file. It might not help you though... will post some pics in a bit

*update*
(https://s15.postimg.org/6e162qzsn/image.png) (https://postimg.org/image/6e162qzsn/)

the program generates flat 2D 'panels' based on points that you input...... however I'm not sure if the app fulfils yours criteria as I'm not sure if it would do this...
(https://s21.postimg.org/p3pz8cuzn/image.png) (https://postimg.org/image/p3pz8cuzn/)

or this......
(https://s17.postimg.org/nnm2mncez/image.png) (https://postimg.org/image/nnm2mncez/)

in a given situation. It does however allow for holes in a mesh...
(https://s13.postimg.org/hdv6qy3cj/image.png) (https://postimg.org/image/hdv6qy3cj/)

There is a bug in it though... see this,,
(https://s12.postimg.org/5jhn9ni8d/image.png)

You can have the source if it helps you

Sorry if this wasn't relevant to you lol
Title: Re: A graph problem (not necessarily math-heavy)
Post by: Snektron on November 09, 2016, 05:20:05 PM
Should the path be a smooth function? Because then you might be able to do something with parametric or parabolic equations.
The problem is the closest path will always (with 3 nodes) be either a straight line, or 2 straight lines with a sharp turn. Which isn't very mathematicy.
The only solution i can think of right now requires an awful lot of vector math (calculate {p | d(A, p) = d(B, p) = d(C, p) ^ A != B ^ A != C ^ B !+ C} and calculate a path through that. That also requires a special case for when the sortest path is "straight").
Title: Re: A graph problem (not necessarily math-heavy)
Post by: kotu on November 09, 2016, 05:52:40 PM
if you are looking at ways of making efficient networks between many nodes (for example to design an underground rail system) you might want to look at slime molds. these single-cell organisms get quite large (20cm across easily) and they form inter-cell paths for food to travel down. found to create very efficient networks, equivalent to expert human designers (for example of rail system)

(https://s-media-cache-ak0.pinimg.com/originals/d2/a0/8f/d2a08f7321542d41e3537e758fdd1696.jpg)

apparently they use pulses to coordinate the maze mapping (i think)
Title: Re: A graph problem (not necessarily math-heavy)
Post by: Hayleia on November 10, 2016, 09:55:58 AM
Quote from: kotu on November 09, 2016, 03:33:14 PM
Are you trying to generate 2D meshes from general shape definitions? Because I played about with something like that about 12 years ago..... just finding the file. It might not help you though... will post some pics in a bit

*snip*

You can have the source if it helps you

Sorry if this wasn't relevant to you lol
I don't know if this would work, depending on the algorithm you use to generate meshes (not mentioning the bug).
See this example:
(https://tiplanet.org/forum/images/forum_uploads/6947_1478771495_58244327403b3.png)
Both meshes are valid meshes for the 4 given points, but the right one according to what I want is the one on the right.

Quote from: Snektron on November 09, 2016, 05:20:05 PM
Should the path be a smooth function? Because then you might be able to do something with parametric or parabolic equations.
The problem is the closest path will always (with 3 nodes) be either a straight line, or 2 straight lines with a sharp turn. Which isn't very mathematicy.
The only solution i can think of right now requires an awful lot of vector math (calculate {p | d(A, p) = d(B, p) = d(C, p) ^ A != B ^ A != C ^ B !+ C} and calculate a path through that. That also requires a special case for when the sortest path is "straight").
I don't care about the path :P
The input is nodes, the output is nodes' neighbours, and you can use whatever you want in between, not paths, paths, whatever paths, smooth or not.

But I think I'll give up on this complicated subject, I'll just use the X closest ones (where I'd have to find a working X) instead of trying something smart...