1
2
3
4
5
6 package net.kwfgrid.gwui.graphview;
7
8 import de.fzi.wim.guibase.graphview.graph.Node;
9
10 import java.util.*;
11
12 /***
13 A breath first search iterator for a <code>WorkflowGraph</code>.
14 The iterator can return only traversed nodes or traversed nodes and edges.
15 If edges are returned each edge is returned between it's start and end node (if the end node has not already been returned due to a cycle in the graph.)
16 The iterator will return every node (and edge if desired) of the graph which can be reached from the specified start node exactly once.
17 */
18 public class BFSIterator implements Iterator {
19 private Collection _visitednodes;
20 private LinkedList _queue;
21 private boolean _returnedges;
22 private boolean _tonodereturned;
23 private boolean _fromnodereturned;
24 private boolean _edgereturned;
25 private ArcEdge _currentedge;
26
27 /***
28 Constructor. The created instance will not return visited edges.
29 @param start The node to start the iteration. Must be instance of <code>TransitionNode</code> or <code>PlaceNode</code>.
30 @exception IllegalArgumentException If <code>start</code> is not an instance of <code>TransitionNode</code> or <code>PlaceNode</code>.
31 */
32 public BFSIterator(WorkflowGraphElement start) throws IllegalArgumentException {
33 this(start, false);
34 }
35
36 /***
37 Constructor.
38 @param start The node to start the iteration. Must be instance of <code>TransitionNode</code> or <code>PlaceNode</code>.
39 @param returnedges If true, the iterator will also return the traversed edges.
40 @exception IllegalArgumentException If <code>start</code> is not an instance of <code>TransitionNode</code> or <code>PlaceNode</code>.
41 */
42 public BFSIterator(WorkflowGraphElement start, boolean returnedges) throws IllegalArgumentException {
43 if (start instanceof TransitionNode || start instanceof PlaceNode) {
44 _returnedges = returnedges;
45 _visitednodes = new LinkedList();
46 _queue = new LinkedList();
47 if (start instanceof TransitionNode) {
48 _currentedge = new InEdge(null, (TransitionNode)start, null);
49 } else {
50 _currentedge = new OutEdge(null, (PlaceNode)start, null);
51 }
52 _queue.addAll(_currentedge.getTo().getEdgesFrom());
53 _tonodereturned = false;
54 _fromnodereturned = true;
55 _edgereturned = true;
56 } else {
57 throw new IllegalArgumentException("Start node must be instance of TransitionNode or PlaceNode.");
58 }
59 }
60
61 public Object next() {
62 Object next = null;
63
64 if (_tonodereturned && _fromnodereturned && _edgereturned) {
65
66 _currentedge = (ArcEdge)_queue.removeFirst();
67 _fromnodereturned = false;
68 _edgereturned = !_returnedges;
69 _tonodereturned = _visitednodes.contains(_currentedge.getTo());
70 if (!_tonodereturned) _queue.addAll(_currentedge.getTo().getEdgesFrom());
71 }
72
73 if (!_fromnodereturned) {
74 next = _currentedge.getFrom();
75 _visitednodes.add(next);
76 _fromnodereturned = true;
77 } else if (!_edgereturned) {
78 next = _currentedge;
79 _edgereturned = true;
80 } else if (!_tonodereturned) {
81 next = _currentedge.getTo();
82 _visitednodes.add(next);
83 _tonodereturned = true;
84 }
85
86 return next;
87 }
88
89 public boolean hasNext() {
90 return !_queue.isEmpty() || !_edgereturned || !_tonodereturned || !_fromnodereturned;
91 }
92
93 /***
94 @exception UnsupportedOperationException Always.
95 */
96 public void remove() {
97 throw new UnsupportedOperationException();
98 }
99 }