ch.bfh.algo
Interface Graph<E,V>

All Superinterfaces:

Collection<V>, Container<V>, Iterable<V>

All Known Subinterfaces:

GenericGraph<E,V,PE,PV>

All Known Implementing Classes:

DefaultBinaryForest, DefaultForest, DefaultGraph, GenericAdjacencyListGraph, GenericBinaryForestGraph, GenericForestGraph

public interface Graph<E,V>
extends Container<V>

The Graph interface has the functionalities of both a directed and an undirected graph. A graph contains two types of elements: E and V. The E's are stored in the edges and the V's in the vertices. Edges and Vertices are seen as Positions, containing E's or V's. Here is the implementation of a BFS Traversal for a Graph.

    public static Sequence> bfsTraversal(Graph g){
        Sequence> buffer = new LinkedSequence>();
        Sequence> result = new LinkedSequence>();
        Set> bufferedVertices = new HashSet>();
        List> vertices = g.vertices();
        for(Position v : vertices){
            if(! bufferedVertices.contains(v)){
                buffer.add(v);
                bufferedVertices.add(v);
                while(! buffer.isEmpty()){
                    Position> pFirst= buffer.first();
                    v = (Position)buffer.element(pFirst);
                    buffer.delete(pFirst);
                    result.add(v);

                    for(Position v2 : g.adjacentVertices(v,Direction.ALL)){
                        if(!bufferedVertices.contains(v2) && v2 !=null){
                            bufferedVertices.add(v2);
                            buffer.add(v2);
                        }
                    }
                }
            }

        }
        return result;
    }
 

Version:

1.0

Author:

Juerg Kraehenbuehl (code) and Emmanuel Benoist (Javadoc)

Method Summary

List<Position<V>>	adjacentVertices(Position<?> vertex, Direction type) Returns a list of the vertices adjacent to vertex.
E	deleteEdge(Position<?> position) Deletes the edge position.
V	deleteVertex(Position<?> position) Deletes the vertex position.
Position<V>	destination(Position<?> edge) Returns the destination of the edge edge
void	detach(Position<?> edge, Position<?> vertex) Separates edge from one of its extremities, the vertex vertex.
E	edgeElement(Position<?> edge) Returns the element contained in edge
List<E>	edgeElements() Returns a list of all elements contained in the edges.
List<Position<E>>	edges() Returns a list of all the edges contained in the graph.
List<Position<E>>	edges(Direction type) Returns a list of all the edges of a desired type.
List<Position<E>>	incidentEdges(Position<?> vertex, Direction type) Returns a list of the incident edges of the vertex.
Position<E>	insertEdge(E element) Creates a new edge containing the element.
Position<E>	insertEdge(E element, Position<?> origin, Position<?> destination) Creates a new edge containing the element.
Position<V>	insertVertex(V element) Creates a new vertex containing the element.
boolean	isDirected(Position<?> edge) Verifies if an edge is directed.
Position<V>	opposite(Position<?> edge, Position<?> vertex) Returns the vertex that is opposite to the vertex vertex on the edge edge.
Position<V>	origin(Position<?> edge) Returns the origine of the edge edge
E	replaceEdge(Position<?> edge, E element) Replaces the element contained in the edge edge by element.
V	replaceVertex(Position<?> vertex, V element) Replaces the element contained in the vertex vertex by element.
void	reverse(Position<?> edge) Exchanges the two extremities of an edge.
void	setDestination(Position<?> edge, Position<?> vertex) Defines the vertex vertex to be the new destination of the edge edge.
void	setDirected(Position<?> edge) Defines the edge as a directed edge.
void	setOrigin(Position<?> edge, Position<?> vertex) Defines the vertex vertex to be the new origin of the edge edge.
void	setUndirected(Position<?> edge) Defines the edge as an undirected edge.
void	swapEdge(Position<?> edge0, Position<?> edge1) Exchanges the content of the two edges edge0 and edge1.
void	swapVertex(Position<?> vertex0, Position<?> vertex1) Exchanges the content of the two vertices vertex0 and vertex1.
V	vertexElement(Position<?> vertex) Returns the element contained in vertex
List<V>	vertexElements() Returns a list of all elements contained in the vertices.
List<Position<V>>	vertices() Returns a list of all the vertices contained in the graph.

Methods inherited from interface ch.bfh.algo.Container

delete, element, encloses, insert, positionIterator, replace, swap

