Search code examples
javaalgorithmpolygongraph-theoryplanar-graph

Java algorithm for finding faces in a graph

I have a planar graph which I am creating myself. I want to find the faces of this graph but I can't find a working algorithm for doing so. What I've done so far is using an algorithm to find all the cycles in the graph but this gives me all possible cycles and I've tried but not found a way to only sort the faces out. One of my ideas was to use Path2Ds contains method to see if another shape was overlapping but since the faces share nodes, that doesn't work. The picture below demonstrates what I want and the code after shows my reproductionable example. My graph and expected output

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class PolygonFinder {

    //  Graph modeled as list of edges
    static int[][] graph
            = {
                {1, 2}, {1, 6}, {1, 5}, {2, 6},
                {2, 3}, {3, 7}, {7, 4}, {3, 4},
                {5, 4}, {6, 5}
            };

    static List<int[]> cycles = new ArrayList<>();

    /**
     * @param args
     */
    public static void main(String[] args) {

        for (int[] graph1 : graph) {
            for (int j = 0; j < graph1.length; j++) {
                findNewCycles(new int[]{graph1[j]});
            }
        }

        cycles.stream().map(cy -> {
            String s = "" + cy[0];
            for (int i = 1; i < cy.length; i++) {
                s += "," + cy[i];
            }
            return s;
        }).forEachOrdered(s -> {
            System.out.println(s);
        });
    }

    static void findNewCycles(int[] path) {
        int n = path[0];
        int x;
        int[] sub = new int[path.length + 1];

        for (int[] graph1 : graph) {
            for (int y = 0; y <= 1; y++) {
                if (graph1[y] == n) {
                    x = graph1[(y + 1) % 2];
                    if (!visited(x, path)) //  neighbor node not on path yet
                    {
                        sub[0] = x;
                        System.arraycopy(path, 0, sub, 1, path.length);
                        //  explore extended path
                        findNewCycles(sub);
                    } else if ((path.length > 2) && (x == path[path.length - 1])) //  cycle found
                    {
                        int[] p = normalize(path);
                        int[] inv = invert(p);
                        if (isNew(p) && isNew(inv)) {
                            cycles.add(p);
                        }
                    }
                }
            }
        }
    }

    //  check of both arrays have same lengths and contents
    static Boolean equals(int[] a, int[] b) {
        Boolean ret = (a[0] == b[0]) && (a.length == b.length);

        for (int i = 1; ret && (i < a.length); i++) {
            if (a[i] != b[i]) {
                ret = false;
            }
        }

        return ret;
    }

    //  create a path array with reversed order
    static int[] invert(int[] path) {
        int[] p = new int[path.length];

        for (int i = 0; i < path.length; i++) {
            p[i] = path[path.length - 1 - i];
        }

        return normalize(p);
    }

    //  rotate cycle path such that it begins with the smallest node
    static int[] normalize(int[] path) {
        int[] p = new int[path.length];
        int x = smallest(path);
        int n;

        System.arraycopy(path, 0, p, 0, path.length);

        while (p[0] != x) {
            n = p[0];
            System.arraycopy(p, 1, p, 0, p.length - 1);
            p[p.length - 1] = n;
        }

        return p;
    }

    //  compare path against known cycles
    //  return true, iff path is not a known cycle
    static Boolean isNew(int[] path) {
        Boolean ret = true;

        for (int[] p : cycles) {
            if (equals(p, path)) {
                ret = false;
                break;
            }
        }

        return ret;
    }

    //  return the int of the array which is the smallest
    static int smallest(int[] path) {
        int min = path[0];

        for (int p : path) {
            if (p < min) {
                min = p;
            }
        }

        return min;
    }

    //  check if vertex n is contained in path
    static Boolean visited(int n, int[] path) {
        Boolean ret = false;

        for (int p : path) {
            if (p == n) {
                ret = true;
                break;
            }
        }

        return ret;
    }
}

The result after running the above code is:

1,6,2
1,5,6,2
1,5,4,7,3,2
1,6,5,4,7,3,2
1,5,4,3,2
1,6,5,4,3,2
1,5,4,7,3,2,6
1,5,4,3,2,6
1,5,6
2,3,7,4,5,6
2,3,4,5,6
3,4,7

