edu.uci.ics.dillenco.simplegraph01
Class Graph

java.lang.Object
  edu.uci.ics.dillenco.simplegraph01.Graph

public class Graph
extends Object

A Graph object represents a graph. A graph can be

• Embedded or not embedded (which means that a dual has been computed)
• Oriented or not oriented (but only if it is embedded)

Constructor Summary

Graph()
Constructs an empty graph (without vertices or edges).

Graph(int nodeCapacity, int edgeCapacity)
Constructs an empty graph (without vertices or edges).

Method Summary

QEdge	addEdge(Node node0, Node node1) Create a new edge and add it to this graph.
Node	addNode() Create a new node and add it to this graph.
void	dump() Prints a dump of the graph on the standard output
void	dump(PrintStream stream) Prints a dump of the graph on the specified print stream.
void	dump(String s) Prints a dump of the graph with specified identifying label string on the standard output.
void	dump(String s, PrintStream stream) Prints a dump of the graph with specified identifying label string on the specified print stream.
Iterable<HalfEdge>	getDirectedEdges() Returns an Iterable with an iterator that runs through all directed edges of this graph, ignoring undirected edges.
Iterable<HalfEdge>	getDirectedEdges(boolean check) Returns an Iterable with an iterator that runs through all directed edges of this graph.
Graph	getDual() Return the dual of this graph, if one has been computed.
int	getEdgeCount() Return the number of edges in this graph.
Iterable<HalfEdge>	getHalfEdges(boolean both) Returns an Iterable with an iterator that runs through all HalfEdges of this graph.
int	getID() Returns the id associated with this graph.
int	getNodeCount() Return the number of nodes in this graph.
Iterable<Node>	getNodes() Returns an Iterable with an iterator that runs through all Nodes of this graph.
Iterable<QEdge>	getQEdges() Returns an Iterable with an iterator that runs through all QEdges of this graph.
void	link(QEdge qEdge, Node node) Link the specified edge into the rotation system at the indicated node.

Methods inherited from class java.lang.Object

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

Constructor Detail

Graph

public Graph()

Constructs an empty graph (without vertices or edges).

Graph

public Graph(int nodeCapacity,
             int edgeCapacity)

Constructs an empty graph (without vertices or edges).

Parameters:

nodeCapacity - the initial capacity of the node list

edgeCapacity - the initial capacity of the edge list

Method Detail

dump

public void dump(String s)

Prints a dump of the graph with specified identifying label string on the standard output.

Parameters:

s - a label string to identify the dump

dump

public void dump()

Prints a dump of the graph on the standard output

dump

public void dump(PrintStream stream)

Prints a dump of the graph on the specified print stream.

Parameters:

stream - the print stream where the dump should be printed

dump

public void dump(String s,
                 PrintStream stream)

Prints a dump of the graph with specified identifying label string on the specified print stream.

Parameters:

s - a label string to identify the dump

stream - the print stream where the dump should be printed

getID

public int getID()

Returns the id associated with this graph. Graph id's are assigned sequentially, starting from 1, as graphs are created.

Returns:

the id associated with this graph.

getNodes

public Iterable<Node> getNodes()

Returns an Iterable with an iterator that runs through all Nodes of this graph. Each node will be returned exactly once, but the order is unspecified. The iterator only supports the hasNext() and next() methods. If remove() is called on the returned iterator, an UnsupportedOperationException will be thrown.

Returns:

an Iterable for this graph

getQEdges

public Iterable<QEdge> getQEdges()

Returns an Iterable with an iterator that runs through all QEdges of this graph. Each edge will be returned exactly once, but the order is unspecified. The iterator only supports the hasNext() and next() methods. If remove() is called on the returned iterator, an UnsupportedOperationException will be thrown.

Returns:

an Iterable for this graph

getHalfEdges

public Iterable<HalfEdge> getHalfEdges(boolean both)

Returns an Iterable with an iterator that runs through all HalfEdges of this graph. Each edge will be returned exactly once, but the order is unspecified. The iterator only supports the hasNext() and next() methods. If remove() is called on the returned iterator, an UnsupportedOperationException will be thrown.

Parameters:

both - if true, a half edge for each of the two half edges associated with an edge will be returned; otherwise, just one of them

Returns:

an Iterable for this graph

getDirectedEdges

public Iterable<HalfEdge> getDirectedEdges()

Returns an Iterable with an iterator that runs through all directed edges of this graph, ignoring undirected edges. Equivalent to getDirectedEdges(false).

Returns:

an Iterable for this graph

getDirectedEdges

public Iterable<HalfEdge> getDirectedEdges(boolean check)

Returns an Iterable with an iterator that runs through all directed edges of this graph. The iterator will run through a sequence of half edges,directed from orig to neighbor. Undirected edges will be skipped or will cause a GraphCheckException to be thrown, depending on the value of check. Each directed edge will be returned exactly once, but the order is unspecified. The iterator only supports the hasNext() and next() methods. If remove() is called on the returned iterator, an UnsupportedOperationException will be thrown.

Parameters:

check - if true, and the graph contains any undirected edges, a GraphCheckException is thrown

Returns:

an Iterable for this graph

addNode

public Node addNode()

Create a new node and add it to this graph.

addEdge

public QEdge addEdge(Node node0,
                     Node node1)

Create a new edge and add it to this graph.

getDual

public Graph getDual()

Return the dual of this graph, if one has been computed.

Returns:

dual of this graph if one has been computed, null otherwise.

getNodeCount

public int getNodeCount()

Return the number of nodes in this graph.

Returns:

the node count

getEdgeCount

public int getEdgeCount()

Return the number of edges in this graph.

Returns:

the edge count

link

public void link(QEdge qEdge,
                 Node node)

Link the specified edge into the rotation system at the indicated node. Successive calls to link at the same node will be arranged in positive order. Note that this call will not handle loops correctly.

Parameters:

qEdge - the QEdge to be linked

node - the Node into whose rotation system the edge is linked