Docs for CS252 Spring 2002: Class TripartiteEmbeddedPlanarGraph

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: INNER | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

jdsl.map.ref
Class TripartiteEmbeddedPlanarGraph

java.lang.Object
  |
  +--jdsl.core.ref.AbstractPositionalContainer
        |
        +--jdsl.graph.ref.AbstractGraph
              |
              +--jdsl.map.ref.TripartiteEmbeddedPlanarGraph

All Implemented Interfaces:: Container, EmbeddedPlanarGraph, InspectableContainer, InspectableEmbeddedPlanarGraph, InspectableGraph, InspectablePositionalContainer, ModifiableGraph, PositionalContainer

public class TripartiteEmbeddedPlanarGraph
extends AbstractGraph
implements EmbeddedPlanarGraph

An implementation of an EmbeddedPlanarGraph via a tripartite OrderedGraph. The vertices of the OrderedGraph represent vertices, edges, and faces of the EmbeddedPlanarGraph. The edges of the OrderedGraph represent the incidence relationship between edges and vertices, and between edges and faces in the EmbeddedPlanarGraph. Each vertex of the OrderedGraph representing an edge of the EmbeddedPlanarGraph has four adjacent vertices: two representing vertices and two representing faces of the EmbeddedPlanarGraph. The convention adopted is the following:

the AFTER_CW ordering of the edges around the vertices of the EPG corresponds to the AFTER ordering of the edges around the vverts of the OG
the AFTER_RHS ordering of the edges around the faces of the EPG corresponds to the AFTER ordering of the edges around the fverts of the OG

Version:: $Id: TripartiteEmbeddedPlanarGraph.java,v 1.24 2001/10/18 15:39:06 lv Exp $
Author:: David Jackson, Baolin Yang, Benoit Hudson, Luca Vismara

Inner classes inherited from class jdsl.graph.ref.AbstractGraph

AbstractGraph.OO_to_O_MergerIterator

Field Summary

protected TripartiteEmbeddedPlanarGraph dual_
          The dual of this graph

protected static int DUAL_INDEX


protected int dualIndex_


protected static java.lang.Object MARKED


protected static int PRIMAL_INDEX


protected int thisIndex_


protected OrderedGraph tripartite_
          The underlying representation of the graph

Constructor Summary

TripartiteEmbeddedPlanarGraph()
          Creates an initial embedded planar graph consisting of a single vertex, no edges, and one face (the external face).

protected TripartiteEmbeddedPlanarGraph(TripartiteEmbeddedPlanarGraph primal)
          Invoked by createDual().

Method Summary

Face aCommonFace(Edge e1, Edge e2)
          O(1)

Face aCommonFace(Vertex v1, Vertex v2)
          O(degree(v1)+degree(v2))

FaceIterator adjacentFaces(Face f)
          O(degree(f))

Face aFace()
          in the current implementation there is always at least one face O(1)

Edge anEdge()
          O(1)

Edge anIncidentEdge(Face f)
          O(1)

Edge anIncidentEdge(Vertex v)
          O(1)

Edge anIncidentEdge(Vertex v, int edgetype)
          O(degree(v))

Face anIncidentFace(Vertex v)
          O(1)

Vertex anIncidentVertex(Face f)
          O(1)

boolean areAdjacent(Edge e1, Edge e2)
          O(1)

boolean areAdjacent(Face f1, Face f2)
          O(min(degree(f1),degree(f2)))

boolean areIncident(Edge e, Face f)
          O(1)

boolean areIncident(Vertex v, Edge e)
          O(1)

boolean areIncident(Vertex v, Face f)
          O(degree(v))

Edge attachVertex(Vertex v, Order order, Edge e, Face f, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)

Edge attachVertexFrom(Vertex origin, Order order, Edge e, Face f, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)

Edge attachVertexTo(Vertex destination, Order order, Edge e, Face f, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)

Vertex aVertex()
          O(1)

EdgeIterator connectingEdges(Face f1, Face f2)
          O(min(degree(f1),degree(f2)))

boolean contains(Accessor p)
          O(1)

protected void createDual()
          Allows overriding this class to create a modified dual.

int degree(Face f)
          O(1)

int degree(Vertex v)
          O(1)

int degree(Vertex v, int edgetype)
          O(degree(v))

