Skip to content

TutorialSimpleGraph

Jump to bottom
Wouter Meulemans edited this page Mar 14, 2022 · 3 revisions

Tutorial: Using graphs represented as adjacency lists

We're going to define and augment a simple graph, to be loaded from IPE and rendered to screen.

Prior knowledge

To complete this tutorial, you are assumed...

  • to understand how to set up a new GeometryCore project; see Tutorial: Getting started
  • to understand how the geometry model works
  • to know basic graph terminology

Learning objectives

In this tutorial, you will learn...

  • how to how with simple, potentially nonplanar graphs as supported by GeometryCore
  • how to construct such a graph from geometric objects
  • how to render the results to a draw panel

GeometryCore versions

Written using version: 1.1.0. Last tested using version: 1.1.0.

Overview

About simple graphs

What we refer to here as "simple" graphs effectively are graphs represented by adjacency lists, though with explicit objects for edges. That is, a vertex has a list of edges that have that vertex as one of its endpoints (its incident edges), and every edge knows its two endpoints.

Graphs are, in principle, undirected and hence do not allow selfloops. Every edge has a start and end, to distinguish its endpoints and match it to the associated oriented geometry. This is consistent and can thus be used to also deal with directed graphs in limited form. It is out of scope of this tutorial to treat this in detail.

Tip: every vertex and edge has a "graph index", which is effectively its index in the graph's overall list of edges. These can be useful in creating temporary maps while you are not changing the graph. The graph index may change arbitrarily when you remove vertices or edges.

Step 1: defining the graph classes

The main idea in how graphs have been set up, is that we typically want to augment them using some data for algorithms. To do so, GeometryCore uses generics, to avoid a need for "getData()" functions, casting and alike. The price to pay is that we usually have to define some boiler-plate code to get started with graphs.

Specifically, we need to create three classes: a Graph class that extends from SimpleGraph, a Vertex class that extends from SimpleVertex, and an Edge class that extends from SimpleEdge. Each of these "Simple" classes takes three generic parameters, in order: the geometry class of the edges, the vertex class, and the edge class.

If we want to define a graph using straight edges, we hence define the following three classes. Note how each of the generic triplets is indentical.

public class Graph extends SimpleGraph<LineSegment,Vertex,Edge>
public class Edge extends SimpleEdge<LineSegment,Vertex,Edge>
public class Vertex extends SimpleVertex<LineSegment,Vertex,Edge>

That's it, your graph is ready for use!

Notes:

  • you should not provide custom constructors for edges and vertices, as these must be instantiated by the graph itself. Augmented data needs to be initialized inline, or after adding the vertex or edge to the graph.
  • if you are using a version prior to 1.2.0, you will need to implement some abstract functions to help link it all together.

Step 2: constructing a graph

The next step is to actually construct a graph. We can do this "manually", by calling .addVertex() and .addEdge(). To add a vertex, we need to provide only its coordinates.

        graph.addVertex(0,0);

To add an edge, we specify its two endpoints, as well as the geometry that represents the edge. Since we are working with a straight-line representation, we provide an instance of LineSegment. Note that we must clone the vertices, as the geometric object needs to be independent from the vertex objects. If you do not clone the vertices, your code will get stuck in an infinite loop when updating a vertex's location.

        graph.addEdge(v1, v2, new LineSegment(v1.clone(), v2.clone()));

When you have geometric objects that represent your graph, then there are several convenience functions provided in the GraphConstruction class. The following code adds the objects in items to the graph graph, which may or may not be empty. The third parameter is a number, that indicates how close two vertices need to be, for them to be considered the same vertex. The fourth parameter must be an object that clones geometries into the right type. This is always of type OrientedGeometry, and in our case must provide an object of type LineSegment.

        GraphConstruction.convertGeometriesToGraph(graph, items, DoubleUtil.EPS, 
                (OrientedGeometry og) -> new LineSegment(og.getStart(), og.getEnd()));

