ch.bfh.algo.core.graph
Class GenericAdjacencyListGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<E>
          java.util.AbstractSequentialList<E>
              ch.bfh.algo.core.sequence.GenericLinkedSequence<V,PV>
                  ch.bfh.algo.core.graph.GenericAdjacencyListGraph<E,V,PE,PV>

All Implemented Interfaces:

Container<V>, GenericContainer<V,PV>, GenericGraph<E,V,PE,PV>, GenericSequence<V,PV>, Graph<E,V>, Sequence<V>, Iterable<V>, Collection<V>, List<V>

Direct Known Subclasses:

DefaultGraph, GenericForestGraph

public class GenericAdjacencyListGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>
extends GenericLinkedSequence<V,PV>
implements GenericGraph<E,V,PE,PV>

Field Summary

protected GraphFactory<PE,PV>

factory

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

GenericAdjacencyListGraph(GraphFactory<PE,PV> factory, boolean directed)

Method Summary

PositionList<V,PV>	adjacentVertices(Position<?> vertex, Direction type) Returns a list of the vertices adjacent to vertex.
PositionList<V,PV>	adjacentVertices(PV vertex, Direction type)
V	delete(PV position)
E	deleteEdge(PE position)
E	deleteEdge(Position<?> position) Deletes the edge position.
V	deleteVertex(Position<?> position) Deletes the vertex position.
V	deleteVertex(PV position)
PV	destination(PE edge)
PV	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.
void	detachVertex(PE edge, PV vertex)
E	edgeElement(PE edge)
E	edgeElement(Position<?> edge) Returns the element contained in edge
GenericSequence<E,PE>	edgeElements() Returns a list of all elements contained in the edges.
PositionList<E,PE>	edges() Returns a list of all the edges contained in the graph.
PositionList<E,PE>	edges(Direction type) Returns a list of all the edges of a desired type.
GraphFactory<PE,PV>	getFactory()
PositionList<E,PE>	incidentEdges(Position<?> vertex, Direction type) Returns a list of the incident edges of the vertex.
PositionList<E,PE>	incidentEdges(PV vertex, Direction type)
PV	insertAfter(PV position, V element)
PV	insertBefore(PV position, V element)
protected PV	insertBetween(PV previous, PV next, V element, PV position)
PE	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.
PE	insertEdge(E element, PV origin, PV destination)
PV	insertVertex(V element) Creates a new vertex containing the element.
boolean	isDirected(PE edge)
boolean	isDirected(Position<?> edge) Verifies if an edge is directed.
PV	opposite(PE edge, PV vertex)
PV	opposite(Position<?> edge, Position<?> vertex) Returns the vertex that is opposite to the vertex vertex on the edge edge.
PV	origin(PE edge)
PV	origin(Position<?> edge) Returns the origine of the edge edge
PositionListIterator<V,PV>	positionListIterator() The positionListIterator method creates and return a ListIterator for the Positions contained in the sequence.
PositionListIterator<V,PV>	positionListIterator(int rank) The positionListIterator method creates and return a ListIterator for the Positions contained in the sequence.
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(PE edge)
void	reverse(Position<?> edge) Exchanges the two extremities of an edge.
void	setDestination(PE edge, PV destination)
void	setDestination(Position<?> edge, Position<?> vertex) Defines the vertex vertex to be the new destination of the edge edge.
void	setDirected(PE edge)
void	setDirected(Position<?> edge) Defines the edge as a directed edge.
LinkedPosition<PE>	setOrigin(PE edge, PV origin)
void	setOrigin(Position<?> edge, Position<?> vertex) Defines the vertex vertex to be the new origin of the edge edge.
LinkedPosition<PE>	setOriginAfter(PE edge, PV origin, LinkedPosition<PE> position)
LinkedPosition<PE>	setOriginBefore(PE edge, PV origin, LinkedPosition<PE> position)
void	setUndirected(PE 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
GenericSequence<V,PV>	vertexElements() Returns a list of all elements contained in the vertices.
PositionList<V,PV>	vertices() Returns a list of all the vertices contained in the graph.

Methods inherited from class ch.bfh.algo.core.sequence.GenericLinkedSequence

after, after, before, before, delete, element, element, encloses, encloses, first, head, insert, insert, insertAfter, insertBefore, insertBetween, last, listIterator, position, positionIterator, rank, rank, replace, replace, size, swap, swap, tail, validate

Methods inherited from class java.util.AbstractSequentialList

add, addAll, get, iterator, remove, set

Methods inherited from class java.util.AbstractList

add, clear, equals, hashCode, indexOf, lastIndexOf, listIterator, removeRange, subList

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface ch.bfh.algo.core.GenericContainer

insert, positionIterator

Methods inherited from interface ch.bfh.algo.Container

delete, element, encloses, replace, swap

Methods inherited from interface java.util.Collection

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

Methods inherited from interface ch.bfh.algo.Container

delete, element, encloses, replace, swap

Methods inherited from interface java.util.Collection

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

Methods inherited from interface java.util.List

add, add, addAll, addAll, clear, contains, containsAll, equals, get, hashCode, indexOf, isEmpty, iterator, lastIndexOf, listIterator, remove, remove, removeAll, retainAll, set, subList, toArray, toArray

Field Detail

factory

protected final GraphFactory<PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>> factory

Constructor Detail

GenericAdjacencyListGraph

public GenericAdjacencyListGraph(GraphFactory<PE,PV> factory,
                                 boolean directed)

Method Detail

getFactory

public GraphFactory<PE,PV> getFactory()

insertBetween

protected PV insertBetween(PV previous,
                           PV next,
                           V element,
                           PV position)

Overrides:

insertBetween in class GenericLinkedSequence<V,PV extends GenericVertex<E,V,PE,PV>>

insertVertex

public PV insertVertex(V element)

Description copied from interface: Graph

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

Specified by:

insertVertex in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

insertVertex in interface Graph<E,V>

Parameters:

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

Returns:

the new vertex Position

insertEdge

public PE insertEdge(E element)

Description copied from interface: Graph

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.

Specified by:

insertEdge in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

insertEdge in interface Graph<E,V>

Parameters:

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

Returns:

the new edge Position

insertEdge

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

Description copied from interface: Graph

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.

Specified by:

insertEdge in interface Graph<E,V>

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

insertEdge

public PE insertEdge(E element,
                     PV origin,
                     PV destination)

Specified by:

insertEdge in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

delete

public V delete(PV position)

Overrides:

delete in class GenericLinkedSequence<V,PV extends GenericVertex<E,V,PE,PV>>

deleteVertex

public V deleteVertex(PV position)

deleteVertex

public V deleteVertex(Position<?> position)
               throws InvalidAccessorException

Description copied from interface: Graph

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

Specified by:

deleteVertex in interface Graph<E,V>

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.

deleteEdge

public E deleteEdge(Position<?> position)
             throws InvalidAccessorException

Description copied from interface: Graph

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

Specified by:

deleteEdge in interface Graph<E,V>

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.

deleteEdge

public E deleteEdge(PE position)

vertices

public PositionList<V,PV> vertices()

Description copied from interface: Graph

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

Specified by:

vertices in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

vertices in interface Graph<E,V>

Returns:

the list of all vertices

edges

public PositionList<E,PE> edges()

Description copied from interface: Graph

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

Specified by:

edges in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

edges in interface Graph<E,V>

Returns:

the list of all edges

edges

public PositionList<E,PE> edges(Direction type)

Description copied from interface: Graph

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

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

Specified by:

edges in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

edges in interface Graph<E,V>

Parameters:

type - the type of the edges

Returns:

the list of all edges

incidentEdges

public PositionList<E,PE> incidentEdges(Position<?> vertex,
                                        Direction type)

Description copied from interface: Graph

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

Specified by:

incidentEdges in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

incidentEdges in interface Graph<E,V>

Parameters:

vertex - the vertex

type - the type of the edges

Returns:

the list of all edges

incidentEdges

public PositionList<E,PE> incidentEdges(PV vertex,
                                        Direction type)

adjacentVertices

public PositionList<V,PV> adjacentVertices(Position<?> vertex,
                                           Direction type)

Description copied from interface: Graph

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.

Specified by:

adjacentVertices in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

adjacentVertices in interface Graph<E,V>

Parameters:

vertex - the vertex

type - the type of the edges

Returns:

the list of adjacent vertices

adjacentVertices

public PositionList<V,PV> adjacentVertices(PV vertex,
                                           Direction type)

setOrigin

public void setOrigin(Position<?> edge,
                      Position<?> vertex)

Description copied from interface: Graph

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.

Specified by:

setOrigin in interface Graph<E,V>

Parameters:

edge - the edge whose origin is being defined

vertex - the new origin

setOrigin

public LinkedPosition<PE> setOrigin(PE edge,
                                    PV origin)

setOriginBefore

public LinkedPosition<PE> setOriginBefore(PE edge,
                                          PV origin,
                                          LinkedPosition<PE> position)

setOriginAfter

public LinkedPosition<PE> setOriginAfter(PE edge,
                                         PV origin,
                                         LinkedPosition<PE> position)

setDestination

public void setDestination(Position<?> edge,
                           Position<?> vertex)

Description copied from interface: Graph

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.

Specified by:

setDestination in interface Graph<E,V>

Parameters:

edge - the edge whose destination is being defined

vertex - the new destination.

setDestination

public void setDestination(PE edge,
                           PV destination)

detach

public void detach(Position<?> edge,
                   Position<?> vertex)

Description copied from interface: Graph

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

Specified by:

detach in interface Graph<E,V>

Parameters:

edge - an edge

vertex - one of the two extremities of edge

detachVertex

public void detachVertex(PE edge,
                         PV vertex)

origin

public PV origin(Position<?> edge)

Description copied from interface: Graph

Returns the origine of the edge edge

Specified by:

origin in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

origin in interface Graph<E,V>

Parameters:

edge - an edge

Returns:

the origin (a vertex) of the edge.

origin

public PV origin(PE edge)

destination

public PV destination(Position<?> edge)

Description copied from interface: Graph

Returns the destination of the edge edge

Specified by:

destination in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

destination in interface Graph<E,V>

Parameters:

edge - an edge

Returns:

the destination (a vertex) of the edge.

destination

public PV destination(PE edge)

setDirected

public void setDirected(Position<?> edge)

Description copied from interface: Graph

Defines the edge as a directed edge.

Specified by:

setDirected in interface Graph<E,V>

Parameters:

edge - an edge

setDirected

public void setDirected(PE edge)

setUndirected

public void setUndirected(Position<?> edge)

Description copied from interface: Graph

Defines the edge as an undirected edge.

Specified by:

setUndirected in interface Graph<E,V>

Parameters:

edge - an edge

setUndirected

public void setUndirected(PE edge)

isDirected

public boolean isDirected(Position<?> edge)

Description copied from interface: Graph

Verifies if an edge is directed.

Specified by:

isDirected in interface Graph<E,V>

Parameters:

edge - an edge

Returns:

true if edge is directed

isDirected

public boolean isDirected(PE edge)

reverse

public void reverse(Position<?> edge)

Description copied from interface: Graph

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

Specified by:

reverse in interface Graph<E,V>

Parameters:

edge - an edge

reverse

public void reverse(PE edge)

opposite

public PV opposite(Position<?> edge,
                   Position<?> vertex)

Description copied from interface: Graph

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.

Specified by:

opposite in interface GenericGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

opposite in interface Graph<E,V>

Parameters:

edge - an edge

opposite

public PV opposite(PE edge,
                   PV vertex)

replaceVertex

public V replaceVertex(Position<?> vertex,
                       V element)

Description copied from interface: Graph

Replaces the element contained in the vertex vertex by element.

Specified by:

replaceVertex in interface Graph<E,V>

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.

replaceEdge

public E replaceEdge(Position<?> edge,
                     E element)

Description copied from interface: Graph

Replaces the element contained in the edge edge by element.

Specified by:

replaceEdge in interface Graph<E,V>

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.

swapEdge

public void swapEdge(Position<?> edge0,
                     Position<?> edge1)

Description copied from interface: Graph

Exchanges the content of the two edges edge0 and edge1.

Specified by:

swapEdge in interface Graph<E,V>

Parameters:

edge0 - the first edge

edge1 - the second edge

swapVertex

public void swapVertex(Position<?> vertex0,
                       Position<?> vertex1)

Description copied from interface: Graph

Exchanges the content of the two vertices vertex0 and vertex1.

Specified by:

swapVertex in interface Graph<E,V>

Parameters:

vertex0 - the first vertex

vertex1 - the second vertex

vertexElements

public GenericSequence<V,PV> vertexElements()

Description copied from interface: Graph

Returns a list of all elements contained in the vertices.

Specified by:

vertexElements in interface Graph<E,V>

Returns:

the list of elements contained in the vertices

edgeElements

public GenericSequence<E,PE> edgeElements()

Description copied from interface: Graph

Returns a list of all elements contained in the edges.

Specified by:

edgeElements in interface Graph<E,V>

Returns:

the list of elements contained in the edges

insertBefore

public PV insertBefore(PV position,
                       V element)

Overrides:

insertBefore in class GenericLinkedSequence<V,PV extends GenericVertex<E,V,PE,PV>>

insertAfter

public PV insertAfter(PV position,
                      V element)

Overrides:

insertAfter in class GenericLinkedSequence<V,PV extends GenericVertex<E,V,PE,PV>>

positionListIterator

public PositionListIterator<V,PV> positionListIterator()

Description copied from interface: Sequence

The positionListIterator method creates and return a ListIterator for the Positions contained in the sequence. This method gives the possibility to iterate over all the Positions in the sequence.

Specified by:

positionListIterator in interface GenericSequence<V,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

positionListIterator in interface Sequence<V>

Overrides:

positionListIterator in class GenericLinkedSequence<V,PV extends GenericVertex<E,V,PE,PV>>

Returns:

a ListIterator<Position<E>> of all the Positions in the sequence.

positionListIterator

public PositionListIterator<V,PV> positionListIterator(int rank)

Description copied from interface: Sequence

The positionListIterator method creates and return a ListIterator for the Positions contained in the sequence. This iterator is initially placed at the rank given as a parmeter This method gives the possibility to iterate over all the Positions in the sequence.

Specified by:

positionListIterator in interface GenericSequence<V,PV extends GenericVertex<E,V,PE,PV>>

Specified by:

positionListIterator in interface Sequence<V>

Overrides:

positionListIterator in class GenericLinkedSequence<V,PV extends GenericVertex<E,V,PE,PV>>

Parameters:

rank - an int denoting the initial position of the pointer of the iterator.

Returns:

a ListIterator<Position<E>> of all the Positions in the sequence.

edgeElement

public E edgeElement(Position<?> edge)

Description copied from interface: Graph

Returns the element contained in edge

Specified by:

edgeElement in interface Graph<E,V>

Parameters:

edge - the edge containing the element

Returns:

element contained in the edge

edgeElement

public E edgeElement(PE edge)

vertexElement

public V vertexElement(Position<?> vertex)

Description copied from interface: Graph

Returns the element contained in vertex

Specified by:

vertexElement in interface Graph<E,V>

Parameters:

vertex - the vertex containing the element

Returns:

element contained in the vertex