Graph data structures:
Basically, graph data structures typically come in three different forms, and the appropriate one can be chosen based upon performance requirements. Adjacency matrices are more efficient for dense graphs, and adjacency lists are preferably for sparse ones.- Adjacency matrices
- Incidence matrices
- Adjacency lists
An adjacency matrix class:
This creates a mutable adjacency matrix class in Java that uses a multidimensional boolean array internally. The boolean array is then manipulated by for loops, which compile to JVM bytecode in the obvious manner.
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class AdjacencyMatrix {
boolean[][] edges;
public AdjacencyMatrix(boolean[][] edges) {
this.edges = edges;
}
public AdjacencyMatrix(int n) {
this.edges = new boolean[n][n];
}
public void setEdge(int x, int y, boolean val) {
edges[x][y] = val;
}
public void swapEdge(int x, int y) {
edges[x][y] = !edges[x][y];
}
public void clear() {
for(int x = 0; x < edges.length; x++) {
for(int y = 0; y < edges.length; y++) {
setEdge(x,y,false);
}
}
}
public void fill() {
for(int x = 0; x < edges.length; x++) {
for(int y = 0; y < edges.length; y++) {
setEdge(x,y,true);
}
}
}
public void complement() {
for(int x = 0; x < edges.length; x++) {
for(int y = 0; y < edges.length; y++) {
swapEdge(x, y);
}
}
}
public void symmetricClosure() {
for(int x = 0; x < edges.length; x++) {
for(int y = 0; y < edges.length; y++) {
setEdge(x, y, edges[x][y] || edges[y][x]);
}
}
}
public void symmetricComponent() {
for(int x = 0; x < edges.length; x++) {
for(int y = 0; y < edges.length; y++) {
setEdge(x, y, edges[x][y] && edges[y][x]);
}
}
}
public void randomize() {
var r = new Random();
for(int x = 0; x < edges.length; x++) {
for(int y = 0; y < edges.length; y++) {
setEdge(x, y, (r.nextInt(2) == 1));
}
}
}
public void transpose() {
// we need to duplicate the old matrix so that we
// don't get stopped out by side effects.
var oldMatrix = new boolean[edges.length][edges.length];
for(int i = 0; i < edges.length; i++) {
oldMatrix[i] = edges[i].clone();
}
for(int x = 0; x < edges.length; x++) {
for(int y = 0; y < edges.length; y++) {
edges[x][y] = oldMatrix[y][x];
}
}
}
public int order() {
return edges.length;
}
public boolean containsEdge(int x, int y) {
return edges[x][y];
}
public int size() {
int rval = 0;
for(int x = 0; x < edges.length; x++) {
for(int y = 0; y < edges.length; y++) {
if(edges[x][y]) {
rval++;
}
}
}
return rval;
}
public String toString() {
return Arrays.deepToString(edges);
}
public byte[] getBytes() {
var l = edges.length;
var rval = new byte[(int) Math.pow(l,2)];
for(int x = 0; x < edges.length; x++) {
for(int y = 0; y < edges.length; y++) {
rval[x*l + y] = (byte) ((this.edges[x][y]) ? 1 : 0);
}
}
return rval;
}
public static AdjacencyMatrix fromBytes(byte[] coll) {
var l = (int) Math.sqrt(coll.length);
var edges = new boolean[l][l];
for(int x = 0; x < l; x++) {
for(int y = 0; y < l; y++) {
edges[x][y] = (coll[x*l + y] == 1);
}
}
return new AdjacencyMatrix(edges);
}
public Set edgeSet() {
Set rval = new HashSet();
for(int x = 0; x < edges.length; x++) {
for(int y = 0; y < edges.length; y++) {
if(edges[x][y]) {
rval.add(new int[]{x,y});
}
}
}
return rval;
}
}
This is notable because it is a mutable class which means it would be hard to recreate exactly in Clojure, which tries to use immutable and persistent data structures for everything. It might pay off to have both an adjacency matrix value and a separate mutable matrix class, but we will leave that aside for now. I will now demonstrate a little bit about how to use this class from Clojure.
Managing adjacency matrices from Clojure
Creating an adjacency matrixThe key to create an adjacency matrix now is to use the make-array function to create a boolean array in order to call the constructor. A new AdjacencyMatrix is created using the new opcode, and then initialized by a call to invokespecial with the appropriate constructor method handle.
(def arr (make-array Boolean/TYPE 4 4))
We can then manipulate the boolean array using the Clojure Java interop methods aget and aset which correspond to the aload and astore instructions of the Java virtual machine.
(aset (aget arr 0) 0 true)
(aset (aget arr 2) 2 true)
Now that we have sufficiently manipulated the data of the adjacency matrix we can pass it to the constructor, in order to initialize an instance of the AdjacencyMatrix class.
(def ^AdjacencyMatrix adjacency-matrix
(AdjacencyMatrix. arr))
The Adjacency matrix constructor is actually overloaded, so assuming that you don't want to do any operations on the input multidimensional boolean array before passing it to the constructor, you can just call the version that uses an integer as its main parameter.
(def ^AdjacencyMatrix adjacency-matrix
(AdjacencyMatrix. 4))
Type hinting the adjacency matrix after you created it ensures that the Clojure code will typically compile to an invokevirtual call with the appropriate method signature, rather than going through reflection.
Manipulating the adjacency matrix
I have now prepared a number of Java methods that can be called to manipulate an adjacency matrix instance from Clojure. For example, clear sets all entries to false.
(.clear adjacency-matrix)
On the other hand, fill does the opposite and it sets all the entries in the adjacency matrix to true. In each case, we can call a Java method using the same sort of dot method call syntax as Java.
(.fill adjacency-matrix)
The fill operation is equivalent to using clear combined with complement which switches each boolean entry in the adjacency matrix to its opposite value.
(doto adjacency-matrix
(.clear)
(.complement))
A final method I created that you can call is transpose. It was actually the hardest to implement because of the nature of its side effects.
(.transpose adjacency-matrix)
Of course, many more methods could be added and are not included here but this demonstates the basic principles of Clojure Java interop.
Storing a matrix to a file:
One interesting thing I added in the Java class is the ability to take the adjacency matrix and convert it to a byte array. The whole point of this is so that I can use it to store an adjacency matrix to a file. Its not an elaborate serialisation method or anything, but it works.
(import java.io.File)
(import java.nio.Files)
(def current-file
(File. (str (System/getProperty "user.home") "/output.bin")))
(Files/write (.toPath current-file) (.getBytes adjacency-matrix))
In order to then get back the data of the adjacency matrix later, all we need to do is call java.nio.Files/readAllBytes and then use the fromBytes method provided in the Java class provided earlier.
(def adjacency-matrix
(AdjacencyMatrix/fromBytes (Files/readAllBytes current-file)))
That should be sufficient for now to demonstrate this basic adjacency matrix. I envision creating thousands of Java classes for various objects of mathematics - like Young diagrams, transformationts, permutations, etc for use in Clojure.
No comments:
Post a Comment