One of my best attempts at solving this is with the following code. The coordinates comes from the picture at the top.

    List<Polygon> polys = new LinkedList<>();
    Polygon p1 = new Polygon();
    p1.addPoint(new Point2D.Double(-4, 4));
    p1.addPoint(new Point2D.Double(-1, 3));
    p1.addPoint(new Point2D.Double(-1, 5));
    Polygon p2 = new Polygon();
    p2.addPoint(new Point2D.Double(-4, 4));
    p2.addPoint(new Point2D.Double(0, -2));
    p2.addPoint(new Point2D.Double(-1, 3));
    p2.addPoint(new Point2D.Double(-1, 5));
    Polygon p3 = new Polygon();
    p3.addPoint(new Point2D.Double(-4, 4));
    p3.addPoint(new Point2D.Double(0, -2));
    p3.addPoint(new Point2D.Double(4, 1));
    p3.addPoint(new Point2D.Double(2, 2));
    p3.addPoint(new Point2D.Double(3, 4));
    p3.addPoint(new Point2D.Double(-1, 5));
    Polygon p4 = new Polygon();
    p4.addPoint(new Point2D.Double(-4, 4));
    p4.addPoint(new Point2D.Double(-1, 3));
    p4.addPoint(new Point2D.Double(0, -2));
    p4.addPoint(new Point2D.Double(4, 1));
    p4.addPoint(new Point2D.Double(2, 2));
    p4.addPoint(new Point2D.Double(3, 4));
    p4.addPoint(new Point2D.Double(-1, 5));
    Polygon p5 = new Polygon();
    p5.addPoint(new Point2D.Double(-4, 4));
    p5.addPoint(new Point2D.Double(0, -2));
    p5.addPoint(new Point2D.Double(4, 1));
    p5.addPoint(new Point2D.Double(3, 4));
    p5.addPoint(new Point2D.Double(-1, 5));
    Polygon p6 = new Polygon();
    p6.addPoint(new Point2D.Double(-4, 4));
    p6.addPoint(new Point2D.Double(-1, 3));
    p6.addPoint(new Point2D.Double(0, -2));
    p6.addPoint(new Point2D.Double(4, 1));
    p6.addPoint(new Point2D.Double(3, 4));
    p6.addPoint(new Point2D.Double(-1, 5));
    Polygon p7 = new Polygon();
    p7.addPoint(new Point2D.Double(-4, 4));
    p7.addPoint(new Point2D.Double(0, -2));
    p7.addPoint(new Point2D.Double(4, 1));
    p7.addPoint(new Point2D.Double(2, 2));
    p7.addPoint(new Point2D.Double(3, 4));
    p7.addPoint(new Point2D.Double(-1, 5));
    p7.addPoint(new Point2D.Double(-1, 3));
    Polygon p8 = new Polygon();
    p8.addPoint(new Point2D.Double(-4, 4));
    p8.addPoint(new Point2D.Double(0, -2));
    p8.addPoint(new Point2D.Double(4, 1));
    p8.addPoint(new Point2D.Double(3, 4));
    p8.addPoint(new Point2D.Double(-1, 5));
    p8.addPoint(new Point2D.Double(-1, 3));
    Polygon p9 = new Polygon();
    p9.addPoint(new Point2D.Double(-4, 4));
    p9.addPoint(new Point2D.Double(0, -2));
    p9.addPoint(new Point2D.Double(-1, 3));
    Polygon p10 = new Polygon();
    p10.addPoint(new Point2D.Double(-1, 5));
    p10.addPoint(new Point2D.Double(3, 4));
    p10.addPoint(new Point2D.Double(2, 2));
    p10.addPoint(new Point2D.Double(4, 1));
    p10.addPoint(new Point2D.Double(0, -2));
    p10.addPoint(new Point2D.Double(-1, 3));
    Polygon p11 = new Polygon();
    p11.addPoint(new Point2D.Double(-1, 5));
    p11.addPoint(new Point2D.Double(3, 4));
    p11.addPoint(new Point2D.Double(4, 1));
    p11.addPoint(new Point2D.Double(0, -2));
    p11.addPoint(new Point2D.Double(-1, 3));
    Polygon p12 = new Polygon();
    p12.addPoint(new Point2D.Double(3, 4));
    p12.addPoint(new Point2D.Double(4, 1));
    p12.addPoint(new Point2D.Double(2, 2));
    polys.add(p1);
    polys.add(p2);
    polys.add(p3);
    polys.add(p4);
    polys.add(p5);
    polys.add(p6);
    polys.add(p7);
    polys.add(p8);
    polys.add(p9);
    polys.add(p10);
    polys.add(p11);
    polys.add(p12);
    Set<Integer> toRemove = new HashSet<>();
    for (Polygon polyI : polys) {
        for (Polygon polyJ : polys) {
            if (polyI.equals(polyJ)) {
                continue;
            }
            if (polyI.contains(polyJ)) {
                toRemove.add(polys.indexOf(polyI));
            }
        }
    }
    List<Integer> list = new LinkedList<>(toRemove);
    Collections.sort(list);
    Collections.reverse(list);
    list.forEach((t) -> {
        polys.remove(t.intValue());
    });

    System.out.println("");
    polys.forEach((t) -> {
        System.out.println(t.getPoints());
    });

