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).

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

Method Summary

(package private) void	add(Node node) Add a node to this graph.
(package private) void	add(QEdge e) Add an edge to this graph.
(package private) void	add(QEdge e, boolean link) Add an edge to this graph.
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.
(package private) void	decrementNextNodeSeqID() Decrement the next available node sequential ID value.
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.
(package private) boolean	getDualFlag() Return a flag indicating whether this is a "primal" or "dual" graph.
int	getEdgeCount() Return the number of edges in this graph.
(package private) HalfEdge	getFirstHalfEdge() Return the first halfEdge 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.
(package private) int	getNextEdgePermID() Get the next available node edge ID value and increment the seed.
(package private) int	getNextNodePermID() Get the next available node permanent ID value and increment the seed.
(package private) int	getNextNodeSeqID() Get the next available node sequential ID value and increment the seed.
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.
(package private) void	setID(int n)

Methods inherited from class java.lang.Object

clone, equals, finalize, 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

Graph

Graph(int nodeCapacity,
      int edgeCapacity,
      boolean dualFlag)

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

dualFlag - true if this graph is constructed as a dual

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.

add

void add(Node node)

Add a node to this graph.

Parameters:

node - node to be added.

addEdge

public QEdge addEdge(Node node0,
                     Node node1)

Create a new edge and add it to this graph.

add

void add(QEdge e)

Add an edge to this graph. Equivalent to add(e,false).

Parameters:

e - edge to be added.

add

void add(QEdge e,
         boolean link)

Add an edge to this graph. Optionally link edge into vertex structure.

Parameters:

e - edge to be added.

link - true if edge is to be linked into vertex structure. If link is set true, edges will be linked in an unspecified order, so this should only be done if order of edges around vertices is not important.

setID

void setID(int n)

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.

getDualFlag

boolean getDualFlag()

Return a flag indicating whether this is a "primal" or "dual" graph. Only needed to allow creating an SNodeMap using the QEdge option when no QEdges have yet been allocated to this graph. May not be necessary.

Returns:

true if this is a "primal" graph.

getFirstHalfEdge

HalfEdge getFirstHalfEdge()

Return the first halfEdge in this graph. Its only purpose is to allow creating an SNodeMap using the QEdge option when no QEdges have yet been allocated to this graph.

Returns:

the first halfEdge in this graph.

getNextNodePermID

int getNextNodePermID()

Get the next available node permanent ID value and increment the seed.

Returns:

the allocated value

getNextNodeSeqID

int getNextNodeSeqID()

Get the next available node sequential ID value and increment the seed.

Returns:

the allocated value

decrementNextNodeSeqID

void decrementNextNodeSeqID()

Decrement the next available node sequential ID value.

getNextEdgePermID

int getNextEdgePermID()

Get the next available node edge ID value and increment the seed.

Returns:

the allocated value

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