bcds.phison
Class SdiGraph<V,E>

java.lang.Object
  bcds.phison.SdiGraph<V,E>

All Implemented Interfaces:

SimGraph<V,E>

public class SdiGraph<V,E>
extends java.lang.Object
implements SimGraph<V,E>

Implements a directed graph in which parallel edges are not allowed (though loops are). The initial S stands for "simple" precisely because parallel edges are not supported.

Both the vertices and the edges may be of any class, provided the following conditions are met:

• The vertex class V must have a constructor accepting a single string parameter, the node id.
• The toString method in V must return the node id which it received at instantiation time.
• The edge class E must be public and non-final, and must have a public default constructor.
• All edges added to the graph must be instantiated, directly or indirectly, by newEdge(String).

The edge class is not used directly. Instead, a new derived class is dynamically created with the help of the package Javassist. The jar file of this package must be in the CLASSPATH at execution time (and it is also required for compiling this class).

The derived edge class contains two references to the edge ends (source and destination vertices) and overrides the toString method so that it returns a string of the form a-b, as in 23-79, where the two integers are the values returned by the toString method of class V.

SdiGraph does not store any vertex or edge attribute within the graph itself. Usually, the caller will maintain such attributes as he/she sees fit, in maps for example. A minimalistic and ficticious example of use of this class is:

  class Test {
    public static void main(String...args) {
      SdiGraph<String, Link> g = new SdiGraph<String, Link>(String.class, Link.class);
      String v0 = "0";
      String v1 = "1";
      String v2;

      g.addVertex(v0);
      g.addVertex(v1);
      g.addVertex(v2=g.newVertex("2"));

      Map<Link, Integer> cost = new Map<Link, Integer>();

      cost.put(g.addEdge(v0, v1), 123);
      cost.put(g.addEdge(v1, v2), 200);
      cost.put(g.addEdge(v2, v0), 42);

      for (String v : g.vertexSet()) {
         int v_weight = 0;

         for (Link e : g.edgesOf(v)) {
             v_weight += cost.get(e);
         }
         System.out.printf("Weight of vertex %s=%d\n", v, v_weight);
      }
    }

    public static class Link {}
 }
 

Note how in this example the class Link is empty.

On referencing vertices and edges. When searching for vertices and edges, SdiGraph uses object identity exclusively to determine equality. Thus, in the previous example we cannot write g.addEdge("0", "1") to add a new edge. Although here the vertex class is String, and it might be tempting to use "0" and v0 interchangeably. However, SdiGraph uses internally IdentityHashMap, both for vertices and edges. Therefore, as the object references for "0" and v0 are different, one cannot be used in place of the other.

On graph input/output. If a graph is never to be read from or stored in a file, a vertex class such as String might suffice. However, if file input/output is required, the classes in the bcds.phison.io package expect a vertex class that implements GraphIONode.

Author:

Juan Segovia S.

Constructor Summary

SdiGraph(java.lang.Class<V> vertex_class, java.lang.Class<E> edge_class)
Creates a new instance in which vertices and edges are of the given types.

Method Summary

E	addEdge(V src, V dest) Creates a new edge between the given source and destination if one does not exist yet, and returns the new edge instance.
boolean	addEdge(V src, V dest, E e) Registers an existing edge instance as connecting two vertices, which are not connected before the call.
boolean	addVertex(V v) Add a vertex to this graph.
E	canonicEdge(E e) Returns the canonicalized form of an edge.
java.util.Set<E>	canonicEdges() Returns the edges in this graph, in canonical form.
SdiGraph<V,E>	createSubgraph(java.util.Set<V> vertex_subset, java.util.Set<E> edge_subset) Creates a new graph in which the vertices and edges are shared with the calling instance.
java.util.Set<E>	edgeSet() Returns an unmodifiable view of the set of vertices in this graph.
java.util.Set<E>	edgesOf(V v) Returns a the set of edges, both incoming and outgoing, of the vertex v.
E	getEdge(V src, V dest) Returns the edge object that links vertices src and dest, if one exists, or null otherwise.
java.lang.Class<E>	getEdgeClass() Returns the class which serves as the parent of all edges created by newEdge(String).
V	getEdgeSource(E e) Returns the vertex for which e is an outgoing edge.
V	getEdgeTarget(E e) Returns the vertex for which e is an incoming edge.
java.lang.Class<V>	getVertexClass() Returns the class used to instantiate vertices in newVertex(String).
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 number of incoming edges of vertex v.
E	newEdge(java.lang.String id) Creates a new edge, without adding it to the graph.
V	newVertex(java.lang.String id) Creates a new vertex, without adding it to the graph.
int	outDegreeOf(V v) Returns the number of outgoing edges of 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) Removes all the edges in the collection c by repeatedly calling removeEdge(E).
void	removeAllVertices(java.util.Collection<V> c) Removes all the edges in the collection c by repeatedly calling removeVertex(V).
boolean	removeEdge(E e) Detaches the given edge from this graph.
boolean	removeVertex(V v) Removes the given vertex and all its associated edges (both incoming and outgoing).
E	reverseEdge(E e) Returns the edge that runs in the reverse direction to e, or null if such an edge does not exist.
java.lang.String	toString() Returns a simple representation of this graph.
java.util.Set<V>	vertexSet() Returns an unmodifiable view of the set of vertices in this graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SdiGraph

