Overview  Package   Class  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES
SUMMARY:  INNER | FIELD | CONSTR | METHOD DETAIL:  FIELD | CONSTR | METHOD

shared
Class Graph

java.lang.Object
  |
  +--shared.Graph
Direct Known Subclasses:
CGraph
public class Graph
extends java.lang.Object
implements ParamTypes

An instance G of the data type graph consists of a list V of nodes and a list E of edges (node and edge are item types). Distinct graphs have disjoint node and edge lists. The value of a variable of type node is either the node of some graph, or the special value nil (which is distinct from all nodes), or is undefined (before the first assignment to the variable). A corresponding statement is true for the variables of type edge.

A graph with empty node list is called empty. A pair of nodes (v,w) is associated with every edge; v is called the source of e and w is called the target of e, and v and w are called endpoints of e. The edge e is said to be incident to its endpoints.

A graph is either directed or undirected. The difference between directed and undirected graphs is the way the edges incident to a node are stored and how the concept adjacent is defined.

In directed graphs two lists of edges are associated with every node v: adj_edges(v) = e v = source(e), i.e., the list of edges starting in v, and in_edges(v) = e Lvert v = target(e), i.e., the list of edges ending in v. The list adj_edges(v) is called the adjacency list of node v and the edges in adj_edges(v) are called the edges adjacent to node v. For directed graphs we often use out_edges(v) as a synonym for adj_edges(v).

In undirected graphs only the list adj_edges(v) is defined for every every node v. Here it contains all edges incident to v, i.e., adj_edges(v) = e v source(e),target(e). An undirectect graph may not contain selfloops, i.e., it may not contain an edge whose source is equal to its target.

In a directed graph an edge is adjacent to its source and in an undirected graph it is adjacent to its source and target. In a directed graph a node w is adjacent to a node v if there is an edge (v,w) E; in an undirected graph w is adjacent to v if there is an edge (v,w) or (w,v) in the graph.

