001: package prefuse.action.filter;
002:
003: import java.util.Iterator;
004:
005: import prefuse.Constants;
006: import prefuse.Visualization;
007: import prefuse.action.GroupAction;
008: import prefuse.data.Graph;
009: import prefuse.data.Tree;
010: import prefuse.data.expression.Predicate;
011: import prefuse.util.PrefuseLib;
012: import prefuse.visual.EdgeItem;
013: import prefuse.visual.NodeItem;
014: import prefuse.visual.VisualItem;
015: import prefuse.visual.expression.InGroupPredicate;
016:
017: /**
018: * <p>Filter Action that computes a fisheye degree-of-interest function over
019: * a tree structure (or the spanning tree of a graph structure). Visibility
020: * and DOI (degree-of-interest) values are set for the nodes in the
021: * structure. This function includes current focus nodes, and includes
022: * neighbors only in a limited window around these foci. The size of this
023: * window is determined by the distance value set for this action. All
024: * ancestors of a focus up to the root of the tree are considered foci as well.
025: * By convention, DOI values start at zero for focus nodes, with decreasing
026: * negative numbers for each hop away from a focus.</p>
027: *
028: * <p>This form of filtering was described by George Furnas as early as 1981.
029: * For more information about Furnas' fisheye view calculation and DOI values,
030: * take a look at G.W. Furnas, "The FISHEYE View: A New Look at Structured
031: * Files," Bell Laboratories Tech. Report, Murray Hill, New Jersey, 1981.
032: * Available online at <a href="http://citeseer.nj.nec.com/furnas81fisheye.html">
033: * http://citeseer.nj.nec.com/furnas81fisheye.html</a>.</p>
034: *
035: * @author <a href="http://jheer.org">jeffrey heer</a>
036: */
037: public class FisheyeTreeFilter extends GroupAction {
038:
039: private String m_sources;
040: private Predicate m_groupP;
041:
042: private int m_threshold;
043:
044: private NodeItem m_root;
045: private double m_divisor;
046:
047: /**
048: * Create a new FisheyeTreeFilter that processes the given group.
049: * @param group the data group to process. This should resolve to
050: * a Graph instance, otherwise exceptions will result when this
051: * Action is run.
052: */
053: public FisheyeTreeFilter(String group) {
054: this (group, 1);
055: }
056:
057: /**
058: * Create a new FisheyeTreeFilter that processes the given group.
059: * @param group the data group to process. This should resolve to
060: * a Graph instance, otherwise exceptions will result when this
061: * Action is run.
062: * @param distance the graph distance threshold from high-interest
063: * nodes past which nodes will not be visible nor expanded.
064: */
065: public FisheyeTreeFilter(String group, int distance) {
066: this (group, Visualization.FOCUS_ITEMS, distance);
067: }
068:
069: /**
070: * Create a new FisheyeTreeFilter that processes the given group.
071: * @param group the data group to process. This should resolve to
072: * a Graph instance, otherwise exceptions will result when this
073: * Action is run.
074: * @param sources the group to use as source nodes, representing the
075: * nodes of highest degree-of-interest.
076: * @param distance the graph distance threshold from high-interest
077: * nodes past which nodes will not be visible nor expanded.
078: */
079: public FisheyeTreeFilter(String group, String sources, int distance) {
080: super (group);
081: m_sources = sources;
082: m_threshold = -distance;
083: m_groupP = new InGroupPredicate(PrefuseLib.getGroupName(group,
084: Graph.NODES));
085: }
086:
087: /**
088: * Get the graph distance threshold used by this filter. This
089: * is the threshold for high-interest nodes, past which nodes will
090: * not be visible nor expanded.
091: * @return the graph distance threshold
092: */
093: public int getDistance() {
094: return -m_threshold;
095: }
096:
097: /**
098: * Set the graph distance threshold used by this filter. This
099: * is the threshold for high-interest nodes, past which nodes will
100: * not be visible nor expanded.
101: * @param distance the graph distance threshold to use
102: */
103: public void setDistance(int distance) {
104: m_threshold = -distance;
105: }
106:
107: /**
108: * Get the name of the group to use as source nodes for measuring
109: * graph distance. These form the roots from which the graph distance
110: * is measured.
111: * @return the source data group
112: */
113: public String getSources() {
114: return m_sources;
115: }
116:
117: /**
118: * Set the name of the group to use as source nodes for measuring
119: * graph distance. These form the roots from which the graph distance
120: * is measured.
121: * @param sources the source data group
122: */
123: public void setSources(String sources) {
124: m_sources = sources;
125: }
126:
127: /**
128: * @see prefuse.action.GroupAction#run(double)
129: */
130: public void run(double frac) {
131: Tree tree = ((Graph) m_vis.getGroup(m_group)).getSpanningTree();
132: m_divisor = tree.getNodeCount();
133: m_root = (NodeItem) tree.getRoot();
134:
135: // mark the items
136: Iterator items = m_vis.visibleItems(m_group);
137: while (items.hasNext()) {
138: VisualItem item = (VisualItem) items.next();
139: item.setDOI(Constants.MINIMUM_DOI);
140: item.setExpanded(false);
141: }
142:
143: // compute the fisheye over nodes
144: Iterator iter = m_vis.items(m_sources, m_groupP);
145: while (iter.hasNext())
146: visitFocus((NodeItem) iter.next(), null);
147: visitFocus(m_root, null);
148:
149: // mark unreached items
150: items = m_vis.visibleItems(m_group);
151: while (items.hasNext()) {
152: VisualItem item = (VisualItem) items.next();
153: if (item.getDOI() == Constants.MINIMUM_DOI)
154: PrefuseLib.updateVisible(item, false);
155: }
156: }
157:
158: /**
159: * Visit a focus node.
160: */
161: private void visitFocus(NodeItem n, NodeItem c) {
162: if (n.getDOI() <= -1) {
163: visit(n, c, 0, 0);
164: if (m_threshold < 0)
165: visitDescendants(n, c);
166: visitAncestors(n);
167: }
168: }
169:
170: /**
171: * Visit a specific node and update its degree-of-interest.
172: */
173: private void visit(NodeItem n, NodeItem c, int doi, int ldist) {
174: PrefuseLib.updateVisible(n, true);
175: double localDOI = -ldist / Math.min(1000.0, m_divisor);
176: n.setDOI(doi + localDOI);
177:
178: if (c != null) {
179: EdgeItem e = (EdgeItem) c.getParentEdge();
180: e.setDOI(c.getDOI());
181: PrefuseLib.updateVisible(e, true);
182: }
183: }
184:
185: /**
186: * Visit tree ancestors and their other descendants.
187: */
188: private void visitAncestors(NodeItem n) {
189: if (n == m_root)
190: return;
191: visitFocus((NodeItem) n.getParent(), n);
192: }
193:
194: /**
195: * Traverse tree descendents.
196: */
197: private void visitDescendants(NodeItem p, NodeItem skip) {
198: int lidx = (skip == null ? 0 : p.getChildIndex(skip));
199:
200: Iterator children = p.children();
201:
202: p.setExpanded(children.hasNext());
203:
204: for (int i = 0; children.hasNext(); ++i) {
205: NodeItem c = (NodeItem) children.next();
206: if (c == skip) {
207: continue;
208: }
209:
210: int doi = (int) (p.getDOI() - 1);
211: visit(c, c, doi, Math.abs(lidx - i));
212: if (doi > m_threshold)
213: visitDescendants(c, null);
214: }
215: }
216:
217: } // end of class FisheyeTreeFilter
|