Examples of org.geotools.graph.structure.Graph

org.geotools.graph.structure.Graph
Represents a graph. A graph is a collection of nodes (verticies) connected by links called edges (arcs).

In most applications nodes of a graph represent the objects being modelled, and the edges represent the relationships between the objects. An example could be a polygon coverage in which one wishes to model a boundary sharing relationship. The following is an illustration.

In the above figure, the objects (nodes) are the polygons themselves, and the relationship (edges) between them is boundary sharing.

However, there exists types of graphs in which the roles are reversed and the edges are the objects, and the nodes are the relationships. An example of such a graph is the stream network shown below.

In the above figure, the objects (edges) are the stream segments and the relationship (nodes) between them is endpoint sharing. However, if desirable one could model the second case similar to the first. The resulting graph is shown below.

The Graph object is intended to serve as a container for a collection of nodes and edges. It does dont define or manage the relationship among the components it contains. @see Node @see Edge @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net @source $URL$

    
    m_serializer.setProperty(SerializedReaderWriter.FILENAME, victim.getAbsolutePath() );
      
      m_serializer.write(builder().getGraph());
      
      Graph before = builder().getGraph();
      Graph after = m_serializer.read();
      
      //ensure same number of nodes and edges
      assertTrue(before.getNodes().size() == after.getNodes().size());
      assertTrue(before.getEdges().size() == after.getEdges().size());
      
      //ensure same graph structure
      GraphVisitor visitor = new GraphVisitor() {
        public int visit(Graphable component) {
          Edge e = (Edge)component;
          
          assertTrue(e.getNodeA().getID() == e.getID());
          assertTrue(e.getNodeB().getID() == e.getID()+1);
          
          return(0);
        }
      };
      after.visitEdges(visitor);
      
      visitor = new GraphVisitor() {
        public int visit(Graphable component) {
          Node n = (Node)component;
          
          if (n.getDegree() == 1) {
            assertTrue(n.getID() == 0 || n.getID() == nnodes-1);  
          }
          else {
            assertTrue(n.getDegree() == 2);
            
            Edge e0 = (Edge)n.getEdges().get(0);
            Edge e1 = (Edge)n.getEdges().get(1);
            
            assertTrue(
              (e0.getID() == n.getID()-1 && e1.getID() == n.getID()) ||
              (e1.getID() == n.getID()-1 && e0.getID() == n.getID())
            );
            
          }
          
          return(0);
        }
      };
      after.visitNodes(visitor);
  }