A directed graph can be made undirected and vice versa: G.make_undirected() makes the directed graph G undirected by appending for each node v the list in_edges(v) to the list adj_edges(v) (removing selfloops). Conversely, G.make_directed() makes the undirected graph G directed by splitting for each node v the list adj_edges(v) into the lists out_edges(v) and in_edges(v). Note that these two operations are not exactly inverse to each other. The data type ugraph (cf. section ref{Undirected Graphs) can only represent undirected graphs.

Reversal Information, Maps and Faces The reversal information of an edge e is accessed through G.reversal(e), it has type edge and may or may not be defined (=nil). Assume that G.reversal(e) is defined and let e' = G.reversal(e). Then e = (v,w) and e' = (w,v) for some nodes v and w, G.reversal(e') is defined and e = G.reversal(e'). In other words, reversal deserves its name.

We call a directed graph bidirected if for every edge of G the reversed edge also belongs to G and we call a bidirected graph a map if all edges have their reversal information defined. Maps are the data structure of choice for embedded graphs. For an edge e of a map G let face_cycle_succ(e) = cyclic_adj_succ(reversal(e)) and consider the sequence e, face_cycle_succ(e), face_cycle_succ(face_cycle_succ(e)),. The first edge to repeat in this sequence is e (why?) and the set of edges appearing in this sequence is called the face cycle containing e. Each edge is contained in some face cycle and face cycles are pairwise disjoint. Let f be the number of face cycles, n be the number of nodes, m be the number of edges, and let c be the number of connected components. Then g = (m/2 - n - f)/2 + c is called the genus of the map (note that m/2 is the number of edges in the underlying undirected graph). The genus is zero if and only if the map is planar, i.e., there is an embedding of G into the plane such that for every node v the counter-clockwise ordering of the edges around v agrees with the cyclic ordering of v's adjacency list.

If a graph G is a map the faces of G can be constructed explicitely by G.compute_faces(). Afterwards, the faces of G can be traversed by different iterators, e.g., forall_faces(f,G) iterates over all faces , forall_adj_faces(v) iterates over all faces adjacent to node v. By using face maps or arrays (data types face_map and face_array) additional information can be associated with the faces of a graph. Note that any update operation performed on G invalidates the list of faces. See the section on face operations for a complete list of available operations for faces.

Inner Class Summary
protected  class Graph.EdgeSorter
          Sorter class for edges.
protected  class Graph.MapEdgeOrd1
          Map edge ordering class.
protected  class Graph.MapEdgeOrd2
          Map edge ordering class.
protected  class Graph.NodeSorter
          Sorter class for nodes.
protected  class Graph.Orderer
          Ordering class for this graph.
 
Field Summary
protected  SortFunction edge_comparer
          Comparison function for comparing edges.
protected  GraphMap edge_data_map
          Graph map of edges.
protected  Graph.MapEdgeOrd1 map_edge_ord1
          Map edge ordering instance.
protected  Graph.MapEdgeOrd2 map_edge_ord2
          Map edge ordering instance.
protected  SortFunction node_comparer
          Comparison function for comparing nodes.
protected  GraphMap node_data_map
          Graph map of nodes.
protected  OrderingFunction order_alg
          Ordering function for sorts.
protected  Graph parent
          The parent graph of this graph.
 int space
          Unused data member.
protected  java.util.LinkedList v_list
          List of nodes in this graph.
 
Fields inherited from interface shared.ParamTypes
CHAR_TYPE_ID, DOUBLE_TYPE_ID, FLOAT_TYPE_ID, INT_TYPE_ID, LONG_TYPE_ID, PTR_TYPE_ID, SHORT_TYPE_ID, UNKNOWN_TYPE_ID
 
Constructor Summary
Graph()
          Constructor.
Graph(Graph a)
          Copy constructor.
Graph(Graph G, java.util.LinkedList el)
          SubGraph constructor.
Graph(Graph a, java.util.LinkedList nl, java.util.LinkedList el)
          SubGraph constructor.
Graph(int sz1, int sz2)
          Constructor.
 
Method Summary
protected  Face access_face(Edge e)
          Returns the face containing e.
 java.util.LinkedList adj_edges(Node v)
          Returns the adjacent edges of the given node.
 java.util.LinkedList adj_nodes(Node v)
          Returns the nodes reached through all adjacent edges.
 Edge adj_pred(Edge e, Node v)
          Returns the previous adjacent edge.
 Edge adj_succ(Edge e, Node v)
          Returns the next adjacent edge.
 java.util.LinkedList all_edges()
          Returns a list of all edges in this graph.
 java.util.LinkedList all_faces()
          Returns a list of all faces in this graph.
 java.util.LinkedList all_nodes()
          Returns a list of all nodes in this graph.
protected  void assign(Edge e, java.lang.Object x)
          Assigns the given data to the graph object.
protected  void assign(Face f, java.lang.Object x)
          Assigns the given data to the graph object.
 void assign(Graph G)
          Copies the given graph into this graph.
protected  void assign(Node v, java.lang.Object x)
          Assigns the given data to the graph object.
 void bucket_sort_edges(GraphMap A)
          Sorts the edge list in the given map.
 void bucket_sort_edges(int l, int h, OrderingFunction ord)
          Sorts the edge list between the given indecies.
 void bucket_sort_edges(OrderingFunction ord)
          Sorts the edge list.
 void bucket_sort_nodes(GraphMap A)
          Sorts the node list in the given map.
 void bucket_sort_nodes(int l, int h, OrderingFunction ord)
          Sorts the node list between the given indecies.
 void bucket_sort_nodes(OrderingFunction ord)
          Sorts the node list.
 void bucket_sort(java.util.LinkedList the_list, int i, int j, OrderingFunction ord_reference)
          Sorts the given list.
 void bucket_sort(java.util.LinkedList the_list, OrderingFunction ord)
          Sorts the given list.
 Edge choose_edge()
          Choose random edge.
 Face choose_face()
          Randomly returns a face.
 Node choose_node()
          Choose a random node.
protected  void clear_all_entries()
          Clears all entries, does nothing.
 void clear()
          Clears this graph of edges, nodes, and faces.
 void comment(java.lang.String S)
          Sets comment string; does nothing.
protected  void copy_all_entries()
          Copies all entries; does nothing.
 void copy_graph(Graph G)
          Copies the given graph.
 Edge cyclic_adj_pred(Edge e, Node v)
          Returns the previous adjacent edge.
 Edge cyclic_adj_succ(Edge e, Node v)
          Returns the next adjacent edge.
 void del_adj_edge(Edge e, Node v, Node w)
          Deletes the given edge between the given nodes.
 void del_all_edges()
          Deletes all edges in graph.
 void del_all_faces()
          Deletes all faces of graph.
 void del_all_nodes()
          Deletes all nodes in graph.
 void del_edge(Edge e)
          Edge to be deleted.
 void del_edges(java.util.LinkedList L)
          Deletes the edges in the given list.
 void del_node(Node v)
          Delete the given node.
 void del_nodes(java.util.LinkedList L)
          Deletes the nodes in the given list.
 java.lang.String edge_type()
          Returns "void".
 java.util.ListIterator edgeIterator()
          Returns a listiterator of edges in this graph.
 boolean empty()
          Returns true if there are no nodes in this graph, false otherwise.
 java.lang.Object entry(Edge e)
          Returns the data stored in this graph object.
 java.lang.Object entry(Face f)
          Returns the data stored in this graph object.
 java.lang.Object entry(Node v)
          Returns the data stored in this graph object.
 Face face_of(Edge e)
          Returns the face containing e.
 java.lang.String face_type()
          Returns "void".
 Edge first_edge()
          Returns the first edge in the edge list.
 Edge first_face_edge(Face f)
          Returns the first edge in the graph face.
 Face first_face()
          Returns the first face in the face list.
 Node first_node()
          Returns the first node in the graph's node list.
 void hide_edge(Edge e)
          Makes the given edge hidden.
 java.lang.Object inf(Edge e)
          Returns the data stored in this graph object.
 java.lang.Object inf(Face f)
          Returns the data stored in this graph object.
 java.lang.Object inf(Node v)
          Returns the data stored in this graph object.
 void ins_adj_edge(Edge e, Node v, Edge e1, Node w, Edge e2, int d1, int d2)
          Adds edge e between the given nodes.
 java.util.LinkedList insert_reverse_edges()
          Creates a list of reversed edges.
 boolean is_directed()
          Returns true if this graph is directed, false otherwise.
 boolean is_hidden(Edge e)
          Returns true if the given edge is hidden, false otherwise.
 boolean is_undirected()
          Returns true if this graph is undirected, false otherwise.
 void join(Graph G)
          Joins the given graph with this graph.
 Edge last_edge()
          Returns the last edge in the edge list.
 Face last_face()
          Returns the last face in the face list.
 Node last_node()
          Returns the last node in the graph's node list.
 void make_directed()
          Converts this graph to a directed graph.
 boolean make_map()
          Returns true if every edge has a reverse edge, false otherwise.
 void make_map(java.util.LinkedList R)
          Adds reverse edges of all edges in graph to the given list.
 void make_undirected()
          Converts this graph to an undirected graph.
 Node merge_nodes(Node v1, Node v2)
          Merges the given nodes.
 void move_edge(Edge e, Edge e1, Edge e2, int d1, int d2)
          Moves edge e.
 void move_edge(Edge e, Edge e1, Node w, int dir)
          Moves edge e.
 void move_edge(Edge e, Node v, Node w)
          Moves edge e.
 Edge new_edge(Edge e1, Edge e2)
          Creates a new edge between the source and target nodes of the given edges.
 Edge new_edge(Edge e1, Edge e2, int d1)
          Creates a new edge between the source and target nodes of the given edges.
 Edge new_edge(Edge e1, Edge e2, int d1, int d2)
          Creates a new edge between the source and target nodes of the given edges.
 Edge new_edge(Edge e1, Edge e2, java.lang.Object i, int dir1, int dir2)
          Creates a new edge
 Edge new_edge(Edge e, Node w)
          Creates a new edge between the source of the given edge and the given target node.
 Edge new_edge(Edge e, Node w, int dir)
          Creates a new edge between the source of the given edge and the given target node.
 Edge new_edge(Edge e, Node w, java.lang.Object i, int dir)
          Creates a new edge between the source of the given edge and the given target node.
 Edge new_edge(Node v, Edge e)
          Creates a new edge between the given source node and the target of the given edge.
 Edge new_edge(Node v, Edge e, int dir)
          Creates a new edge between the given source node and the target of the given edge.
 Edge new_edge(Node v, Edge e, Node w)
          Creates a new edge between the given nodes.
 Edge new_edge(Node v, Edge e1, Node w, Edge e2)
          Creates a new edge between the given nodes.
 Edge new_edge(Node v, Edge e1, Node w, Edge e2, int d1)
          Creates a new edge between the given nodes.
 Edge new_edge(Node v, Edge e1, Node w, Edge e2, int d1, int d2)
          Creates a new edge between the given nodes.
 Edge new_edge(Node v, Edge e1, Node w, Edge e2, java.lang.Object i, int d1, int d2)
          Creates a new edge to the given nodes.
 Edge new_edge(Node v, Edge e, Node w, int d)
          Creates a new edge between the given nodes.
 Edge new_edge(Node v, Edge e, Node w, java.lang.Object i, int dir)
          Creates a new edge between the given nodes.
 Edge new_edge(Node v, Edge e, java.lang.Object i, int dir)
          Creates a new edge between the target of the given edge and the given source node.
 Edge new_edge(Node v, Node w)
          Creates a new edge between the given nodes.
 Edge new_edge(Node v, Node w, Edge e)
          Creates a new edge between the given nodes.
 Edge new_edge(Node v, Node w, Edge e, int d)
          Creates a new edge between the given nodes.
 Edge new_edge(Node v, Node w, Edge e, java.lang.Object i, int dir)
          Creates a new edge between the given nodes.
 Edge new_edge(Node v, Node w, java.lang.Object i)
          Creates a new edge between the given nodes and containing the given information.
 java.lang.Object new_node()
          Creates a new node.
protected  Node new_node(java.lang.Object i)
          Creates a new node.
 Edge next_face_edge(Edge e, Face F)
          Returns the next edge in the face.
 java.lang.String node_type()
          Returns "void".
 java.util.ListIterator nodeIterator()
          Returns a listiterator of the list of nodes in this graph.
 int number_of_edges()
          Returns the number of edges.
 int number_of_faces()
          Returns the number of faces.
 int number_of_nodes()
          Returns the number of nodes.
protected  void post_clear_handler()
          Function called after entries are cleared.
protected  void post_del_edge_handler(Node A, Node B)
          Function called after edge is deleted.
protected  void post_del_node_handler()
          Function called after node deleted.
protected  void post_hide_edge_handler(Edge E)
          Function called after edge is hidden.
protected  void post_move_edge_handler(Edge E, Node A, Node B)
          Function called after edge is moved.
protected  void post_new_edge_handler(Edge E)
          Function called after new edge is created.
protected  void post_new_node_handler(Node A)
          Function called after inserting a node.
protected  void post_restore_edge_handler(Edge E)
          Function called after edge is restored.
protected  void pre_clear_handler()
          Function called before entries are cleared.
protected  void pre_del_edge_handler(Edge E)
          Function called when edge is deleted.
protected  void pre_del_node_handler(Node A)
          Function called before deleting a node.
protected  void pre_hide_edge_handler(Edge E)
          Function called before edge is hidden.
protected  void pre_move_edge_handler(Edge E, Node A, Node B)
          Function called before edge is moved.
protected  void pre_new_edge_handler(Node A, Node B)
          Function called before a new edge is created.
protected  void pre_new_node_handler()
          Function called before inserting a node.
protected  void pre_restore_edge_handler(Edge E)
          Function called before edge is restored.
 Edge pred_edge(Edge e)
          Returns the previous edge in the edge list.
 Face pred_face(Face f)
          Returns the previous face in the face list.
 Node pred_node(Node v)
          Returns the previous node in the node list.
 void print(java.lang.String s, java.io.Writer out)
          Prints graph to the supplied writer.
 void print(java.io.Writer out)
          Prints graph to the supplied writer.
 boolean query()
          Returns true.
 boolean query(Edge E)
          Returns true.
 boolean query(Node N, Node M)
          Returns true.
 int register_map(GraphMap M)
          Registers the given GraphMap.
 void restore_all_edges()
          Restore all edges.
 void restore_edge(Edge e)
          Restores edge from being hidden.
 void rev_all_edges()
          Reverses the direction on all edges.
 Edge rev_edge(Edge e)
          Reverses the direction of the given edge.
 Graph rev()
          Reverses all edges.
 Edge reversal(Edge e)
          Returns the reversed edge.
 Edge reverse(Edge e)
          Returns the reversed edge.
 void set_edge_entry(Edge e, java.lang.String s)
          Sets the edge entry, does nothing.
 void set_node_entry(Node v, java.lang.String s)
          Sets the node entry, does nothing.
 int size(Face f)
          Returns the size of the given face.
protected  void sort_edges()
          Sorts edges.
 void sort_edges(GraphMap A)
          Sort edges in the given graph map; does nothing.
 void sort_edges(java.util.LinkedList el)
          Sort edges in the given list.
 void sort_edges(SortFunction sorter)
          Sorts edges using the given sort function.
protected  void sort_nodes()
          Sorts nodes.
 void sort_nodes(GraphMap A)
          Sort nodes in the given graph map; does nothing.
 void sort_nodes(java.util.LinkedList vl)
          Sort nodes in the given list.
 void sort_nodes(SortFunction sorter)
          Sorts nodes using the given sort function.
 Node split_edge(Edge e, Edge e1, Edge e2)
          Splits edge e into e1 and e2.
protected  Node split_edge(Edge e, java.lang.Object node_inf, Edge e1, Edge e2)
          Splits edge e into edges e1 and e2.
 Edge succ_edge(Edge e)
          Returns the next edge in the edge list.
 Face succ_face(Face f)
          Returns the next face in the face list.
 Node succ_node(Node v)
          Returns the next node in the node list.
 void touch(Edge E, java.lang.String S)
          Does nothing.
 void touch(Node N, java.lang.String S)
          Does nothing.
 void unregister_map(GraphMap M)
          Unregisters the given GraphMap.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

v_list

protected java.util.LinkedList v_list
List of nodes in this graph.

parent

protected Graph parent
The parent graph of this graph.

node_data_map

protected GraphMap node_data_map
Graph map of nodes.

edge_data_map

protected GraphMap edge_data_map
Graph map of edges.

space

public int space
Unused data member.

edge_comparer

protected SortFunction edge_comparer
Comparison function for comparing edges.

node_comparer

protected SortFunction node_comparer
Comparison function for comparing nodes.

order_alg

protected OrderingFunction order_alg
Ordering function for sorts.

map_edge_ord1

protected Graph.MapEdgeOrd1 map_edge_ord1
Map edge ordering instance.

map_edge_ord2

protected Graph.MapEdgeOrd2 map_edge_ord2
Map edge ordering instance.
Constructor Detail

Graph

public Graph()
Constructor.

Graph

public Graph(int sz1,
             int sz2)
Constructor.
Parameters:
sz1 - Number of nodes.
sz2 - Number of Edges.

Graph

public Graph(Graph a,
             java.util.LinkedList nl,
             java.util.LinkedList el)
SubGraph constructor.
Parameters:
a - Parent graph.
nl - List of nodes for this graph.
el - List of edges for this graph.

Graph

public Graph(Graph G,
             java.util.LinkedList el)
SubGraph constructor.
Parameters:
G - Parent graph.
el - List of Edges for this graph.

Graph

public Graph(Graph a)
Copy constructor.
Parameters:
a - Graph to be copied.
Method Detail

nodeIterator

public java.util.ListIterator nodeIterator()
Returns a listiterator of the list of nodes in this graph.
Returns:
The list iterator of nodes.

edgeIterator

public java.util.ListIterator edgeIterator()
Returns a listiterator of edges in this graph.
Returns:
The list iterator of edges in this graph.

new_edge

public Edge new_edge(Node v,
                     Edge e1,
                     Node w,
                     Edge e2,
                     java.lang.Object i,
                     int d1,
                     int d2)
Creates a new edge to the given nodes. Can be used with undirected graphs.
Parameters:
v - The source node.
e1 - Edge connecting to the source node.
w - The target node.
e2 - Edge connecting to the target node.
i - The data to be stored in the edge.
d1 - Method of connecting to e1. The new edge is connected after(if d1=0)/before(if d1=1) e1.
d2 - Method of connecting to e2. The new edge is connected after(if d2=0)/before(if d2=1) e2.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Node w,
                     java.lang.Object i)
