jdsl.map.api
Interface EmbeddedPlanarGraph

All Superinterfaces:
Container, InspectableContainer, InspectableEmbeddedPlanarGraph, InspectableGraph, InspectablePositionalContainer, ModifiableGraph, PositionalContainer
All Known Implementing Classes:
TripartiteEmbeddedPlanarGraph

public interface EmbeddedPlanarGraph
extends InspectableEmbeddedPlanarGraph, ModifiableGraph

An interface describing an embedded planar graph. In an embedded planar graph the ordering of the edges incident with a vertex is given by a planar embedding of the graph. The graph must be connected. Directed and undirected edges may coexist. Multiple edges and self-loops are allowed. A position and its dual position may store different elements (the actual behavior is implementation-dependent). If an edge is directed, its dual edge need not be (the actual behavior is implementation-dependent). Structural changes to the embedded planar graph affect also the dual.

Version:
$Id: EmbeddedPlanarGraph.java,v 1.12 2001/05/07 13:33:44 lv Exp $
Author:
Luca Vismara (lv)

Method Summary
 Edge attachVertex(Vertex v, Order order, Edge e, Face f, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          Attaches a new vertex to an existing vertex by inserting a new edge in a specified order.
 Edge attachVertexFrom(Vertex origin, Order order, Edge e, Face f, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          Attaches a new vertex by inserting a new directed edge in a specified order from an existing vertex.
 Edge attachVertexTo(Vertex destination, Order order, Edge e, Face f, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          Attaches a new vertex by inserting a new directed edge in a specified order to an existing vertex.
 EmbeddedPlanarGraph dual()
           
 Edge insertDirectedEdge(Vertex v1, Order order1, Edge e1, Vertex v2, Order order2, Edge e2, Face f, java.lang.Object info)
          Inserts a new directed edge from an existing origin vertex to an existing destination vertex in a specified order; the two vertices must be incident on a common face.
 Edge insertEdge(Vertex v1, Order order1, Edge e1, Vertex v2, Order order2, Edge e2, Face f, java.lang.Object info)
          Inserts a new edge between two existing vertices in a specified order; the two vertices must be incident with a common face.
 Face removeEdge(Edge e)
          Removes an edge.
 Face removeVertex(Vertex v)
          Removes a vertex and all its incident edges.
 void setDirectionFrom(Edge e, Vertex v)
          Sets the direction of an edge away from a vertex.
 void setDirectionTo(Edge e, Vertex v)
          Sets the direction of an edge towards a vertex.
 void setLeftFace(Edge e, Face f)
          Sets the direction of an edge so that a face is its left face.
 void setRightFace(Edge e, Face f)
          Sets the direction of an edge so that a face is its right face.
 Edge splitVertex(Vertex v, Edge e1, Face f1, Edge e2, Face f2, java.lang.Object edgeinfo)
          Splits an existing vertex into two new vertices connected by a new edge.
 Vertex unsplitVertex(Edge e, java.lang.Object vertexinfo)
          Merges two adjacent vertices and removes the edge(s) connecting them.
 
Methods inherited from interface jdsl.map.api.InspectableEmbeddedPlanarGraph
aCommonFace, aCommonFace, adjacentFaces, aFace, anIncidentEdge, anIncidentFace, anIncidentVertex, areAdjacent, areAdjacent, areIncident, areIncident, connectingEdges, degree, dual, dual, dual, faces, incidentEdge, incidentEdge, incidentEdges, incidentFace, incidentFaces, incidentFaces, incidentVertex, incidentVertices, inspectableDual, leftFace, numFaces, opposite, rightFace
 
Methods inherited from interface jdsl.graph.api.InspectableGraph
aCommonVertex, aConnectingEdge, adjacentVertices, adjacentVertices, anEdge, anIncidentEdge, anIncidentEdge, areAdjacent, areIncident, aVertex, connectingEdges, degree, degree, destination, directedEdges, edges, endVertices, incidentEdges, incidentEdges, isDirected, numEdges, numVertices, opposite, origin, undirectedEdges, vertices
 
Methods inherited from interface jdsl.core.api.InspectablePositionalContainer
positions
 
Methods inherited from interface jdsl.core.api.InspectableContainer
contains, elements, isEmpty, size
 
Methods inherited from interface jdsl.graph.api.ModifiableGraph
makeUndirected, reverseDirection, splitEdge, unsplitEdge
 
Methods inherited from interface jdsl.core.api.PositionalContainer
swapElements
 
Methods inherited from interface jdsl.core.api.Container
newContainer, replaceElement
 

Method Detail

setDirectionFrom

public void setDirectionFrom(Edge e,
                             Vertex v)
                      throws InvalidAccessorException,
                             InvalidEdgeException,
                             InvalidVertexException
Sets the direction of an edge away from a vertex. This method overrides the method from jdsl.graph.api.ModifiableGraph. It throws an InvalidEdgeException if the edge to be directed is a self-loop; in this case it is possible to direct the edge by setting its left or right face.
Specified by:
setDirectionFrom in interface ModifiableGraph
Parameters:
e - an edge
v - an endvertex of e
Throws:
InvalidAccessorException - if e or v is null or not contained in this graph
InvalidEdgeException - if e is a self-loop
InvalidVertexException - if v is not an endvertex of e
See Also:
setLeftFace(Edge,Face), setRightFace(Edge,Face)

setDirectionTo

public void setDirectionTo(Edge e,
                           Vertex v)
                    throws InvalidAccessorException,
                           InvalidEdgeException,
                           InvalidVertexException
Sets the direction of an edge towards a vertex. This method overrides the method from jdsl.graph.api.ModifiableGraph. It throws an InvalidEdgeException if the edge to be directed is a self-loop; in this case it is possible to direct the edge by setting its left or right face.
Specified by:
setDirectionTo in interface ModifiableGraph
Parameters:
e - an edge
v - an endvertex of e
Throws:
InvalidAccessorException - if e or v is null or not contained in this graph
InvalidEdgeException - if e is a self-loop
InvalidVertexException - if v is not an endvertex of e
See Also:
setLeftFace(Edge,Face), setRightFace(Edge,Face)

setLeftFace

public void setLeftFace(Edge e,
                        Face f)
                 throws InvalidAccessorException,
                        InvalidFaceException
Sets the direction of an edge so that a face is its left face. Useful for setting the direction of a self-loop.
Parameters:
e - an edge
f - a face incident with e
Throws:
InvalidAccessorException - if e or f is null or not contained in this graph
InvalidFaceException - if f is not incident with e

setRightFace

public void setRightFace(Edge e,
                         Face f)
                  throws InvalidAccessorException,
                         InvalidFaceException
Sets the direction of an edge so that a face is its right face. Useful for setting the direction of a self-loop.
Parameters:
e - an edge
f - a face incident with e
Throws:
InvalidAccessorException - if e or f is null or not contained in this graph
InvalidFaceException - if f is not incident with e

attachVertex

public Edge attachVertex(Vertex v,
                         Order order,
                         Edge e,
                         Face f,
                         java.lang.Object vertexInfo,
                         java.lang.Object edgeInfo)
                  throws InvalidAccessorException,
                         InvalidOrderException,
                         InvalidEdgeException,
                         InvalidFaceException
Attaches a new vertex to an existing vertex by inserting a new edge in a specified order. If the existing vertex is an isolated vertex, Edge.NONE must be used as the edge parameter.
Parameters:
v - a vertex
order - indicates if the new edge is to be inserted Order.AFTER_CW or Order.AFTER_CCW e around v
e - an edge incident with v or Edge.NONE if v is an isolated vertex
f - a face incident with e; this parameter is meaningful only if e is a self-loop, otherwise null can be passed; the new vertex and the new edge will be incident with this face
vertexInfo - the object to be stored in the new vertex and in its dual face
edgeInfo - the object to be stored in the new edge and in its dual edge
Returns:
the new edge e'. To get the new vertex, use method opposite(v,e')
Throws:
InvalidAccessorException - if v or e (or f, if meaningful) is null or not contained in this graph
InvalidOrderException - if order is different from Order.AFTER_CW or Order.AFTER_CCW
InvalidEdgeException - if e is not an edge incident with v, or if Edge.NONE is passed as the edge parameter and v is not an isolated vertex, or if Edge.NONE is not passed as the edge parameter and v is an isolated vertex
InvalidFaceException - if e is a self-loop and f is not a face incident with e
See Also:
InspectableGraph.opposite(Vertex,Edge)

attachVertexFrom

public Edge attachVertexFrom(Vertex origin,
                             Order order,
                             Edge e,
                             Face f,
                             java.lang.Object vertexInfo,
                             java.lang.Object edgeInfo)
                      throws InvalidAccessorException,
                             InvalidOrderException,
                             InvalidEdgeException,
                             InvalidFaceException
Attaches a new vertex by inserting a new directed edge in a specified order from an existing vertex. If the existing vertex is an isolated vertex, Edge.NONE must be used as the edge parameter.
Parameters:
origin - a vertex
order - indicates if the new edge is to be inserted Order.AFTER_CW or Order.AFTER_CCW e around v
e - an edge incident with v or Edge.NONE if v is an isolated vertex
f - a face incident with e; this parameter is meaningful only if e is a self-loop, otherwise null can be passed; the new vertex and the new edge will be incident with this face
vertexInfo - the object to be stored in the new vertex and in its dual face
edgeInfo - the object to be stored in the new edge and in its dual edge
Returns:
the new edge e'. To get the new vertex, use method opposite(v,e')
Throws:
InvalidAccessorException - if v or e (or f, if meaningful) is null or not contained in this graph
InvalidOrderException - if order is different from Order.AFTER_CW or Order.AFTER_CCW
InvalidEdgeException - if e is not an edge incident with v, or if Edge.NONE is passed as the edge parameter and v is not an isolated vertex, or if Edge.NONE is not passed as the edge parameter and v is an isolated vertex
InvalidFaceException - if e is a self-loop and f is not a face incident with e
See Also:
InspectableGraph.opposite(Vertex,Edge)

attachVertexTo

public Edge attachVertexTo(Vertex destination,
                           Order order,
                           Edge e,
                           Face f,
                           java.lang.Object vertexInfo,
                           java.lang.Object edgeInfo)
                    throws InvalidVertexException,
                           InvalidOrderException,
                           InvalidEdgeException,
                           InvalidFaceException
Attaches a new vertex by inserting a new directed edge in a specified order to an existing vertex. If the existing vertex is an isolated vertex, Edge.NONE must be used as the edge parameter.
Parameters:
destination - a vertex
order - indicates if the new edge is to be inserted Order.AFTER_CW or Order.AFTER_CCW e around v
e - an edge incident with v or Edge.NONE if v is an isolated vertex
f - a face incident with e; this parameter is meaningful only if e is a self-loop, otherwise null can be passed; the new vertex and the new edge will be incident with this face
vertexInfo - the object to be stored in the new vertex and in its dual face
edgeInfo - the object to be stored in the new edge and in its dual edge
Returns:
the new edge e'. To get the new vertex, use method opposite(v,e')
Throws:
InvalidAccessorException - if v or e (or f, if meaningful) is null or not contained in this graph
InvalidOrderException - if order is different from Order.AFTER_CW or Order.AFTER_CCW
InvalidEdgeException - if e is not an edge incident with v, or if Edge.NONE is passed as the edge parameter and v is not an isolated vertex, or if Edge.NONE is not passed as the edge parameter and v is an isolated vertex
InvalidFaceException - if e is a self-loop and f is not a face incident with e
See Also:
InspectableGraph.opposite(Vertex,Edge)

