lu.cs.co.graph
Class Graph

java.lang.Object
  |
  +--lu.cs.co.graph.Graph

Direct Known Subclasses:

Book, Miles, RandomGraph, Roget, Words

public class Graph

extends Object

A class for combinatorial graphs. Provides constructors for only the most basic graph, several subclasses provide additional constructurs.

Field Summary

int	m The number of edges
int	n The number of vertices
String	name The graph's name

Constructor Summary

Graph(Graph G, boolean comp)
Constructs a new Graph from a graph, possibly complementing it.

Graph(int n, boolean complete)
Construct a trivial (complete or empty) graph of given size.

Graph(Subgraph S)
The subgraph induced by a set of vertices.

Method Summary

int	degree(Vertex v) The degree of a given vertex in an undirected graph.
Edges	edges() Creates an iterator over the edges of this graph.
Vertex	findByName(String s) Deprecated. Use getVertex(String) instead.
boolean[][]	getAdjecencyMatrix() Compute this graph's adjecency matrix.
int[][]	getDistanceMatrix() Compute this graph's distance matrix.
Edge	getEdge(Vertex u, Vertex v) Get the edge joining two given vertices in this graph, assuming it exists.
int	getIndex(Vertex v) Gets the index of a given vertex in the ordering of this graph's vertices.
Vertex	getVertex(int i) Gets a vertex with a given index in the ordering of the vertices of this graph.
Vertex	getVertex(String S) Gets a vertex matching a given string.
boolean	hasEdge(Vertex u, Vertex v) Check if two given vertices are incident in this graph.
Edges	incident(Vertex v) Creates an iterator over the edges in this graph that are incident to a given vertex.
Edges	incoming(Vertex v) Creates an iterator over the edges in this graph that are incoming to a given vertex.
int	indegree(Vertex v) Returns the outdegree of a given vertex.
int	index(Vertex v) Deprecated. Use getIndex instead
boolean	isDirected() Check if this graph is directed or not.
static void	main(String[] args) Construct a graph from standard input and write its description to standard output.
int	outdegree(Vertex v) The indegree of a given vertex.
Edges	outgoing(Vertex v) Creates an iterator over the edges in this graph that are outgoing from a given vertex.
static Graph	parseGraph(String[] args) The graph specified by an array of strings, useful for input from the command line in a uniform fashion.
String	toString() Creates a string representation of this Graph.
Vertices	vertices() Creates an iterator over the vertices of this graph.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

name

public String name

The graph's name

n

public int n

The number of vertices

m

public int m

The number of edges

Constructor Detail

Graph

public Graph(Graph G,
             boolean comp)

Constructs a new Graph from a graph, possibly complementing it. If comp is false then the newly created graph is a copy of the argument. All vertices and edges are cloned (so the copy shares no vertices with the original). The vertex names are retained. If comp is true all vertices are cloned, and an undirected edge is inserted between two nodes if and only if these were unconnected in the original. The length of the new edge is 1.

Graph

public Graph(int n,
             boolean complete)

Construct a trivial (complete or empty) graph of given size. The complete graph has an undirected edge between every pair of nodes. The empty graph has no edges.

Parameters:

n - the number of vertices

complete - if true, construct the complete graph (all edges are present); otherwise construct the empty graph (no edges are present)

Graph

public Graph(Subgraph S)

The subgraph induced by a set of vertices. The resulting graph contains precisely the vertices in the argument subgraph, and retains every edge between these vertices in the argument subgraph. More precisely: if G=(V,E) is a graph and S=(V',E') a subgraph in G, i.e., V' is a subset of V and E is a subset of E', then the subgraph of G induced by S is (V', E''), where E'' contains the edge (u,v) if and only if it belons to E and u and v belong to V'.

All vertices and edges are cloned (so the subgraph shares no vertices with the original). The vertex names are retained.

Method Detail

parseGraph

public static Graph parseGraph(String[] args)

The graph specified by an array of strings, useful for input from the command line in a uniform fashion. For example '23 31' specifies a random graph with 23 vertices and 31 edges, while 'miles 30' specifies Miles(23). The syntax is terse, different constructors are invoked depending on how the input can be parsed.

n m

new RandomGraph(n,m,0), A random graph

n m min max

new RandomGraph(new RandomGraph(n,m,0),min,max,0) , A random graph with random edge lengths

"miles" n

new Miles(n)

"miles" n dist deg

new Miles(int dist deg)

"words" n

new Words(n)

"words" n dH dC

new Words(n,dH,dC,0)

"book" ttl

new Book(ttl)

"book" ttl n

new Book(ttl,n)

"book" ttl n skip

new Book(ttl,n,skip)

index

public int index(Vertex v)

Deprecated. Use getIndex instead

Gets the index of a given vertex in the ordering of this graph's vertices.

Parameters:

v - the given vertex (assumed to belong to this graph)

Returns:

the index of the given vertex in the range 0..n-1

See Also:

getIndex

edges

public Edges edges()

Creates an iterator over the edges of this graph.

Returns:

an iterator representing the edges of this graph in no particular order

incoming

public Edges incoming(Vertex v)

Creates an iterator over the edges in this graph that are incoming to a given vertex.

Parameters:

v - the given vertex (assumed to belong to this graph)

Returns:

an iterator over the edges incoming to the given vertex in no particular order

outgoing

public Edges outgoing(Vertex v)

Creates an iterator over the edges in this graph that are outgoing from a given vertex.

Parameters:

v - the given vertex (assumed to belong to this graph)

Returns:

an iterator over the edges outgoing from the given vertex in no particular order

incident

public Edges incident(Vertex v)

Creates an iterator over the edges in this graph that are incident to a given vertex. Assumes that the graph is undirected, otherwise the incoming and outcoming methods should be used.

Parameters:

v - the given vertex (assumed to belong to this graph)

Returns:

an iterator over the edges incoming to the given vertex in no particular order

vertices

public Vertices vertices()

Creates an iterator over the vertices of this graph.

Returns:

an iterator representing the vertices of this graph in no particular order

indegree

public int indegree(Vertex v)

Returns the outdegree of a given vertex.

Returns:

the number of edges that are outgoing from the given vertex

outdegree

public int outdegree(Vertex v)

The indegree of a given vertex.

Parameters:

v - the given vertex (assumed to belong to this graph)

Returns:

the number of edges that are outgoing from the given vertex

degree

public int degree(Vertex v)

The degree of a given vertex in an undirected graph. The same as outdegree(Vertex).

Parameters:

v - the given vertex (assumed to belong to this graph)

Returns:

the number of edges that are outgoing from the given vertex

findByName

public Vertex findByName(String s)
                  throws NoSuchElementException

Deprecated. Use getVertex(String) instead.

Finds a vertex by a given name. If the string s represents an integer i returns the ith vertex. Else returns a vertex whose name matches s. No uniqueness assumptions are made. The implementation is extremelty inefficient.

Returns:

a vertex whose name field s is a prefix of

Throws:

NoSuchElementException - if no vertex name begins with s

See Also:

getVertex

getVertex

public Vertex getVertex(int i)

Gets a vertex with a given index in the ordering of the vertices of this graph.

Parameters:

i - an index in the range 0..n-1 (otherwise an ArrayIndexOutOfBounds exception is thrown)

Returns:

the vertex with the given index

getVertex

public Vertex getVertex(String S)
                 throws NoSuchElementException

Gets a vertex matching a given string. If the give string represents an integer i returns the ith vertex. Else returns a vertex whose name matches the given string. No uniqueness assumptions are made. The implementation is extremelty inefficient.

Parameters:

S - the given string

Returns:

a vertex such that the given string is a prefix of the vertex' name

Throws:

NoSuchElementException - if no vertex name begins with the given string

getIndex

public int getIndex(Vertex v)

Gets the index of a given vertex in the ordering of this graph's vertices.

Parameters:

v - the given vertex (assumed to belong to this graph)

Returns:

the index of the given vertex in the range 0..n-1

hasEdge

public boolean hasEdge(Vertex u,
                       Vertex v)

Check if two given vertices are incident in this graph. If the edge is directed, it must point from the first given vertex to the second.

Parameters:

u - a given vertex (assumed to belong to this graph)

v - the other given vertex (assumed to belong to this graph)

Returns:

true if this graph contains an edge from u to v

getEdge

public Edge getEdge(Vertex u,
                    Vertex v)

Get the edge joining two given vertices in this graph, assuming it exists. If the edge is directed, it must point from the first given vertex to the second. If no such edge exists, a NoSuchElementException is thrown.

Parameters:

u - a given vertex (assumed to belong to this graph)

v - the other given vertex (assumed to belong to this graph)

Returns:

an edge from u to v in this graph

Throws:

NoSuchElementException - if no such edge exists in this graph

isDirected

public boolean isDirected()

Check if this graph is directed or not. The definition is that a graph is undirected unless it contains any directed edge.

Returns:

true if and only if this graph is directed

toString

public String toString()

Creates a string representation of this Graph. The syntax follows the DOT format, thus such strings can be directly input to graph drawing programs like dotty and neato.

Returns:

a human-readable representation of the graph

Overrides:

toString in class Object

getAdjecencyMatrix

public boolean[][] getAdjecencyMatrix()

Compute this graph's adjecency matrix.

Returns:

the adjecency matrix of the graph

getDistanceMatrix

public int[][] getDistanceMatrix()

Compute this graph's distance matrix. The entry D[i][j] of this matrix contains the length of the edge from the i'th to the j'th vertex if such an edge exists, otherwise it is undefined.

Returns:

the distance matrix of this graph

main

public static void main(String[] args)

Construct a graph from standard input and write its description to standard output.

See Also:

parseGraph