Creates a new edge between the given nodes and containing the given information.
Parameters:
v - The source node for the new edge.
w - The target node for the new edge.
i - The data to be stored in the edge.
Returns:
The new edge.

new_edge

public Edge new_edge(Edge e,
                     Node w,
                     java.lang.Object i,
                     int dir)
Creates a new edge between the source of the given edge and the given target node.
Parameters:
e - The edge connected to the source node.
w - The target node.
i - The data stored in the new edge.
dir - Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Edge e,
                     java.lang.Object i,
                     int dir)
Creates a new edge between the target of the given edge and the given source node.
Parameters:
v - The source node.
e - The edge connected to the target node.
i - The data stored in the new edge.
dir - Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
Returns:
The new edge.

new_edge

public Edge new_edge(Edge e1,
                     Edge e2,
                     java.lang.Object i,
                     int dir1,
                     int dir2)
Creates a new edge
Parameters:
e1 - Edge connecting to source node.
e2 - Edge connecting to target node.
i - The data stored in the new edge.
dir1 - Method of connecting to e1. The new edge is connected after(if dir1=0)/before(if dir1=1) e1.
dir2 - Method of connecting to e2. The new edge is connected after(if dir2=0)/before(if dir2=1) e2.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Edge e,
                     Node w,
                     java.lang.Object i,
                     int dir)