Polygons methods used is listed here.

@Override
public boolean contains(Point2D point) {
    return getPath().contains(point);
}

@Override
public boolean contains(IPolygon polygon) {
    List<Point2D> p2Points = polygon.getPoints();
    for (Point2D point : p2Points) {
        if (getPath().contains(point)) {
            if (!points.contains(point)) {
                return true;
            }
        }
    }
    return false;
}

private Path2D getPath() {
    Path2D path = new Path2D.Double();
    path.moveTo(points.get(0).getX(), points.get(0).getY());
    for (int i = 1; i < points.size(); i++) {
        path.lineTo(points.get(i).getX(), points.get(i).getY());
    }
    path.closePath();
    return path;
}

This code gives me the result below and the 2nd-4th is not wanted.

[Point2D.Double[-4.0, 4.0], Point2D.Double[-1.0, 3.0], Point2D.Double[-1.0, 5.0]]
[Point2D.Double[-4.0, 4.0], Point2D.Double[0.0, -2.0], Point2D.Double[-1.0, 3.0], Point2D.Double[-1.0, 5.0]]
[Point2D.Double[-4.0, 4.0], Point2D.Double[-1.0, 3.0], Point2D.Double[0.0, -2.0], Point2D.Double[4.0, 1.0], Point2D.Double[2.0, 2.0], Point2D.Double[3.0, 4.0], Point2D.Double[-1.0, 5.0]]
[Point2D.Double[-4.0, 4.0], Point2D.Double[0.0, -2.0], Point2D.Double[4.0, 1.0], Point2D.Double[2.0, 2.0], Point2D.Double[3.0, 4.0], Point2D.Double[-1.0, 5.0], Point2D.Double[-1.0, 3.0]]
[Point2D.Double[-4.0, 4.0], Point2D.Double[0.0, -2.0], Point2D.Double[-1.0, 3.0]]
[Point2D.Double[-1.0, 5.0], Point2D.Double[3.0, 4.0], Point2D.Double[2.0, 2.0], Point2D.Double[4.0, 1.0], Point2D.Double[0.0, -2.0], Point2D.Double[-1.0, 3.0]]
[Point2D.Double[3.0, 4.0], Point2D.Double[4.0, 1.0], Point2D.Double[2.0, 2.0]]
Solution

    1. For each edge, take the co-ordinates within your embedding of the edge's vertices and use them to calculate the angle of the edge using trigonometry.

      For example, the angle from (x1, y1) to (x2, y2) measured anti-clockwise from the positive x-axis is given by Math.atan2(y2-y1,x2-x1).

    2. For each vertex, create a cyclic edge ordering by sorting the edges by their angle. This could be stored as an array or you could use a cyclic list data structure.

    3. Pick an edge, follow it to an adjacent vertex and then follow the next adjacent clockwise edge and repeat following edges to the next vertex and then the next clockwise edge until you get back to the starting edge; then you have found a face of the graph.

    4. Repeat step 3 picking an unvisited edge or a visited edge in the opposite direction to previous and follow it in that same clockwise direction to find the next face. Repeat this until all the edges have been visited twice (once in each direction) and then you have found all the faces.

    In Java, that would be:

    import java.awt.geom.Point2D;
