edu.ucla.sspace.graph

Class SubgraphIterator<E extends Edge,G extends Graph<E>>

java.lang.Object

edu.ucla.sspace.graph.SubgraphIterator<E,G>

All Implemented Interfaces:

Serializable, Iterator<G>

public class SubgraphIterator<E extends Edge,G extends Graph<E>>
extends Object
implements Iterator<G>, Serializable

An implementation of the EnumerateSubgraphs (ESU) method from Wernicke (2006), which enumerates all possible k-vertex subgraphs of a given graph. For full details see:

• Sebastian Wernicke. Efficient detection of network motifs. in IEEE/ACM Transactions on Computational Biology and Bioinformatics.

In summary, this iterator returns all possible size-k subgraphs of the input graph through an efficient traversal.

This implementation does not store the entire set of possible subgraphs in memory at one time, but may hold some arbitrary number of them in memory and compute the rest as needed.

This class is not thread-safe and does not support the remove() method.

Author:

David Jurgens

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
SubgraphIterator(G g, int subgraphSize) Constructs an iterator over all the subgraphs of g with the specified subgraph size.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	hasNext()
G	next()
void	remove() Throws an UnsupportedOperationException if called.

Methods inherited from class java.lang.Object

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

Constructor Detail

SubgraphIterator

public SubgraphIterator(G g,
                int subgraphSize)

Constructs an iterator over all the subgraphs of g with the specified subgraph size.

Parameters:

g - a graph

subgraphSize - the size of the subgraphs to return

Throws:

IllegalArgumentException - if subgraphSize is less than 1 or is greater than the number of vertices of g

NullPointerException - if g is null

Method Detail

hasNext

public boolean hasNext()

Specified by:

hasNext in interface Iterator<G extends Graph<E>>

next

public G next()

Specified by:

next in interface Iterator<G extends Graph<E>>

remove

public void remove()

Throws an UnsupportedOperationException if called.

Specified by:

remove in interface Iterator<G extends Graph<E>>