?? graph.java
字號:
System.err.println("new_edge(v,w): w not in graph");
if ( e_free.size() == 0){
//obs e = (edge)std_memory.allocate_bytes(edge_bytes());
//obs new (e) edge_struct(v,w,inf);
e = new Edge(v,w,info);
e.id = ++max_edge_index;
}
else{
e = (Edge)e_free.removeFirst();
e.data = info;
e.term[0] = v;
e.term[1] = w;
e.rev = null;
e.succ_adj_edge[0] = null;
e.succ_adj_edge[1] = null;
e.pred_adj_edge[0] = null;
e.pred_adj_edge[1] = null;
}
e_list.addLast(e);
GraphMap m;
//obs forall(m,map_list[1]) m->re_init_entry(e);
for(ListIterator maps = map_list[1].listIterator();
maps.hasNext();
m = (GraphMap)maps.next(), m.re_init_entry(e));
return e;
}
private Face add_face(Object info){
Face f;
if (f_free.size() == 0){
//obs f = (face)std_memory.allocate_bytes(face_bytes());
//obs new (f) face_struct(inf);
f = new Face(info);
f.owner = this;
f.id = ++max_face_index;
}
else{
f = (Face)f_free.removeFirst();
f.data = info;
}
f_list.addLast(f);
GraphMap m;
//obs forall(m,map_list[2]) m->re_init_entry(f);
for(ListIterator maps = map_list[2].listIterator();
maps.hasNext();
m = (GraphMap)maps.next(), m.re_init_entry(f));
return f;
}
/** Adds edge e between the given nodes.
* @param e Edge to be added.
* @param v Source node for the edge.
* @param e1 Edge connected to the source node.
* @param w Target node for the edge.
* @param e2 Edge connected to the target node.
* @param d1 Method of connecting to e1. The new edge is connected after(if d1=0)/before(if d1=1) e1.
* @param d2 Method of connecting to e2. The new edge is connected after(if d2=0)/before(if d2=1) e2. */
public void ins_adj_edge(Edge e, Node v, Edge e1, Node w, Edge e2,int d1,int d2){
// insert edge e
// after(if d1=0)/before(if d1=1) e1 to adj_list of v
// after(if d2=0)/before(if d2=1) e2 to in_list (adj_list) of w
// (most general form of new_edge)
if ( undirected )
{ if (v == w)
System.err.print("new_edge(v,e1,w,e2): selfloop in undirected graph.");
if (e1 != null && v != e1.source() && v != e1.target())
System.err.print("new_edge(v,e1,w,e2): v is not adjacent to e1.");
if (e2 != null && w != e2.source() && w != e2.target())
System.err.print("new_edge(v,e1,w,e2): w is not adjacent to e2.");
v.insert_adj_edge(e,e1,0,0,d1);
w.insert_adj_edge(e,e2,0,1,d2);
}
else
{ if (e1 != null && v != e1.source())
System.err.print("new_edge(v,e1,w,e2): v is not source of e1.");
if (e2 != null && w != e2.source() && w != e2.target())
System.err.print("new_edge(v,e1,w,e2): w is not target of e2.");
v.insert_adj_edge(e,e1,0,0,d1);
w.insert_adj_edge(e,e2,1,1,d2);
}
}
/** Deletes the given edge between the given nodes.
* @param e The edge to be deleted.
* @param v The source node for the edge.
* @param w The target node for the edge. */
public void del_adj_edge(Edge e, Node v, Node w)
{ if (undirected){
v.del_adj_edge(e,0,0);
w.del_adj_edge(e,0,1);
}
else{
v.del_adj_edge(e,0,0);
w.del_adj_edge(e,1,1);
}
}
/** Registers the given GraphMap.
* @param M Graphmap to be registered.
* @return -1 if there is not enough free_data space, 0 otherwise. */
public int register_map(GraphMap M){
int k = M.kind;
map_list[k].addLast(M); //appends the map onto the end of map_list
// M.g_loc = map_list[k].size() - 1; //M.g_loc gets the index number of GraphMap M in map_list
//waiting on LEDA_GRAPH_DATA if (LEDA_GRAPH_DATA) //may be added to Globals class
// if (free_data[k].size() <= 0)
// System.err.println("graph::register_map: all data " + data_sz[k] + " slots used"); //error_handler 1
return (free_data[k].size() <= 0) ? -1 : 0; //free_data[k].removeFirst();
}
/** Unregisters the given GraphMap.
* @param M Graphmap to be unregistered. */
public void unregister_map(GraphMap M){
int k = M.kind;
map_list[k].remove(M.g_loc);
if (M.g_index > 0) free_data[k].addFirst(new Integer(M.g_index));
}
/** Returns the first node in the graph's node list.
* @return The first node.
*/
public Node first_node(){return (Node) v_list.getFirst();}
/** Returns the last node in the graph's node list.
* @return The last node.
*/
public Node last_node(){return (Node) v_list.getLast();}
/** Returns the next node in the node list.
* @param v The node whose successor is requested.
* @return The next node. */
public Node succ_node(Node v){
if (v != null && v.id < v_list.size() && v.id > 0)
{return (Node)v_list.get(v.id + 1);}
else {return null;}
}
/** Returns the previous node in the node list.
* @param v The node whose predecessor is requested.
* @return The previous node. */
public Node pred_node(Node v){
if (v != null && v.id <= v_list.size() && v.id >= 0)
{return (Node)v_list.get(v.id - 1);}
else {return null;}
}
/** Returns the first edge in the edge list.
* @return The first edge. */
public Edge first_edge(){return (Edge) e_list.getFirst();}
/** Returns the last edge in the edge list.
* @return The last edge. */
public Edge last_edge(){return (Edge) e_list.getLast();}
/** Returns the next edge in the edge list.
* @param e The edge whose successor is requested.
* @return The next edge.
*/
public Edge succ_edge(Edge e){
if (e != null && e.id < e_list.size() && e.id >= 0)
{return (Edge)e_list.get(e.id + 1);}
else {return null;}
}
/** Returns the previous edge in the edge list.
* @param e The edge whose predecessor is requested.
* @return The previous edge. */
public Edge pred_edge(Edge e){
if (e != null && e.id <= e_list.size() && e.id > 0)
{return (Edge)e_list.get(e.id - 1);}
else {return null;}
}
/** Copy constructor.
* @param a Graph to be copied.
*/
public Graph(Graph a){
undirected = a.undirected;
copy_graph(a);
node_data_map = new GraphMap(this,0);
edge_data_map = new GraphMap(this,1);
adj_iterator = new GraphMap(this,0,0);
a.copy_all_entries();
}
/** Copies all entries; does nothing.
*/
protected void copy_all_entries(){
//obs Node v;
//waiting for copy_node_entry for(ListIterator nodes = v_list.listIterator();
//waiting for copy_node_entry nodes.hasNext();
//waiting for copy_node_entry copy_node_entry(((Node)nodes.next()).data));
//obs forall_nodes(v,this) copy_node_entry(v.data[0]);
//obs for(Node LOOP_VAR = G.first_node(); LOOP_VAR != null; LOOP_VAR = G.succ_node(LOOP_VAR);)
//obs copy_node_entry(LOOP_VAR.data);
//obs Edge e;
//obs forall_edges(e,this) copy_edge_entry(e.data[0]);
//waiting for copy_edge_entry for(ListIterator edges = e_list.listIterator();
//waiting for copy_edge_entry edges.hasNext();
//waiting for copy_edge_entry copy_edge_entry(((Edge)edges.next()).data));
// hidden edges
//waiting for copy_edge_entry for(ListIterator h_edges = h_list.listIterator();
//waiting for copy_edge_entry h_edges.hasNext();
//waiting for copy_edge_entry copy_edge_entry(((Edge)h_edges.next()).data));
//obs for(e = (Edge)h_list.getFirst(); e != null; e = (Edge)h_list.succ(e))
//obs copy_edge_entry(e.data);
}
/** Clears all entries, does nothing.
*/
protected void clear_all_entries(){
//waiting for clear_node_entry for(ListIterator nodes = v_list.listIterator();
//waiting for clear_node_entry nodes.hasNext();
//waiting for clear_node_entry clear_node_entry(((Node)nodes.next()).data));
//obs node v;
//obs forall_nodes(v,*this) clear_node_entry(v->data[0]);
//waiting for clear_edge_entry for(ListIterator edges = e_list.listIterator();
//waiting for clear_edge_entry edges.hasNext();
//waiting for clear_edge_entry clear_edge_entry(((Edge)edges.next()).data));
//obs edge e;
//obs forall_edges(e,*this) clear_edge_entry(e->data[0]);
// hidden edges
//waiting for clear_edge_entry for(ListIterator h_edges = h_list.listIterator();
//waiting for clear_edge_entry h_edges.hasNext();
//waiting for clear_edge_entry clear_edge_entry(((Edge)h_edges.next()).data));
//obs for(e = (edge)h_list.head(); e; e = (edge)h_list.succ(e))
//obs clear_edge_entry(e->data[0]);
}
/** Returns "void".
* @return "void" */
public String node_type(){ return "void"; }
/** Returns "void".
* @return "void" */
public String edge_type(){ return "void"; }
/** Returns "void".
* @return "void" */
public String face_type(){ return "void"; }
/** Copies the given graph.
* @param G The graph to be copied. */
public void copy_graph(Graph G){
int n = G.number_of_nodes();
for(int k = 0; k < 3; k++){
data_sz[k] = G.data_sz[k];
//free_data isn't a list of integers for(int i=0; i < data_sz[k]; i++) free_data[k].addLast(i);
}
max_node_index = -1;
max_edge_index = -1;
max_face_index = -1;
e_list.clear();
FaceOf = null;
parent = null;
if (n == 0) return; //If there are no nodes in Graph G there is no need to copy them
Node[] node_vec = new Node[G.max_node_index+1]; //allocate additional vectors
Edge[] edge_vec = new Edge[G.max_edge_index+1];
if (node_vec == null || edge_vec == null) //checks to see if vectors were allocated
System.err.println(" copy_graph: out of memory"); //error_handler 1
// allocate a single block of memory for all nodes
//no memory allocation in java // memory_allocate_block(sizeof(node_struct),n);
Node v;
for(ListIterator nodes = G.v_list.listIterator();
nodes.hasNext();
v = (Node)nodes.next(),
new_node(v.data));
// allocate a single block of memory for all edges
// memory_allocate_block(sizeof(edge_struct),m);
boolean loops_deleted = false;
// copy faces (if existing)
Face f;
Face f1;
for(ListIterator faces = G.f_list.listIterator();
faces.hasNext();
f = (Face)faces.next());
node_vec = null;
edge_vec = null;
if ( loops_deleted )
System.err.println("selfloops deleted in ugraph copy constructor");
}
/** Creates a new node.
* @return A new node. */
public Object new_node(){
Object x = null;
pre_new_node_handler();
Node v = add_node(x);
v.setIndexNumber(v_list.indexOf(v));//used to provide reference numbers for Inducer.display_struct
post_new_node_handler(v);
return v;
}
/** Creates a new node.
* @param i Data to be stored in this node.
* @return A new node. */
protected Node new_node(Object i){
pre_new_node_handler();
Node v = add_node(i);
v.setIndexNumber(v_list.indexOf(v)); //used to provide reference numbers for Inducer.display_struct
post_new_node_handler(v);
return v;
}
private Face new_face(Object i){
return add_face(i);
}
private Face new_face(){
Object i = null;
return add_face(i);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -