|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--jdsl.core.ref.AbstractPositionalContainer | +--jdsl.graph.ref.AbstractGraph | +--jdsl.graph.ref.IncidenceListGraph
An implementation of the Graph interface, including self-loops, parallel edges, and mixed directed and undirected edges. For specifications of the methods, see the documentation of the interfaces. The remainder of this description is about the implementation.
The following is a high-level description of the design; low-level details appear further below. The graph is implemented via a list of vertices and a list of edges. The nodes of these "global" lists are the vertices and edges of the graph, respectively. In addition to the global lists of vertices and edges, each vertex has a "local" list of its incident edges. Thus, each edge participates in two local lists (one for each endpoint) plus the global list. Each vertex participates in only the global list. Although sequential data structures are used to implement the graph, the graph conceptually consists of unordered sets; no guarantee is made about where in the various lists a given accessor appears.
This design forces most of the methods' time complexities. Insertion and deletion of vertices and edges are constant-time because the various doubly-linked lists can be modified in constant time. Adjacency queries are typically O(degrees of vertices involved). Iterations take time linear in the number of things iterated over.
The remainder of this description is about low-level details of the design, and efficiency tradeoffs of alternate designs.
The global list of edges exists to avoid having the duplicates in edges() that would result from asking all vertices for their incident edges (each edge would appear twice). For most other purposes, the only global list required would be the vertex list. An alternate design would get rid of the global edge list and would do a traversal to get edges(). This would save space at the cost of increasing the complexity of edges() from O(E) to O(V+E).
Both global lists are implemented with JDSL NodeSequences. In contrast, the local incidence lists at each vertex are implemented "by hand," with links in the ILEdges, for space efficiency. Internal methods that refer to those links also take a vertex, so the edge knows which set of links is being referred to (the set for one endpoint or the set for the other endpoint). Each local list includes a dummy edge to handle special cases (empty list, iterating till end of list, inserting at beginning of list).
To avoid the space overhead of having the global lists' positions point to vertex/edge objects, which would need to point back to the positions, the positions *are* the vertices/edges. This is accomplished by inheriting from the position implementation of the NodeSequence (called FNSNode) and using the posInsert* methods to put objects of the subclass into the global lists.
Research issues. The following are changes to the design that could be made if experiments indicated they were worthwhile:
Graph
,
Vertex
,
Edge
,
EdgeDirection
Inner classes inherited from class jdsl.graph.ref.AbstractGraph |
AbstractGraph.OO_to_O_MergerIterator |
Fields inherited from interface jdsl.graph.api.EdgeDirection |
IN, OUT, UNDIR |
Constructor Summary | |
IncidenceListGraph()
Creates a new IncidenceListGraph with default parameters. |
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 vertexInfo,
java.lang.Object edgeInfo)
O(1) |
Edge |
attachVertexFrom(Vertex v,
java.lang.Object vertexInfo,
java.lang.Object edgeInfo)
O(1) |
Edge |
attachVertexTo(Vertex v,
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(E) |
ObjectIterator |
elements()
O(V+E) |
Vertex[] |
endVertices(Edge e)
O(1) |
EdgeIterator |
incidentEdges(Vertex v)
O(degree) |
EdgeIterator |
incidentEdges(Vertex v,
int edgetype)
O(degree) |
Edge |
insertDirectedEdge(Vertex v1,
Vertex v2,
java.lang.Object elt)
O(1) |
Edge |
insertEdge(Vertex v1,
Vertex v2,
java.lang.Object elt)
O(1) |
Vertex |
insertVertex(java.lang.Object elt)
O(1) |
boolean |
isDirected(Edge e)
O(1) |
void |
makeUndirected(Edge e)
O(1) |
Container |
newContainer()
O(1) |
int |
numEdges()
O(1) |
int |
numVertices()
O(1) |
Vertex |
opposite(Vertex v,
Edge e)
O(1) |
Vertex |
origin(Edge e)
O(1) |
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 elt)
O(1) |
java.lang.String |
toString()
|
Edge |
unsplitEdge(Vertex v,
java.lang.Object o)
Note: the "two" edges incident on v cannot be the same edge. |
VertexIterator |
vertices()
O(V) |
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, 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 |
public IncidenceListGraph()
O(1)
Method Detail |
public Container newContainer()
newContainer
in interface Container
jdsl.core.api.Container
public java.lang.Object replaceElement(Accessor p, java.lang.Object newElement)
replaceElement
in interface Container
jdsl.core.api.Container
a
- Accessor in this containernewElement
- to be stored at aInvalidAccessorException
- if a is null or does not
belong to this containerpublic boolean contains(Accessor p)
contains
in interface InspectableContainer
jdsl.core.api.InspectableContainer
InvalidAccessorException
- if a is nullpublic ObjectIterator elements()
elements
in interface InspectableContainer
jdsl.core.api.InspectableContainer
public int numVertices()
numVertices
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
public int numEdges()
numEdges
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
public VertexIterator vertices()
vertices
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
public Vertex aVertex()
aVertex
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
public EdgeIterator edges()
edges
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
public Edge anEdge()
anEdge
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
public int degree(Vertex v) throws InvalidAccessorException
degree
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
v
- a vertexv
InvalidAccessorException
- if v
is
not contained in this graphpublic int degree(Vertex v, int edgetype) throws InvalidAccessorException
degree
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
v
- a vertexedgetype
- A constant from the EdgeDirection
interfacev
InvalidAccessorException
- if v
is
not contained in this graphEdgeDirection
public EdgeIterator incidentEdges(Vertex v) throws InvalidAccessorException
incidentEdges
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
v
- a vertexv
InvalidAccessorException
- if v
is not
contained in this graphpublic EdgeIterator incidentEdges(Vertex v, int edgetype) throws InvalidAccessorException
incidentEdges
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
v
- a vertexedgetype
- A constant from the EdgeDirection
interfacev
InvalidAccessorException
- if v
is not
contained in this graphEdgeDirection
public Edge anIncidentEdge(Vertex v) throws InvalidAccessorException
anIncidentEdge
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
v
- a vertexv
, or Edge.NONE if
there is no edge incident on v
InvalidAccessorException
- if v
is not
contained in this graphpublic Edge anIncidentEdge(Vertex v, int edgetype) throws InvalidAccessorException
anIncidentEdge
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
v
- a vertexedgetype
- A constant from the EdgeDirection
interfacev
,
or Edge.NONE if there is no such edge incident on v
InvalidAccessorException
- if v
is not
contained in this graphEdgeDirection
public Vertex[] endVertices(Edge e)
endVertices
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
e
- an edgee
;
if e
is directed, the first element of the array is the origin of e
and the second element is the destination of e
InvalidAccessorException
- if e
is not
contained in this graphpublic boolean areIncident(Vertex v, Edge e)
areIncident
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
v
- a vertexe
- an edgev
and e
are incident,
i.e., whether v
is an endvertex of e
InvalidAccessorException
- if either v
or
e
is not contained in this graphpublic Vertex opposite(Vertex v, Edge e)
opposite
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
v
- one endvertex of e
e
- an edgee
different from v
InvalidVertexException
- if v
is not an
endvertex of e
InvalidAccessorException
- if v
or e
is not contained in this graphpublic Vertex origin(Edge e)
origin
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
e
- an edgee
, if e
is directedInvalidEdgeException
- if e
is undirectedInvalidAccessorException
- if e
is not
contained in this graphpublic Vertex destination(Edge e)
destination
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
e
- an edgee
, if
e
is directedInvalidEdgeException
- if e
is undirectedInvalidAccessorException
- if e
is not
contained in this graphpublic Vertex insertVertex(java.lang.Object elt)
insertVertex
in interface Graph
jdsl.graph.api.Graph
element
- the object to be stored in the new vertexpublic java.lang.Object removeVertex(Vertex v) throws InvalidAccessorException
removeVertex
in interface Graph
jdsl.graph.api.Graph
v
- the vertex to be deletedv
InvalidAccessorException
- if the vertex does not
belong to this graphpublic Edge attachVertex(Vertex v, java.lang.Object vertexInfo, java.lang.Object edgeInfo) throws InvalidAccessorException
attachVertex
in interface Graph
jdsl.graph.api.Graph
v
- a vertexvertexElement
- the object to be stored in v
edgeElement
- the object to be stored in the new edgeopposite(v,e)
InvalidAccessorException
- if vertex to be attached to
does not belong to this graphpublic Edge attachVertexFrom(Vertex v, java.lang.Object vertexInfo, java.lang.Object edgeInfo) throws InvalidAccessorException
attachVertexFrom
in interface Graph
jdsl.graph.api.Graph
origin
- a vertexvertexElement
- the object to be stored in v
edgeElement
- the object to be stored in the new edgee
; to get the new vertex, use method
opposite(v,e)
InvalidAccessorException
- if origin
does not belong to this graphpublic Edge attachVertexTo(Vertex v, java.lang.Object vertexInfo, java.lang.Object edgeInfo) throws InvalidAccessorException
attachVertexTo
in interface Graph
jdsl.graph.api.Graph
destination
- a vertexvertexElement
- the object to be stored in v
edgeElement
- the object to be stored in the new edgee
; to get the new vertex, use method
opposite(v,e)
InvalidAccessorException
- if destination
does not belong to this graphpublic Edge insertEdge(Vertex v1, Vertex v2, java.lang.Object elt) throws InvalidAccessorException
insertEdge
in interface Graph
jdsl.graph.api.Graph
v1
- the first endvertexv2
- the second endvertexelement
- the object to be stored in the new edgeInvalidAccessorException
- if either v1
or
v2
does not belong to this graphpublic Edge insertDirectedEdge(Vertex v1, Vertex v2, java.lang.Object elt) throws InvalidAccessorException
insertDirectedEdge
in interface Graph
jdsl.graph.api.Graph
v1
- the origin vertexv2
- the destination vertexelement
- the object to be stored in the new edgeInvalidAccessorException
- if either v1
or
v2
does not belong to this graphpublic java.lang.Object removeEdge(Edge e) throws InvalidAccessorException
removeEdge
in interface Graph
jdsl.graph.api.Graph
e
- the edge to be removede
InvalidAccessorException
- if the edge does not belong
to this graphpublic Vertex splitEdge(Edge e, java.lang.Object elt) throws InvalidAccessorException
splitEdge
in interface ModifiableGraph
jdsl.graph.api.ModifiableGraph
e
- the edge to be splitvertElement
- the object to be stored in v
w
; to get the new edges, use method
incidentEdges(w)
InvalidAccessorException
- if the edge does not belong
to this graphpublic Edge unsplitEdge(Vertex v, java.lang.Object o) throws InvalidAccessorException, InvalidVertexException
O(1)
unsplitEdge
in interface ModifiableGraph
jdsl.graph.api.ModifiableGraph
v
- the vertex to be removededgeElement
- the element to be stored in the new edgeInvalidVertexException
- If the vertex is not of degree 2
or is of degree 2 but the "two" edges are a single self-loopInvalidAccessorException
- if the vertex does not
belong to this graphpublic boolean isDirected(Edge e)
isDirected
in interface InspectableGraph
jdsl.graph.api.InspectableGraph
e
- an edgetrue
if e
is directed,
false
otherwiseInvalidAccessorException
- if e
is not
contained in this graphpublic void setDirectionFrom(Edge e, Vertex v)
setDirectionFrom
in interface ModifiableGraph
jdsl.graph.api.ModifiableGraph
e
- an edgev
- an endvertex of e
InvalidVertexException
- if v
is not an
endvertex of e
but both v
and
e
belong to this graphInvalidAccessorException
- if either e
or
v
does not belong to this graphpublic void setDirectionTo(Edge e, Vertex v)
setDirectionTo
in interface ModifiableGraph
jdsl.graph.api.ModifiableGraph
e
- an edgev
- an endvertex of e
InvalidVertexException
- if v
is not an
endvertex of e
InvalidAccessorException
- if either e
or
v
does not belong to this graphpublic void makeUndirected(Edge e)
makeUndirected
in interface ModifiableGraph
jdsl.graph.api.ModifiableGraph
e
- an edgeInvalidAccessorException
- if the edge does not belong
to this graphpublic void reverseDirection(Edge e)
reverseDirection
in interface ModifiableGraph
jdsl.graph.api.ModifiableGraph
e
- an edgeInvalidEdgeException
- If the edge is undirectedInvalidAccessorException
- if the edge does not belong
to this graphpublic java.lang.String toString()
toString
in class java.lang.Object
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |