6
\$\begingroup\$

Earlier I posted a question about model simulation, now I have code for model 'spatial' representation. My model consists of moving parts that can perform actions and each part occupies space within the model.

I would like to use a graph to to represent relationships between model parts. ISpace defines methods for working with points(vertices). Space is the base class and I used two HashMaps to represent vertices and points because there should be one-to-one relation between them. I have looked at JGraph documentation and they represent graphs with sets of vertices and edges(links between two vertices), so maybe I should move my Point class into my Vertex class? (probably just use JGraph or another package instead of my own code).

Space2D should represent a 2D toroidal space (like in Conway's game of life). Vertex could be any class.

package spacetest;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.UUID;

public class SpaceTest {

    public static void main(String[] args) {

        int vertexCount = 1000;
        int spaceWidth = 99;
        int spaceHeight = 99;

        Space2D space = new Space2D(0, spaceWidth, 0, spaceHeight);

        Random rand = new Random();

        for (int i = 0; i < vertexCount; i++) {
            Vertex v = new Vertex();
            Point p = new Point(rand.nextInt(spaceWidth), rand.nextInt(spaceWidth));

            while (space.vertexExists(p)) {
                p.x = rand.nextInt(spaceWidth);
                p.y = rand.nextInt(spaceHeight);
            }

            try {
                space.addElement(p, v);
            } catch (Exception e) {
                System.out.println(e.getStackTrace());
            }
        }

        printVertices(space);

        for (int i = 0; i < 10; i++) {
            Vertex[] vertices = space.getVertices().toArray(new Vertex[0]);
            for (Vertex vertice : vertices) {
                Point p = new Point(rand.nextInt(spaceWidth), rand.nextInt(spaceHeight));
                try {
                    space.moveVertex(vertice, p);
                } catch (Exception e) {
                    System.out.println(e.getStackTrace());
                }
            }

            System.out.println("----------------------------");
            printVertices(space);
        }
    }

    private static void printVertices(Space2D space) {
        for (Vertex v : space.getVertices()) {
            Point p = space.getPoint(v);
            System.out.println(p.x + ", " + p.y);
            for (Vertex n : space.getNeighbors(v)) {
                Point np = space.getPoint(n);
                System.out.println("\t" + np.x + ", " + np.y);
            }
        }
    }
}

interface ISpace<P, V> {

    boolean addElement(P point, V vertex);

    boolean removeElement(P point, V vertex);

    boolean elementExists(P point, V vertex);

    boolean pointExists(V vertex);

    P getPoint(V vertex);

    boolean vertexExists(P point);

    V getVertex(P point);

    boolean moveVertex(V vertex, P destination);

    Collection<P> getPoints();

    Collection<V> getVertices();

    ArrayList<V> getNeighbors(V vertex);

    ArrayList<P> getAdjacentPoints(P point);
}

abstract class Space<P, V> implements ISpace<P, V> {

    private final Map<P, V> vertices = new HashMap<>();
    private final Map<V, P> points = new HashMap<>();
    private final Map<P, ArrayList<P>> adjacencyMap = new HashMap<>();

    @Override
    public boolean addElement(P point, V vertex) {
        ArrayList<P> adjacentPoints = getAdjacentPoints(point);
        if (!points.containsKey(vertex) && !vertices.containsKey(point)) {
            vertices.put(point, vertex);
            points.put(vertex, point);

            if (!adjacencyMap.containsKey(point)) {
                adjacencyMap.put(point, new ArrayList<P>());
            }

            for (P adjacentPoint : adjacentPoints) {
                if (vertices.containsKey(adjacentPoint)) {
                    adjacencyMap.get(point).add(adjacentPoint);
                    adjacencyMap.get(adjacentPoint).add(point);
                }
            }
            return true;
        } else {
            return false;
        }
    }

    @Override
    public boolean removeElement(P point, V vertex) {
        if (points.containsKey(vertex) && vertices.containsKey(point)) {
            points.remove(vertex);
            vertices.remove(point);

            for (P neighbor : adjacencyMap.get(point)) {
                if (adjacencyMap.containsKey(neighbor)) {
                    adjacencyMap.get(neighbor).remove(point);
                }
            }

            adjacencyMap.remove(point);
            return true;
        } else {
            return false;
        }
    }

    @Override
    public boolean elementExists(P point, V vertex) {
        return pointExists(vertex) && vertexExists(point);
    }

    @Override
    public boolean pointExists(V vertex) {
        return points.containsKey(vertex);
    }

    @Override
    public P getPoint(V vertex) {
        if (pointExists(vertex)) {
            return points.get(vertex);
        } else {
            return null;
        }
    }

    @Override
    public boolean vertexExists(P point) {
        return vertices.containsKey(point);
    }

    @Override
    public V getVertex(P point) {
        if (vertexExists(point)) {
            return vertices.get(point);
        } else {
            return null;
        }
    }

    @Override
    public boolean moveVertex(V vertex, P destination) {
        if (pointExists(vertex) && vertexExists(destination)) {
            removeElement(getPoint(vertex), vertex);
            addElement(destination, vertex);
            return true;
        } else {
            return false;
        }
    }

    @Override
    public Collection<P> getPoints() {
        return points.values();
    }

    @Override
    public Collection<V> getVertices() {
        return vertices.values();
    }

    @Override
    public ArrayList<V> getNeighbors(V vertex) {
        ArrayList<V> neighbors = new ArrayList<>();
        P point = getPoint(vertex);
        for (P neighboringPoint : adjacencyMap.get(point)) {
            neighbors.add(getVertex(neighboringPoint));
        }

        return neighbors;
    }
}

class Space2D extends Space<Point, Vertex> {

    private int xMin;
    private int xMax;
    private int yMin;
    private int yMax;

    public Space2D(int xMin, int xMax, int yMin, int yMax) {
        this.xMin = xMin;
        this.xMax = xMax;
        this.yMin = yMin;
        this.yMax = yMax;
    }

    public int getX_min() {
        return xMin;
    }

    public void setX_min(int x_min) {
        this.xMin = x_min;
    }

    public int getX_max() {
        return xMax;
    }

    public void setX_max(int x_max) {
        this.xMax = x_max;
    }

    public int getY_max() {
        return yMax;
    }

    public void setY_max(int y_max) {
        this.yMax = y_max;
    }

    @Override
    public ArrayList<Point> getAdjacentPoints(Point origin) {
        int xWest = (origin.x == xMin) ? (xMax) : (origin.x - 1);
        int xEast = (origin.x == xMax) ? (xMin) : (origin.x + 1);
        int yNorth = (origin.y == yMin) ? (yMax) : (origin.y - 1);
        int ySouth = (origin.y == yMax) ? (yMin) : (origin.y + 1);

        ArrayList<Point> adjacentPoints = new ArrayList<>();

        Point northWest = new Point(xWest, yNorth);
        Point north = new Point(origin.x, yNorth);
        Point northEast = new Point(xEast, yNorth);
        Point east = new Point(xEast, origin.y);
        Point southEast = new Point(xEast, ySouth);
        Point south = new Point(origin.x, ySouth);
        Point southWest = new Point(xWest, ySouth);
        Point west = new Point(xWest, origin.y);

        adjacentPoints.add(northWest);
        adjacentPoints.add(north);
        adjacentPoints.add(northEast);
        adjacentPoints.add(east);
        adjacentPoints.add(southEast);
        adjacentPoints.add(south);
        adjacentPoints.add(southWest);
        adjacentPoints.add(west);

        return adjacentPoints;
    }
}

class Point {

    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Point)) {
            return false;
        }
        Point another = (Point) o;
        return ((x == another.x) && (y == another.y));
    }

    @Override
    public int hashCode() {
        int hash = 5;
        hash = 97 * hash + this.x;
        hash = 97 * hash + this.y;
        return hash;
    }
}

