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