insertEdge

public Edge insertEdge(Vertex v1,
                       Order order1,
                       Edge e1,
                       Vertex v2,
                       Order order2,
                       Edge e2,
                       Face f,
                       java.lang.Object info)
                throws InvalidAccessorException,
                       InvalidOrderException,
                       InvalidEdgeException,
                       InvalidFaceException,
                       PlanarityViolationException
Inserts a new edge between two existing vertices in a specified order; the two vertices must be incident with a common face. The common face is removed; its element() can still be retrieved. Two new adjacent faces storing null are inserted.
Parameters:
v1 - the first endvertex
order1 - indicates if the new edge is to be inserted Order.AFTER_CW or Order.AFTER_CCW e1 around v1
e1 - an edge incident with v1 or Edge.NONE if v is an isolated vertex
v2 - the second endvertex
order2 - indicates if the new edge is to be inserted Order.AFTER_CW or Order.AFTER_CCW e2 around v2
e2 - an edge incident with v2 or Edge.NONE if v is an isolated vertex
f - a face incident with e1 (e2); this parameter is meaningful only if e1 (e2) is a self-loop, otherwise null can be passed; the new edge will split this face
info - the object to be stored in the new edge and in its dual edge
Returns:
the new edge
Throws:
InvalidAccessorException - if v1, e1, v2, or e2 (or f, if meaningful) is null or not contained in this graph
InvalidOrderException - if order is different from Order.AFTER_CW or Order.AFTER_CCW
InvalidEdgeException - if e1 (e2) is not an edge incident with v1 (v2), or if Edge.NONE is passed as the edge parameter and v1 (v2) is not an isolated vertex, or if Edge.NONE is not passed as the edge parameter and v1 (v2) is an isolated vertex
InvalidFaceException - if e1 (e2) is a self-loop and f is not a face incident with e1 (e2)
PlanarityViolationException - if the face identified by v1, order1, e1 is different from the face identified by v2, order2, e2

insertDirectedEdge

public Edge insertDirectedEdge(Vertex v1,
                               Order order1,
                               Edge e1,
                               Vertex v2,
                               Order order2,
                               Edge e2,
                               Face f,
                               java.lang.Object info)
                        throws InvalidAccessorException,
                               InvalidOrderException,
                               InvalidEdgeException,
                               InvalidFaceException,
                               PlanarityViolationException
Inserts a new directed edge from an existing origin vertex to an existing destination vertex in a specified order; the two vertices must be incident on a common face. The common face is removed; its element() can still be retrieved. Two new adjacent faces storing null are inserted.
Parameters:
v1 - the origin vertex
order1 - indicates if the new edge is to be inserted Order.AFTER_CW or Order.AFTER_CCW e1 around v1
e1 - an edge incident with v1 or Edge.NONE if v is an isolated vertex
v2 - the destination vertex
order2 - indicates if the new edge is to be inserted Order.AFTER_CW or Order.AFTER_CCW e2 around v2
e2 - an edge incident with v2 or Edge.NONE if v is an isolated vertex
f - a face incident with e1 (v2); this parameter is meaningful only if e1 (e2) is a self-loop, otherwise null can be passed; the new edge will split this face
info - the object to be stored in the new edge and in its dual edge
Returns:
the new edge
Throws:
InvalidAccessorException - if v1, e1, v2, or e2 (or f, if meaningful) is null or not contained in this graph
InvalidOrderException - if order is different from Order.AFTER_CW or Order.AFTER_CCW
InvalidEdgeException - if e1 (e2) is not an edge incident with v1 (v2), or if Edge.NONE is passed as the edge parameter and v1 (v2) is not an isolated vertex, or if Edge.NONE is not passed as the edge parameter and v1 (v2) is an isolated vertex
InvalidFaceException - if e1 (e2) is a self-loop and f is not a face incident with e1 (e2)
PlanarityViolationException - if the face identified by v1, order1, e1 is different from the face identified by v2, order2, e2