Vertex destination(Edge e)
          O(1)

EmbeddedPlanarGraph dual()


Edge dual(Edge e)
          O(1)

Vertex dual(Face f)
          O(1)

Face dual(Vertex v)
          O(1)

EdgeIterator edges()
          O(m)

ObjectIterator elements()
          O(n+m+l)

Vertex[] endVertices(Edge e)
          O(1)

FaceIterator faces()
          O(l)

Edge incidentEdge(Face f, Order order, Edge e, Vertex v)
          O(1) Implemented through the dual graph

Edge incidentEdge(Vertex v, Order order, Edge e, Face f)
          O(1)

EdgeIterator incidentEdges(Face f)
          O(degree(f))

EdgeIterator incidentEdges(Vertex v)
          O(degree(v))

EdgeIterator incidentEdges(Vertex v, int edgetype)
          O(degree(v))

Face incidentFace(Vertex v, Order order, Edge e)


Face[] incidentFaces(Edge e)
          O(1)

FaceIterator incidentFaces(Vertex v)
          O(degree(v))

Vertex incidentVertex(Face f, Order order, Edge e)


VertexIterator incidentVertices(Face f)
          O(degree(f))

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)
          O(degree(face)), where face is the face split by the insertion of the new edge

InspectableEmbeddedPlanarGraph inspectableDual()
          O(1)

boolean isDirected(Edge e)
          O(1)

Face leftFace(Edge e)
          O(1)

static void main(java.lang.String[] argv)


void makeUndirected(Edge e)
          O(1)

Container newContainer()
          O(1)

int numEdges()
          O(1)

int numFaces()
          O(1)

int numVertices()
          O(1)

Face opposite(Face f, Edge e)
          O(1)

Vertex opposite(Vertex v, Edge e)
          O(1)

Vertex origin(Edge e)
          O(1)

PositionIterator positions()
          O(n+m+l)

Face removeEdge(Edge e)
          O(1)

Face removeVertex(Vertex v)
          O(degree(v))

java.lang.Object replaceElement(Accessor p, java.lang.Object newElement)
          O(1)

void reverseDirection(Edge e)
          O(1)

Face rightFace(Edge e)
          O(1)

void setDirectionFrom(Edge e, Vertex newOrigin)
          O(1)

void setDirectionTo(Edge e, Vertex newDestination)
          O(1)

void setLeftFace(Edge e, Face f)
          O(1)

void setRightFace(Edge e, Face f)
          O(1)

int size()
          O(1)

Vertex splitEdge(Edge e, java.lang.Object info)
          O(1)

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.

Edge unsplitEdge(Vertex v, java.lang.Object info)
          O(1)

Vertex unsplitVertex(Edge e, java.lang.Object vertexInfo)
          Merges two adjacent vertices and removes the edge(s) connecting them.

VertexIterator vertices()
          O(n)

Methods inherited from class jdsl.graph.ref.AbstractGraph

aCommonVertex, aConnectingEdge, adjacentVertices, adjacentVertices, areAdjacent, connectingEdges, directedEdges, undirectedEdges

Methods inherited from class jdsl.core.ref.AbstractPositionalContainer

isEmpty, swapElements

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface jdsl.graph.api.InspectableGraph

aCommonVertex, aConnectingEdge, adjacentVertices, adjacentVertices, areAdjacent, connectingEdges, directedEdges, undirectedEdges

Methods inherited from interface jdsl.core.api.InspectableContainer

isEmpty

Methods inherited from interface jdsl.core.api.PositionalContainer

swapElements

Field Detail

PRIMAL_INDEX

protected static final int PRIMAL_INDEX

DUAL_INDEX

protected static final int DUAL_INDEX

MARKED

protected static final java.lang.Object MARKED

thisIndex_

protected final int thisIndex_

dualIndex_

protected final int dualIndex_

tripartite_

protected OrderedGraph tripartite_

The underlying representation of the graph

dual_

protected TripartiteEmbeddedPlanarGraph dual_

The dual of this graph

Constructor Detail

TripartiteEmbeddedPlanarGraph

public TripartiteEmbeddedPlanarGraph()

Creates an initial embedded planar graph consisting of a single vertex, no edges, and one face (the external face).

TripartiteEmbeddedPlanarGraph

