📄 adj__list_8h-source.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>DMTL: adj_list.h Source File</title><link href="doxygen.css" rel="stylesheet" type="text/css"><link href="tabs.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.4.7 --><div class="tabs"> <ul> <li><a href="index.html"><span>Main Page</span></a></li> <li><a href="annotated.html"><span>Classes</span></a></li> <li id="current"><a href="files.html"><span>Files</span></a></li> <li><a href="pages.html"><span>Related Pages</span></a></li> </ul></div><h1>adj_list.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*</span><a name="l00002"></a>00002 <span class="comment"> * Copyright (C) 2005 M.J. Zaki <zaki@cs.rpi.edu>, Rensselaer Polytechnic Institute</span><a name="l00003"></a>00003 <span class="comment"> * Written by parimi@cs.rpi.edu</span><a name="l00004"></a>00004 <span class="comment"> * Updated by chaojv@cs.rpi.edu, alhasan@cs.rpi.edu, salems@cs.rpi.edu</span><a name="l00005"></a>00005 <span class="comment"> *</span><a name="l00006"></a>00006 <span class="comment"> * This program is free software; you can redistribute it and/or</span><a name="l00007"></a>00007 <span class="comment"> * modify it under the terms of the GNU General Public License</span><a name="l00008"></a>00008 <span class="comment"> * as published by the Free Software Foundation; either version 2</span><a name="l00009"></a>00009 <span class="comment"> * of the License, or (at your option) any later version.</span><a name="l00010"></a>00010 <span class="comment"> *</span><a name="l00011"></a>00011 <span class="comment"> * This program is distributed in the hope that it will be useful,</span><a name="l00012"></a>00012 <span class="comment"> * but WITHOUT ANY WARRANTY; without even the implied warranty of</span><a name="l00013"></a>00013 <span class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the</span><a name="l00014"></a>00014 <span class="comment"> * GNU General Public License for more details.</span><a name="l00015"></a>00015 <span class="comment"> *</span><a name="l00016"></a>00016 <span class="comment"> * You should have received a copy of the GNU General Public License along</span><a name="l00017"></a>00017 <span class="comment"> * with this program; if not, write to the Free Software Foundation, Inc.,</span><a name="l00018"></a>00018 <span class="comment"> * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.</span><a name="l00019"></a>00019 <span class="comment"> */</span><a name="l00020"></a>00020 <a name="l00021"></a>00021 <span class="preprocessor">#ifndef _ADJ_LIST</span><a name="l00022"></a>00022 <span class="preprocessor"></span><span class="preprocessor">#define _ADJ_LIST</span><a name="l00023"></a>00023 <span class="preprocessor"></span><a name="l00024"></a>00024 <span class="preprocessor">#include <ext/hash_map></span><a name="l00025"></a>00025 <span class="preprocessor">#include <algorithm></span><a name="l00026"></a>00026 <span class="preprocessor">#include <map></span><a name="l00027"></a>00027 <span class="preprocessor">#include <sstream></span><a name="l00028"></a>00028 <span class="preprocessor">#include <iostream></span><a name="l00029"></a>00029 <a name="l00030"></a>00030 <span class="keyword">using namespace </span>std;<a name="l00031"></a>00031 <a name="l00032"></a>00032 <a name="l00033"></a>00033 <span class="keyword">template</span><<span class="keyword">typename</span> VERTEX_T, <span class="keyword">typename</span> EDGE_T, <span class="keyword">template</span> <<span class="keyword">typename</span>> <span class="keyword">class </span>ALLOC> <span class="keyword">struct </span><a class="code" href="structvertex__info.html">vertex_info</a>;<a name="l00034"></a>00034 <span class="keyword">template</span><<span class="keyword">typename</span> VERTEX_T, <span class="keyword">typename</span> EDGE_T, <span class="keyword">template</span> <<span class="keyword">typename</span>> <span class="keyword">class </span>ALLOC><a name="l00035"></a>00035 ostream& operator<< (ostream&, const vertex_info<VERTEX_T, EDGE_T, ALLOC>&);<a name="l00036"></a>00036 <a name="l00038"></a>00038 <span class="keyword">template</span><<span class="keyword">typename</span> VERTEX_T, <span class="keyword">typename</span> EDGE_T, <span class="keyword">template</span> <<span class="keyword">typename</span>> <span class="keyword">class </span>ALLOC=std::allocator><a name="l00039"></a><a class="code" href="structvertex__info.html">00039</a> <span class="keyword">struct </span><a class="code" href="structvertex__info.html">vertex_info</a><a name="l00040"></a>00040 {<a name="l00041"></a>00041 <a name="l00042"></a>00042 <span class="keyword">typedef</span> pair<int, EDGE_T> EDGE_P;<a name="l00043"></a>00043 <span class="keyword">typedef</span> vector<EDGE_P, ALLOC<EDGE_P> > EDGES;<a name="l00044"></a>00044 <span class="keyword">typedef</span> <span class="keyword">typename</span> EDGES::iterator EIT;<a name="l00045"></a>00045 <span class="keyword">typedef</span> <span class="keyword">typename</span> EDGES::const_iterator CONST_EIT;<a name="l00046"></a>00046 <a name="l00047"></a>00047 <a class="code" href="structvertex__info.html">vertex_info</a>(<span class="keyword">const</span> VERTEX_T& vert, <span class="keyword">const</span> <span class="keywordtype">int</span>& idval): <a class="code" href="structvertex__info.html#487be5ba6c64222a987df9935b35a7e3">v</a>(vert), id(idval) {}<a name="l00049"></a><a class="code" href="structvertex__info.html#941543799d811878576348b498c9dde7">00049</a> EIT <a class="code" href="structvertex__info.html#941543799d811878576348b498c9dde7">out_begin</a>() {<span class="keywordflow">return</span> out_edges.begin();}<a name="l00051"></a><a class="code" href="structvertex__info.html#0069d9a39a97ae7d778ad1365d46c80c">00051</a> CONST_EIT <a class="code" href="structvertex__info.html#941543799d811878576348b498c9dde7">out_begin</a>()<span class="keyword"> const </span>{<span class="keywordflow">return</span> out_edges.begin();}<a name="l00053"></a><a class="code" href="structvertex__info.html#21b2bc555c6dcfda047a29195ae88f0f">00053</a> EIT <a class="code" href="structvertex__info.html#21b2bc555c6dcfda047a29195ae88f0f">out_end</a>() {<span class="keywordflow">return</span> out_edges.end();}<a name="l00055"></a><a class="code" href="structvertex__info.html#556689d5abf2223e18d84987e2c15e4a">00055</a> CONST_EIT <a class="code" href="structvertex__info.html#21b2bc555c6dcfda047a29195ae88f0f">out_end</a>()<span class="keyword"> const </span>{<span class="keywordflow">return</span> out_edges.end();}<a name="l00056"></a>00056 <a name="l00058"></a><a class="code" href="structvertex__info.html#1241e0ec56565800476b10f535dff31c">00058</a> EIT <a class="code" href="structvertex__info.html#1241e0ec56565800476b10f535dff31c">in_begin</a>() {<span class="keywordflow">return</span> in_edges.begin();}<a name="l00060"></a><a class="code" href="structvertex__info.html#700c089f31b8be52e880c42b208d94ef">00060</a> CONST_EIT <a class="code" href="structvertex__info.html#1241e0ec56565800476b10f535dff31c">in_begin</a>()<span class="keyword"> const </span>{<span class="keywordflow">return</span> in_edges.begin();}<a name="l00062"></a><a class="code" href="structvertex__info.html#ce98965517fd288800f040083104c952">00062</a> EIT <a class="code" href="structvertex__info.html#ce98965517fd288800f040083104c952">in_end</a>() {<span class="keywordflow">return</span> in_edges.end();}<a name="l00064"></a><a class="code" href="structvertex__info.html#da7df0e170e50ee65e3a52d95b10cc9f">00064</a> CONST_EIT <a class="code" href="structvertex__info.html#ce98965517fd288800f040083104c952">in_end</a>()<span class="keyword"> const </span>{<span class="keywordflow">return</span> in_edges.end();}<a name="l00066"></a><a class="code" href="structvertex__info.html#0c2ffeafef1c0ac4edfbb40e17012ce8">00066</a> <span class="keywordtype">void</span> <a class="code" href="structvertex__info.html#0c2ffeafef1c0ac4edfbb40e17012ce8">add_out_edge</a>(<span class="keyword">const</span> <span class="keywordtype">int</span>& dest, <span class="keyword">const</span> EDGE_T& e)<a name="l00067"></a>00067 {<a name="l00068"></a>00068 <span class="comment">//out_edges.insert(make_pair(dest, e));</span><a name="l00069"></a>00069 out_edges.push_back(make_pair(dest, e));<a name="l00070"></a>00070 }<a name="l00072"></a><a class="code" href="structvertex__info.html#8a6a269a00fc8b59c28aa76d8f70bdc2">00072</a> <span class="keywordtype">void</span> <a class="code" href="structvertex__info.html#8a6a269a00fc8b59c28aa76d8f70bdc2">add_in_edge</a>(<span class="keyword">const</span> <span class="keywordtype">int</span>& src, <span class="keyword">const</span> EDGE_T& e)<a name="l00073"></a>00073 {<a name="l00074"></a>00074 <span class="comment">//in_edges.insert(make_pair(src, e));</span><a name="l00075"></a>00075 in_edges.push_back(make_pair(src, e));<a name="l00076"></a>00076 }<a name="l00077"></a>00077 <a name="l00082"></a><a class="code" href="structvertex__info.html#e7b64741f0cd85da0dd2117c4ee2e13e">00082</a> <span class="keywordtype">bool</span> <a class="code" href="structvertex__info.html#e7b64741f0cd85da0dd2117c4ee2e13e">out_edge</a>(<span class="keyword">const</span> <span class="keywordtype">int</span>& dest, EDGE_T& e)<span class="keyword"> const </span>{<a name="l00083"></a>00083 CONST_EIT it;<a name="l00084"></a>00084 <span class="keywordflow">for</span>(it=<a class="code" href="structvertex__info.html#941543799d811878576348b498c9dde7">out_begin</a>(); it!=<a class="code" href="structvertex__info.html#21b2bc555c6dcfda047a29195ae88f0f">out_end</a>(); it++)<a name="l00085"></a>00085 <span class="keywordflow">if</span>(it->first==dest) {<a name="l00086"></a>00086 e=it->second;<a name="l00087"></a>00087 <span class="keywordflow">return</span> <span class="keyword">true</span>;<a name="l00088"></a>00088 }<a name="l00089"></a>00089 <span class="keywordflow">return</span> <span class="keyword">false</span>;<a name="l00090"></a>00090 }<span class="comment">//out_edge()</span><a name="l00091"></a>00091 <a name="l00094"></a><a class="code" href="structvertex__info.html#6257bc363dd9b634b969cd80b521e428">00094</a> <span class="keywordtype">bool</span> <a class="code" href="structvertex__info.html#6257bc363dd9b634b969cd80b521e428">in_edge</a>(<span class="keyword">const</span> <span class="keywordtype">int</span>& src, EDGE_T& e)<span class="keyword"> const </span>{<a name="l00095"></a>00095 CONST_EIT it;<a name="l00096"></a>00096 <span class="keywordflow">for</span>(it=<a class="code" href="structvertex__info.html#1241e0ec56565800476b10f535dff31c">in_begin</a>(); it!=<a class="code" href="structvertex__info.html#ce98965517fd288800f040083104c952">in_end</a>(); it++)<a name="l00097"></a>00097 <span class="keywordflow">if</span>(it->first==src) {<a name="l00098"></a>00098 e=it->second;<a name="l00099"></a>00099 <span class="keywordflow">return</span> <span class="keyword">true</span>;<a name="l00100"></a>00100 }<a name="l00101"></a>00101 <span class="keywordflow">return</span> <span class="keyword">false</span>;<a name="l00102"></a>00102 }<span class="comment">//in_edge()</span><a name="l00104"></a><a class="code" href="structvertex__info.html#715d4cac16eeec7402149ac6b1bbd572">00104</a> <span class="comment"></span> <span class="keywordtype">bool</span> operator< (const vertex_info<VERTEX_T, EDGE_T, ALLOC>& vertex2) <span class="keyword">const</span> {<a name="l00105"></a>00105 <a name="l00106"></a>00106 <span class="keywordflow">if</span>(<a class="code" href="structvertex__info.html#487be5ba6c64222a987df9935b35a7e3">v</a> < vertex2.v)<a name="l00107"></a>00107 <span class="keywordflow">return</span> <span class="keyword">true</span>;<a name="l00108"></a>00108 <span class="keywordflow">else</span><a name="l00109"></a>00109 <span class="keywordflow">return</span> <span class="keyword">false</span>;<a name="l00110"></a>00110 }<a name="l00111"></a>00111 ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -