jdsl.graph.api
Interface Graph

All Superinterfaces:

Container, InspectableContainer, InspectableGraph, InspectablePositionalContainer, ModifiableGraph, PositionalContainer

All Known Implementing Classes:

IncidenceListGraph

public interface Graph

extends ModifiableGraph

An interface describing a combinatorial graph. Directed and undirected edges may coexist. Multiple parallel edges and self-loops are allowed. The graph can be disconnected. Note that the Vertex and Edge interfaces, which are subinterfaces of jdsl.core.api.Position, are empty interfaces, for type safety only.

Version:

$Id: Graph.java,v 1.8 2001/03/23 19:08:33 lv Exp $

Author:

Luca Vismara (lv)

See Also:

Vertex, Edge, ModifiableGraph

Method Summary

Edge	attachVertex(Vertex v, java.lang.Object vertexElement, java.lang.Object edgeElement) Attaches a new vertex, containing an object, to an existing vertex by inserting a new undirected edge.
Edge	attachVertexFrom(Vertex origin, java.lang.Object vertexElement, java.lang.Object edgeElement) Attaches a new vertex, containing an object, by inserting a new directed edge from an existing vertex.
Edge	attachVertexTo(Vertex destination, java.lang.Object vertexElement, java.lang.Object edgeElement) Attaches a new vertex, containing an object, by inserting a new directed edge to an existing vertex.
Edge	insertDirectedEdge(Vertex v1, Vertex v2, java.lang.Object element) Inserts a new directed edge from an existing vertex to another.
Edge	insertEdge(Vertex v1, Vertex v2, java.lang.Object element) Inserts a new undirected edge between two existing vertices.
Vertex	insertVertex(java.lang.Object element) Inserts a new isolated vertex.
java.lang.Object	removeEdge(Edge e)
java.lang.Object	removeVertex(Vertex v) Removes a vertex and all its incident edges.

Methods inherited from interface jdsl.graph.api.ModifiableGraph

makeUndirected, reverseDirection, setDirectionFrom, setDirectionTo, splitEdge, unsplitEdge

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.core.api.PositionalContainer

swapElements

Methods inherited from interface jdsl.core.api.Container

newContainer, replaceElement

Method Detail

insertVertex

public Vertex insertVertex(java.lang.Object element)

Inserts a new isolated vertex.

Parameters:

element - the object to be stored in the new vertex

Returns:

the new vertex

attachVertex

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

Attaches a new vertex, containing an object, to an existing vertex by inserting a new undirected edge. This is equivalent to calling insertVertex(.) followed by insertEdge(.).

Parameters:

v - a vertex

vertexElement - the object to be stored in v

edgeElement - 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 vertex to be attached to does not belong to this graph

attachVertexFrom

public Edge attachVertexFrom(Vertex origin,
                             java.lang.Object vertexElement,
                             java.lang.Object edgeElement)
                      throws InvalidAccessorException

Attaches a new vertex, containing an object, by inserting a new directed edge from an existing vertex. This is equivalent to calling insertVertex(.) followed by insertDirectedEdge(.).

Parameters:

origin - a vertex

vertexElement - the object to be stored in v

edgeElement - 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 origin does not belong to this graph

attachVertexTo

public Edge attachVertexTo(Vertex destination,
                           java.lang.Object vertexElement,
                           java.lang.Object edgeElement)
                    throws InvalidAccessorException

Attaches a new vertex, containing an object, by inserting a new directed edge to an existing vertex. This is equivalent to calling insertVertex(.) followed by insertDirectedEdge(.).

Parameters:

destination - a vertex

vertexElement - the object to be stored in v

edgeElement - 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 destination does not belong to this graph

insertEdge

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

Inserts a new undirected edge between two existing vertices.

Parameters:

v1 - the first endvertex

v2 - the second endvertex

element - the object to be stored in the new edge

Returns:

the new edge

Throws:

InvalidAccessorException - if either v1 or v2 does not belong to this graph

insertDirectedEdge

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

Inserts a new directed edge from an existing vertex to another.

Parameters:

v1 - the origin vertex

v2 - the destination vertex

element - the object to be stored in the new edge

Returns:

the new edge

Throws:

InvalidAccessorException - if either v1 or v2 does not belong to this graph

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 the vertex does not belong to 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 the edge does not belong to this graph