protected TripartiteEmbeddedPlanarGraph(TripartiteEmbeddedPlanarGraph primal)

Invoked by createDual().

Method Detail

createDual

protected void createDual()

Allows overriding this class to create a modified dual. This is pretty much required for a nice subclass of this.

contains

public boolean contains(Accessor p)

O(1)

Specified by:: contains in interface InspectableContainer

Following copied from interface: jdsl.core.api.InspectableContainer

Throws:: InvalidAccessorException - if a is null

elements

public ObjectIterator elements()

O(n+m+l)

Specified by:: elements in interface InspectableContainer

Following copied from interface: jdsl.core.api.InspectableContainer

Returns:: an iterator over all the elements stored in this container

size

public int size()

O(1)

Specified by:: size in interface InspectableContainer
Overrides:: size in class AbstractGraph

Following copied from interface: jdsl.core.api.InspectableContainer

Returns:: Number of elements stored by the container.

newContainer

public Container newContainer()

O(1)

Specified by:: newContainer in interface Container

Following copied from interface: jdsl.core.api.Container

Returns:: A new, empty Container of the same class as this one.

replaceElement

public java.lang.Object replaceElement(Accessor p,
                                       java.lang.Object newElement)

O(1)

Specified by:: replaceElement in interface Container

Following copied from interface: jdsl.core.api.Container

Parameters:: a - Accessor in this container; newElement - to be stored at a
Returns:: old element, previously stored at a
Throws:: InvalidAccessorException - if a is null or does not belong to this container

positions

public PositionIterator positions()

O(n+m+l)

Specified by:: positions in interface InspectablePositionalContainer
Overrides:: positions in class AbstractGraph

Following copied from interface: jdsl.core.api.InspectablePositionalContainer

Returns:: A PositionIterator over all positions in the container

degree

public int degree(Vertex v)
           throws InvalidAccessorException

O(1)

Specified by:: degree in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: v - a vertex
Returns:: the number of edges (directed and undirected) incident with v
Throws:: InvalidAccessorException - if v is not contained in this graph

degree

public int degree(Vertex v,
                  int edgetype)
           throws InvalidAccessorException

O(degree(v))

Specified by:: degree in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: v - a vertex; edgetype - A constant from the EdgeDirection interface
Returns:: the number of edges of the specified type incident with v
Throws:: InvalidAccessorException - if v is not contained in this graph
See Also:: EdgeDirection

numVertices

public int numVertices()

O(1)

Specified by:: numVertices in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:: the number of vertices

numEdges

public int numEdges()

O(1)

Specified by:: numEdges in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:: the number of edges

vertices

public VertexIterator vertices()

O(n)

Specified by:: vertices in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:: an iterator over all vertices in the graph

edges

public EdgeIterator edges()

O(m)

Specified by:: edges in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:: an iterator over all edges in the graph

endVertices

public Vertex[] endVertices(Edge e)
                     throws InvalidAccessorException

O(1)

Specified by:: endVertices in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: e - an edge
Returns:: an array (of size 2) containing the two endvertices of e; if e is directed, the first element of the array is the origin of e and the second element is the destination of e
Throws:: InvalidAccessorException - if e is not contained in this graph

origin

public Vertex origin(Edge e)
              throws InvalidAccessorException,
                     InvalidEdgeException

O(1)

Specified by:: origin in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: e - an edge
Returns:: the origin vertex of e, if e is directed
Throws:: InvalidEdgeException - if e is undirected; InvalidAccessorException - if e is not contained in this graph

destination

public Vertex destination(Edge e)
                   throws InvalidAccessorException,
                          InvalidEdgeException

O(1)

Specified by:: destination in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: e - an edge
Returns:: the destination vertex of e, if e is directed
Throws:: InvalidEdgeException - if e is undirected; InvalidAccessorException - if e is not contained in this graph

opposite

public Vertex opposite(Vertex v,
                       Edge e)
                throws InvalidVertexException,
                       InvalidAccessorException

O(1)

Specified by:: opposite in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: v - one endvertex of e; e - an edge
Returns:: the endvertex of e different from v
Throws:: InvalidVertexException - if v is not an endvertex of e; InvalidAccessorException - if v or e is not contained in this graph

isDirected

public boolean isDirected(Edge e)
                   throws InvalidAccessorException

