jdsl.map.ref
Class IncidenceListOrderedGraph

java.lang.Object
  |
  +--jdsl.core.ref.AbstractPositionalContainer
        |
        +--jdsl.graph.ref.AbstractGraph
              |
              +--jdsl.map.ref.IncidenceListOrderedGraph
All Implemented Interfaces:
Container, InspectableContainer, InspectableGraph, InspectableOrderedGraph, InspectablePositionalContainer, ModifiableGraph, OrderedGraph, PositionalContainer

public class IncidenceListOrderedGraph
extends AbstractGraph
implements OrderedGraph

Implements the OrderedGraph interface by a list of vertices, each of which has a circular sequence of edges. The graph also has a list of edges, in order to support certain operation more easily and quickly (for example, elements(), isElement(), size()).

The sequences store as their elements the positions of the graph. So verts_ stores ILOGVertex's as its elements, edges_ stores ILOGEdge's. The positions in turn know their position within the appropriate sequence, so that when the user gives the graph a vertex or an edge, the graph can extract that information in constant-time.

That is a source of some difficulty for the edges, since they are contained within the graph's edgelist, as well as within its two endvertices' incidence lists. This was resolved by requiring the caller to identify itself, so that the edge can then know which position to report.

This class does not claim to be the most efficient graph data structure possible: asymptotic improvements are possible in certain methods, and large constant factors could be fixed. Some places to improve:

Version:
$Id: IncidenceListOrderedGraph.java,v 1.11 2001/04/03 16:20:55 lv Exp $
Author:
Benoit Hudson, Luca Vismara (lv)

Inner classes inherited from class jdsl.graph.ref.AbstractGraph
AbstractGraph.OO_to_O_MergerIterator
 
Constructor Summary
IncidenceListOrderedGraph()
           
 
Method Summary
 Edge anEdge()
          O(1)
 Edge anIncidentEdge(Vertex v)
          O(1)
 Edge anIncidentEdge(Vertex v, int edgetype)
          O(degree)
 boolean areIncident(Vertex v, Edge e)
          O(1)
 Edge attachVertex(Vertex v, java.lang.Object vertexElement, java.lang.Object edgeElement)
           
 Edge attachVertex(Vertex v, Order order, Edge e, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)
 Edge attachVertexFrom(Vertex v, java.lang.Object vertexElement, java.lang.Object edgeElement)
           
 Edge attachVertexFrom(Vertex origin, Order order, Edge e, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)
 Edge attachVertexTo(Vertex v, java.lang.Object vertexElement, java.lang.Object edgeElement)
           
 Edge attachVertexTo(Vertex destination, Order order, Edge e, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)
 Vertex aVertex()
          O(1)
 boolean contains(Accessor p)
          O(1)
 int degree(Vertex v)
          O(1)
 int degree(Vertex v, int edgetype)
          O(degree)
 Vertex destination(Edge e)
          O(1)
 EdgeIterator edges()
          O(m)
 ObjectIterator elements()
          O(n+m)
 Vertex[] endVertices(Edge e)
          O(1)
 EdgeIterator incidentEdges(Vertex v)
          O(degree)
 EdgeIterator incidentEdges(Vertex v, int edgetype)
          O(degree)
 Edge insertDirectedEdge(Vertex v1, Order order1, Edge e1, Vertex v2, Order order2, Edge e2, java.lang.Object info)
          O(1)
 Edge insertDirectedEdge(Vertex v1, Vertex v2, java.lang.Object element)
           
 Edge insertEdge(Vertex v1, Order order1, Edge e1, Vertex v2, Order order2, Edge e2, java.lang.Object info)
          O(1)
 Edge insertEdge(Vertex v1, Vertex v2, java.lang.Object element)
           
 Vertex insertVertex(java.lang.Object elt)
          O(1)
 boolean isDirected(Edge e)
          O(1)
 void makeUndirected(Edge e)
          O(1)
 void moveEndVertex(Edge e1, Vertex v1, Vertex v2, Order order, Edge e2)
          O(1)
 Container newContainer()
          O(1)
 Edge nextIncidentEdge(Vertex v, Edge e)
          O(1)
 Edge nextIncidentEdge(Vertex v, Edge e, int edgetype)
          O(degree)
 int numEdges()
          O(1)
 int numVertices()
          O(1)
 Vertex opposite(Vertex v, Edge e)
          O(1)
 Vertex origin(Edge e)
          O(1)
 Edge prevIncidentEdge(Vertex v, Edge e)
          O(1)
 Edge prevIncidentEdge(Vertex v, Edge e, int edgetype)
          O(degree)
 java.lang.Object removeEdge(Edge e)
          O(1)
 java.lang.Object removeVertex(Vertex v)
          O(degree)
 java.lang.Object replaceElement(Accessor p, java.lang.Object newElement)
          O(1)
 void reverseDirection(Edge e)
          O(1)
 void setDirectionFrom(Edge e, Vertex v)
          O(1)
 void setDirectionTo(Edge e, Vertex v)
          O(1)
 Vertex splitEdge(Edge e, java.lang.Object info)
          O(1)
 Edge splitVertex(Vertex v, Edge e1, Edge e2, java.lang.Object edgeinfo)
          O(degree)
 Edge unsplitEdge(Vertex v, java.lang.Object info)
          O(1)
 Vertex unsplitVertex(Edge e, java.lang.Object vertexinfo)
          O(degree1+degree2)
 VertexIterator vertices()
          O(n)
 
