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.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 |
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 vertexorder
- indicates if the new edge is to be inserted
Order.BEFORE or Order.AFTER e around ve
- an edge incident with v or Edge.NONE if v is an isolated
vertexvertexInfo
- the object to be stored in the new vertexedgeInfo
- 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 graphInvalidEdgeException
- 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 vertexorder
- indicates if the new edge is to be inserted
Order.BEFORE or Order.AFTER e around ve
- an edge incident with v or Edge.NONE if v is an isolated
vertexvertexInfo
- the object to be stored in the new vertexedgeInfo
- 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 graphInvalidEdgeException
- 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 vertexorder
- indicates if the new edge is to be inserted
Order.BEFORE or Order.AFTER e around ve
- an edge incident with v or Edge.NONE if v is an isolated
vertexvertexInfo
- the object to be stored in the new vertexedgeInfo
- 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 graphInvalidEdgeException
- 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 vertexorder1
- indicates if the new edge is to be inserted
Order.BEFORE or Order.AFTER e1 around v1e1
- an edge incident with v1 or Edge.NONE if v1 is an
isolated vertexv2
- a vertex different form v1order2
- indicates if the new edge is to be inserted
Order.BEFORE or Order.AFTER e2 around v2e2
- an edge incident with v2 or Edge.NONE if v2 is an
isolated vertexinfo
- 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 graphInvalidVertexException
- if v1 and v2 are the same vertexInvalidEdgeException
- 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 vertexorder1
- indicates if the new edge is to be inserted
Order.BEFORE or Order.AFTER e1 around v1e1
- an edge incident with v1 or Edge.NONE if v1 is an
isolated vertexv2
- the destination vertex, different from v1order2
- indicates if the new edge is to be inserted
Order.BEFORE or Order.AFTER e2 around v2e2
- an edge incident with v2 or Edge.NONE if v2 is an
isolated vertexinfo
- 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 graphInvalidVertexException
- if v1 and v2 are the same vertexInvalidEdgeException
- 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 splite1
- an edge incident with v or Edge.NONE if v is an
isolated vertexe2
- an edge incident with v or Edge.NONE if v is an
isolated vertexedgeinfo
- 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 graphInvalidEdgeException
- 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 removedvertexinfo
- 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 edgev1
- an endvertex of e1v2
- a vertex (not necessarily different from v1)order
- indicates if the new edge is to be inserted
Order.BEFORE or Order.AFTER e2 around v2e2
- 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 graphInvalidVertexException
- if v1 is not an endvertex of e1
or if v2 is equal to the endvertex of e1 opposite to v1InvalidEdgeException
- 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