Methods inherited from interface java.util.Collection

add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray

Method Detail

insertVertex

Position<V> insertVertex(V element)

Creates a new vertex containing the element. This vertex is then returned (it is a Position<V>).

Parameters:

element - the element to be used as a label for the new vertex.

Returns:

the new vertex Position

insertEdge

Position<E> insertEdge(E element)

Creates a new edge containing the element. This edge is then returned (it is a Position<E>). The edge does not have any extremities (adjacent vertices). They have to be defined afterward.

Parameters:

element - the element to be used as a label for the new edge.

Returns:

the new edge Position

insertEdge

Position<E> insertEdge(E element,
                       Position<?> origin,
                       Position<?> destination)
                       throws InvalidAccessorException

Creates a new edge containing the element. Which extremities are the two vertices origin and destination. This edge is then returned (it is a Position<E>). If the graph is directed, the new edge is directed; if we have an undirected graph, then the new edge is also undirected.

Parameters:

element - the element to be used as a label for the new edge.

origin - the vertex that will be the origin of the new edge

destination - the vertex that will become the destination of the new edge.

Returns:

the new edge Position

Throws:

InvalidAccessorException

deleteEdge

E deleteEdge(Position<?> position)
             throws InvalidAccessorException

Deletes the edge position. The edge is automatically removed from the two vertices at its extremities.

Parameters:

position - the edge to be removed from the graph.

Returns:

the element contained by the removed edge.

Throws:

InvalidAccessorException - if the position is not a valide edge of this graph.

deleteVertex

V deleteVertex(Position<?> position)
               throws InvalidAccessorException

Deletes the vertex position. This also removes all the edges that had position for an extremity.

Parameters:

position - the vertex to be removed from the graph.

Returns:

the element contained by the removed vertex.

Throws:

InvalidAccessorException - if the position is not a valide vertex of this graph.

replaceEdge

E replaceEdge(Position<?> edge,
              E element)
              throws InvalidAccessorException

Replaces the element contained in the edge edge by element.

Parameters:

edge - the edge whose element will be replaced;

element - the new label of the edge.

Returns:

the old value of edge that has just be replaced.

Throws:

InvalidAccessorException - if the position is not a valide edge of this graph.

replaceVertex

V replaceVertex(Position<?> vertex,
                V element)
                throws InvalidAccessorException

Replaces the element contained in the vertex vertex by element.

Parameters:

vertex - the vertex whose element will be replaced;

element - the new label of the vertex.

Returns:

the old value of vertex that has just be replaced.

Throws:

InvalidAccessorException - if the position is not a valide edge of this graph.

swapEdge

void swapEdge(Position<?> edge0,
              Position<?> edge1)
              throws InvalidAccessorException

Exchanges the content of the two edges edge0 and edge1.

Parameters:

edge0 - the first edge

edge1 - the second edge

Throws:

InvalidAccessorException - if one of the edges is not a valide edge of this graph.

swapVertex

void swapVertex(Position<?> vertex0,
                Position<?> vertex1)
                throws InvalidAccessorException

Exchanges the content of the two vertices vertex0 and vertex1.

Parameters:

vertex0 - the first vertex

vertex1 - the second vertex

Throws:

InvalidAccessorException - if one of the vertices is not a valide vertex of this graph.

setOrigin

void setOrigin(Position<?> edge,
               Position<?> vertex)
               throws InvalidAccessorException

Defines the vertex vertex to be the new origin of the edge edge. If the edge is undirected, origin is simply one of the two extremities.

Parameters:

edge - the edge whose origin is being defined

vertex - the new origin

Throws:

InvalidAccessorException - if the vertex or the edge do not belong to the graph

setDestination

void setDestination(Position<?> edge,
                    Position<?> vertex)
                    throws InvalidAccessorException

Defines the vertex vertex to be the new destination of the edge edge. If the edge is undirected, destination is simply one of the two extremities.

Parameters:

edge - the edge whose destination is being defined

vertex - the new destination.

Throws:

InvalidAccessorException - if the vertex or the edge do not belong to the graph

origin

Position<V> origin(Position<?> edge)
                   throws InvalidAccessorException

Returns the origine of the edge edge

Parameters:

edge - an edge

Returns:

the origin (a vertex) of the edge.

Throws:

InvalidAccessorException - if the vertex or the edge do not belong to the graph

destination

