1 cananian 1.3.2.4 // WeightedGraph.java, created Mon Nov 16 23:33:21 1998 by mfoltz
2 cananian 1.3.2.4 // Copyright (C) 1998 Mark A. Foltz <mfoltz@ai.mit.edu>
3 cananian 1.3.2.4 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.3.2.4
5 mfoltz 1.1 // -*-Mode: Java-*-
6 mfoltz 1.1 // WeightedGraph.java --
7 mfoltz 1.1 // Author: Mark Foltz <mfoltz@ai.mit.edu>
8 mfoltz 1.1 // Maintainer: Mark Foltz <mfoltz@ai.mit.edu>
9 mfoltz 1.1 // Version:
10 mfoltz 1.1 // Created: <Thu Oct 22 23:11:21 1998>
11 mfoltz 1.3 // Time-stamp: <1998-11-21 18:59:53 mfoltz>
12 mfoltz 1.1 // Keywords:
13 mfoltz 1.1
14 mfoltz 1.2 package harpoon.Analysis.Partition;
15 mfoltz 1.1
16 mfoltz 1.1 import java.util.Enumeration;
17 mfoltz 1.1 import java.util.Hashtable;
18 mfoltz 1.1
19 mfoltz 1.1 /**
20 mfoltz 1.1 *
21 mfoltz 1.1 * @author Mark A. Foltz <mfoltz@ai.mit.edu>
22 cananian 1.4 * @version $Id: WeightedGraph.java,v 1.4 2002/02/25 20:58:28 cananian Exp $
23 mfoltz 1.1 */
24 mfoltz 1.1
25 mfoltz 1.1 public class WeightedGraph {
26 mfoltz 1.1
27 mfoltz 1.1 Hashtable _nodes = new Hashtable();
28 mfoltz 1.3 // public static final long _pinfinity = Long.MAX_VALUE;
29 mfoltz 1.3 // public static final long _ninfinity = -Long.MAX_VALUE;
30 mfoltz 1.1 int _dummyindex = 0;
31 mfoltz 1.1
32 mfoltz 1.3 public WeightedGraph() { }
33 mfoltz 1.1
34 mfoltz 1.1 public WeightedGraph(WeightedGraph g) {
35 mfoltz 1.1 Enumeration nodes = g.getNodes();
36 mfoltz 1.1 WGNode node, oldto, to;
37 mfoltz 1.1 int i;
38 mfoltz 1.1
39 mfoltz 1.1 while (nodes.hasMoreElements()) {
40 mfoltz 1.1 addNode(new WGNode((WGNode) nodes.nextElement()));
41 mfoltz 1.1 }
42 mfoltz 1.1
43 mfoltz 1.1 nodes = getNodes();
44 mfoltz 1.1 while (nodes.hasMoreElements()) {
45 mfoltz 1.1 node = (WGNode) nodes.nextElement();
46 mfoltz 1.1 for (i = 0; i < node.degree(); i++) {
47 mfoltz 1.1 oldto = (WGNode) node._edges.elementAt(i);
48 mfoltz 1.1 to = getNode(oldto._name);
49 mfoltz 1.1 if (to != null) node._edges.setElementAt(to, i);
50 mfoltz 1.1 }
51 mfoltz 1.1 }
52 mfoltz 1.1
53 mfoltz 1.1 }
54 mfoltz 1.1
55 mfoltz 1.1 public WGNode getNode(String name) {
56 mfoltz 1.1 return (WGNode) _nodes.get(name);
57 mfoltz 1.1 }
58 mfoltz 1.1
59 mfoltz 1.1 public Enumeration getNodes() {
60 mfoltz 1.1 return _nodes.elements();
61 mfoltz 1.1 }
62 mfoltz 1.1
63 mfoltz 1.1 public WGNode addNode(WGNode node) {
64 mfoltz 1.1 return (WGNode) _nodes.put(node._name, node);
65 mfoltz 1.1 }
66 mfoltz 1.1
67 mfoltz 1.1 public WGNode clearNode(WGNode node) {
68 mfoltz 1.1 return (WGNode) _nodes.remove(node._name);
69 mfoltz 1.1 }
70 mfoltz 1.1
71 mfoltz 1.1 public WGNode removeNode(WGNode node) {
72 mfoltz 1.1 node.removeEdges();
73 mfoltz 1.1 return (WGNode) _nodes.remove(node._name);
74 mfoltz 1.1 }
75 mfoltz 1.1
76 mfoltz 1.1 public boolean isEmpty() {
77 mfoltz 1.1 return _nodes.isEmpty();
78 mfoltz 1.1 }
79 mfoltz 1.1
80 mfoltz 1.1 public void clear() {
81 mfoltz 1.1 _nodes.clear();
82 mfoltz 1.1 }
83 mfoltz 1.1
84 mfoltz 1.1 public int size() {
85 mfoltz 1.1 return _nodes.size();
86 mfoltz 1.1 }
87 mfoltz 1.1
88 mfoltz 1.1 public boolean contains(WGNode node) {
89 mfoltz 1.1 return _nodes.containsKey(node._name);
90 mfoltz 1.1 }
91 mfoltz 1.1
92 mfoltz 1.1 public String toString() {
93 mfoltz 1.1 WGNode n;
94 mfoltz 1.1 StringBuffer sb = new StringBuffer();
95 mfoltz 1.1 for (Enumeration e = getNodes(); e.hasMoreElements();) {
96 mfoltz 1.1 n = (WGNode) e.nextElement();
97 mfoltz 1.1 sb.append(n.toString());
98 mfoltz 1.1 }
99 mfoltz 1.1 return sb.toString();
100 mfoltz 1.1 }
101 mfoltz 1.1
102 mfoltz 1.1 public void addDummies(int n) {
103 mfoltz 1.1 WGNode dummy;
104 mfoltz 1.1 for (int i = 0; i < n; i++) {
105 mfoltz 1.1 dummy = new WGNode("__dummy"+_dummyindex,null);
106 mfoltz 1.1 dummy._dummy = true;
107 mfoltz 1.1 _nodes.put(dummy._name, dummy);
108 mfoltz 1.1 _dummyindex++;
109 mfoltz 1.1 }
110 mfoltz 1.1 }
111 mfoltz 1.1
112 mfoltz 1.1 public void removeDummies() {
113 mfoltz 1.1 WGNode node;
114 mfoltz 1.1 for (Enumeration e = _nodes.elements(); e.hasMoreElements();) {
115 mfoltz 1.1 node = (WGNode) e.nextElement();
116 mfoltz 1.1 if (node._dummy) _nodes.remove(node._name);
117 mfoltz 1.1 }
118 mfoltz 1.1 }
119 mfoltz 1.1
120 mfoltz 1.1 static public void addToEdge(WGNode from, WGNode to, long weight) {
121 mfoltz 1.1 from.addToEdge(to, weight);
122 mfoltz 1.1 to.addToEdge(from, weight);
123 mfoltz 1.1 }
124 mfoltz 1.1
125 mfoltz 1.1 static public void setEdge(WGNode from, WGNode to, long weight) {
126 mfoltz 1.1 from.setEdge(to, weight);
127 mfoltz 1.1 to.setEdge(from, weight);
128 mfoltz 1.1 }
129 mfoltz 1.1
130 mfoltz 1.1 static public void exchange(WeightedGraph g1, WGNode n1, WeightedGraph g2, WGNode n2) {
131 mfoltz 1.1 g1.addNode(g2.getNode(n2._name));
132 mfoltz 1.1 g2.addNode(g1.getNode(n1._name));
133 mfoltz 1.1 g1.clearNode(n1);
134 mfoltz 1.1 g2.clearNode(n2);
135 mfoltz 1.1 }
136 mfoltz 1.1
137 mfoltz 1.1 static WeightedGraph createRandomGraph(int n, int u, int v, long w) {
138 mfoltz 1.1
139 mfoltz 1.1 WeightedGraph g = new WeightedGraph();
140 mfoltz 1.1 WGNode[] nodes = new WGNode[n];
141 mfoltz 1.1 int num_edges, i, j, k;
142 mfoltz 1.1
143 mfoltz 1.1 for (i = 0; i < n; i++) {
144 mfoltz 1.1 nodes[i] = new WGNode("Node"+i,null);
145 mfoltz 1.1 g.addNode(nodes[i]);
146 mfoltz 1.1 }
147 mfoltz 1.1
148 mfoltz 1.1 for (i = 0; i < n; i++) {
149 mfoltz 1.1 num_edges = u - v + (int) (Math.random()*2*v);
150 mfoltz 1.1 for (j = 0; j < num_edges; j++) {
151 mfoltz 1.1 k = (int) (Math.random()*n);
152 mfoltz 1.1 if (k != i) WeightedGraph.addToEdge(nodes[i], nodes[k], (long) (Math.random()*w));
153 mfoltz 1.1 }
154 mfoltz 1.1 }
155 mfoltz 1.1
156 mfoltz 1.1 return g;
157 mfoltz 1.1
158 mfoltz 1.1 }
159 mfoltz 1.3
160 mfoltz 1.3 // a Long.MAX_VALUE weight is +infinity. a -Long.MAX_VALUE weight is -infinity.
161 mfoltz 1.3 // must maintain this distinction through ops.
162 mfoltz 1.3
163 mfoltz 1.3 static long weightPlus(long w1, long w2) {
164 mfoltz 1.3 if ((w1 == Long.MAX_VALUE && w2 == -Long.MAX_VALUE)
165 mfoltz 1.3 || (w1 == -Long.MAX_VALUE && w2 == Long.MAX_VALUE)) return 0;
166 mfoltz 1.3 if (w1 == Long.MAX_VALUE || w2 == Long.MAX_VALUE) return Long.MAX_VALUE;
167 mfoltz 1.3 else if (w1 == -Long.MAX_VALUE || w2 == -Long.MAX_VALUE) return -Long.MAX_VALUE;
168 mfoltz 1.3 else return w1+w2;
169 mfoltz 1.3 }
170 mfoltz 1.3
171 mfoltz 1.3 // static boolean weightLEQ(long w1, long w2) {
172 mfoltz 1.3 // if (w2 == -1) return true;
173 mfoltz 1.3 // else if (w1 == -1 && w2 != -1) return false;
174 mfoltz 1.3 // else return (w1 <= w2);
175 mfoltz 1.3 // }
176 mfoltz 1.3
177 mfoltz 1.3 // static long weightNeg(long w) {
178 mfoltz 1.3 // if (w == -1) return -2;
179 mfoltz 1.3 // else if (w == -2) return -1;
180 mfoltz 1.3 // else return -w;
181 mfoltz 1.3 // }
182 mfoltz 1.1
183 mfoltz 1.1 }
184 mfoltz 1.1
185 mfoltz 1.1