Dijkstra Algorithm view (Node, Edges)

please format code with </> button * homework policy * asking questions

Hello,

we have to implement the Dijkstra Algorithm. But at the beginning you have an empty field where you can click to create the nodes and edges between the nodes. In MousePressed we have implemented the nodes, but we dont know how we can connect two nodes with a line. Furthermore we dont really know how we can distinguish betwenn drawing a node or an edge in the funktion mousePressed.
Maybe there is someone who can help us!!

void setup() {
  size(400,400);
}


 void draw() {
 

   
}
 
 void mouseClicked(){
  
   // wenn Stelle noch nicht belegt
   
  Node node= new Node(); 

   // wenn an der Stelle ein Knoten ist 
   // -> Kante ziehen 
   
 }

static class Zaehler{
  
  
 static int knotennummerzaehler = -1;

 
  
}  

class Node extends Zaehler{
 
  // number inside the node
  int knotennummer;
  
  // neuen Knoten erstellen
  Node(){
    
    hochzaehler();
    fill(0);
    ellipse(mouseX,mouseY,50,50); 
    fill(255);
    textSize(20);
    text(knotennummer,mouseX,mouseY);

}

void hochzaehler(){
 
// number increases
  knotennummerzaehler ++;
  knotennummer = knotennummerzaehler;
  
 }
   
  
}  

class Edge{
  
 Edge(){
   
    fill(0);
    line(mouseX, mouseY,0,0);
    
   
   
 }
  
 
}

Here’s one idea that would work well.

When the mouse is clicked, look to see if it was clicked on a node.

If it wasn’t, that click creates a node.

If, however, the click WAS on an existing node, you’re starting to create an edge. When this occurs, you must wait for the next click to happen. If the next click is on a node, create an edge between those two nodes. If that next click is not on a node, however, then nothing happens.


You can also remove nodes and edges this way if you’re clever! If you click a node to start an edge, but then don’t click a second node, that can mean to remove the clicked node (don’t forget to remove all edges that connect to it too!).

Also, if you try to make an edge between two nodes that already have an edge, that can mean to remove that edge. Essentially it’s toggling edges between the clicked nodes, not just creating one.


Implementation of this is left as part of the exercise. Do post what you come up with - It’d be most helpful for others!

1 Like

I would focus on creating the classes for the Nodes and Edges first. For instance the Node class needs to know its own position, an Edge would have 2 Node fields (for the start and the end) and a weighting (might be distance between start and end nodes).

Both the Node class and Edge class would have their own method to draw itself e.g. display()

Once you have the classes then create a small fixed network of nodes and edges and make sure they render OK

Then you can consider how to create the network dynamically with the mouse.

Finally create the path finding algorithm and test it.

2 Likes

Thank you guys for your answer!!
@TfGuy44 can you describe how i can check if there is a node or not? My idea was to initialize a variable int noNodeexists = 0; and in mousePressed i check this with an if-clause.
So kinda like this…