removeVertex

public Face removeVertex(Vertex v)
                  throws InvalidAccessorException,
                         ConnectivityViolationException
Removes a vertex and all its incident edges. Unless the vertex has degree 1, all the faces incident with the vertex are removed and a new face storing null is inserted. If you need the elements stored at the removed vertex, edges, and faces, get them beforehand.
Parameters:
v - the vertex to be removed
Returns:
the new face created by the removal of v, if degree(v) > 1; the face incident with v, if degree(v) == 1
Throws:
InvalidAccessorException - if v is null or not contained in this graph
ConnectivityViolationException - if the vertex removal disconnects the graph

removeEdge

public Face removeEdge(Edge e)
                throws InvalidAccessorException,
                       ConnectivityViolationException
Removes an edge. The two faces incident with the edge are removed and a new face storing null is inserted. If you need the elements stored at the removed edge and faces, get them beforehand.
Parameters:
e - the edge to be removed
Returns:
the new face created by the removal of e
Throws:
InvalidAccessorException - if e is null or not contained in this graph
ConnectivityViolationException - if the edge removal disconnects the graph

splitVertex

public Edge splitVertex(Vertex v,
                        Edge e1,
                        Face f1,
                        Edge e2,
                        Face f2,
                        java.lang.Object edgeinfo)
                 throws InvalidAccessorException,
                        InvalidEdgeException,
                        InvalidFaceException
Splits an existing vertex into two new vertices connected by a new edge. The old vertex is removed (if you need its element, get it beforehand). The new vertices store null elements, and the new edge stores the parameter edgeinfo. The edges incident with v from e1 Order.AFTER_CW to e2 (inclusive) are incident with one new vertex; the other edges are incident with the other new vertex.
          e1                 e1
       \ /            \     /
       -O-     --->   -O---O-
       / \            /     \
          e2                 e2
 
Parameters:
v - the vertex to be split
e1 - an edge incident with v or Edge.NONE if v is an isolated vertex
f1 - a face incident with e1; this parameter is meaningful only if e1 is a self-loop, otherwise null can be passed; the new edge will be incident with this face
e2 - an edge incident with v or Edge.NONE if v is an isolated vertex
f2 - a face incident with e2; this parameter is meaningful only if e2 is a self-loop, otherwise null can be passed; the new edge will be incident with this face
edgeinfo - the object to be stored in the new edge and in its dual edge
Returns:
the new edge e'; to get the new vertices, use method endVertices(e')
Throws:
InvalidAccessorException - if v, e1, or e2 (or f1 or f2, if meaningful) is null or not contained in this graph
InvalidEdgeException - if e1 or e2 is not an edge incident with v, or if Edge.NONE is passed as e1 or e2 and v is not an isolated vertex, or if Edge.NONE is not passed as e1 and e2 and v is an isolated vertex
InvalidFaceException - if e1 (e2) is a self-loop and f1 (f2) is not a face incident with e1 (e2)
See Also:
InspectableGraph.endVertices(Edge)

unsplitVertex

public Vertex unsplitVertex(Edge e,
                            java.lang.Object vertexinfo)
                     throws InvalidAccessorException,
                            InvalidEdgeException
Merges two adjacent vertices and removes the edge(s) connecting them. The edge(s) and the vertices are removed (if you need their elements, get them beforehand), and a new vertex is inserted in their place. The new vertex stores the vertexinfo parameter.
       \  e  /          \ /
       -O---O-   --->   -O-
       /     \          / \
 
Parameters:
e - the edge to be removed
vertexinfo - the object to be stored in the new vertex and in its dual face
Returns:
the new vertex
Throws:
InvalidAccessorException - if e is null or not contained in this graph
InvalidEdgeException - if e is a self-loop

dual

public EmbeddedPlanarGraph dual()
Returns:
the dual embedded planar graph