Creates a new edge between the given nodes.
Parameters:
v - The source node.
e - Edge connected to the source node.
w - The target node.
i - The data stored in the new edge.
dir - Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Node w,
                     Edge e,
                     java.lang.Object i,
                     int dir)
Creates a new edge between the given nodes.
Parameters:
v - The source node.
w - The target node.
e - Edge connected to the target node.
i - The data stored in the new edge.
dir - Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Node w)
Creates a new edge between the given nodes.
Parameters:
v - The source node.
w - The target node.
Returns:
The new edge.

new_edge

public Edge new_edge(Edge e,
                     Node w)
Creates a new edge between the source of the given edge and the given target node.
Parameters:
e - Edge connected to the source node.
w - The target node.
Returns:
The new edge.

new_edge

public Edge new_edge(Edge e,
                     Node w,
                     int dir)
Creates a new edge between the source of the given edge and the given target node.
Parameters:
e - Edge connected to the source node.
w - The target node.
dir - Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Edge e)
Creates a new edge between the given source node and the target of the given edge.
Parameters:
v - The source node.
e - Edge connected to the target node.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Edge e,
                     int dir)
Creates a new edge between the given source node and the target of the given edge.
Parameters:
v - The source node.
e - Edge connected to the target node.
dir - Method of connecting to e. The new edge is connected after(if dir=0)/before(if dir=1) e.
Returns:
The new edge.