View Full Code Here

      victim.deleteOnExit();
      m_serializer.setProperty(SerializedReaderWriter.FILENAME, victim.getAbsolutePath() );
      
      m_serializer.write(builder().getGraph());
      
      Graph before = builder().getGraph();
      Graph after = m_serializer.read();
      
      //ensure same number of nodes and edges
      assertTrue(before.getNodes().size() == after.getNodes().size());
      assertTrue(before.getEdges().size() == after.getEdges().size());
      
      //ensure same structure
      GraphVisitor visitor = new GraphVisitor() {
        public int visit(Graphable component) {
          Node n = (Node)component;
          String id = (String)n.getObject();
          
          assertTrue(obj2node.get(id) != null);
          
          StringTokenizer st = new StringTokenizer(id, ".");
          
          if (st.countTokens() == 1) {
            //root
            assertTrue(n.getDegree() == 2); 
            
            Node n0 = ((Edge)n.getEdges().get(0)).getOtherNode(n);
            Node n1 = ((Edge)n.getEdges().get(1)).getOtherNode(n);
            
            assertTrue(
              n0.getObject().equals("0.0") && n1.getObject().equals("0.1")
           || n0.getObject().equals("0.1") && n1.getObject().equals("0.0")
            );
          }
          else if (st.countTokens() == k+1) {
            //leaf
            assertTrue(n.getDegree() == 1);
            
            Node parent = ((Edge)n.getEdges().get(0)).getOtherNode(n);
            String parentid = (String)parent.getObject();
            
            assertTrue(parentid.equals(id.substring(0, id.length()-2)));   
          } 
          else {
            //internal
            assertTrue(n.getDegree() == 3);
            
            String id0 = ((Edge)n.getEdges().get(0)).getOtherNode(n).getObject()
                           .toString();
            String id1 = ((Edge)n.getEdges().get(1)).getOtherNode(n).getObject()
                           .toString();
            String id2 = ((Edge)n.getEdges().get(2)).getOtherNode(n).getObject()
                           .toString();
            
            String parentid = id.substring(0, id.length()-2);
            
            assertTrue(
             id0.equals(parentid) && id1.equals(id+".0") && id2.equals(id+".1")
          || id0.equals(parentid) && id2.equals(id+".0") && id1.equals(id+".1")
          || id1.equals(parentid) && id0.equals(id+".0") && id2.equals(id+".1")
          || id1.equals(parentid) && id2.equals(id+".0") && id0.equals(id+".1")
          || id2.equals(parentid) && id0.equals(id+".0") && id1.equals(id+".1")
          || id2.equals(parentid) && id1.equals(id+".0") && id0.equals(id+".1")
            );
          }  
          
          return(0);
        }
      };
      after.visitNodes(visitor);
      
    }
    catch(Exception e) {
      e.printStackTrace();
      assertTrue(false);

View Full Code Here

        victim.deleteOnExit();
      m_serializer.setProperty(SerializedReaderWriter.FILENAME, victim.getAbsolutePath());
      
      m_serializer.write(builder().getGraph());
      
      Graph before = builder().getGraph();
      Graph after = m_serializer.read();
      
      //ensure same number of nodes and edges
      assertTrue(before.getNodes().size() == after.getNodes().size());
      assertTrue(before.getEdges().size() == after.getEdges().size());
      
      GraphVisitor visitor = new GraphVisitor() {
        public int visit(Graphable component) {
          Node n = (Node)component;
          if (n.getID() == 0 || n.getID() == nnodes-1) 
            assertTrue(n.getDegree() == 0);
          else if (n.getID() == 1 || n.getID() == nnodes-2)
            assertTrue(n.getDegree() == 1);
          else assertTrue(n.getDegree() == 2); 
           
          return(0); 
        }
      };
      after.visitNodes(visitor);
    }
    catch(Exception e) {
      e.printStackTrace();
      assertTrue(false); 
    }