Methods inherited from class jdsl.graph.ref.AbstractGraph
aCommonVertex, aConnectingEdge, adjacentVertices, adjacentVertices, areAdjacent, areAdjacent, connectingEdges, directedEdges, positions, size, 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, areAdjacent, connectingEdges, directedEdges, undirectedEdges
 
Methods inherited from interface jdsl.core.api.InspectablePositionalContainer
positions
 
Methods inherited from interface jdsl.core.api.InspectableContainer
isEmpty, size
 
Methods inherited from interface jdsl.core.api.PositionalContainer
swapElements
 

Constructor Detail

IncidenceListOrderedGraph

public IncidenceListOrderedGraph()
Method Detail

contains

public boolean contains(Accessor p)
                 throws InvalidAccessorException
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)
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

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)
                                throws InvalidAccessorException
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

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

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

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

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

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

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

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)
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

incidentEdges

public EdgeIterator incidentEdges(Vertex v)
                           throws InvalidAccessorException
O(degree)
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)
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

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

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

opposite

public Vertex opposite(Vertex v,
                       Edge e)
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

origin

public Vertex origin(Edge e)
              throws 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 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

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)
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

setDirectionFrom

public void setDirectionFrom(Edge e,
                             Vertex v)
                      throws InvalidVertexException,
                             InvalidAccessorException
O(1)
Specified by:
setDirectionFrom in interface ModifiableGraph
Following copied from interface: jdsl.graph.api.ModifiableGraph
Parameters:
e - an edge
v - an endvertex of e
Throws:
InvalidVertexException - if v is not an endvertex of e but both v and e belong to this graph
InvalidAccessorException - if either e or v does not belong to this graph

setDirectionTo

public void setDirectionTo(Edge e,
                           Vertex v)
                    throws InvalidEdgeException,
                           InvalidAccessorException
O(1)
Specified by:
setDirectionTo in interface ModifiableGraph
Following copied from interface: jdsl.graph.api.ModifiableGraph
Parameters:
e - an edge
v - an endvertex of e
Throws:
InvalidVertexException - if v is not an endvertex of e
InvalidAccessorException - if either e or v does not belong to this graph

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

removeEdge

public java.lang.Object removeEdge(Edge e)
                            throws InvalidAccessorException
O(1)
Specified by:
removeEdge in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
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

removeVertex

public java.lang.Object removeVertex(Vertex v)
                              throws InvalidAccessorException
O(degree)
Specified by:
removeVertex in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
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

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

prevIncidentEdge

public Edge prevIncidentEdge(Vertex v,
                             Edge e)
                      throws InvalidAccessorException,
                             InvalidEdgeException
O(1)
Specified by:
prevIncidentEdge in interface InspectableOrderedGraph
Following copied from interface: jdsl.map.api.InspectableOrderedGraph
Parameters:
v - a vertex
e - an edge incident with v
Returns:
the edge incident with v preceding e
Throws:
InvalidAccessorException - if v or e is not contained in this graph
InvalidEdgeException - if e is not an edge incident with v