new_edge

public Edge new_edge(Edge e1,
                     Edge e2,
                     int d1,
                     int d2)
Creates a new edge between the source and target nodes of the given edges.
Parameters:
e1 - Edge connected to the source node.
e2 - Edge connected to the target node.
d1 - Method of connecting to e1. The new edge is connected after(if d1=0)/before(if d1=1) e1.
d2 - Method of connecting to e2. The new edge is connected after(if d2=0)/before(if d2=1) e2.
Returns:
The new edge.

new_edge

public Edge new_edge(Edge e1,
                     Edge e2,
                     int d1)
Creates a new edge between the source and target nodes of the given edges. The new edge is added after e2.
Parameters:
e1 - Edge connected to the source node.
e2 - Edge connected to the target node.
d1 - Method of connecting to e1. The new edge is connected after(if d1=0)/before(if d1=1) e1.
Returns:
The new edge.

new_edge

public Edge new_edge(Edge e1,
                     Edge e2)
Creates a new edge between the source and target nodes of the given edges. The new edge is added after both edges.
Parameters:
e1 - Edge connected to the source node.
e2 - Edge connected to the target node.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Edge e1,
                     Node w,
                     Edge e2,
                     int d1,
                     int d2)
Creates a new edge between the given nodes.
Parameters:
v - The source node.
e1 - Edge connected to the source node.
w - The target node.
e2 - Edge connected to the target node.
d1 - Method of connecting to e1. The new edge is connected after(if d1=0)/before(if d1=1) e1.
d2 - Method of connecting to e2. The new edge is connected after(if d2=0)/before(if d2=1) e2.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Edge e1,
                     Node w,
                     Edge e2,
                     int d1)
Creates a new edge between the given nodes. The new edge is added after e2.
Parameters:
v - The source node.
e1 - Edge connected to the source node.
w - The target node.
e2 - Edge connected to the target node.
d1 - Method of connecting to e1. The new edge is connected after(if d1=0)/before(if d1=1) e1.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Edge e1,
                     Node w,
                     Edge e2)
Creates a new edge between the given nodes. The new edge is added after both edges.
Parameters:
v - The source node.
e1 - Edge connected to the source node.
w - The target node.
e2 - Edge connected to the target node.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Edge e,
                     Node w,
                     int d)
Creates a new edge between the given nodes.
Parameters:
v - The source node.
e - Edge connected to the source node.
w - The target node.
d - Method of connecting to e. The new edge is connected after(if d=0)/before(if d=1) e.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Edge e,
                     Node w)
Creates a new edge between the given nodes. the new edge is added after e.
Parameters:
v - The source node.
e - Edge connected to the source node.
w - The target node.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Node w,
                     Edge e,
                     int d)
Creates a new edge between the given nodes.
Parameters:
v - The source node.
w - The target node.
e - Edge connected to the target node.
d - Method of connecting to e. The new edge is connected after(if d=0)/before(if d=1) e.
Returns:
The new edge.

new_edge

public Edge new_edge(Node v,
                     Node w,
                     Edge e)
Creates a new edge between the given nodes.
Parameters:
v - The source node.
w - The target node.
e - Edge connected to the target node.
Returns:
The new edge.

ins_adj_edge

public void ins_adj_edge(Edge e,
                         Node v,
                         Edge e1,
                         Node w,
                         Edge e2,
                         int d1,
                         int d2)
Adds edge e between the given nodes.
Parameters:
e - Edge to be added.
v - Source node for the edge.
e1 - Edge connected to the source node.
w - Target node for the edge.
e2 - Edge connected to the target node.
d1 - Method of connecting to e1. The new edge is connected after(if d1=0)/before(if d1=1) e1.
d2 - Method of connecting to e2. The new edge is connected after(if d2=0)/before(if d2=1) e2.

del_adj_edge

public void del_adj_edge(Edge e,
                         Node v,
                         Node w)
Deletes the given edge between the given nodes.
Parameters:
e - The edge to be deleted.
v - The source node for the edge.
w - The target node for the edge.

register_map

public int register_map(GraphMap M)
Registers the given GraphMap.
Parameters:
M - Graphmap to be registered.
Returns:
-1 if there is not enough free_data space, 0 otherwise.

unregister_map

public void unregister_map(GraphMap M)
Unregisters the given GraphMap.
Parameters:
M - Graphmap to be unregistered.

first_node

public Node first_node()
Returns the first node in the graph's node list.
Returns:
The first node.

last_node

public Node last_node()
Returns the last node in the graph's node list.
Returns:
The last node.

succ_node

public Node succ_node(Node v)
Returns the next node in the node list.
Parameters:
v - The node whose successor is requested.
Returns:
The next node.

pred_node

public Node pred_node(Node v)
Returns the previous node in the node list.
Parameters:
v - The node whose predecessor is requested.
Returns:
The previous node.

first_edge

public Edge first_edge()
Returns the first edge in the edge list.
Returns:
The first edge.

last_edge

public Edge last_edge()
Returns the last edge in the edge list.
Returns:
The last edge.

succ_edge

public Edge succ_edge(Edge e)
Returns the next edge in the edge list.
Parameters:
e - The edge whose successor is requested.
Returns:
The next edge.

pred_edge

public Edge pred_edge(Edge e)
Returns the previous edge in the edge list.
Parameters:
e - The edge whose predecessor is requested.
Returns:
The previous edge.