View Full Code Here

      e.setID(i-1);
      e.getNodeA().setID(i-1);
      e.getNodeB().setID(i);
    }
    
    Graph built = generator().getGraph();
    
    //ensure correct graph structure
    assertTrue(built.getEdges().size() == n);
    assertTrue(built.getNodes().size() == n+1);
    
    GraphVisitor visitor = new GraphVisitor() {
      public int visit(Graphable component) {
        DirectedNode node = (DirectedNode)component;
        Coordinate c = (Coordinate)node.getObject();
        
        if (node.getDegree() == 1) {
          assertTrue(
            (node.getID()==0&&node.getInDegree()==0&&node.getOutDegree()==1)|| 
            (node.getID()==n&&node.getInDegree()==1&&node.getOutDegree()==0)
          );
        }
        else {
          assertTrue(node.getInDegree() == 1 && node.getOutDegree() == 1);
        }
        
        assertTrue(
          c.x == base.x + node.getID() && c.y == base.y + node.getID() 
        );
        return(0);
      }
    };
    built.visitNodes(visitor);
    
    //ensure correct edge direction
    visitor = new GraphVisitor() {
      public int visit(Graphable component) {
        DirectedEdge e = (DirectedEdge)component;

View Full Code Here

    //complete the circle
    generator().add(
      new LineSegment(new Coordinate(base.x + n, base.y + n), base) 
    );
    
    Graph built = generator().getGraph();
    
    assertTrue(built.getEdges().size() == n+1);
    assertTrue(built.getNodes().size() == n+1);
    
    GraphVisitor visitor = new GraphVisitor() {
      public int visit(Graphable component) {
        DirectedNode node = (DirectedNode)component;
        assertTrue(node.getInDegree() == 1 && node.getOutDegree() == 1);

View Full Code Here

      e.setID(i-1);
      e.getNodeA().setID(i-1);
      e.getNodeB().setID(i);
    }
    
    Graph built = generator().getGraph();
    
    //ensure correct graph structure
    assertTrue(built.getEdges().size() == n);
    assertTrue(built.getNodes().size() == n+1);
    
    GraphVisitor visitor = new GraphVisitor() {
      public int visit(Graphable component) {
        Node node = (Node)component;
        Coordinate c = (Coordinate)node.getObject();
        
        if (node.getDegree() == 1) {
          assertTrue(node.getID() == 0 || node.getID() == n);
        }
        else {
          assertTrue(node.getDegree() == 2);
        }
        
        assertTrue(
          c.x == base.x + node.getID() && c.y == base.y + node.getID() 
        );
        return(0);
      }
    };
    built.visitNodes(visitor);
    
    visitor = new GraphVisitor() {
      public int visit(Graphable component) {
        Edge edge = (Edge)component;
        LineSegment line = (LineSegment)edge.getObject();
        
        assertTrue(line.p1.x == line.p0.x + 1 && line.p1.y == line.p0.y+1);
        
        return(0);
      }
    };
    built.visitEdges(visitor);
    
  }

View Full Code Here

    //complete the circle
    generator().add(
      new LineSegment(new Coordinate(base.x + n, base.y + n), base) 
    );
    
    Graph built = generator().getGraph();
    
    assertTrue(built.getEdges().size() == n+1);
    assertTrue(built.getNodes().size() == n+1);
    
    //all nodes should be of degree 2
    assertTrue(
      built.getNodesOfDegree(2).size() == built.getNodes().size()
    );
  }

View Full Code Here

      
      serializer().setProperty(SerializedReaderWriter.FILENAME, victim.getAbsolutePath());
      
      serializer().write(builder().getGraph());
      
      Graph before = builder().getGraph();
      Graph after = serializer().read();
      
      //ensure same number of nodes and edges
      assertTrue(before.getNodes().size() == after.getNodes().size());
      assertTrue(before.getEdges().size() == after.getEdges().size());


      //ensure two nodes of degree 1, and nnodes-2 nodes of degree 2
      assertTrue(after.getNodesOfDegree(1).size() == 2);
      assertTrue(after.getNodesOfDegree(2).size() == nnodes-2);
            
    }
    catch(Exception e) {
      e.printStackTrace();
      assertTrue(false);

View Full Code Here

      victim.deleteOnExit();
      serializer().setProperty(SerializedReaderWriter.FILENAME, victim.getAbsolutePath());
      
      serializer().write(builder().getGraph());
      
      Graph before = builder().getGraph();
      Graph after = serializer().read();
      
      assertTrue(after.getNodesOfDegree(2).size() == 1); //root
      assertTrue(after.getNodesOfDegree(3).size() == Math.pow(2,k)-2); //internal
      assertTrue(after.getNodesOfDegree(1).size() == Math.pow(2,k)); //leaves
    }
    catch(Exception e) {
      e.printStackTrace();
        
    }

View Full Code Here

0 1 2 3

TOP

Related Classes of org.geotools.graph.structure.Graph

org.geotools.graph.build.basic.BasicDirectedGraphBuilderTest

org.geotools.graph.build.basic.BasicGraphBuilderTest

org.geotools.graph.build.line.LineStringGraphGeneratorTest

org.geotools.graph.build.opt.OptDirectedGraphBuilderTest

org.geotools.graph.build.opt.OptGraphBuilderTest

org.geotools.graph.build.polygon.PolygonGraphGeneratorTest

org.geotools.graph.GraphExamples

org.geotools.graph.io.standard.BasicGraphSerializerTest

org.geotools.graph.io.standard.DirectedGraphSerializerTest

org.geotools.graph.io.standard.OptDirectedGraphSerializerTest

All source code are property of their respective owners. Java is a trademark of Sun Microsystems, Inc and owned by ORACLE Inc. Contact coftware#gmail.com.