📄 graphiterator.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"><!--NewPage--><HTML><HEAD><!-- Generated by javadoc (build 1.4.2_13) on Tue Jun 05 11:36:40 GMT-05:00 2007 --><META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><TITLE>GraphIterator (Geotools 2.3.x 2.3.2 API)</TITLE><META NAME="keywords" CONTENT="org.geotools.graph.traverse.GraphIterator interface"><META NAME="keywords" CONTENT="setTraversal()"><META NAME="keywords" CONTENT="getTraversal()"><META NAME="keywords" CONTENT="init()"><META NAME="keywords" CONTENT="next()"><META NAME="keywords" CONTENT="cont()"><META NAME="keywords" CONTENT="killBranch()"><LINK REL ="stylesheet" TYPE="text/css" HREF="../../../../stylesheet.css" TITLE="Style"><SCRIPT type="text/javascript">function windowTitle(){ parent.document.title="GraphIterator (Geotools 2.3.x 2.3.2 API)";}</SCRIPT></HEAD><BODY BGCOLOR="white" onload="windowTitle();"><!-- ========= START OF TOP NAVBAR ======= --><A NAME="navbar_top"><!-- --></A><A HREF="#skip-navbar_top" title="Skip navigation links"></A><TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY=""><TR><TD COLSPAN=3 BGCOLOR="#EEEEFF" CLASS="NavBarCell1"><A NAME="navbar_top_firstrow"><!-- --></A><TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY=""> <TR ALIGN="center" VALIGN="top"> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../overview-summary.html"><FONT CLASS="NavBarFont1"><B>Overview</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-summary.html"><FONT CLASS="NavBarFont1"><B>Package</B></FONT></A> </TD> <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> <FONT CLASS="NavBarFont1Rev"><B>Class</B></FONT> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="class-use/GraphIterator.html"><FONT CLASS="NavBarFont1"><B>Use</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A> </TD> </TR></TABLE></TD><TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM></EM></TD></TR><TR><TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2"> PREV CLASS <A HREF="../../../../org/geotools/graph/traverse/GraphTraversal.html" title="interface in org.geotools.graph.traverse"><B>NEXT CLASS</B></A></FONT></TD><TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2"> <A HREF="../../../../index.html" target="_top"><B>FRAMES</B></A> <A HREF="GraphIterator.html" target="_top"><B>NO FRAMES</B></A> <SCRIPT type="text/javascript"> <!-- if(window==top) { document.writeln('<A HREF="../../../../allclasses-noframe.html"><B>All Classes</B></A>'); } //--></SCRIPT><NOSCRIPT> <A HREF="../../../../allclasses-noframe.html"><B>All Classes</B></A></NOSCRIPT></FONT></TD></TR><TR><TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2"> SUMMARY: NESTED | FIELD | CONSTR | <A HREF="#method_summary">METHOD</A></FONT></TD><TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">DETAIL: FIELD | CONSTR | <A HREF="#method_detail">METHOD</A></FONT></TD></TR></TABLE><A NAME="skip-navbar_top"></A><!-- ========= END OF TOP NAVBAR ========= --><HR><!-- ======== START OF CLASS DATA ======== --><H2><FONT SIZE="-1">org.geotools.graph.traverse</FONT><BR>Interface GraphIterator</H2><DL><DT><B>All Known Implementing Classes:</B> <DD><A HREF="../../../../org/geotools/graph/traverse/basic/AbstractGraphIterator.html" title="class in org.geotools.graph.traverse.basic">AbstractGraphIterator</A></DD></DL><HR><DL><DT>public interface <B>GraphIterator</B></DL><P>Defines an algorithm in which to traverse the components of a graph. A graph iterator operates by repeatedly returing graph components to the caller. The order in which to return the components is specific to the iterator. However, <B>most</B> iterators follow the following conventions:<BR> <BR> <UL> <LI>Components are visited only once</LI> <LI>The next component to be returned is determined by the components that have been previously visited </UL> The following is an example of a GraphIterator. It returns nodes of a graph in a standard <B>Depth First Search</B> order, starting from a specified node. The nodes have been numbered to correspond to the iteration pattern. <BR> <BR> <IMG src="doc-files/dfs.gif"/> * indicates source of traversal<BR> <BR> <BR> In order to analyze the traversal, the following terms are defined:<BR> <BR> The <B>Next Set</B> of a traversal is the set of components that will be visited in a later stage of the traversal.<BR> The <B>Branch Set</B> of an component <B>e</B> is defined as the set of components that can be visited in a later stage of the traversal as a direct result of visiting <B>e</B>. <BR> <BR> In most traversals, the two sets are related. The Next Set is built by analyzing the Branch Set of the component being visited in the current stage of the traversal. Revisiting the above example, a Depth First Search Traversal operates as follows:<BR> <BR> <UL> <LI>Each node is visited only once.</LI> <LI>The Next Set is organized as a <B>Last In First Out</B> Queue (Stack).</LI> <LI>At each stage, every node in the Branch Set that has not yet been visited is added to the Next Set. </UL> As well it is assumed that nodes related to a node are sorted in alphabetic order. <BR> <BR> The following table summarizes the stages of the traversal:<BR> <BR> <TABLE border="1" style="font-family:Arial;font-size:10pt;" width="80%"> <TH>Stage</TH> <TH>Visited Node</TH> <TH>Branch Set </TH> <TH>Next Set</TH> <TH>Comment</TH> <TR align="center"> <TD align="center" width="10%">0</TD> <TD width="10%"> </TD> <TD width="10%"> </TD> <TD width="10%">{A}</TD> <TD width="40%" align="left"> Initial stage, iteration starts explicitly from A</TD> </TR> <TR align="center"> <TD>1</TD><TD>A</TD><TD>{B,F}</TD><TD>{F,B}</TD> <TD align="left"> Related nodes added to <B>Next Set</B> in LIFO order.</TD> </TR> <TR align="center"> <TD>2</TD><TD>F</TD><TD>{A,B}</TD><TD>{B,B}</TD> <TD align="left"> A already visited so not added to <B>Next Set</B><BR> B not yet visited so added to queue.</TD> </TR> <TR align="center"> <TD>3</TD><TD>B</TD><TD>{A,C,D,E,F}</TD><TD>{B,E,D,C}</TD> <TD align="left"> A,F already visited so not added to <B>Next Set</B></TD> </TR> <TR align="center"> <TD>4</TD><TD>B</TD><TD> </TD><TD>{E,D,C}</TD> <TD align="left"> B already visited so ignore and move to next stage</TD> </TR> <TR align="center"> <TD>5</TD><TD>E</TD><TD>{B}</TD><TD>{D,C}</TD> <TD align="left"> </TD> </TR> <TR align="center"> <TD>6</TD><TD>D</TD><TD>{B,C}</TD><TD>{C,C}</TD> <TD align="left"> </TD> </TR> <TR align="center"> <TD>7</TD><TD>C</TD><TD>{B,D}</TD><TD>{C}</TD> <TD align="left"> </TD> </TR> <TR align="center"> <TD>8</TD><TD align="center">C</TD><TD> </TD><TD>{ }</TD> <TD align="left"> C already visited so ignore and move to next stage</TD> </TR> <TR align="center"> <TD>9</TD><TD> </TD><TD> </TD><TD>{ }</TD> <TD align="left"> Next set empty, iteration complete.</TD> </TR> </TABLE><BR> <BR> At any stage of a travesal a branch may be <B>killed</B>.When a branch is killed at a stage of an iteration, no elements in the current <B>Branch Set</B> are added to the <B>Next Set</B>. This is illustrated by revisiting the Depth First Search Iteration, but this time killing the branch at node B. The following table summarizes the stages of the traversal:<BR> <BR> <TABLE border="1" style="font-family:Arial;font-size:10pt;" width="80%"> <TH>Stage</TH> <TH>Visited Node</TH> <TH>Branch Set </TH> <TH>Next Set</TH> <TH>Comment</TH> <TR align="center"> <TD align="center" width="10%">0</TD> <TD width="10%"> </TD> <TD width="10%"> </TD> <TD width="10%">{A}</TD> <TD width="40%" align="left"> Initial stage, iteration starts explicitly from A</TD> </TR> <TR align="center"> <TD>1</TD><TD>A</TD><TD>{B,F}</TD><TD>{F,B}</TD> <TD align="left"> Related nodes added to <B>Next Set</B> in LIFO order.</TD> </TR> <TR align="center"> <TD>2</TD><TD>F</TD><TD>{A,B}</TD><TD>{B,B}</TD> <TD align="left"> A already visited so not added to <B>Next Set</B><BR> B not yet visited so added to queue.</TD> </TR> <TR align="center"> <TD>3</TD><TD>B</TD><TD>{A,C,D,E,F}</TD><TD>{B}</TD> <TD align="left"> <B>Branch Killed.</B> No nodes added to <B>Next Set</B></TD> </TR> <TR align="center"> <TD>4</TD><TD>B</TD><TD> </TD><TD>{ }</TD> <TD align="left"> B already visited so ignore and move to next stage</TD> </TR> <TR align="center"> <TD>9</TD><TD> </TD><TD> </TD><TD>{ }</TD> <TD align="left"> Next set empty, iteration complete.</TD> </TR> </TABLE><BR> In this example, killing the branch at node B results in nodes C, D, and E never being visited.<BR><P><P><DL><DT><B>Author:</B></DT> <DD>Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net</DD>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -