jdsl.map.api
Interface OrderedGraph

All Superinterfaces:
Container, InspectableContainer, InspectableGraph, InspectableOrderedGraph, InspectablePositionalContainer, ModifiableGraph, PositionalContainer
All Known Implementing Classes:
IncidenceListOrderedGraph

public interface OrderedGraph
extends InspectableOrderedGraph, ModifiableGraph

An interface describing an ordered graph. An ordered graph is a graph in which the edges incident with each vertex are circularly ordered. The graph may be non-connected. Directed and undirected edges may coexist. Multiple edges are allowed, self-loops are not allowed.

Version:
$Id: OrderedGraph.java,v 1.9 2001/04/03 16:18:40 lv Exp $
Author:
Luca Vismara (lv)

Method Summary
 Edge attachVertex(Vertex v, Order order, Edge e, 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, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          Attaches a new vertex by inserting a new directed edge from an existing vertex in a specified order.
 Edge attachVertexTo(Vertex destination, Order order, Edge e, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          Attaches a new vertex by inserting a new directed edge to an existing vertex in a specified position.
 Edge insertDirectedEdge(Vertex v1, Order order1, Edge e1, Vertex v2, Order order2, Edge e2, java.lang.Object info)
          Inserts a new directed edge from an existing vertex to another in a specified order.
 Edge insertEdge(Vertex v1, Order order1, Edge e1, Vertex v2, Order order2, Edge e2, java.lang.Object info)
          Inserts a new edge between two existing vertices in a specified order.
 Vertex insertVertex(java.lang.Object info)
          Inserts a new isolated vertex.
 void moveEndVertex(Edge e1, Vertex v1, Vertex v2, Order o, Edge e2)
          Moves one of the endvertices of an edge to an existing vertex by inserting the edge in a specified order.
 java.lang.Object removeEdge(Edge e)
           
 java.lang.Object removeVertex(Vertex v)
          Removes a vertex and all its incident edges.
 Edge splitVertex(Vertex v, Edge e1, Edge e2, 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.InspectableOrderedGraph
nextIncidentEdge, nextIncidentEdge, prevIncidentEdge, prevIncidentEdge
 
Methods inherited from interface jdsl.graph.api.InspectableGraph
aCommonVertex, aConnectingEdge, adjacentVertices, adjacentVertices, anEdge, anIncidentEdge, anIncidentEdge, areAdjacent, 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, setDirectionFrom, setDirectionTo, splitEdge, unsplitEdge
 
Methods inherited from interface jdsl.core.api.PositionalContainer
swapElements
 
Methods inherited from interface jdsl.core.api.Container
newContainer, replaceElement
 

Method Detail

attachVertex

public Edge attachVertex(Vertex v,
                         Order order,
                         Edge e,
                         java.lang.Object vertexInfo,
                         java.lang.Object edgeInfo)
                  throws InvalidAccessorException,
                         InvalidEdgeException
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.BEFORE or Order.AFTER e around v
e - an edge incident with v or Edge.NONE if v is an isolated vertex
vertexInfo - the object to be stored in the new vertex
edgeInfo - the object to be stored in the new edge
Returns:
the new edge e'. To get the new vertex, use method opposite(v,e')
Throws:
InvalidAccessorException - if v or e is null or not contained in this graph
InvalidEdgeException - if e is not an edge incident with v, or if Edge.NONE is passed as e and v is not an isolated vertex, or if Edge.NONE is not passed as e and v is an isolated vertex

attachVertexFrom

public Edge attachVertexFrom(Vertex origin,
                             Order order,
                             Edge e,
                             java.lang.Object vertexInfo,
                             java.lang.Object edgeInfo)
                      throws InvalidAccessorException,
                             InvalidEdgeException
Attaches a new vertex by inserting a new directed edge from an existing vertex in a specified order. 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.BEFORE or Order.AFTER e around v
e - an edge incident with v or Edge.NONE if v is an isolated vertex
vertexInfo - the object to be stored in the new vertex
edgeInfo - the object to be stored in the new edge
Returns:
the new edge e'. To get the new vertex, use method opposite(v,e')
Throws:
InvalidAccessorException - if v or e is null or not contained in this graph
InvalidEdgeException - if e is not an edge incident with v, or if Edge.NONE is passed as e and v is not an isolated vertex, or if Edge.NONE is not passed as e and v is an isolated vertex

attachVertexTo

public Edge attachVertexTo(Vertex destination,
                           Order order,
                           Edge e,
                           java.lang.Object vertexInfo,
                           java.lang.Object edgeInfo)
                    throws InvalidVertexException,
                           InvalidEdgeException
Attaches a new vertex by inserting a new directed edge to an existing vertex in a specified position. 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.BEFORE or Order.AFTER e around v
e - an edge incident with v or Edge.NONE if v is an isolated vertex
vertexInfo - the object to be stored in the new vertex
edgeInfo - the object to be stored in the new edge
Returns:
the new edge e'. To get the new vertex, use method opposite(v,e')
Throws:
InvalidAccessorException - if v or e is null or not contained in this graph
InvalidEdgeException - if e is not an edge incident with v, or if Edge.NONE is passed as e and v is not an isolated vertex, or if Edge.NONE is not passed as e and v is an isolated vertex

insertEdge

public Edge insertEdge(Vertex v1,
                       Order order1,
                       Edge e1,
                       Vertex v2,
                       Order order2,
                       Edge e2,
                       java.lang.Object info)
                throws InvalidAccessorException,
                       InvalidVertexException,
                       InvalidEdgeException
Inserts a new edge between two existing vertices in a specified order. If any of the two vertices is an isolated vertex, Edge.NONE must be used as the edge parameter for it.
Parameters:
v1 - a vertex
order1 - indicates if the new edge is to be inserted Order.BEFORE or Order.AFTER e1 around v1
e1 - an edge incident with v1 or Edge.NONE if v1 is an isolated vertex
v2 - a vertex different form v1
order2 - indicates if the new edge is to be inserted Order.BEFORE or Order.AFTER e2 around v2
e2 - an edge incident with v2 or Edge.NONE if v2 is an isolated vertex
info - the object to be stored in the new edge
Returns:
the new edge
Throws:
InvalidAccessorException - if v1, v2, e1, or e2 is null or not contained in this graph
InvalidVertexException - if v1 and v2 are the same vertex
InvalidEdgeException - if e1 (e2) is not an edge incident with v1 (v2), or if Edge.NONE is passed as e1 (e2) and v1 (v2) is not an isolated vertex, or if Edge.NONE is not passed as e1 (e2) and v1 (v2) is an isolated vertex

insertDirectedEdge

public Edge insertDirectedEdge(Vertex v1,
                               Order order1,
                               Edge e1,
                               Vertex v2,
                               Order order2,
                               Edge e2,
                               java.lang.Object info)
                        throws InvalidAccessorException,
                               InvalidVertexException,
                               InvalidEdgeException
Inserts a new directed edge from an existing vertex to another in a specified order. If any of the two vertices is an isolated vertex, Edge.NONE must be used as the edge parameter for it.
Parameters:
v1 - the origin vertex
order1 - indicates if the new edge is to be inserted Order.BEFORE or Order.AFTER e1 around v1
e1 - an edge incident with v1 or Edge.NONE if v1 is an isolated vertex
v2 - the destination vertex, different from v1
order2 - indicates if the new edge is to be inserted Order.BEFORE or Order.AFTER e2 around v2
e2 - an edge incident with v2 or Edge.NONE if v2 is an isolated vertex
info - the object to be stored in the new edge
Returns:
the new edge
Throws:
InvalidAccessorException - if v1, v2, e1, or e2 is null or not contained in this graph
InvalidVertexException - if v1 and v2 are the same vertex
InvalidEdgeException - if e1 (e2) is not an edge incident with v1 (v2), or if Edge.NONE is passed as e1 (e2) and v1 (v2) is not an isolated vertex, or if Edge.NONE is not passed as e1 (e2) and v1 (v2) is an isolated vertex

splitVertex

public Edge splitVertex(Vertex v,
                        Edge e1,
                        Edge e2,
                        java.lang.Object edgeinfo)
                 throws InvalidAccessorException,
                        InvalidEdgeException
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 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
e2 - an edge incident with v or Edge.NONE if v is an isolated vertex
edgeinfo - the object to be stored in the new edge
Returns:
the new edge e'; to get the new vertices, use method endVertices(e')
Throws:
InvalidAccessorException - if v, e1, or e2 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

unsplitVertex

public Vertex unsplitVertex(Edge e,
                            java.lang.Object vertexinfo)
                     throws InvalidAccessorException
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
Returns:
the new vertex
Throws:
InvalidAccessorException - if e is null or not contained in this graph

insertVertex

public Vertex insertVertex(java.lang.Object info)
Inserts a new isolated vertex.
Parameters:
info - the object to be stored in the new vertex
Returns:
the new vertex

removeVertex

public java.lang.Object removeVertex(Vertex v)
                              throws InvalidAccessorException
Removes a vertex and all its incident edges. If you need the elements stored at the removed edges, get them beforehand.
Parameters:
v - the vertex to be deleted
Returns:
the element stored at v
Throws:
InvalidAccessorException - if v is null or not contained in this graph

removeEdge

public java.lang.Object removeEdge(Edge e)
                            throws InvalidAccessorException
Parameters:
e - the edge to be removed
Returns:
the element formerly stored at e
Throws:
InvalidAccessorException - if e is null or not contained in this graph

moveEndVertex

public void moveEndVertex(Edge e1,
                          Vertex v1,
                          Vertex v2,
                          Order o,
                          Edge e2)
                   throws InvalidVertexException,
                          InvalidEdgeException
Moves one of the endvertices of an edge to an existing vertex by inserting the edge in a specified order. The existing vertex may be the same endvertex; thus, this method can be used to rearrange the order of the edges around a vertex. If the existing vertex is an isolated vertex, Edge.NONE must be used as the second edge parameter.
Parameters:
e1 - an edge
v1 - an endvertex of e1
v2 - a vertex (not necessarily different from v1)
order - indicates if the new edge is to be inserted Order.BEFORE or Order.AFTER e2 around v2
e2 - an edge incident with v2 or Edge.NONE if v2 is an isolated vertex
Throws:
InvalidAccessorException - if e1, v1, or v2 is null or not contained in this graph
InvalidVertexException - if v1 is not an endvertex of e1 or if v2 is equal to the endvertex of e1 opposite to v1
InvalidEdgeException - if e2 is equal to e1, or if Edge.NONE is passed as e1, or if Edge.NONE is passed as e2 and v2 is not an isolated vertex, or if Edge.NONE is not passed as e2 and v2 is an isolated vertex