edu.stanford.nlp.graph
Class DirectedMultiGraph<V,E>

java.lang.Object
  extended by edu.stanford.nlp.graph.DirectedMultiGraph<V,E>
Type Parameters:
V - Type of vertices
E - Type of edges.
All Implemented Interfaces:
Graph<V,E>, java.io.Serializable

public class DirectedMultiGraph<V,E>
extends java.lang.Object
implements Graph<V,E>

Simple graph library; this is directed for now. This class focuses on time efficiency rather than memory efficiency.

Author:
sonalg, John Bauer
See Also:
Serialized Form

Constructor Summary
DirectedMultiGraph()
           
 
Method Summary
 void add(V source, V dest, E data)
          adds vertices (if not already in the graph) and the edge between them
 boolean addVertex(V v)
          For adding a zero degree vertex
 void clear()
          clears the graph, removes all edges and nodes
 boolean containsVertex(V v)
           
 java.util.List<E> convertPath(java.util.List<V> nodes, boolean directionSensitive)
           
 java.lang.Iterable<E> edgeIterable()
           
 java.util.Iterator<E> edgeIterator()
           
 boolean equals(java.lang.Object that)
           
 java.util.List<E> getAllEdges()
           
 java.util.Set<V> getAllVertices()
           
 java.util.Set<V> getChildren(V vertex)
          for undirected graph, it is just the neighbors
 java.util.List<java.util.Set<V>> getConnectedComponents()
           
 java.util.List<E> getEdges(V source, V dest)
           
 java.util.List<E> getIncomingEdges(V v)
          for undirected graph, it is just the edges from the node
 int getInDegree(V vertex)
          for undirected graph, it should just be the degree
 java.util.Set<V> getNeighbors(V v)
          Gets both parents and children nodes
 int getNumEdges()
           
 int getNumVertices()
           
 int getOutDegree(V vertex)
           
 java.util.List<E> getOutgoingEdges(V v)
          for undirected graph, it is just the edges from the node
 java.util.Set<V> getParents(V vertex)
          for undirected graph, it is just the neighbors
 java.util.List<V> getShortestPath(V node1, V node2)
          direction insensitive (the paths can go "up" or through the parents)
 java.util.List<V> getShortestPath(V node1, V node2, boolean directionSensitive)
          can specify the direction sensitivity
 java.util.List<E> getShortestPathEdges(V node1, V node2)
           
 java.util.List<E> getShortestPathEdges(V node1, V node2, boolean directionSensitive)
           
 int hashCode()
          Be careful hashing these.
 java.lang.Iterable<E> incomingEdgeIterable(V vertex)
           
 java.util.Iterator<E> incomingEdgeIterator(V vertex)
           
 boolean isEdge(V source, V dest)
          only checks if there is an edge from source to dest.
 boolean isEmpty()
          False if there are any vertices in the graph, true otherwise.
 boolean isNeighbor(V source, V dest)
           
 java.lang.Iterable<E> outgoingEdgeIterable(V vertex)
           
 java.util.Iterator<E> outgoingEdgeIterator(V vertex)
           
 boolean removeEdge(V source, V dest, E data)
           
 boolean removeEdges(V source, V dest)
           
 boolean removeVertex(V vertex)
          remove a vertex (and its edges) from the graph.
 boolean removeVertices(java.util.Collection<V> vertices)
           
 void removeZeroDegreeNodes()
          Deletes nodes with zero incoming and zero outgoing edges
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

DirectedMultiGraph

public DirectedMultiGraph()
Method Detail

hashCode

public int hashCode()
Be careful hashing these. They are mutable objects, and changing the object will throw off the hash code, messing up your hash table

Overrides:
hashCode in class java.lang.Object

equals

public boolean equals(java.lang.Object that)
Overrides:
equals in class java.lang.Object

addVertex

public boolean addVertex(V v)
For adding a zero degree vertex

Specified by:
addVertex in interface Graph<V,E>
Parameters:
v -

add

public void add(V source,
                V dest,
                E data)
adds vertices (if not already in the graph) and the edge between them

Specified by:
add in interface Graph<V,E>
Parameters:
source -
dest -
data -

removeEdges

public boolean removeEdges(V source,
                           V dest)
Specified by:
removeEdges in interface Graph<V,E>

removeEdge

public boolean removeEdge(V source,
                          V dest,
                          E data)
Specified by:
removeEdge in interface Graph<V,E>

removeVertex

public boolean removeVertex(V vertex)
remove a vertex (and its edges) from the graph.

Specified by:
removeVertex in interface Graph<V,E>
Parameters:
vertex -
Returns:
true if successfully removes the node