import java.awt.Polygon;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.stream.Collectors;
import java.text.MessageFormat;

public class GraphFaces
{
  static class Vertex
  {
    final int index;
    final Point2D point;
    final ArrayList<Edge> outboundEdges = new ArrayList<>();
    
    
    public Vertex( final int index, final Point2D point )
    {
      this.index = index;
      this.point = point;
    }
    
    public void addEdge( final Edge edge )
    {
      this.outboundEdges.add( edge );
    }
    
    public void sortEdges()
    {
      this.outboundEdges.sort((e1,e2)->Double.compare(e1.angle,e2.angle));
      
      Edge prev = this.outboundEdges.get(this.outboundEdges.size() - 1);
      for ( final Edge edge: this.outboundEdges )
      {
        edge.setNextEdge( prev );
        prev = edge;
      }
    }
    
    @Override
    public String toString()
    {
      return Integer.toString(this.index);
      // return MessageFormat.format("({0},{1})",this.point.getX(),this.point.getY());
    }
  }
  
  static class Edge
  {
    final Vertex from;
    final Vertex to;
    final double angle;
    boolean visited = false;
    Edge next = null;
    Edge reverse = null;
    
    public Edge( final Vertex from, final Vertex to )
    {
      this.from = from;
      this.to = to;
      this.angle = Math.atan2(to.point.getY() - from.point.getY(), to.point.getX() - from.point.getX());
      from.addEdge( this );
    }
    
    public Vertex getFrom()
    {
      return this.from;
    }

    public Vertex getTo()
    {
      return this.to;
    }

    public void setNextEdge( final Edge edge )
    {
      this.next = edge;
    }

    public void setReverseEdge( final Edge edge )
    {
      this.reverse = edge;
    }

    @Override
    public String toString()
    {
      return MessageFormat.format("{0} -> {1}", this.from, this.to);
    }
  }

  public static void main(final String[] args)
  {
    final Vertex[] vertices = {
      new Vertex( 1, new Point2D.Double(-4,+4) ),
      new Vertex( 2, new Point2D.Double(-1,+5) ),
      new Vertex( 3, new Point2D.Double(+3,+4) ),
      new Vertex( 4, new Point2D.Double(+4,+1) ),
      new Vertex( 5, new Point2D.Double(+0,-2) ),
      new Vertex( 6, new Point2D.Double(-1,+3) ),
      new Vertex( 7, new Point2D.Double(+2,+2) )
    };
     
    final int[][] graph = {
      {1, 2}, {1, 6}, {1, 5}, {2, 6}, {2, 3}, {3, 7}, {7, 4}, {3, 4}, {5, 4}, {6, 5}
    };
    
    final Edge[] edges = new Edge[2 * graph.length];

    for ( int i = 0; i < graph.length; i++ )
    {
      final Vertex from = vertices[graph[i][0]-1];
      final Vertex to = vertices[graph[i][1]-1];
      edges[2*i] = new Edge( from, to );
      edges[2*i+1] = new Edge( to, from );
      
      edges[2*i].setReverseEdge(edges[2*i+1]);
      edges[2*i+1].setReverseEdge(edges[2*i]);
    }
    
    
    for ( final Vertex vertex: vertices )
    {
      vertex.sortEdges();
    }
    
    final ArrayList<ArrayList<Edge>> faces = new ArrayList<>();
    for ( final Edge edge: edges )
    {
      if ( edge.visited )
      {
        continue;
      }
      final ArrayList<Edge> face = new ArrayList<>();
      faces.add( face );
      Edge e = edge;
      do
      {
        face.add(e);
        e.visited = true;
        e = e.reverse.next;
      }
      while (e != edge);
      
      System.out.println( face.stream().map(Edge::getFrom).collect(Collectors.toList()) );
    }
  }
}

    Which outputs:

    [1, 2, 3, 4, 5]
[2, 1, 6]
[6, 1, 5]
[2, 6, 5, 4, 7, 3]
[3, 7, 4]

    Note: this includes the exterior face of the graph.

    Alternatively, if you want to: test your graph for planarity; generate all possible embeddings of a (biconnected) graph; and generate a cyclic edge ordering for one (or more) of those embeddings then you can use the PhD thesis Planarity Testing by Path Addition, which includes complete Java source code in the appendices.