prevIncidentEdge

public Edge prevIncidentEdge(Vertex v,
                             Edge e,
                             int edgetype)
                      throws InvalidAccessorException,
                             InvalidEdgeException
O(degree)
Specified by:
prevIncidentEdge in interface InspectableOrderedGraph
Following copied from interface: jdsl.map.api.InspectableOrderedGraph
Parameters:
v - a vertex
e - an edge incident with v
edgetype - a constant from the EdgeDirection interface
Returns:
the edge of the specified type incident with v preceding e, or Edge.NONE if no such edge exists
Throws:
InvalidAccessorException - if v or e is not contained in this graph
InvalidEdgeException - if e is not an edge incident with v

nextIncidentEdge

public Edge nextIncidentEdge(Vertex v,
                             Edge e)
                      throws InvalidAccessorException,
                             InvalidEdgeException
O(1)
Specified by:
nextIncidentEdge in interface InspectableOrderedGraph
Following copied from interface: jdsl.map.api.InspectableOrderedGraph
Parameters:
v - a vertex
e - an edge incident with v
Returns:
the edge incident with v following e
Throws:
InvalidAccessorException - if v or e is not contained in this graph
InvalidEdgeException - if e is not an edge incident with v

nextIncidentEdge

public Edge nextIncidentEdge(Vertex v,
                             Edge e,
                             int edgetype)
                      throws InvalidAccessorException,
                             InvalidEdgeException
O(degree)
Specified by:
nextIncidentEdge in interface InspectableOrderedGraph
Following copied from interface: jdsl.map.api.InspectableOrderedGraph
Parameters:
v - a vertex
e - an edge incident with v
edgetype - a constant from the EdgeDirection interface
Returns:
the edge of the specified type incident with v following e, or Edge.NONE if no such edge exists
Throws:
InvalidAccessorException - if v or e is not contained in this graph
InvalidEdgeException - if e is not an edge incident with v

insertVertex

public Vertex insertVertex(java.lang.Object elt)
O(1)
Specified by:
insertVertex in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
Parameters:
info - the object to be stored in the new vertex
Returns:
the new vertex

insertEdge

public Edge insertEdge(Vertex v1,
                       Order order1,
                       Edge e1,
                       Vertex v2,
                       Order order2,
                       Edge e2,
                       java.lang.Object info)
                throws InvalidEdgeException
O(1)
Specified by:
insertEdge in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
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)
O(1)
Specified by:
insertDirectedEdge in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
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

attachVertex

public Edge attachVertex(Vertex v,
                         Order order,
                         Edge e,
                         java.lang.Object vertexInfo,
                         java.lang.Object edgeInfo)
                  throws InvalidEdgeException
O(1)
Specified by:
attachVertex in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
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)
O(1)
Specified by:
attachVertexFrom in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
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)
O(1)
Specified by:
attachVertexTo in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
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

splitVertex

public Edge splitVertex(Vertex v,
                        Edge e1,
                        Edge e2,
                        java.lang.Object edgeinfo)
O(degree)
Specified by:
splitVertex in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
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)
O(degree1+degree2)
Specified by:
unsplitVertex in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
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

moveEndVertex

public void moveEndVertex(Edge e1,
                          Vertex v1,
                          Vertex v2,
                          Order order,
                          Edge e2)
                   throws InvalidVertexException,
                          InvalidEdgeException
O(1)
Specified by:
moveEndVertex in interface OrderedGraph
Following copied from interface: jdsl.map.api.OrderedGraph
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

attachVertex

public Edge attachVertex(Vertex v,
                         java.lang.Object vertexElement,
                         java.lang.Object edgeElement)

attachVertexFrom

public Edge attachVertexFrom(Vertex v,
                             java.lang.Object vertexElement,
                             java.lang.Object edgeElement)

attachVertexTo

public Edge attachVertexTo(Vertex v,
                           java.lang.Object vertexElement,
                           java.lang.Object edgeElement)

insertDirectedEdge

public Edge insertDirectedEdge(Vertex v1,
                               Vertex v2,
                               java.lang.Object element)

insertEdge

public Edge insertEdge(Vertex v1,
                       Vertex v2,
                       java.lang.Object element)