void mousePressed(){

if( noNodeexists == 0){
Node node = new Node();
}
else {

// draw edge

}

@quark i understand your point. Every node needs to know where he is and every edge needs to know the beginning and ending… but i dont know how to start

Is this a homework / assessment?

@quark do you mean to draw the node/edge in display() instead of the constructor?

its a little project from university

The point is that this is not a simplistic task and it has to be broken down into logical parts otherwise it will be a nightmare.

Are you on a computing course?

Will you be marked on the final program?

The fact that you don’t know the answer tells me that you are not experienced at designing classes. Not to worry we all have to start somewhere.

The Node and Edge constructors will never be used to draw anything

The Node and Edge constructors will never be used to process mouse input

2 Likes

Okay haha :smiley:
i did it like this
but how can i let the node know where it is?

class Knoten extends Zaehler{

int knotennummer;

// neuen Knoten erstellen
Knoten(){

hochzaehler();
fill(0);
display();
fill(255);
textSize(20);
text(knotennummer,mouseX,mouseY);

}

void display(){

ellipse(mouseX,mouseY,50,50);

}
void hochzaehler(){

knotennummerzaehler ++;
knotennummer = knotennummerzaehler;

}

}

Your Node class should keep track of where that Node is.

Your array (or arrayList, probably) of Nodes has all your Nodes in it.

When you get a mouse click, you can use a loop over your array of Nodes to see if that click was near the position of any of them.

1 Like

OK here is a very simple Node class that you can start with

public class Node {
  private float x;
  private float y;

  public Node(float x, float y){
    this.x = x;
    this.y = y;
  }
  
  public void display(){
    strokeWeight(2);
    stroke(0); // black
    fill(0,255,0);
    ellipse(x, y, 16, 16);
  }
}

Note the ctor is only used to create the node and the display() method can be called from inside draw()

2 Likes

Sorry, but inside draw in the class Node or in the other draw Method?

When i call display() in the constructor of Node it works as well …:smiley:

I did it like this now. So the nodes are in the ArrayList. Probably not right but a beginning. But i didnt create the ArrayList inside the class Node, as you can see. Is it right?
In mouseClicked the Nodes will be added to the List.

import java.util.ArrayList; 


void setup() {
  size(600,600);
}


 void draw() {
 
   
}
 
 void mouseClicked(){
   
  // loop over Array of nodes to check if there is another node
   
  Node knoten = new Node(mouseX,mouseY); 
  
  // Adding node
  NodeList.add(knoten);
 // println(NodeList.size());
 // println(NodeList.indexOf(knoten));

 }
  
 
    
ArrayList<Node> NodeList = new ArrayList<Node>();    
  
// class Node    
 public class Node extends Zaehler {
  private float x;
  private float y;
  int knotennummer;


void draw(){
  
// display(); 
  
}

  public Node(float x, float y){
    hochzaehler();
    this.x = x;
    this.y = y;
    display();
  }
  
  public void display(){
    strokeWeight(2);
    stroke(0); // black
    fill(0);
    ellipse(x, y, 60, 60);
    
    fill(255);
    textSize(20);
    text(knotennummer,x,y); //number inside the node
  }

void hochzaehler(){
 
  knotennummerzaehler ++;
  knotennummer = knotennummerzaehler;
  
 }
   
  
}

static class Zaehler{
  
  
 static int knotennummerzaehler = -1;

 
  
}  
class Edge {
  
  
  
  void display(){
  
  //line();
  
}
  
    Edge(){
   
    fill(0);
    line(mouseX, mouseY,0,0);
    
   
   
 }
  
   
}

This might be able to help you, please note it is in p5 not processing but the principals are the same.

1 Like

Thank you! I will check it

1 Like

Let me know if you want some help understanding the code, there are quite a few different algorithms for this sketch.

Like this

Node n0, n1;

void setup() {
  size(400, 400);
  n0 = new Node(89.7, 123.55);
  n1 = new Node(341.34, 289.01);
}

void draw() {
  background(200, 255, 200);
  n0.display();
  n1.display();
}

public class Node {
  private float x;
  private float y;

  public Node(float x, float y) {
    this.x = x;
    this.y = y;
  }

  public void display() {
    strokeWeight(2);
    stroke(0); // black
    fill(0, 255, 0);
    ellipse(x, y, 16, 16);
  }
}

Just because something works doesn’t make it right - remember

1 Like

librakl didn’t have background(); at start of draw(), so it looked like it worked. Because the drawing in the constructor just stayed on the screen.

  • But quark is right of course: never drawing in the constructor.

  • I would argue the second statement (never process mouse input in the constructor) though, because when he wants to generate a new node on mouse input he needs the mouse position in the constructor (or at least pass the mouse position to the constructor).

void mousePressed() {
   nodes.add(new Node(mouseX,mouseY));
}

Chrisir

1 Like