removeVertices

public boolean removeVertices(java.util.Collection<V> vertices)
Specified by:
removeVertices in interface Graph<V,E>

getNumVertices

public int getNumVertices()
Specified by:
getNumVertices in interface Graph<V,E>

getOutgoingEdges

public java.util.List<E> getOutgoingEdges(V v)
Description copied from interface: Graph
for undirected graph, it is just the edges from the node

Specified by:
getOutgoingEdges in interface Graph<V,E>

getIncomingEdges

public java.util.List<E> getIncomingEdges(V v)
Description copied from interface: Graph
for undirected graph, it is just the edges from the node

Specified by:
getIncomingEdges in interface Graph<V,E>

getNumEdges

public int getNumEdges()
Specified by:
getNumEdges in interface Graph<V,E>

getParents

public java.util.Set<V> getParents(V vertex)
Description copied from interface: Graph
for undirected graph, it is just the neighbors

Specified by:
getParents in interface Graph<V,E>

getChildren

public java.util.Set<V> getChildren(V vertex)
Description copied from interface: Graph
for undirected graph, it is just the neighbors

Specified by:
getChildren in interface Graph<V,E>

getNeighbors

public java.util.Set<V> getNeighbors(V v)
Gets both parents and children nodes

Specified by:
getNeighbors in interface Graph<V,E>
Parameters:
v -

clear

public void clear()
clears the graph, removes all edges and nodes

Specified by:
clear in interface Graph<V,E>

containsVertex

public boolean containsVertex(V v)
Specified by:
containsVertex in interface Graph<V,E>

isEdge

public boolean isEdge(V source,
                      V dest)
only checks if there is an edge from source to dest. To check if it is connected in either direction, use isNeighbor

Specified by:
isEdge in interface Graph<V,E>
Parameters:
source -
dest -

isNeighbor

public boolean isNeighbor(V source,
                          V dest)
Specified by:
isNeighbor in interface Graph<V,E>

getAllVertices

public java.util.Set<V> getAllVertices()
Specified by:
getAllVertices in interface Graph<V,E>

getAllEdges

public java.util.List<E> getAllEdges()
Specified by:
getAllEdges in interface Graph<V,E>

isEmpty

public boolean isEmpty()
False if there are any vertices in the graph, true otherwise. Does not care about the number of edges.

Specified by:
isEmpty in interface Graph<V,E>

removeZeroDegreeNodes

public void removeZeroDegreeNodes()
Deletes nodes with zero incoming and zero outgoing edges

Specified by:
removeZeroDegreeNodes in interface Graph<V,E>

getEdges

public java.util.List<E> getEdges(V source,
                                  V dest)
Specified by:
getEdges in interface Graph<V,E>

getShortestPath

public java.util.List<V> getShortestPath(V node1,
                                         V node2)
direction insensitive (the paths can go "up" or through the parents)


getShortestPathEdges

public java.util.List<E> getShortestPathEdges(V node1,
                                              V node2)

getShortestPath

public java.util.List<V> getShortestPath(V node1,
                                         V node2,
                                         boolean directionSensitive)
can specify the direction sensitivity

Parameters:
node1 -
node2 -
directionSensitive - - whether the path can go through the parents
Returns:
the list of nodes you get through to get there

getShortestPathEdges

public java.util.List<E> getShortestPathEdges(V node1,
                                              V node2,
                                              boolean directionSensitive)

convertPath

public java.util.List<E> convertPath(java.util.List<V> nodes,
                                     boolean directionSensitive)

getInDegree

public int getInDegree(V vertex)
Description copied from interface: Graph
for undirected graph, it should just be the degree

Specified by:
getInDegree in interface Graph<V,E>

getOutDegree

public int getOutDegree(V vertex)
Specified by:
getOutDegree in interface Graph<V,E>

getConnectedComponents

public java.util.List<java.util.Set<V>> getConnectedComponents()
Specified by:
getConnectedComponents in interface Graph<V,E>

incomingEdgeIterator

public java.util.Iterator<E> incomingEdgeIterator(V vertex)

incomingEdgeIterable

public java.lang.Iterable<E> incomingEdgeIterable(V vertex)

outgoingEdgeIterator

public java.util.Iterator<E> outgoingEdgeIterator(V vertex)

outgoingEdgeIterable

public java.lang.Iterable<E> outgoingEdgeIterable(V vertex)

edgeIterator

public java.util.Iterator<E> edgeIterator()

edgeIterable

public java.lang.Iterable<E> edgeIterable()

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object


Stanford NLP Group