#Kruskals Algorithm

1 messages · Page 1 of 1 (latest)

bronze lodge
#

Yeah probably

native spruce
#

okay thanks

bronze lodge
#

Anyhow, I was bored and wanted to learn if I could create it with the new open AI bot. Works a bit. So I remade the wiki example.

native spruce
#

aw cool

bronze lodge
#

In the start you can see the recreation of the graph of the wiki

#

And that is the output of the algorithm

image.png
#

Where it is numbered like this

#

So the algorithm is valid this way

native spruce
#

oh awesome, so with the code i have made it essentially randomizes the points and will therefor have randomized weights (the weights being the length of the edges)

#

reading this code it will obviouslky only take in 7 points each with the same weights and outputs every time

#

i looking to see if i can do basically what your algorithm does but on a larger scale and randomized

#

you can see at the top of my code it randomizes the points and the number of them

bronze lodge
#

Your vertices are fine imho. You just need logic to make the possible edges and weigh them. So make a a new loop that check if vertices are within a distance of each other, and then you make an Edge for it and add it to the list.

#

Do you understand?

# 

    private void NodeSet()
    {
        int nodeListLength = Random.Range(60, 100);

        for (int i = 0; i < nodeListLength; i++)
        {
            xCoord = Random.Range(-9, 10);
            yCoord = Random.Range(-4, 5);
            nodePosition = new Vector2(xCoord, yCoord);
            nodePoints.Add(nodePosition);
            if (nodePoints.Count > 1)
            {
                for (int j = 0; j < nodePoints.Count - 1; j++)
                {
                    if (nodePosition == nodePoints[j])
                    {
                        nodePoints.Remove(nodePoints[j]);
                    }
                }
            }
        }
        for (int i = 0; i < nodePoints.Count; i++)
        {
            Instantiate(nodePrefab, nodePoints[i], Quaternion.identity);
        }

    foreach node in nodes
      foreach otherNode in nodes
        check if not the same, check the distance lower then w/e you want
          make an edge and add it to the list
    }
native spruce
#

thanks, ill have a read of this two seconds

#

okay thanks that makes sense, but in my head i would need to create not just one list of the nodes im using, i would need to create multiple lists as the path doesnt span from one point. how would i conditionally create multiple lists and basically combine them when two groups of nodes 'meet'

#

or can i just keep adding the points to one list in a different way than how im describing

bronze lodge
#

i would need to create multiple lists as the path doesnt span from one point I don't understand this part, and the line after it.

native spruce
#

so i guess what im trying to say is that each circle here represents a list, and if a red line connects two of these lists, they would combine into one list. and when there is only one list connecting all the node points the program ends

image.png
bronze lodge
#

Hmm.

            new Edge { Source = 0, Destination = 1, Weight = 7},
            new Edge { Source = 0, Destination = 3, Weight = 5},
            new Edge { Source = 1, Destination = 2, Weight = 8},
            new Edge { Source = 1, Destination = 3, Weight = 9},
            new Edge { Source = 1, Destination = 4, Weight = 7},
            new Edge { Source = 2, Destination = 4, Weight = 5},
            new Edge { Source = 3, Destination = 4, Weight = 15},
            new Edge { Source = 3, Destination = 5, Weight = 6},
            new Edge { Source = 4, Destination = 5, Weight = 8},
            new Edge { Source = 4, Destination = 6, Weight = 9},
            new Edge { Source = 5, Destination = 6, Weight = 11}

What happens is that this gets sorted on Weight, then the shortest red lines get made first.
It just continues to add red edges to the final list
List<Edge> mst = new List<Edge>();
Until the algorithm is complete. Does that answer it?

#

You do see the algorithm checking with the Blue lines constantly right? Those are all the possible Edges in that graph

#

It skips the ones that actually make the graph go in circles.

native spruce
#

ah okay that is what i was typing to ask there, im a bit of a novice so could you point me to the part of the code you sent over that checks to see if the line its checking is looping back?

bronze lodge
# 
                // If including this edge does't cause
                // cycle, include it in result and increment the index
                // of result for next edge
                if (x != y)
                {
                    mst.Add(nextEdge);
                    Union(subsets, x, y);
                }
#

Or the whole while loop to be honest

#

But that part specifically make it add the edge or not.

native spruce
#

okay thanks. im going to look over what you gave me and ill see if i can figure something out. ill let you know if im in need of any more help

#

but youve been super helpful so far

bronze lodge
native spruce
#

haha yeah it is pretty cool honestly, but yeah ill look over what ive got and get back if i have any more questions

bronze lodge
native spruce
#

holy shit no way you did that

#

thank you so much

#

also another quick question, would there be a way to instead of having the random points be ints, could i make them floats instead

#

since these are going to be essentially paths baked onto a perlin noise map id like to make them slightly more dynamic

bronze lodge
# 

                    if (nodePosition == nodePoints[j])
                    {

Also that wont work anymore on floats then.

#

But the chance of floats being the same is almost nothing.

native spruce
#

awesome thanks

bronze lodge
#

Also, there is an edge case where this will break. If there is a vertex not in range of another vertex, it will not get an edge:

                    float distance = Vector2.Distance(nodePoints[i], nodePoints[j]);
                    if (distance < 5)

That will break the algorithm.