Position<V> destination(Position<?> edge)
                        throws InvalidAccessorException

Returns the destination of the edge edge

Parameters:

edge - an edge

Returns:

the destination (a vertex) of the edge.

Throws:

InvalidAccessorException - if the vertex or the edge do not belong to the graph

detach

void detach(Position<?> edge,
            Position<?> vertex)
            throws InvalidAccessorException

Separates edge from one of its extremities, the vertex vertex.

Parameters:

edge - an edge

vertex - one of the two extremities of edge

Throws:

InvalidAccessorException - if the vertex or the edge do not belong to the graph, or if the edge is not incident to the vertex.

setDirected

void setDirected(Position<?> edge)
                 throws InvalidAccessorException

Defines the edge as a directed edge.

Parameters:

edge - an edge

Throws:

InvalidAccessorException - if the edge does not belong to the graph

setUndirected

void setUndirected(Position<?> edge)
                   throws InvalidAccessorException

Defines the edge as an undirected edge.

Parameters:

edge - an edge

Throws:

InvalidAccessorException - if the edge does not belong to the graph

isDirected

boolean isDirected(Position<?> edge)
                   throws InvalidAccessorException

Verifies if an edge is directed.

Parameters:

edge - an edge

Returns:

true if edge is directed

Throws:

InvalidAccessorException - if the edge does not belong to the graph

reverse

void reverse(Position<?> edge)
             throws InvalidAccessorException

Exchanges the two extremities of an edge. The origin becomes the destination and vice versa.

Parameters:

edge - an edge

Throws:

InvalidAccessorException - if the edge does not belong to the graph

opposite

Position<V> opposite(Position<?> edge,
                     Position<?> vertex)
                     throws InvalidAccessorException

Returns the vertex that is opposite to the vertex vertex on the edge edge. It vertex is the origin of edge, then it returns its destination, and it returns its origin if vertex is the destination of edge.

Parameters:

edge - an edge

Throws:

InvalidAccessorException - if the edge does not belong to the graph

vertices

List<Position<V>> vertices()

Returns a list of all the vertices contained in the graph.

Returns:

the list of all vertices

edges

List<Position<E>> edges()

Returns a list of all the edges contained in the graph.

Returns:

the list of all edges

edges

List<Position<E>> edges(Direction type)

Returns a list of all the edges of a desired type. type can have the following values:

• Direction.DIRECTED
• Direction.UNDIRECTED
• Direction.ALL

Parameters:

type - the type of the edges

Returns:

the list of all edges

incidentEdges

List<Position<E>> incidentEdges(Position<?> vertex,
                                Direction type)
                                throws InvalidAccessorException

Returns a list of the incident edges of the vertex. Depending on the value of type, the result is different.

• if type==Direction.IN the method returns the in incident edges
• if type==Direction.OUT the method returns the out incident edges
• and if type==Direction.ALL then the method returns all the incident edges (including the undirected ones).

Parameters:

vertex - the vertex

type - the type of the edges

Returns:

the list of all edges

Throws:

InvalidAccessorException

adjacentVertices

List<Position<V>> adjacentVertices(Position<?> vertex,
                                   Direction type)
                                   throws InvalidAccessorException

Returns a list of the vertices adjacent to vertex. Depending on the value of type, the result is different.

• if type==Direction.IN the method returns the vertices linked to vertex through an in incident edge
• if type==Direction.OUT the method returns the vertices linked to vertex through an out incident edges
• and if type==Direction.ALL then the method returns all the adjacent vertices.

Parameters:

vertex - the vertex

type - the type of the edges

Returns:

the list of adjacent vertices

Throws:

InvalidAccessorException

vertexElements

List<V> vertexElements()

Returns a list of all elements contained in the vertices.

Returns:

the list of elements contained in the vertices

edgeElements

List<E> edgeElements()

Returns a list of all elements contained in the edges.

Returns:

the list of elements contained in the edges

vertexElement

V vertexElement(Position<?> vertex)
                throws InvalidAccessorException

Returns the element contained in vertex

Parameters:

vertex - the vertex containing the element

Returns:

element contained in the vertex

Throws:

InvalidAccessorException

edgeElement

E edgeElement(Position<?> edge)
              throws InvalidAccessorException

Returns the element contained in edge

Parameters:

edge - the edge containing the element

Returns:

element contained in the edge

Throws:

InvalidAccessorException