copy_all_entries

protected void copy_all_entries()
Copies all entries; does nothing.

clear_all_entries

protected void clear_all_entries()
Clears all entries, does nothing.

node_type

public java.lang.String node_type()
Returns "void".
Returns:
"void"

edge_type

public java.lang.String edge_type()
Returns "void".
Returns:
"void"

face_type

public java.lang.String face_type()
Returns "void".
Returns:
"void"

copy_graph

public void copy_graph(Graph G)
Copies the given graph.
Parameters:
G - The graph to be copied.

new_node

public java.lang.Object new_node()
Creates a new node.
Returns:
A new node.

new_node

protected Node new_node(java.lang.Object i)
Creates a new node.
Parameters:
i - Data to be stored in this node.
Returns:
A new node.

assign

public void assign(Graph G)
Copies the given graph into this graph.
Parameters:
G - The graph to be copied.

set_node_entry

public void set_node_entry(Node v,
                           java.lang.String s)
Sets the node entry, does nothing.
Parameters:
v - The node to be set.
s - The new setting.

set_edge_entry

public void set_edge_entry(Edge e,
                           java.lang.String s)
Sets the edge entry, does nothing.
Parameters:
e - The edge to be set.
s - The new setting.

pre_new_node_handler

protected void pre_new_node_handler()
Function called before inserting a node.

post_new_node_handler

protected void post_new_node_handler(Node A)
Function called after inserting a node.
Parameters:
A - The node added.

pre_del_node_handler

protected void pre_del_node_handler(Node A)
Function called before deleting a node.
Parameters:
A - Node deleted.

post_del_node_handler

protected void post_del_node_handler()
Function called after node deleted.

pre_new_edge_handler

protected void pre_new_edge_handler(Node A,
                                    Node B)
Function called before a new edge is created.
Parameters:
A - Source node.
B - Target node.

post_new_edge_handler

protected void post_new_edge_handler(Edge E)
Function called after new edge is created.
Parameters:
E - The new edge.

pre_del_edge_handler

protected void pre_del_edge_handler(Edge E)
Function called when edge is deleted.
Parameters:
E - The edge deleted.

post_del_edge_handler

protected void post_del_edge_handler(Node A,
                                     Node B)
Function called after edge is deleted.
Parameters:
A - Source node of edge.
B - Target node of edge.

pre_move_edge_handler

protected void pre_move_edge_handler(Edge E,
                                     Node A,
                                     Node B)
Function called before edge is moved.
Parameters:
E - Edge moved.
A - Edge's source node.
B - Edge's target node.

post_move_edge_handler

protected void post_move_edge_handler(Edge E,
                                      Node A,
                                      Node B)
Function called after edge is moved.
Parameters:
E - The edge moved.
A - The edge's source node.
B - The edge's target node.

pre_hide_edge_handler

protected void pre_hide_edge_handler(Edge E)
Function called before edge is hidden.
Parameters:
E - Edge to hide.

post_hide_edge_handler

protected void post_hide_edge_handler(Edge E)
Function called after edge is hidden.
Parameters:
E - Edge hidden.

pre_restore_edge_handler

protected void pre_restore_edge_handler(Edge E)
Function called before edge is restored.
Parameters:
E - Edge to be restored.

post_restore_edge_handler

protected void post_restore_edge_handler(Edge E)
Function called after edge is restored.
Parameters:
E - Edge restored.

pre_clear_handler

protected void pre_clear_handler()
Function called before entries are cleared.

post_clear_handler

protected void post_clear_handler()
Function called after entries are cleared.

number_of_nodes

public int number_of_nodes()
Returns the number of nodes.
Returns:
Number of nodes.

number_of_edges

public int number_of_edges()
Returns the number of edges.
Returns:
Number of edges.

all_nodes

public java.util.LinkedList all_nodes()
Returns a list of all nodes in this graph.
Returns:
A list of nodes.

all_edges

public java.util.LinkedList all_edges()
Returns a list of all edges in this graph.
Returns:
A list of edges.

all_faces

public java.util.LinkedList all_faces()
Returns a list of all faces in this graph.
Returns:
A list of faces.

choose_node

public Node choose_node()
Choose a random node.
Returns:
A node.

choose_edge

public Edge choose_edge()
Choose random edge.
Returns:
An edge.

is_directed

public boolean is_directed()
Returns true if this graph is directed, false otherwise.
Returns:
True if this graph is directed, false otherwise.

is_undirected

public boolean is_undirected()
Returns true if this graph is undirected, false otherwise.
Returns:
True if this graph is undirected, false otherwise.

empty

public boolean empty()
Returns true if there are no nodes in this graph, false otherwise.
Returns:
True if there are no nodes in this graph, false otherwise.

entry

public java.lang.Object entry(Node v)
Returns the data stored in this graph object.
Parameters:
v - The object whose information is requested.
Returns:
The data stored in the given object.

entry

public java.lang.Object entry(Edge e)
Returns the data stored in this graph object.
Parameters:
e - The object whose information is requested.
Returns:
The data stored in the given object.

entry

public java.lang.Object entry(Face f)
Returns the data stored in this graph object.
Parameters:
f - The object whose information is requested.
Returns:
The data stored in the given object.

inf

public java.lang.Object inf(Node v)
Returns the data stored in this graph object.
Parameters:
v - The object whose information is requested.
Returns:
The data stored in the given object.

inf

public java.lang.Object inf(Edge e)
Returns the data stored in this graph object.
Parameters:
e - The object whose information is requested.
Returns:
The data stored in the given object.

inf

public java.lang.Object inf(Face f)
Returns the data stored in this graph object.
Parameters:
f - The object whose information is requested.
Returns:
The data stored in the given object.

split_edge

protected Node split_edge(Edge e,
                          java.lang.Object node_inf,
                          Edge e1,
                          Edge e2)
Splits edge e into edges e1 and e2.
Parameters:
e - Edge to be split.
node_inf - Node data for target node.
e1 - First edge si is split into.
e2 - Second edge e is split into.
Returns:
The new target node.

assign

protected void assign(Node v,
                      java.lang.Object x)
Assigns the given data to the graph object.
Parameters:
v - The node to store the data.
x - The data stored.

assign

protected void assign(Edge e,
                      java.lang.Object x)
Assigns the given data to the graph object.
Parameters:
e - The edge to store the data.
x - The data stored.

assign

protected void assign(Face f,
                      java.lang.Object x)
Assigns the given data to the graph object.
Parameters:
f - The face to store the data.
x - The data stored.

access_face

protected Face access_face(Edge e)
Returns the face containing e.
Parameters:
e - Edge for which face is requested.
Returns:
The face holding e.

merge_nodes

public Node merge_nodes(Node v1,
                        Node v2)
Merges the given nodes.
Parameters:
v1 - First node merged.
v2 - Second node merged.
Returns:
The merged node.

split_edge

public Node split_edge(Edge e,
                       Edge e1,
                       Edge e2)
Splits edge e into e1 and e2.
Parameters:
e - Edge to be split.
e1 - First edge split from e.
e2 - Second edge split from e.
Returns:
The target node of the split edge.

hide_edge

public void hide_edge(Edge e)
Makes the given edge hidden.
Parameters:
e - Edge to hide.

is_hidden

public boolean is_hidden(Edge e)
Returns true if the given edge is hidden, false otherwise.
Parameters:
e - The edge to be checked.
Returns:
True if the given edge is hidden, false otherwise.

restore_edge

public void restore_edge(Edge e)
Restores edge from being hidden.
Parameters:
e - Edge to be restored.

restore_all_edges

public void restore_all_edges()
Restore all edges.

del_node

public void del_node(Node v)
Delete the given node.
Parameters:
v - The node to be deleted.

del_edge

public void del_edge(Edge e)
Edge to be deleted.
Parameters:
e - Edge to be deleted.

del_nodes

public void del_nodes(java.util.LinkedList L)
Deletes the nodes in the given list.
Parameters:
L - List of nodes to be deleted.

del_edges

public void del_edges(java.util.LinkedList L)
Deletes the edges in the given list.
Parameters:
L - List of edges to be deleted.

del_all_nodes

public void del_all_nodes()
Deletes all nodes in graph.

del_all_edges

public void del_all_edges()
Deletes all edges in graph.

del_all_faces

public void del_all_faces()
Deletes all faces of graph.

move_edge

public void move_edge(Edge e,
                      Edge e1,
                      Edge e2,
                      int d1,
                      int d2)
Moves edge e.
Parameters:
e - Edge to be moved.
e1 - Edge connected to the source node.
e2 - Edge connected to the target node.
d1 - Method of connecting to e1. The new edge is connected after(if d1=0)/before(if d1=1) e1.
d2 - Method of connecting to e2. The new edge is connected after(if d2=0)/before(if d2=1) e2.

move_edge

public void move_edge(Edge e,
                      Edge e1,
                      Node w,
                      int dir)
Moves edge e.
Parameters:
e - Edge to be moved.
e1 - Edge connected to the source node.
w - New target node.
dir - Method of connecting to e1. The new edge is connected after(if dir=0)/before(if dir=1) e1.

move_edge

public void move_edge(Edge e,
                      Node v,
                      Node w)
Moves edge e.
Parameters:
e - Edge to be moved.
v - New source node.
w - New target node.

rev_edge

public Edge rev_edge(Edge e)
Reverses the direction of the given edge.
Parameters:
e - The edge whose direction is reversed.
Returns:
The reversed edge.

rev_all_edges

public void rev_all_edges()
Reverses the direction on all edges.

rev

public Graph rev()
Reverses all edges.
Returns:
Graph of reversed edges.

insert_reverse_edges

public java.util.LinkedList insert_reverse_edges()
Creates a list of reversed edges.
Returns:
List of reversed edges.

make_undirected

public void make_undirected()
Converts this graph to an undirected graph.

make_directed

public void make_directed()
Converts this graph to a directed graph.

clear

public void clear()
Clears this graph of edges, nodes, and faces.

join

public void join(Graph G)
Joins the given graph with this graph.
Parameters:
G - Graph to be joined.

reversal

public Edge reversal(Edge e)
Returns the reversed edge.
Parameters:
e - The edge for which reversed is requested.
Returns:
The reverse of e.

reverse

public Edge reverse(Edge e)
Returns the reversed edge.
Parameters:
e - The edge for which reversed is requested.
Returns:
The reverse of e.

face_of

public Face face_of(Edge e)
Returns the face containing e.
Parameters:
e - Edge for which face is requested.
Returns:
The face holding e.

number_of_faces

public int number_of_faces()
Returns the number of faces.
Returns:
The number of faces.

first_face

public Face first_face()
Returns the first face in the face list.
Returns:
The first face in the face list.

last_face

public Face last_face()
Returns the last face in the face list.
Returns:
The last face in the face list.

succ_face

public Face succ_face(Face f)
Returns the next face in the face list.
Parameters:
f - The face whose successor is requested.
Returns:
The next face.

pred_face

public Face pred_face(Face f)
Returns the previous face in the face list.
Parameters:
f - The face whose predecessor is requested.
Returns:
The previous face.

choose_face

public Face choose_face()
Randomly returns a face.
Returns:
A face.

adj_nodes

public java.util.LinkedList adj_nodes(Node v)
Returns the nodes reached through all adjacent edges.
Parameters:
v - The node for which adjacent nodes are requested.
Returns:
List of adjacent nodes.

adj_edges