O(1)

Specified by:: isDirected in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: e - an edge
Returns:: true if e is directed, false otherwise
Throws:: InvalidAccessorException - if e is not contained in this graph

aVertex

public Vertex aVertex()

O(1)

Specified by:: aVertex in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:: an arbitrary vertex, or Vertex.NONE if the graph is empty

anEdge

public Edge anEdge()

O(1)

Specified by:: anEdge in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Returns:: an arbitrary edge, or Edge.NONE if the graph has no edges

anIncidentEdge

public Edge anIncidentEdge(Vertex v)
                    throws InvalidAccessorException

O(1)

Specified by:: anIncidentEdge in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: v - a vertex
Returns:: any edge incident on v, or Edge.NONE if there is no edge incident on v
Throws:: InvalidAccessorException - if v is not contained in this graph

anIncidentEdge

public Edge anIncidentEdge(Vertex v,
                           int edgetype)
                    throws InvalidAccessorException

O(degree(v))

Specified by:: anIncidentEdge in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: v - a vertex; edgetype - A constant from the EdgeDirection interface
Returns:: any edge of the specified type incident on v, or Edge.NONE if there is no such edge incident on v
Throws:: InvalidAccessorException - if v is not contained in this graph
See Also:: EdgeDirection

areIncident

public boolean areIncident(Vertex v,
                           Edge e)
                    throws InvalidAccessorException

O(1)

Specified by:: areIncident in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: v - a vertex; e - an edge
Returns:: whether v and e are incident, i.e., whether v is an endvertex of e
Throws:: InvalidAccessorException - if either v or e is not contained in this graph

incidentEdges

public EdgeIterator incidentEdges(Vertex v)
                           throws InvalidAccessorException

O(degree(v))

Specified by:: incidentEdges in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: v - a vertex
Returns:: an iterator over all edges incident on v
Throws:: InvalidAccessorException - if v is not contained in this graph

incidentEdges

public EdgeIterator incidentEdges(Vertex v,
                                  int edgetype)
                           throws InvalidAccessorException

O(degree(v))

Specified by:: incidentEdges in interface InspectableGraph

Following copied from interface: jdsl.graph.api.InspectableGraph

Parameters:: v - a vertex; edgetype - A constant from the EdgeDirection interface
Returns:: an iterator over all edges of the specified type incident on v
Throws:: InvalidAccessorException - if v is not contained in this graph
See Also:: EdgeDirection

makeUndirected

public void makeUndirected(Edge e)
                    throws InvalidAccessorException

O(1)

Specified by:: makeUndirected in interface ModifiableGraph

Following copied from interface: jdsl.graph.api.ModifiableGraph

Parameters:: e - an edge
Throws:: InvalidAccessorException - if the edge does not belong to this graph

reverseDirection

public void reverseDirection(Edge e)
                      throws InvalidEdgeException,
                             InvalidAccessorException

O(1)

Specified by:: reverseDirection in interface ModifiableGraph

Following copied from interface: jdsl.graph.api.ModifiableGraph

Parameters:: e - an edge
Throws:: InvalidEdgeException - If the edge is undirected; InvalidAccessorException - if the edge does not belong to this graph

splitEdge

public Vertex splitEdge(Edge e,
                        java.lang.Object info)
                 throws InvalidAccessorException

O(1)

Specified by:: splitEdge in interface ModifiableGraph

Following copied from interface: jdsl.graph.api.ModifiableGraph

Parameters:: e - the edge to be split; vertElement - the object to be stored in v
Returns:: the new vertex w; to get the new edges, use method incidentEdges(w)
Throws:: InvalidAccessorException - if the edge does not belong to this graph

unsplitEdge

public Edge unsplitEdge(Vertex v,
                        java.lang.Object info)
                 throws InvalidAccessorException,
                        InvalidVertexException

O(1)

Specified by:: unsplitEdge in interface ModifiableGraph

Following copied from interface: jdsl.graph.api.ModifiableGraph

Parameters:: v - the vertex to be removed; edgeElement - the element to be stored in the new edge
Returns:: the new edge
Throws:: InvalidVertexException - If the vertex is not of degree 2 or is of degree 2 but the "two" edges are a single self-loop; InvalidAccessorException - if the vertex does not belong to this graph