Hi Veeky Forums
Is there any algorithm that allows me to create a graph only with the position of the nodes and generates the edges without redundancy?
For example if I have 3 points, (1,2), (2,2), (3,2), it will create only two edges (1,2)-(2,2) and (2,2)-(3,2) without (1,2)-(3,2)
I can't find anything similar on the internet
Hi Veeky Forums
Colton Rogers
Ryder Long
Just put your points in a list and connect everything to the element below it. That was easy.
Hunter Mitchell
Do you care which set of edges it chooses? Can paths cross? If it doesn't matter, then
Juan Morris
Pretty sure you can use Dijkstra's algorithm and find the minimum spanning tree?
Tyler Sanders
Minimum spanning tree of complete graph formed by distances between each node, using Prim's algorithm
Jackson Morris
Just generate a path graph / linear graph.
en.wikipedia.org
make_graph(list nodes)
new graph G;
G.nodes = nodes; //copy over
G.edges = list(); //empty list
prev_node = nodes.pop_first();
while(nodes.size > 0 ){
cur_node = nodes.pop_first();
G.edges.add( pair(prev_node, cur_node) );
prev_node = cur_node;
}
return G;
Or even simpler, make a star graph and delete the line "prev_node = cur_node;" so everything is connected to the first node.
en.wikipedia.org
cs majors don't belong here.
Owen Lopez
thats some nice kode there girl
Jordan Brooks
>without redundancy
Your example didn't really clarify what you mean by redundancy. It's hard to ask for help when you don't even know what you are trying to do.
Ryder Ramirez
Obviously he means connectedness.
Eli Martinez
Did you just assume their gender?!
Anthony Scott
minimum according to what? the edges don't fucking exist yet
Robert Bennett
He's a CS major. All he is capable of doing is spouting buzzwords he doesn't understand in the vain attempt to appear knowledgeable.
Connor Bennett
It's unclear what you're asking (what is "redundancy"?), and as it currently stands there are multiple correct answers to your question. Any path graph is also its own a minimum spanning tree. Your algorithm can just connect node i to node i+1.
Owen Martinez
OP here, with my first reply
It is better if I write down the original problem, maybe that will help better understand me.Also please not that I am not a native English speaker.
I am developing an indoor navigation software, where I want to represent the rooms as nodes of a graph and then use shortest path to determine the path for the user.
My professor said that hardcode the edges into the database, but I want to create a program that makes the graph just from the nodes(less work for possible users especially in bigger building).
By redundancy I mean that if a corridor has 5 rooms I want it to have 4 edges and not connect every room to every room.
I was just interested if this was already made so I don't have to reinvent the wheel or I have to figure out an algorithm myself(which is almost done, but it's possible I didn't covered all possibilities)
Daniel Reed
So you want the shortest hamiltonian path in your graph. Is that it?
en.wikipedia.org
You're out of luck for really big buildings, but it's a known problem.
Isaiah Allen
Any connected graph with n nodes and n-1 edges is a tree.
You want to create some sort of tree, perhaps a minimum spanning tree? If you don't want a MST, why not?
Ethan Reed
I don't think so.
I want to avoid the bottom of pic related. If the nodes are in the same line they should be connected only one time in that line.
I don't want MST, I want to use the edges of the graph as the path for the navigation, and edges should only connect nodes if they are in line of sight (so don't connect two nodes if they have a wall or room between them)
James Flores
Well if you don't want angled corridors (reasonable) you should look into en.m.wikipedia.org
Jose Richardson
From what I understand this would create multiple nonexistent paths(edges) for each room(node) if there are more than one corridor. which is now realizing the same problem with my solution too even if it's rear in mine
Wyatt Gray
Connect each node with an edge w/ weight 1 if they share a coordinate then find a MST?
Joseph Bennett
if you want to avoid redundant connections then you just have to avoid making arcs between the current node and nodes that are already connected when you build the graph. so when you connect, pick a node that has no associated arcs.
Ayden Fisher
for your originally posted problem just make a tree
a tree by definition has no cycles
what i'm confused about is how are you trying to map the building using a single tree?
unless the building itself is shaped like a tree a single graph is not guaranteed give you the shortest paths of all nodes involved
iirc there's method that maps only the paths (corners as nodes, hallways as edges) and pathing to a room just involves pathing to the closest intersection
Owen Parker
>Create Graph with all Edges
>Do Dijkstra to find the smallest spantree
>Save the new tree
>Did the work with the force of 3000 dying suns to get a tree without any redundancies