Notes:

  • The source and target of the created edges follow the directions in the given geometric objects. If edges are described by multiple objects, the direction follows that of the first object in the given list.
  • The above construction creates an edge for every edge (and the necessary vertices) for all edges in the provided objects. That is, for a PolyLine and Polygon, each of its vertices is considered a vertex, and each of its edges an edge in the graph. For more generic types, such as GeometryString, it treats every edge of the string (which can be a PolyLine) as a single edge. If your edge types are to be of type PolyLine, you can use these generic containers as a workaround to avoid splitting a single PolyLine into separate edges.

Step 3: rendering the result

One of the advantages of using the provided graph classes is that the vertices and edges implement GeometryConvertable and can thus be provided to many functions directly. We hence do not need more than two lines to render all vertices and edges, after configuring the draw settings:

        draw(graph.getEdges());        
        draw(graph.getVertices());

Full code

Graph.java

package tutorials.simplegraph;

import nl.tue.geometrycore.geometry.linear.LineSegment;
import nl.tue.geometrycore.graphs.simple.SimpleGraph;

public class Graph extends SimpleGraph<LineSegment,Vertex,Edge> {
    
}

Vertex.java

package tutorials.simplegraph;

import nl.tue.geometrycore.geometry.linear.LineSegment;
import nl.tue.geometrycore.graphs.simple.SimpleVertex;

public class Vertex extends SimpleVertex<LineSegment,Vertex,Edge> {
        
}

Edge.java

package tutorials.simplegraph;

import nl.tue.geometrycore.geometry.linear.LineSegment;
import nl.tue.geometrycore.graphs.simple.SimpleEdge;

public class Edge extends SimpleEdge<LineSegment,Vertex,Edge> {
    
}

DrawPanel.java

package tutorials.simplegraph;

import java.awt.Color;
import java.io.IOException;
import nl.tue.geometrycore.geometry.OrientedGeometry;
import nl.tue.geometrycore.geometry.Vector;
import nl.tue.geometrycore.geometry.linear.LineSegment;
import nl.tue.geometrycore.geometry.linear.Rectangle;
import nl.tue.geometrycore.geometryrendering.GeometryPanel;
import nl.tue.geometrycore.geometryrendering.glyphs.PointStyle;
import nl.tue.geometrycore.geometryrendering.styling.Dashing;
import nl.tue.geometrycore.geometryrendering.styling.SizeMode;
import nl.tue.geometrycore.graphs.GraphConstruction;
import nl.tue.geometrycore.gui.GUIUtil;
import nl.tue.geometrycore.io.ipe.IPEReader;
import nl.tue.geometrycore.util.DoubleUtil;

public class DrawPanel extends GeometryPanel {

    public static void main(String[] args) throws IOException {
        
        Graph graph = new Graph();

        Vertex v1 = graph.addVertex(0, 0);
        Vertex v2 = graph.addVertex(10, 10);
        Vertex v3 = graph.addVertex(0, 10);
        graph.addEdge(v1, v2, new LineSegment(v1.clone(), v2.clone()));
        graph.addEdge(v2, v3, new LineSegment(v2.clone(), v3.clone()));
                
        IPEReader read = IPEReader.clipboardReader();
		List<ReadItem> items = read.read();
        GraphConstruction.convertGeometriesToGraph(graph, items, DoubleUtil.EPS, 
                (OrientedGeometry og) -> new LineSegment(og.getStart(), og.getEnd()));
                                
        DrawPanel draw = new DrawPanel();
        draw.graph = graph;
        GUIUtil.makeMainFrame("Tutorial: Getting Started", draw, null);
    }

    private Graph graph;

    @Override
    protected void drawScene() {
        setSizeMode(SizeMode.VIEW);
        setStroke(Color.black, 1, Dashing.SOLID);
        setPointStyle(PointStyle.CIRCLE_WHITE, 4);
        draw(graph.getEdges());        
        draw(graph.getVertices());
    }

    @Override
    public Rectangle getBoundingRectangle() {
        return Rectangle.byBoundingBox(graph.getVertices());
    }

    @Override
    protected void mousePress(Vector loc, int button, boolean ctrl, boolean shift, boolean alt) {
        
    }

    @Override
    protected void keyPress(int keycode, boolean ctrl, boolean shift, boolean alt) {
        
    }

}

Clone this wiki locally