bcds.phison
Interface SimGraph<V,E>

All Known Implementing Classes:

SdiGraph

public interface SimGraph<V,E>

Defines the interface of the graph used in Phison. The graph is assumed to be directed and simple (no loops, no parallel links). Nodes and edges can be of any type.

Author:

Juan Segovia S.

Method Summary

E	addEdge(V src, V dest) Instantiates a new edge object that links vertex src to vertex dest and adds it to this graph.
boolean	addEdge(V src, V dest, E e) Registers that the edge e links vertex src to vertex dest.
boolean	addVertex(V v) Adds a vertex to this graph.
E	canonicEdge(E e) If two vertices are linked in both directions, that is, two edges exist between them, one per direction, return one of these two edges as the "preferent" one.
java.util.Set<E>	canonicEdges() Returns a set containing all the "canonic" edges of this graph.
SimGraph<V,E>	createSubgraph(java.util.Set<V> vertex_subset, java.util.Set<E> edge_subset) Creates a new graph consisting of a subset of this graphs's edges and vertices.
java.util.Set<E>	edgeSet() Returns an unmodifiable view of the set of edges of this graph.
java.util.Set<E>	edgesOf(V v) Returns an unmodifiable view of the set of edges of the vertex v, both incoming and outgoing.
E	getEdge(V src, V dest) Returns the edge between src and dest, or null if no such edge exists.
java.lang.Class<E>	getEdgeClass() Returns the class to which all edges in this graph belong.
V	getEdgeSource(E e) Returns the source vertex of the given edge.
V	getEdgeTarget(E e) Returns the destination vertex of the given edge.
java.lang.Class<V>	getVertexClass() Returns the class to which all vertices in this graph belong.
java.util.Set<E>	incomingEdgesOf(V v) Returns an unmodifiable view of the set of incoming edges of the vertex v.
int	inDegreeOf(V v) Returns the cardinality of the set of incoming edges of the vertex v.
E	newEdge(java.lang.String id) Creates a new edge.
V	newVertex(java.lang.String id) Creates a new vertex.
int	outDegreeOf(V v) Returns the cardinality of the set of outgoing edges of the vertex v.
java.util.Set<E>	outgoingEdgesOf(V v) Returns an unmodifiable view of the set of outgoing edges of the vertex v.
void	removeAllEdges(java.util.Collection<E> c)
void	removeAllVertices(java.util.Collection<V> c)
boolean	removeEdge(E e) Removes the edge e from this graph.
boolean	removeVertex(V v) Removes the vertex v from this graph and all its associated edges.
E	reverseEdge(E e) Returns getEdge(getEdgeTarget(e), getEdgeSource(e)), which may an edge object or null.
java.util.Set<V>	vertexSet() Returns an unmodifiable view of the set of vertices of this graph.

Method Detail

addVertex

boolean addVertex(V v)

Adds a vertex to this graph. If the given vertex already exists in the graph, returns false.

addEdge

E addEdge(V src,
          V dest)

Instantiates a new edge object that links vertex src to vertex dest and adds it to this graph. If there is already such an edge, returns null, otherwise, returns the new edge instance.

addEdge

boolean addEdge(V src,
                V dest,
                E e)

Registers that the edge e links vertex src to vertex dest. If e is null, a new edge is instantiated. Returns false if the two given vertices are already connected.

removeEdge

boolean removeEdge(E e)

Removes the edge e from this graph. Returns false if the given edge is not part of this graph.

removeVertex

boolean removeVertex(V v)

Removes the vertex v from this graph and all its associated edges. Returns false if the given vertex is not part of this graph.

removeAllEdges

void removeAllEdges(java.util.Collection<E> c)

removeAllVertices

void removeAllVertices(java.util.Collection<V> c)

getEdge

E getEdge(V src,
          V dest)

Returns the edge between src and dest, or null if no such edge exists.

getEdgeSource

V getEdgeSource(E e)

Returns the source vertex of the given edge.

getEdgeTarget

V getEdgeTarget(E e)

Returns the destination vertex of the given edge.

vertexSet

java.util.Set<V> vertexSet()

Returns an unmodifiable view of the set of vertices of this graph.

edgeSet

java.util.Set<E> edgeSet()

Returns an unmodifiable view of the set of edges of this graph.

outgoingEdgesOf

java.util.Set<E> outgoingEdgesOf(V v)

Returns an unmodifiable view of the set of outgoing edges of the vertex v.

incomingEdgesOf

java.util.Set<E> incomingEdgesOf(V v)

Returns an unmodifiable view of the set of incoming edges of the vertex v.

edgesOf

java.util.Set<E> edgesOf(V v)

Returns an unmodifiable view of the set of edges of the vertex v, both incoming and outgoing.

outDegreeOf

int outDegreeOf(V v)

Returns the cardinality of the set of outgoing edges of the vertex v.

inDegreeOf

int inDegreeOf(V v)

Returns the cardinality of the set of incoming edges of the vertex v.

newVertex

V newVertex(java.lang.String id)

Creates a new vertex. The parameter id is passed to the of the class returned by getVertexClass(). In general, the id should be a zero-based integer. No check is performed on the uniqueness of vertex ids. Note that a new vertex instance is created, but it is not automatically added to the graph.

newEdge

E newEdge(java.lang.String id)

Creates a new edge. It invoks the constructor that accepts a a single string of the class returned by getEdgeClass(). The parameter id is typically a string of the form "s-d", as in 13-7. Note that a new edge instance is created, but it is not automatically added to the graph.

createSubgraph

SimGraph<V,E> createSubgraph(java.util.Set<V> vertex_subset,
                             java.util.Set<E> edge_subset)

Creates a new graph consisting of a subset of this graphs's edges and vertices. The returned subgraph and this graph are separate entities: changes in one does not affect the other (for example addition or remotion of nodes and links). In that sense, this is similar to a (shallow) copy constructor.

Parameters:

vertex_subset - The set of vertices to include in the subgraph. If null, all vertices are included.

edge_subset - The set of edges to include in the subgraph. If null, all edges are included. For an edge to be effectively included in the subgraph, both its end vertices must also be there.

canonicEdge

E canonicEdge(E e)

If two vertices are linked in both directions, that is, two edges exist between them, one per direction, return one of these two edges as the "preferent" one. If the edge e does not have its reverse(e), return the same edge.

The decision on which of the directions to choose as the "canonic" edge is unspecified; the only condition is that this method must always return the same edge direction for any of its directed components.

"Canonic" edges are useful when one needs to treat the graph as undirected.

canonicEdges

java.util.Set<E> canonicEdges()

Returns a set containing all the "canonic" edges of this graph.

reverseEdge

E reverseEdge(E e)

Returns getEdge(getEdgeTarget(e), getEdgeSource(e)), which may an edge object or null.

getVertexClass

java.lang.Class<V> getVertexClass()

Returns the class to which all vertices in this graph belong.

getEdgeClass

java.lang.Class<E> getEdgeClass()

Returns the class to which all edges in this graph belong.