Tag: algorithms

Java class for visualising Graphs

Hello, everyone!
While studying graph algorithms I created a class that helps visualise what your algorithm is doing. That’s helpful for debugging and helps learn the way the algorithm works.

ezgif.com-crop
DFS algorithm in action

You can plug any graph algorithm, the important part is to notify the JPanel whenever you want to repaint.

Here is the code:


package com.algos;
import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import javax.swing.*;
public class GraphPanel extends JPanel {
private static final long serialVersionUID = 7148504528835036003L;
private List<GraphNode> graph = new ArrayList<>();
public static class GraphNode {
public static final double radius = 30;
public Point point;
public int index;
public List<GraphNode> children;
public boolean currentlyVisited = false;
public GraphNode(int index, Point point) {
this.point = point;
this.index = index;
children = new ArrayList<>();
}
public void draw(Graphics g) {
if (this.currentlyVisited) {
g.setColor(Color.GREEN);
g.fillOval(this.point.x, this.point.y, (int)radius * 2, (int)radius * 2);
} else {
g.setColor(Color.BLACK);
g.drawOval(this.point.x, this.point.y, (int)radius * 2, (int)radius * 2);
}
g.setColor(Color.BLACK);
g.drawChars(new char[]{Character.forDigit(this.index, 10)}, 0, 1, this.point.x, this.point.y);
}
}
@Override
public void paintComponent(Graphics g) {
super.paintComponent(g);
for (GraphNode gf : graph) {
gf.draw(g);
for (GraphNode child : gf.children) {
g.drawLine(gf.point.x + (int) GraphNode.radius, gf.point.y + (int) GraphNode.radius, child.point.x + (int) GraphNode.radius, child.point.y + (int) GraphNode.radius);
}
}
}
public void addNodes(GraphNode… nodes) {
this.graph.addAll(Arrays.asList(nodes));
}
}

view raw

GraphPanel.java

hosted with ❤ by GitHub

And here is how you might use it.


package com.algos;
import com.algos.GraphPanel.GraphNode;
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Queue;
import javax.swing.SwingUtilities;
import javax.swing.JFrame;
import javax.swing.JPanel;
/**
* A panel maintaining a picture of a Do Not Enter sign.
*/
public class GraphsGraphics {
private static boolean[] visited = new boolean[100];
private static Queue<GraphNode> queue = new ArrayDeque<>();
public static void DFS(GraphNode currentNode, GraphNode searchedNode, JPanel panel) {
System.out.println("Currently we are visiting node " + currentNode.index);
currentNode.currentlyVisited = true;
panel.updateUI();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
}
currentNode.currentlyVisited = false;
panel.updateUI();
if (currentNode.index == searchedNode.index) {
System.out.println("Node found: " + searchedNode.index);
return;
}
if (visited[currentNode.index]) {
return;
}
visited[currentNode.index] = true;
for (GraphNode child : currentNode.children) {
DFS(child, searchedNode, panel);
}
}
public static void BFS(GraphNode currentNode, GraphNode searchedNode, JPanel panel) {
currentNode.currentlyVisited = true;
panel.updateUI();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
}
currentNode.currentlyVisited = false;
panel.updateUI();
if (currentNode.index == searchedNode.index) {
System.out.println("Node found: " + searchedNode.index);
return;
}
if (visited[currentNode.index]) {
return;
}
System.out.println("Currently visiting node " + currentNode.index);
visited[currentNode.index] = true;
for (GraphNode child : currentNode.children) {
queue.add(child);
}
if (!queue.isEmpty()) {
BFS(queue.poll(), searchedNode, panel);
}
}
/**
* A little driver in case you want a stand-alone application.
*/
public static void main(String[] args) {
GraphNode rootNode = new GraphNode(0, new Point(300, 20));
GraphNode node1 = new GraphNode(1, new Point(200, 100));
GraphNode node2 = new GraphNode(2, new Point(400, 100));
GraphNode node3 = new GraphNode(3, new Point(500, 200));
GraphNode node4 = new GraphNode(4, new Point(100, 200));
GraphNode node5 = new GraphNode(5, new Point(40, 300));
GraphNode node6 = new GraphNode(6, new Point(200, 300));
rootNode.children.add(node1);
rootNode.children.add(node2);
node1.children.add(node4);
node2.children.add(node3);
node4.children.add(node5);
node4.children.add(node6);
GraphPanel panel = new GraphPanel();
panel.addNodes(rootNode, node1, node2, node3, node4, node5, node6);
SwingUtilities.invokeLater(() -> {
panel.setBackground(Color.GRAY.darker());
JFrame frame = new JFrame("A simple graphics program");
frame.setSize(800, 600);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.getContentPane().add(panel, BorderLayout.CENTER);
frame.setVisible(true);
});
BFS(rootNode, node6, panel);
}
}

view raw

Main.java

hosted with ❤ by GitHub

Happy learning!

Factorization of a number in C

Let’s see how we can split a real number into prime numbers.

One of the main theorems in mathematics states that every real number R (R > 1) can be represented with prime numbers P1, P2, P3 where (P1 < P2 < P3.. etc.)

So for example:

  • 520 = 2 * 2 * 2 * 5 * 13
  • 64 = 2 * 2 * 2 * 2 * 2 * 2
  • 2345 = 5 * 7 * 67

How we can do that in C:

1. Include the library needed for in/output to the console.


#include stdio.h

2. Next we declare the number which we want to factorize


unsigned n = 432;

3. We should have a variable that is the current factor. We start from 1, but in the beginning of the “while” we increment, so effectively we are starting from 2.


unsigned i = 1;

4. We declare the body of the main (outer) loop. It will process until the number we are factorizing is different from 1.


while (n != 1) {
....
}

5. First step in the loop is to increment “i” which will lead us to the next factor.
Note: this code is in the main “while” loop described above.


i++;

6. We need a variable to count the number of times the current factor is contained in “n”.


unsigned k = 0;

7. We start another (inner) “while” loop that will divide “n” by “i” until it cannot be evenly divided.


while (n % i == 0) {
....
}

8. In the above (inner) “while” loop we increment “k” (the number of times a factor exists in the number we want to factorize – “n”). And we also reduce “n”, by dividing it with “i”.


k++;
n /= i;

9. Next we print the current factor “i”, “k” number of times.


for (j = 0; j < k; j++) {
printf("%u ", i);
}

That’s it! As console output we get all the factors, starting from the smallest.

Hope you enjoyed this lesson, if you did, please subscribe for more!