Source code: com/phoenixst/plexus/operations/Product.java
1 /*
2 * $Id: Product.java,v 1.14 2003/11/04 22:36:55 rconner Exp $
3 *
4 * Copyright (C) 1994-2003 by Phoenix Software Technologists,
5 * Inc. and others. All rights reserved.
6 *
7 * THIS PROGRAM AND DOCUMENTATION IS PROVIDED UNDER THE TERMS OF THE
8 * COMMON PUBLIC LICENSE ("AGREEMENT") WHICH ACCOMPANIES IT. ANY
9 * USE, REPRODUCTION OR DISTRIBUTION OF THE PROGRAM CONSTITUTES
10 * RECIPIENT'S ACCEPTANCE OF THE AGREEMENT.
11 *
12 * The license text can also be found at
13 * http://opensource.org/licenses/cpl.php
14 */
15
16 package com.phoenixst.plexus.operations;
17
18 import java.util.*;
19
20 import org.apache.commons.collections.IteratorUtils;
21
22 import com.phoenixst.plexus.*;
23
24
25 /**
26 * A <code>Graph</code> which is the product of two other
27 * <code>Graphs</code>. The nodes are immutable {@link List} objects
28 * with exactly two elements, the first element being a node from the
29 * first graph and the second being a node from the second graph.
30 * <strong>Note: At the present time, only undirected simple graphs
31 * may be used.</strong>
32 *
33 * <P>If either wrapped <code>Graph</code> contains
34 * <code>Edges</code> which point to other <code>Edges</code>, the
35 * product will <strong>not</strong> reflect this. The node and edge
36 * aspects of any such <code>Edge</code> will be distinct in the
37 * product.
38 *
39 * @version $Revision: 1.14 $
40 * @author Ray A. Conner
41 *
42 * @since 1.0
43 */
44 public class Product extends AbstractGraph
45 implements java.io.Serializable
46 {
47
48 private Graph a;
49 private Graph b;
50
51 // FIXME - allow other than undirected simple graphs
52
53
54 ////////////////////////////////////////
55 // Constructor
56 ////////////////////////////////////////
57
58
59 /**
60 * Creates a new <code>Product</code> graph.
61 */
62 public Product( Graph a, Graph b )
63 {
64 if( a.isDirected() || !a.isSimple() ) {
65 throw new IllegalArgumentException( "Graph must be undirected and simple." );
66 }
67 if( b.isDirected() || !b.isSimple() ) {
68 throw new IllegalArgumentException( "Graph must be undirected and simple." );
69 }
70
71 if( a.nodeSize() == 0 || b.nodeSize() == 0 ) {
72 throw new IllegalArgumentException( "Graphs must have more than zero nodes." );
73 }
74 this.a = a;
75 this.b = b;
76 }
77
78
79 ////////////////////////////////////////
80 // Product Methods
81 ////////////////////////////////////////
82
83
84 /**
85 *
86 */
87 public Graph getLeftOperand()
88 {
89 return a;
90 }
91
92
93 /**
94 *
95 */
96 public Graph getRightOperand()
97 {
98 return b;
99 }
100
101
102 ////////////////////////////////////////
103 // Private Methods
104 ////////////////////////////////////////
105
106
107 private static final boolean equals( Object a, Object b )
108 {
109 return (a == null) ? (b == null) : a.equals( b );
110 }
111
112
113 private List checkNodeType( Object node )
114 {
115 List list = (List) node;
116 if( list.size() != 2 ) {
117 throw new NoSuchNodeException( "Node is not in this graph: " + node );
118 }
119 return list;
120 }
121
122
123 private List checkNode( Object node )
124 {
125 List list = (List) node;
126 if( list.size() != 2
127 || !a.containsNode( list.get( 0 ) )
128 || !b.containsNode( list.get( 1 ) ) ) {
129 throw new NoSuchNodeException( "Node is not in this graph: " + node );
130 }
131 return list;
132 }
133
134
135 ////////////////////////////////////////
136 // Graph Methods
137 ////////////////////////////////////////
138
139
140 /**
141 * Returns <code>false</code>.
142 */
143 public boolean isDirected()
144 {
145 return false;
146 }
147
148
149 /**
150 * Returns <code>true</code>.
151 */
152 public boolean isSimple()
153 {
154 return true;
155 }
156
157
158 /**
159 * Returns the number of nodes in this <code>Graph</code>.
160 */
161 public int nodeSize()
162 {
163 return a.nodeSize() * b.nodeSize();
164 }
165
166
167 /**
168 * Returns the number of edges in this <code>Graph</code>.
169 */
170 public int edgeSize()
171 {
172 return (a.nodeSize() * b.edgeSize())
173 + (b.nodeSize() * a.edgeSize());
174 }
175
176
177 /**
178 * Returns the degree of <code>node</code>, defined as the number
179 * of edges incident on <code>node</code>, with self-loops
180 * counted twice.
181 */
182 public int degree( Object node )
183 {
184 Object aNode = ((List) node).get( 0 );
185 Object bNode = ((List) node).get( 1 );
186 return a.degree( aNode ) + b.degree( bNode );
187 }
188
189
190 /**
191 * Throws an <code>UnsupportedOperationException</code>.
192 */
193 public boolean removeNode( Object node )
194 {
195 throw new UnsupportedOperationException();
196 }
197
198
199 /**
200 * Returns <code>true</code> if this <code>Graph</code> contains
201 * <code>node</code>.
202 */
203 public boolean containsNode( Object node )
204 {
205 if( !(node instanceof List) ) {
206 return false;
207 }
208 List list = (List) node;
209 return list.size() == 2
210 && a.containsNode( list.get( 0 ) )
211 && b.containsNode( list.get( 1 ) );
212 }
213
214
215 /**
216 * Throws an <code>UnsupportedOperationException</code>.
217 */
218 public boolean removeEdge( Edge edge )
219 {
220 throw new UnsupportedOperationException();
221 }
222
223
224 /**
225 * Returns the edge from <code>tail</code> to <code>head</code>,
226 * or <code>null</code> if it does not exist.
227 */
228 public Edge getEdge( Object tail, Object head )
229 {
230 List tailList = checkNode( tail );
231 List headList = checkNode( head );
232 Object aTail = tailList.get( 0 );
233 Object bTail = tailList.get( 1 );
234 Object aHead = headList.get( 0 );
235 Object bHead = headList.get( 1 );
236
237 Edge edge = null;
238 if( equals( aTail, aHead ) ) {
239 edge = b.getEdge( bTail, bHead );
240 } else if( equals( bTail, bHead ) ) {
241 edge = a.getEdge( aTail, aHead );
242 }
243 return (edge != null)
244 ? new EdgeImpl( tail, head, edge )
245 : null;
246 }
247
248
249 /**
250 * Throws an <code>UnsupportedOperationException</code>.
251 */
252 public void clear()
253 {
254 throw new UnsupportedOperationException();
255 }
256
257
258 public Iterator nodeIterator()
259 {
260 return new NodeIterator();
261 }
262
263
264 public Iterator edgeIterator()
265 {
266 return isEmpty() ? IteratorUtils.EMPTY_ITERATOR : new AllEdgesIteratorImpl();
267 }
268
269
270 /**
271 * Returns an </code>Iterator</code> over all the edges from
272 * <code>tail</code> to <code>head</code>.
273 */
274 public Iterator edgeIterator( Object tail, Object head )
275 {
276 List tailList = checkNode( tail );
277 List headList = checkNode( head );
278 Object aTail = tailList.get( 0 );
279 Object bTail = tailList.get( 1 );
280 Object aHead = headList.get( 0 );
281 Object bHead = headList.get( 1 );
282
283 if( equals( aTail, aHead ) ) {
284 return new EdgeIteratorImpl( tail, head, b.edgeIterator( bTail, bHead ) );
285 } else if( equals( bTail, bHead ) ) {
286 return new EdgeIteratorImpl( tail, head, a.edgeIterator( aTail, aHead ) );
287 } else {
288 return IteratorUtils.EMPTY_ITERATOR;
289 }
290 }
291
292
293 /**
294 * Returns a {@link Traverser} from <code>node</code> to all
295 * adjacent nodes.
296 */
297 public Traverser traverser( Object node )
298 {
299 return new TraverserImpl( node );
300 }
301
302
303 ////////////////////////////////////////
304 // Other methods
305 ////////////////////////////////////////
306
307
308 public String toString()
309 {
310 StringBuffer s = new StringBuffer();
311 s.append( "Product[ " );
312 s.append( a );
313 s.append( ", " );
314 s.append( b );
315 s.append( " ]" );
316 return s.toString();
317 }
318
319
320 ////////////////////////////////////////
321 // Private Classes
322 ////////////////////////////////////////
323
324
325 /**
326 * An immutable <code>Edge</code> that wraps an edge from one of
327 * the argument graphs, but uses a tail and head from this graph.
328 */
329 private class EdgeImpl
330 implements Edge,
331 java.io.Serializable
332 {
333 private Object tail;
334 private Object head;
335 private Edge edge;
336
337 private EdgeImpl( Object tail, Object head,
338 Edge edge )
339 {
340 this.tail = tail;
341 this.head = head;
342 this.edge = edge;
343 }
344
345 // Private helper methods
346
347 private boolean isFromGraph( Graph g )
348 {
349 return Product.this == g;
350 }
351
352 // Edge methods
353
354 public boolean isDirected()
355 {
356 return edge.isDirected();
357 }
358
359 public Object getUserObject()
360 {
361 return edge.getUserObject();
362 }
363
364 public void setUserObject( Object object )
365 {
366 throw new UnsupportedOperationException();
367 }
368
369 public Object getTail()
370 {
371 return tail;
372 }
373
374 public Object getHead()
375 {
376 return head;
377 }
378
379 public Object getOtherEndpoint( Object node )
380 {
381 if( Product.equals( node, tail ) ) {
382 return head;
383 } else if( Product.equals( node, head ) ) {
384 return tail;
385 } else {
386 throw new IllegalArgumentException( "Edge is not incident on the node: " + node );
387 }
388 }
389
390 // Other methods
391
392 public boolean equals( Object object )
393 {
394 return (object instanceof EdgeImpl)
395 && equals( (EdgeImpl) object );
396 }
397
398 public boolean equals( EdgeImpl edgeImpl )
399 {
400 if( !edgeImpl.isFromGraph( Product.this ) || !edge.equals( edgeImpl.edge ) ) {
401 return false;
402 }
403 if( isDirected() ) {
404 return Product.equals( tail, edgeImpl.tail )
405 && Product.equals( head, edgeImpl.head );
406 } else {
407 return (Product.equals( tail, edgeImpl.tail )
408 && Product.equals( head, edgeImpl.head ))
409 || (Product.equals( tail, edgeImpl.head )
410 && Product.equals( head, edgeImpl.tail ));
411 }
412 }
413
414 public int hashCode()
415 {
416 return ((tail == null) ? 0 : tail.hashCode())
417 ^ ((head == null) ? 0 : head.hashCode())
418 ^ edge.hashCode();
419 }
420
421 public String toString()
422 {
423 StringBuffer s = new StringBuffer();
424 s.append( tail );
425 s.append( " -- (" );
426 s.append( getUserObject() );
427 s.append( isDirected() ? ") -> " : ") -- " );
428 s.append( head );
429 return s.toString();
430 }
431 }
432
433
434 private class NodeIterator
435 implements Iterator
436 {
437 /*
438 * This implementation is basically a nested loop. The outer
439 * loop is over the nodes in A and the inner is over the
440 * nodes in B.
441 */
442
443 private Iterator aIter;
444 private Iterator bIter;
445 private Object aNode;
446
447 public NodeIterator()
448 {
449 aIter = a.nodeIterator();
450 bIter = IteratorUtils.EMPTY_ITERATOR;
451 }
452
453 public boolean hasNext()
454 {
455 return aIter.hasNext() || bIter.hasNext();
456 }
457
458 public Object next()
459 {
460 if( !bIter.hasNext() ) {
461 aNode = aIter.next();
462 bIter = b.nodeIterator();
463 }
464 return new OrderedPair( aNode, bIter.next() );
465 }
466
467 public void remove()
468 {
469 throw new UnsupportedOperationException();
470 }
471 }
472
473
474 private class AllEdgesIteratorImpl
475 implements Iterator
476 {
477 /*
478 * This implementation is somewhat like this pseudocode:
479 *
480 * for( aEdge in a.edges() ) {
481 * for( bNode in b.nodes() ) {
482 * edge = (aEdge.tail, bNode) -> (aEdge.head, bNode)
483 * }
484 * }
485 * for( bEdge in b.edges() ) {
486 * for( aNode in a.nodes() ) {
487 * edge = (aNode, bEdge.tail) -> (aNode, bEdge.head)
488 * }
489 * }
490 */
491
492 private Iterator aEdgeIter;
493 private Iterator bNodeIter;
494
495 private Iterator bEdgeIter;
496 private Iterator aNodeIter;
497
498 // Current edge goes from (aTail,bTail) to (aHead,bHead)
499 private Edge edge;
500 private Object aTail;
501 private Object bTail;
502 private Object aHead;
503 private Object bHead;
504
505 public AllEdgesIteratorImpl()
506 {
507 aEdgeIter = a.edgeIterator();
508 bNodeIter = IteratorUtils.EMPTY_ITERATOR;
509 bEdgeIter = b.edgeIterator();
510 aNodeIter = IteratorUtils.EMPTY_ITERATOR;
511 }
512
513 public boolean hasNext()
514 {
515 return bEdgeIter.hasNext() || aEdgeIter.hasNext()
516 || aNodeIter.hasNext() || bNodeIter.hasNext();
517 }
518
519 public Object next()
520 {
521 if( aEdgeIter.hasNext() || bNodeIter.hasNext() ) {
522 // Still in first half, edges from (a1,b)->(a2,b)
523 if( !bNodeIter.hasNext() ) {
524 edge = (Edge) aEdgeIter.next();
525 aTail = edge.getTail();
526 aHead = edge.getHead();
527 bNodeIter = b.nodeIterator();
528 }
529 bTail = bNodeIter.next();
530 bHead = bTail;
531 } else {
532 // In second half, edges from (a,b1)->(a,b2)
533 if( !aNodeIter.hasNext() ) {
534 edge = (Edge) bEdgeIter.next();
535 bTail = edge.getTail();
536 bHead = edge.getHead();
537 aNodeIter = a.nodeIterator();
538 }
539 aTail = aNodeIter.next();
540 aHead = aTail;
541 }
542
543 return new EdgeImpl( new OrderedPair( aTail, bTail ),
544 new OrderedPair( aHead, bHead ),
545 edge );
546 }
547
548 public void remove()
549 {
550 throw new UnsupportedOperationException();
551 }
552 }
553
554
555 private class EdgeIteratorImpl
556 implements Iterator
557 {
558 private Object tail;
559 private Object head;
560 private Iterator edgeIter;
561
562 public EdgeIteratorImpl( Object tail, Object head, Iterator edgeIter )
563 {
564 this.tail = tail;
565 this.head = head;
566 this.edgeIter = edgeIter;
567 }
568
569 public boolean hasNext()
570 {
571 return edgeIter.hasNext();
572 }
573
574 public Object next()
575 {
576 return new EdgeImpl( tail, head, (Edge) edgeIter.next() );
577 }
578
579 public void remove()
580 {
581 throw new UnsupportedOperationException();
582 }
583 }
584
585
586 private class TraverserImpl
587 implements Traverser
588 {
589 /*
590 * This implementation traverses over the nodes in A adjacent
591 * to the first element of the OrderedPair, and then over the nodes
592 * in B adjacent to the second element of the OrderedPair.
593 */
594
595 private List node;
596 private List head;
597 private Traverser aTraverser;
598 private Traverser bTraverser;
599 private Edge edge;
600 private boolean hasStarted;
601
602 public TraverserImpl( Object node )
603 {
604 this.node = checkNodeType( node );
605 aTraverser = a.traverser( this.node.get( 0 ) );
606 bTraverser = b.traverser( this.node.get( 1 ) );
607 hasStarted = false;
608 }
609
610 public boolean hasNext()
611 {
612 return aTraverser.hasNext() || bTraverser.hasNext();
613 }
614
615 public Object next()
616 {
617 if( aTraverser.hasNext() ) {
618 Object aNode = aTraverser.next();
619 edge = aTraverser.getEdge();
620 head = new OrderedPair( aNode, node.get( 1 ) );
621 } else {
622 Object bNode = bTraverser.next();
623 edge = bTraverser.getEdge();
624 head = new OrderedPair( node.get( 0 ), bNode );
625 }
626 hasStarted = true;
627 return head;
628 }
629
630 public void remove()
631 {
632 throw new UnsupportedOperationException();
633 }
634
635 public Edge getEdge()
636 {
637 if( !hasStarted ) {
638 throw new IllegalStateException();
639 }
640 return new EdgeImpl( node, head, edge );
641 }
642
643 public void removeEdge()
644 {
645 throw new UnsupportedOperationException();
646 }
647
648 public Object getOtherEndpoint()
649 {
650 if( !hasStarted ) {
651 throw new IllegalStateException();
652 }
653 return node;
654 }
655 }
656
657
658 /**
659 * A simple immutable ordered pair implementation.
660 */
661 private static class OrderedPair extends AbstractList
662 implements RandomAccess,
663 java.io.Serializable
664 {
665 private Object first;
666 private Object second;
667
668 OrderedPair( Object first, Object second )
669 {
670 this.first = first;
671 this.second = second;
672 }
673
674 public int size()
675 {
676 return 2;
677 }
678
679 public Object get( int index )
680 {
681 if( index == 0 ) {
682 return first;
683 } else if( index == 1 ) {
684 return second;
685 } else {
686 throw new IndexOutOfBoundsException( "Index: " + index );
687 }
688 }
689 }
690
691 }