class Vertex {

    private final UUID id = UUID.randomUUID();
}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

You have some broad-spectrum questions....

  • If JGraph supports the features you need, then absolutely, you should use it.

    Writing code is fun, and challenging, and all those things.... but, at some point you have to maintain it. Maintaining code becomes tedious, especially when you could be doing other things like writing code.

    Offloading asks that are going to become maintenance tasks is a smart thing.

  • In your own space model, you are not doing things in what I would consider a logical format.... for a start, your code is not thread-safe.

    I would expect your program to have performance challenges, and the logical first step in any performance-challenged code is to use parallelism. As a consequence, I would expect Point, Vertex, and Space2D to be Immutable... (class is a public final class ..., all fields are private final, and there are no 'setter' methods). Immutable classes are thread safe, and will help a lot with performance.

  • Vertex+edge vs. your model. Typically with models like this there are a few foundational perspectives that make sense. You could, for example, use polar coordinates instead of x/y because polar-coordinates are more easy to do spacial geometry with. Unfortunately they involve more complicated algorithms getting data in to and out of the model. If your work is primarily 'inside the model' rather than 'outside the model', then using polar space may make sense because the bulk of the work will be faster.

    The same is true for things like Edges vs. Vertices. They each have advantages in different conditions. Depending on your conditions, the one model may make sense over the other.

    What you have presented here is not nearly enough to make that decision.... but, for what it's worth, what you are doing is also not really pushing the performance limits enough on your systems to make the differences noticeable.

\$\endgroup\$
1
  • \$\begingroup\$ Yes JgraphT supports UndirectedGraph and also ListenableGraph which would I think fit very nicely with my project.Parallelism is yet another Java feature I will have to learn about. Thank you for your comments \$\endgroup\$ Commented Mar 1, 2014 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.