public SdiGraph(java.lang.Class<V> vertex_class,
                java.lang.Class<E> edge_class)

Creates a new instance in which vertices and edges are of the given types.

Throws:

java.lang.IllegalArgumentException - if vertex_class does not have a public constructor that accepts a String, or if edge_classdoes not have a public default constructor.

Method Detail

addVertex

public boolean addVertex(V v)

Add a vertex to this graph. Returns false if the given vertex is already in the graph. Typically, new vertices are created by calling newVertex(java.lang.String), but that is not a requirement.

Specified by:

addVertex in interface SimGraph<V,E>

addEdge

public E addEdge(V src,
                 V dest)

Creates a new edge between the given source and destination if one does not exist yet, and returns the new edge instance. Returns null if both vertices are already linked. Both vertices must be in this graph.

Specified by:

addEdge in interface SimGraph<V,E>

Throws:

java.lang.IllegalArgumentException - if src or dest are not in this graph.

java.lang.RuntimeException - if edge instantiation fails in any way.

addEdge

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

Registers an existing edge instance as connecting two vertices, which are not connected before the call. If e is null, a new edge object is instantiated. If edge e it not null, it must have been instantiated by calling newEdge(java.lang.String) on this graph or one of its subgraphs.

Internal information kept in private members on the edge object are updated (the source and destination vertices).

This method may also throw the exceptions listed in #addEdge(V, V).

Specified by:

addEdge in interface SimGraph<V,E>

Returns:

true to indicate that the edge was successfully registered, and false if the edge was already present in this graph.

Throws:

java.lang.IllegalArgumentException - if e is not null but has not been created by this graph's newEdge.

java.lang.IllegalArgumentException - if e is already in use as linking another pair of vertices.

removeEdge

public boolean removeEdge(E e)

Detaches the given edge from this graph. Returns false if the edge e is not in this graph, and true if the removal is successful. The edge object is left unchanged, in particular, its internal pointers to its vertices remain intact after this call.

Specified by:

removeEdge in interface SimGraph<V,E>

removeVertex

public boolean removeVertex(V v)

Removes the given vertex and all its associated edges (both incoming and outgoing). Returns false if the vertex is not in this graph, and true otherwise.

Specified by:

removeVertex in interface SimGraph<V,E>

getEdge

public E getEdge(V src,
                 V dest)

Returns the edge object that links vertices src and dest, if one exists, or null otherwise. null is returned if either or both vertices do not belong to this graph,

Specified by:

getEdge in interface SimGraph<V,E>

getEdgeSource

public V getEdgeSource(E e)

Returns the vertex for which e is an outgoing edge.

Note that if e is not a valid edge for this graph, the result is undefined. For example, if g and h are two unrelated graphs, g.getEdgeSource(h.getEdge(vx, vy)) might succeed but the returned vertex is not valid for the graph g.

Specified by:

getEdgeSource in interface SimGraph<V,E>

Throws:

java.lang.RuntimeException - if reading the source vertex of the given edge fails, which usually happens if e has not been instantiated by calling newEdge(java.lang.String).

getEdgeTarget

public V getEdgeTarget(E e)

Returns the vertex for which e is an incoming edge. The comments for getEdgeSource(E) applies to this method as well.

See getEdgeSource(E) for the list of exceptions thrown.

Specified by:

getEdgeTarget in interface SimGraph<V,E>

reverseEdge

public E reverseEdge(E e)

Returns the edge that runs in the reverse direction to e, or null if such an edge does not exist. This method is implemented as getEdge(getEdgeTarget(e), getEdgeSource(e)). See the called methods for the list of exceptions thrown.

Specified by:

reverseEdge in interface SimGraph<V,E>

vertexSet

public java.util.Set<V> vertexSet()

Returns an unmodifiable view of the set of vertices in this graph. The returned set is cached, that is, it is created on the first call to vertexSet that follows the addition or remotion of vertices.

Specified by:

vertexSet in interface SimGraph<V,E>

edgeSet

public java.util.Set<E> edgeSet()

Returns an unmodifiable view of the set of vertices in this graph. The returned set is cached, that is, it is created on the first call to edgeSet that follows the addition or remotion of edges.

Specified by:

edgeSet in interface SimGraph<V,E>

outgoingEdgesOf

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

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

Specified by:

outgoingEdgesOf in interface SimGraph<V,E>

Throws:

java.lang.NullPointerException - if vertex v does not exist in the graph, or is null.

incomingEdgesOf

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

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

Specified by:

incomingEdgesOf in interface SimGraph<V,E>

Throws:

java.lang.NullPointerException - if vertex v does not exist in the graph, or if null.

removeAllEdges

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

Removes all the edges in the collection c by repeatedly calling removeEdge(E).

Specified by:

removeAllEdges in interface SimGraph<V,E>

removeAllVertices

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

Removes all the edges in the collection c by repeatedly calling removeVertex(V).

Specified by:

removeAllVertices in interface SimGraph<V,E>

getVertexClass

public java.lang.Class<V> getVertexClass()

Returns the class used to instantiate vertices in newVertex(String). This is the class received in the constructor.

Specified by:

getVertexClass in interface SimGraph<V,E>

getEdgeClass

public java.lang.Class<E> getEdgeClass()

Returns the class which serves as the parent of all edges created by newEdge(String). This is the class received in the constructor.

Specified by:

getEdgeClass in interface SimGraph<V,E>

edgesOf

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

Returns a the set of edges, both incoming and outgoing, of the vertex v. Beware that each call generates a new set instance.

Specified by:

edgesOf in interface SimGraph<V,E>

Throws:

java.lang.NullPointerException - if vertex v does not exist in the graph, or is null.

outDegreeOf

public int outDegreeOf(V v)

Returns the number of outgoing edges of vertex v.

Specified by:

outDegreeOf in interface SimGraph<V,E>

Throws:

java.lang.NullPointerException - if vertex v does not exist in the graph, or is null.

inDegreeOf

public int inDegreeOf(V v)

Returns the number of incoming edges of vertex v.

Specified by:

inDegreeOf in interface SimGraph<V,E>

Throws:

java.lang.NullPointerException - if vertex v does not exist in the graph, or is null.

createSubgraph

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

Creates a new graph in which the vertices and edges are shared with the calling instance.

Note that the subgraph and its parent share types (edge and vertex class and constructors) but changes in one (addition of vertices, reassignment of edges, etc) do not affect the other.

Specified by:

createSubgraph in interface SimGraph<V,E>

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.

newVertex

public V newVertex(java.lang.String id)

Creates a new vertex, without adding it to the graph. The parameter id is passed to the vertex constructor as its sole parameter.

Specified by:

newVertex in interface SimGraph<V,E>

Throws:

java.lang.RuntimeException - if instantiation fails in any way.

newEdge

public E newEdge(java.lang.String id)

Creates a new edge, without adding it to the graph. The parameter id is ignored, that is, it is not passed to the edge constructor.

Specified by:

newEdge in interface SimGraph<V,E>

Throws:

java.lang.RuntimeException - if instantiation fails in any way.

canonicEdge

public E canonicEdge(E e)

Returns the canonicalized form of an edge. If both links a-b and b-a exists, this method systematically returns one of them when applied to both edges independently. The canonic edge of a uni-directional edge is itself.

For example, given the edge 10-3, this implementation will return the edge 3-10, that is, the source will be the numerically smaller of the end points (as integers). If integer conversion cannot be applied, the comparison is performed as strings.

Specified by:

canonicEdge in interface SimGraph<V,E>

canonicEdges

public java.util.Set<E> canonicEdges()

Returns the edges in this graph, in canonical form. Thus, if the graph consists of edges having all both directons, the number of elements in the set returned will be half the number of edges in the graph.

Specified by:

canonicEdges in interface SimGraph<V,E>

toString

public java.lang.String toString()

Returns a simple representation of this graph. The returned string is of the form
Vertices: [x, y, z] Edges: [x-y, x-z].

Overrides:

toString in class java.lang.Object