public java.util.LinkedList adj_edges(Node v)
Returns the adjacent edges of the given node.
Parameters:
v - The node for which adjacent edges are requested.
Returns:
List of adjacent edges.

size

public int size(Face f)
Returns the size of the given face.
Parameters:
f - The face for which size is requested.
Returns:
The face size.

first_face_edge

public Edge first_face_edge(Face f)
Returns the first edge in the graph face.
Parameters:
f - Face for which a first edge is requested.
Returns:
The first edge.

next_face_edge

public Edge next_face_edge(Edge e,
                           Face F)
Returns the next edge in the face.
Parameters:
e - The edge for which a successor is requested.
F - The face for which the next edge is requested.
Returns:
The next edge.

adj_succ

public Edge adj_succ(Edge e,
                     Node v)
Returns the next adjacent edge.
Parameters:
e - Edge for which successor is requested.
v - The node connected to these adjacent edges.
Returns:
The next adjacent edge.

adj_pred

public Edge adj_pred(Edge e,
                     Node v)
Returns the previous adjacent edge.
Parameters:
e - Edge for which predecessor edge is requested.
v - The node connected to these adjacent edges.
Returns:
The next previous edge.

cyclic_adj_succ

public Edge cyclic_adj_succ(Edge e,
                            Node v)
Returns the next adjacent edge. If end is reached, first edge is returned.
Parameters:
e - Edge for which successor is requested.
v - The node connected to these adjacent edges.
Returns:
The next adjacent edge.

cyclic_adj_pred

public Edge cyclic_adj_pred(Edge e,
                            Node v)
Returns the previous adjacent edge. If beginning is reached, return the last edge.
Parameters:
e - Edge for which predecessor edge is requested.
v - The node connected to these adjacent edges.
Returns:
The next previous edge.

make_map

public boolean make_map()
Returns true if every edge has a reverse edge, false otherwise.
Returns:
True if every edge has a reverse edge, false otherwise.

make_map

public void make_map(java.util.LinkedList R)
Adds reverse edges of all edges in graph to the given list.
Parameters:
R - List of reverse edges.

sort_nodes

public void sort_nodes(GraphMap A)
Sort nodes in the given graph map; does nothing.
Parameters:
A - Graph map of nodes.

sort_edges

public void sort_edges(GraphMap A)
Sort edges in the given graph map; does nothing.
Parameters:
A - Graph map of edges.

sort_nodes

public void sort_nodes(java.util.LinkedList vl)
Sort nodes in the given list.
Parameters:
vl - List of nodes.

sort_edges

public void sort_edges(java.util.LinkedList el)
Sort edges in the given list.
Parameters:
el - List of edges.

sort_nodes

public void sort_nodes(SortFunction sorter)
Sorts nodes using the given sort function.
Parameters:
sorter - Sort function.

sort_edges

public void sort_edges(SortFunction sorter)
Sorts edges using the given sort function.
Parameters:
sorter - Sort function.

sort_nodes

protected void sort_nodes()
Sorts nodes.

sort_edges

protected void sort_edges()
Sorts edges.

bucket_sort

public void bucket_sort(java.util.LinkedList the_list,
                        int i,
                        int j,
                        OrderingFunction ord_reference)
Sorts the given list.
Parameters:
the_list - The list to be sorted.
i - The index of the first value to be sorted.
j - The index of the last value to be sorted.
ord_reference - Ordering function.

bucket_sort

public void bucket_sort(java.util.LinkedList the_list,
                        OrderingFunction ord)
Sorts the given list.
Parameters:
the_list - The list to be sorted.
ord - Ordering function.

bucket_sort_nodes

public void bucket_sort_nodes(int l,
                              int h,
                              OrderingFunction ord)
Sorts the node list between the given indecies.
Parameters:
l - The index of the first value to be sorted.
h - The index of the last value to be sorted.
ord - Ordering function.

bucket_sort_edges

public void bucket_sort_edges(int l,
                              int h,
                              OrderingFunction ord)
Sorts the edge list between the given indecies.
Parameters:
l - The index of the first value to be sorted.
h - The index of the last value to be sorted.
ord - Ordering function.

bucket_sort_nodes

public void bucket_sort_nodes(OrderingFunction ord)
Sorts the node list.
Parameters:
ord - Ordering function.

bucket_sort_edges

public void bucket_sort_edges(OrderingFunction ord)
Sorts the edge list.
Parameters:
ord - Ordering function.

bucket_sort_nodes

public void bucket_sort_nodes(GraphMap A)
Sorts the node list in the given map.
Parameters:
A - The graph map to be sorted.

bucket_sort_edges

public void bucket_sort_edges(GraphMap A)
Sorts the edge list in the given map.
Parameters:
A - The graph map to be sorted.

touch

public void touch(Node N,
                  java.lang.String S)
Does nothing.
Parameters:
N - The node to be examined.
S - The string used for comment.

touch

public void touch(Edge E,
                  java.lang.String S)
Does nothing.
Parameters:
E - The edge to be examined.
S - The string used for comment.

comment

public void comment(java.lang.String S)
Sets comment string; does nothing.
Parameters:
S - The string used for comment.

query

public boolean query()
Returns true.
Returns:
Always true.

query

public boolean query(Node N,
                     Node M)
Returns true.
Parameters:
N - Source node queried.
M - Target node queried.
Returns:
Always true.

query

public boolean query(Edge E)
Returns true.
Parameters:
E - Edge queried.
Returns:
Always true.

print

public void print(java.lang.String s,
                  java.io.Writer out)
Prints graph to the supplied writer.
Parameters:
s - Header string.
out - The writer to which display is written.

print

public void print(java.io.Writer out)
Prints graph to the supplied writer.
Parameters:
out - The writer to which display is written.
Overview  Package   Class  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES
SUMMARY:  INNER | FIELD | CONSTR | METHOD DETAIL:  FIELD | CONSTR | METHOD