Home Explore Help
Register Sign In
devn00b
/
EQ2EMu
9
3
Fork 0
Files Issues 75 Pull Requests 0 Wiki
Tree: 206dc6819b
Branches Tags
EQ2EMu
/
EQ2
/
source
/
depends
/
boost_1_72_0
/
libs
/
graph
/
doc
/
graph_concepts.html

graph_concepts.html 17 KB
History Raw

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498 
  1. <HTML>
    2. 

  2. <!--
    3. 

  3.      Copyright (c) Jeremy Siek 2000
    4. 

  4.     
    5. 

  5.      Distributed under the Boost Software License, Version 1.0.
    6. 

  6.      (See accompanying file LICENSE_1_0.txt or copy at
    7. 

  7.      http://www.boost.org/LICENSE_1_0.txt)
    8. 

  8.   -->
    9. 

  9. <Head>
    10. 

  10. <Title>Boost Graph Concepts</Title>
    11. 

  11. <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
    12. 

  12.         ALINK="#ff0000"> 
    13. 

  13. <IMG SRC="../../../boost.png" 
    14. 

  14.      ALT="C++ Boost" width="277" height="86"> 
    15. 

  15. 

  16. <BR Clear>
    17. 

  17. 

  18. 

  19. <H1><A NAME="chapter:graph-concepts"></A>
    20. 

  20. Graph Concepts
    21. 

  21. </H1>
    22. 

  22. 

  23. <P>
    24. 

  24. The heart of the Boost Graph Library (BGL) is the interface, or
    25. 

  25. concepts (in the parlance of generic programming), that define how a
    26. 

  26. graph can be examined and manipulated in a data-structure neutral
    27. 

  27. fashion. In fact, the BGL interface need not even be implemented using
    28. 

  28. a data-structure, as for some problems it is easier or more efficient
    29. 

  29. to define a graph implicitly based on some functions.
    30. 

  30. 

  31. <P>
    32. 

  32. The BGL interface does not appear as a single graph concept.  Instead
    33. 

  33. it is factored into much smaller pieces. The reason for this is that
    34. 

  34. the purpose of a concept is to summarize the requirements for
    35. 

  35. <i>particular</i> algorithms. Any one algorithm does not need every
    36. 

  36. kind of graph operation, typically only a small subset.  Furthermore,
    37. 

  37. there are many graph data-structures that can not provide efficient
    38. 

  38. implementations of all the operations, but provide highly efficient
    39. 

  39. implementations of the operations necessary for a particular algorithm.
    40. 

  40. By factoring the graph interface into many smaller concepts we
    41. 

  41. provide the graph algorithm writer with a good selection from which to
    42. 

  42. choose the concept that is the closest match for their algorithm.
    43. 

  43. 

  44. Note that because of the use of traits classes rather than member
    45. 

  45. types, it is not safe (and often will not work) to define subclasses of BGL
    46. 

  46. graph types; those types may be missing important traits and properties that
    47. 

  47. were defined externally to the class definition.
    48. 

  48. 

  49. <H2>Graph Structure Concepts Overview</H2>
    50. 

  50. 

  51. <P>
    52. 

  52. <A HREF="#fig:graph-concepts">Figure 1</A> shows the refinements
    53. 

  53. relations between the graph concepts. The reason for factoring the
    54. 

  54. graph interface into so many concepts is to encourage algorithm
    55. 

  55. interfaces to require and use only the minimum interface of a graph,
    56. 

  56. thereby increasing the reusability of the algorithm.
    57. 

  57. 

  58. 

  59. <p></p>
    60. 

  60. <DIV ALIGN="CENTER"><A NAME="fig:graph-concepts"></A></A>
    61. 

  61. <TABLE>
    62. 

  62. <CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG>
    63. 

  63. The graph concepts and refinement relationships.
    64. 

  64. </CAPTION>
    65. 

  65. <TR><TD><IMG SRC="./figs/concepts.gif"></TD></TR>
    66. 

  66. </TABLE>
    67. 

  67. </DIV>
    68. 

  68. <p></p>
    69. 

  69. 

  70. <A HREF="#tab:graph-concept-reqs">Table&nbsp;1</A>
    71. 

  71. gives a summary of the valid expressions and associated types for the
    72. 

  72. graph concepts and provides links to the detailed descriptions of
    73. 

  73. each of the concepts. The notation used in the table is as follows.
    74. 

  74. 

  75. <h3>Notation</h3>
    76. 

  76. 

  77. <Table>
    78. 

  78. <TR>
    79. 

  79. <TD><tt>G</tt></TD>
    80. 

  80. <TD>A type that is a model of Graph.</TD>
    81. 

  81. </TR>
    82. 

  82. 

  83. <TR>
    84. 

  84. <TD><tt>g</tt></TD>
    85. 

  85. <TD>An object of type <tt>G</tt>.</TD>
    86. 

  86. </TR>
    87. 

  87. 

  88. <TR>
    89. 

  89. <TD><tt>e</tt></TD>
    90. 

  90. <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
    91. 

  91. </TR>
    92. 

  92. 

  93. <TR>
    94. 

  94. <TD><tt>e_iter</tt></TD>
    95. 

  95. <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::out_edge_iterator</tt>.</TD>
    96. 

  96. </TR>
    97. 

  97. 

  98. <TR>
    99. 

  99. <TD><tt>u,v</tt></TD>
    100. 

  100. <TD>Are objects of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
    101. 

  101. </TR>
    102. 

  102. 

  103. <TR>
    104. 

  104. <TD><TT>ep</TT></TD><TD>is an object of type <TT>G::edge_property_type</TT></TD>
    105. 

  105. </TR>
    106. 

  106. 

  107. <TR>
    108. 

  108. <TD><TT>vp</TT></TD><TD>is an object of type <TT>G::vertex_property_type</TT></TD>
    109. 

  109. </TR>
    110. 

  110. 

  111. <TR>
    112. 

  112. <TD><tt>Property</tt></TD>
    113. 

  113. <TD>A type used to specify a vertex or edge property.</TD>
    114. 

  114. </TR>
    115. 

  115. 

  116. <TR>
    117. 

  117. <TD><tt>property</tt></TD>
    118. 

  118. <TD>An object of type <tt>Property</tt>.</td>
    119. 

  119. </TR>
    120. 

  120. 

  121. </table>
    122. 

  122. 

  123. 

  124. 

  125. 

  126. <P>
    127. 

  127. <BR><P></P>
    128. 

  128. <DIV ALIGN="CENTER"><A NAME="tab:graph-concept-reqs"></A>
    129. 

  129. <TABLE>
    130. 

  130. <CAPTION ALIGN="BOTTOM"><STRONG>Table 1:</STRONG>
    131. 

  131.     Summary of the graph concepts.
    132. 

  132.     </CAPTION>
    133. 

  133. <TR><TD>  
    134. 

  134. <TABLE border>
    135. 

  135. <TR><TH ALIGN="LEFT">
    136. 

  136. <B>Expression</B> </TH>
    137. 

  137. <TH ALIGN="LEFT" VALIGN="TOP"> <B>Return Type or Description</B> </TH>
    138. 

  138. </TR>
    139. 

  139. <TR><TD ALIGN="LEFT" COLSPAN=2>  
    140. 

  140.  <a href="./Graph.html">Graph</a> </TD>
    141. 

  141. </TR>
    142. 

  142. <TR><TD ALIGN="LEFT">  
    143. 

  143. <TT>boost::graph_traits&lt;G&gt;::vertex_descriptor</TT> </TD>
    144. 

  144. <TD ALIGN="LEFT" VALIGN="TOP">  The type for
    145. 

  145.   vertex representative objects. </TD>
    146. 

  146. </TR>
    147. 

  147. <TR><TD ALIGN="LEFT"> 
    148. 

  148. <TT>boost::graph_traits&lt;G&gt;::edge_descriptor</TT> </TD>
    149. 

  149. <TD ALIGN="LEFT" VALIGN="TOP"> The type for
    150. 

  150.   edge representative objects. </TD>
    151. 

  151. </TR>
    152. 

  152. <TR><TD ALIGN="LEFT"> 
    153. 

  153. <TT>boost::graph_traits&lt;G&gt;::directed_category</TT> </TD>
    154. 

  154. <TD ALIGN="LEFT" VALIGN="TOP"> Directed or undirected? </TD>
    155. 

  155. </TR>
    156. 

  156. <TR><TD ALIGN="LEFT"> 
    157. 

  157. <TT>boost::graph_traits&lt;G&gt;::edge_parallel_category</TT> </TD>
    158. 

  158. <TD ALIGN="LEFT" VALIGN="TOP"> Allow parallel edges? </TD>
    159. 

  159. </TR>
    160. 

  160. <TR><TD ALIGN="LEFT">
    161. 

  161. <TT>boost::graph_traits&lt;G&gt;::traversal_category</TT> </TD> <TD
    162. 

  162. ALIGN="LEFT" VALIGN="TOP">The ways in which the vertices and edges of
    163. 

  163. the graph can be visited.</TD>
    164. 

  164. </TR>
    165. 

  165. <!---------------------------------------------------------------->
    166. 

  166. <TR><TD ALIGN="LEFT" COLSPAN=2>  
    167. 

  167.  <a href="./IncidenceGraph.html">IncidenceGraph</a> refines Graph </TD>
    168. 

  168. </TR>
    169. 

  169. <TR><TD ALIGN="LEFT">  
    170. 

  170. <TT>boost::graph_traits&lt;G&gt;::out_edge_iterator</TT> </TD>
    171. 

  171. <TD ALIGN="LEFT" VALIGN="TOP"> Iterate through
    172. 

  172.   the out-edges. </TD>
    173. 

  173. </TR>
    174. 

  174. <TR><TD ALIGN="LEFT"> 
    175. 

  175. <TT>boost::graph_traits&lt;G&gt;::degree_size_type</TT> </TD>
    176. 

  176. <TD ALIGN="LEFT" VALIGN="TOP"> The integer type for
    177. 

  177. vertex degree. </TD>
    178. 

  178. </TR>
    179. 

  179. <TR><TD ALIGN="LEFT"> 
    180. 

  180. <TT>out_edges(v, g)</TT> </TD>
    181. 

  181. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;out_edge_iterator, out_edge_iterator&gt;</TT> </TD>
    182. 

  182. </TR>
    183. 

  183. <TR><TD ALIGN="LEFT"> 
    184. 

  184. <TT>source(e, g)</TT> </TD>
    185. 

  185. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
    186. 

  186. </TR>
    187. 

  187. <TR><TD ALIGN="LEFT"> 
    188. 

  188. <TT>target(e, g)</TT> </TD>
    189. 

  189. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
    190. 

  190. </TR>
    191. 

  191. <TR><TD ALIGN="LEFT"> 
    192. 

  192. <TT>out_degree(v, g)</TT> </TD>
    193. 

  193. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD>
    194. 

  194. </TR>
    195. 

  195. <!---------------------------------------------------------------->
    196. 

  196. <TR><TD ALIGN="LEFT" COLSPAN=2>  
    197. 

  197.  <a href="./BidirectionalGraph.html">BidirectionalGraph</a> refines
    198. 

  198.   IncidenceGraph </TD>
    199. 

  199. </TR>
    200. 

  200. <TR><TD ALIGN="LEFT">  
    201. 

  201. <TT>boost::graph_traits&lt;G&gt;::in_edge_iterator</TT> </TD>
    202. 

  202. <TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the in-edges. </TD>
    203. 

  203. </TR>
    204. 

  204. <TR><TD ALIGN="LEFT"> 
    205. 

  205. <TT>in_edges(v, g)</TT> </TD>
    206. 

  206. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;in_edge_iterator, in_edge_iterator&gt;</TT> </TD>
    207. 

  207. </TR>
    208. 

  208. <TR><TD ALIGN="LEFT"> 
    209. 

  209. <TT>in_degree(v, g)</TT> </TD>
    210. 

  210. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD>
    211. 

  211. </TR>
    212. 

  212. <TR><TD ALIGN="LEFT"> 
    213. 

  213. <TT>degree(e, g)</TT> </TD>
    214. 

  214. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD>
    215. 

  215. </TR>
    216. 

  216. <!---------------------------------------------------------------->
    217. 

  217. <TR><TD ALIGN="LEFT" COLSPAN=2>  
    218. 

  218. <a href="./AdjacencyGraph.html">AdjacencyGraph</a> refines Graph</TD>
    219. 

  219. </TR>
    220. 

  220. <TR><TD ALIGN="LEFT"> 
    221. 

  221. <TT>boost::graph_traits&lt;G&gt;::adjacency_iterator</TT> </TD>
    222. 

  222. <TD ALIGN="LEFT" VALIGN="TOP"> Iterate through
    223. 

  223.   adjacent vertices. </TD>
    224. 

  224. </TR>
    225. 

  225. <TR><TD ALIGN="LEFT"> 
    226. 

  226. <TT>adjacent_vertices(v, g)</TT> </TD>
    227. 

  227. <TD ALIGN="LEFT" VALIGN="TOP"><TT>std::pair&lt;adjacency_iterator, adjacency_iterator&gt;</TT> </TD>
    228. 

  228. </TR>
    229. 

  229. <!---------------------------------------------------------------->
    230. 

  230. <TR><TD ALIGN="LEFT" COLSPAN=2>  
    231. 

  231. <a href="./VertexListGraph.html">VertexListGraph</a> refines
    232. 

  232.   Graph</TD>
    233. 

  233. </TR>
    234. 

  234. <TR><TD ALIGN="LEFT">  
    235. 

  235. <TT>boost::graph_traits&lt;G&gt;::vertex_iterator</TT> </TD>
    236. 

  236. <TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the
    237. 

  237.   graph's vertex set. </TD>
    238. 

  238. </TR>
    239. 

  239. <TR><TD ALIGN="LEFT"> 
    240. 

  240. <TT>boost::graph_traits&lt;G&gt;::vertices_size_type</TT> </TD>
    241. 

  241. <TD ALIGN="LEFT" VALIGN="TOP"> The unsigned integer type for
    242. 

  242. number of vertices in the graph. </TD>
    243. 

  243. </TR>
    244. 

  244. <TR><TD ALIGN="LEFT"> 
    245. 

  245. <TT>vertices(g)</TT>  </TD>
    246. 

  246. <TD ALIGN="LEFT" VALIGN="TOP"><TT>std::pair&lt;vertex_iterator, vertex_iterator&gt;</TT> </TD>
    247. 

  247. </TR>
    248. 

  248. <TR><TD ALIGN="LEFT"> 
    249. 

  249. <TT>num_vertices(g)</TT> </TD>
    250. 

  250. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertices_size_type</TT>  </TD>
    251. 

  251. </TR>
    252. 

  252. <!---------------------------------------------------------------->
    253. 

  253. <TR><TD ALIGN="LEFT" COLSPAN=2>  
    254. 

  254. <a href="./EdgeListGraph.html">EdgeListGraph</a> refines Graph</TD>
    255. 

  255. </TR>
    256. 

  256. <TR><TD ALIGN="LEFT">  
    257. 

  257. <TT>boost::graph_traits&lt;G&gt;::edge_iterator</TT> </TD>
    258. 

  258. <TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the graph's
    259. 

  259.   edge set. </TD>
    260. 

  260. </TR>
    261. 

  261. <TR><TD ALIGN="LEFT"> 
    262. 

  262. <TT>boost::graph_traits&lt;G&gt;::edges_size_type</TT> </TD>
    263. 

  263. <TD ALIGN="LEFT" VALIGN="TOP"> The unsigned integer type for
    264. 

  264. number of edges in the graph. </TD>
    265. 

  265. </TR>
    266. 

  266. <TR><TD ALIGN="LEFT"> 
    267. 

  267. <TT>edges(g)</TT> </TD>
    268. 

  268. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;edge_iterator, edge_iterator&gt;</TT> </TD>
    269. 

  269. </TR>
    270. 

  270. <TR><TD ALIGN="LEFT">  
    271. 

  271. <TT>num_edges(g)</TT> </TD>
    272. 

  272. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>edges_size_type</TT>  </TD>
    273. 

  273. </TR>
    274. 

  274. <TR><TD ALIGN="LEFT"> 
    275. 

  275. <TT>source(e, g)</TT> </TD>
    276. 

  276. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
    277. 

  277. </TR>
    278. 

  278. <TR><TD ALIGN="LEFT"> 
    279. 

  279. <TT>target(e, g)</TT> </TD>
    280. 

  280. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
    281. 

  281. </TR>
    282. 

  282. <!---------------------------------------------------------------->
    283. 

  283. <TR><TD ALIGN="LEFT" COLSPAN=2>  
    284. 

  284. <a href="./AdjacencyMatrix.html">AdjacencyMatrix</a> refines Graph</TD>
    285. 

  285. </TR>
    286. 

  286. <TR><TD ALIGN="LEFT">  
    287. 

  287. <TT>edge(u, v, g)</TT> </TD>
    288. 

  288. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;edge_descriptor, bool&gt;</TT> </TD>
    289. 

  289. </TR>
    290. 

  290. <TR><TD ALIGN="LEFT" COLSPAN=2>  
    291. 

  291. <a href="./MutableGraph.html">MutableGraph</a> refines
    292. 

  292.   Graph</TD>
    293. 

  293. </TR>
    294. 

  294. <TR><TD ALIGN="LEFT">  
    295. 

  295. <TT>add_vertex(g)</TT> </TD>
    296. 

  296. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
    297. 

  297. </TR>
    298. 

  298. <TR><TD ALIGN="LEFT">  
    299. 

  299. <TT>clear_vertex(v, g)</TT> </TD>
    300. 

  300. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
    301. 

  301. </TR>
    302. 

  302. <TR><TD ALIGN="LEFT">  
    303. 

  303. <TT>remove_vertex(v, g)</TT> </TD>
    304. 

  304. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
    305. 

  305. </TR>
    306. 

  306. <TR><TD ALIGN="LEFT"> 
    307. 

  307. <TT>add_edge(u, v, g)</TT> </TD>
    308. 

  308. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;edge_descriptor, bool&gt;</TT> </TD>
    309. 

  309. </TR>
    310. 

  310. <TR><TD ALIGN="LEFT"> 
    311. 

  311. <TT>remove_edge(u, v, g)</TT> </TD>
    312. 

  312. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
    313. 

  313. </TR>
    314. 

  314. <TR><TD ALIGN="LEFT"> 
    315. 

  315. <TT>remove_edge(e, g)</TT> </TD>
    316. 

  316. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
    317. 

  317. </TR>
    318. 

  318. <TR><TD ALIGN="LEFT"> 
    319. 

  319. <TT>remove_edge(e_iter, g)</TT> </TD>
    320. 

  320. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
    321. 

  321. </TR>
    322. 

  322. <!---------------------------------------------------------------->
    323. 

  323. <TR><TD ALIGN="LEFT" COLSPAN=2>  
    324. 

  324. <a href="./MutablePropertyGraph.html">MutablePropertyGraph</a> refines
    325. 

  325.   Graph</TD>
    326. 

  326. </TR>
    327. 

  327. <TR><TD ALIGN="LEFT">  
    328. 

  328. <TT>add_vertex(vp, g)</TT> </TD>
    329. 

  329. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
    330. 

  330. </TR>
    331. 

  331. <TR><TD ALIGN="LEFT"> 
    332. 

  332. <TT>add_edge(u, v, ep, g)</TT> </TD>
    333. 

  333. <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;edge_descriptor,
    334. 

  334.   bool&gt;</TT> </TD>
    335. 

  335. </TR>
    336. 

  336. <!---------------------------------------------------------------->
    337. 

  337. <TR>
    338. 

  338. <TD ALIGN="LEFT" COLSPAN=2>  
    339. 

  339. <a href="./PropertyGraph.html">PropertyGraph</a> refines Graph</TD>
    340. 

  340. </TR>
    341. 

  341. <TR><TD ALIGN="LEFT">  
    342. 

  342. <TT>boost::property_map&lt;G, Property&gt;::type</TT> </TD>
    343. 

  343. <TD ALIGN="LEFT" VALIGN="TOP">Type for a mutable property map.</TD>
    344. 

  344. </TR>
    345. 

  345. <TR><TD ALIGN="LEFT"> 
    346. 

  346. <TT>boost::property_map&lt;G, Property&gt;::const_type</TT> </TD>
    347. 

  347. <TD ALIGN="LEFT" VALIGN="TOP">Type for a non-mutable property map.</TD>
    348. 

  348. </TR>
    349. 

  349. <TR><TD ALIGN="LEFT"> 
    350. 

  350. <TT>get(property, g)</TT> </TD>
    351. 

  351. <TD ALIGN="LEFT" VALIGN="TOP"> Function to get a property map. </TD>
    352. 

  352. </TR>
    353. 

  353. 

  354. <TR><TD ALIGN="LEFT"> 
    355. 

  355. <TT>get(property,&nbsp;g,&nbsp;x)</TT>
    356. 

  356. </TD>
    357. 

  357. <TD ALIGN="LEFT" VALIGN="TOP">Get property value for vertex or edge <tt>x</tt>. </TD>
    358. 

  358. </TR>
    359. 

  359. 

  360. <TR><TD ALIGN="LEFT"> 
    361. 

  361. <TT>put(property,&nbsp;g,&nbsp;x,&nbsp;v)</TT>
    362. 

  362. </TD>
    363. 

  363. <TD ALIGN="LEFT" VALIGN="TOP">Set property value for vertex or edge
    364. 

  364. <tt>x</tt> to <tt>v</tt>. </TD>
    365. 

  365. </TR>
    366. 

  366. 

  367. </table>
    368. 

  368. </table>
    369. 

  369. </DIV><P></P>
    370. 

  370. <BR>
    371. 

  371. 

  372. <P>
    373. 

  373. 

  374. <H2><A NAME="sec:undirected-graphs"></A>
    375. 

  375. Undirected Graphs
    376. 

  376. </H2>
    377. 

  377. 

  378. <P>
    379. 

  379. The interface that the BGL provides for accessing and manipulating an
    380. 

  380. undirected graph is the same as the interface for directed graphs
    381. 

  381. described in the following sections, however there are some
    382. 

  382. differences in the behaviour and semantics.  For example, in a
    383. 

  383. directed graph we can talk about out-edges and in-edges of a vertex.
    384. 

  384. In an undirected graph there is no ``in'' and ``out'', there are just
    385. 

  385. edges incident to a vertex. Nevertheless, in the BGL we still use the
    386. 

  386. <TT>out_edges()</TT> function (or <TT>in_edges()</TT>) to access the
    387. 

  387. incident edges in an undirected graph. Similarly, an undirected edge
    388. 

  388. has no ``source'' and ``target'' but merely an unordered pair of
    389. 

  389. vertices, but in the BGL we still use <TT>source()</TT> and
    390. 

  390. <TT>target()</TT> to access these vertices.  The reason the BGL does
    391. 

  391. not provide a separate interface for undirected graphs is that many
    392. 

  392. algorithms on directed graphs also work on undirected graphs, and it
    393. 

  393. would be inconvenient to have to duplicate the algorithms just because
    394. 

  394. of an interface difference. When using undirected graphs just mentally
    395. 

  395. disregard the directionality in the function names. The example below
    396. 

  396. demonstrates using the <TT>out_edges()</TT>, <TT>source()</TT>, and
    397. 

  397. <TT>target()</TT> with an undirected graph. The source code for this
    398. 

  398. example and the following one can be found in <a
    399. 

  399. href="../example/undirected_adjacency_list.cpp"><TT>example/undirected_adjacency_list.cpp</TT></a>.
    400. 

  400. 

  401. <P>
    402. 

  402. <PRE>
    403. 

  403.   const int V = 2;
    404. 

  404.   typedef ... UndirectedGraph;
    405. 

  405.   UndirectedGraph undigraph(V);
    406. 

  406. 

  407.   std::cout &lt;&lt; "the edges incident to v: ";
    408. 

  408.   boost::graph_traits&lt;UndirectedGraph&gt;::out_edge_iterator e, e_end;
    409. 

  409.   boost::graph_traits&lt;UndirectedGraph&gt;::vertex_descriptor 
    410. 

  410.     s = vertex(0, undigraph);
    411. 

  411.   for (boost::tie(e, e_end) = out_edges(s, undigraph); e != e_end; ++e)
    412. 

  412.     std::cout &lt;&lt; "(" &lt;&lt; source(*e, undigraph) 
    413. 

  413.               &lt;&lt; "," &lt;&lt; target(*e, undigraph) &lt;&lt; ")" &lt;&lt; endl;
    414. 

  414. </PRE>
    415. 

  415. 

  416. <P>
    417. 

  417. Even though the interface is the same for undirected graphs, there are
    418. 

  418. some behavioral differences because edge equality is defined
    419. 

  419. differently. In a directed graph, edge <i>(u,v)</i> is never equal to edge
    420. 

  420. <i>(v,u)</i>, but in an undirected graph they may be equal.  If the
    421. 

  421. undirected graph is a multigraph then <i>(u,v)</i> and <i>(v,u)</i> might be
    422. 

  422. parallel edges. If the graph is not a multigraph then <i>(u,v)</i> and
    423. 

  423. <i>(v,u)</i> must be the same edge.
    424. 

  424. 

  425. <P>
    426. 

  426. In the example below the edge equality test will return <TT>false</TT>
    427. 

  427. for the directed graph and <TT>true</TT> for the undirected graph. The
    428. 

  428. difference also affects the meaning of <TT>add_edge()</TT>. In the
    429. 

  429. example below, if we had also written <TT>add_edge(v, u,
    430. 

  430. undigraph)</TT>, this would have added a parallel edge between
    431. 

  431. <i>u</i> and <i>v</i> (provided the graph type allows parallel
    432. 

  432. edges). The difference in edge equality also affects the association
    433. 

  433. of edge properties. In the directed graph, the edges <i>(u,v)</i> and
    434. 

  434. <i>(v,u)</i> can have distinct weight values, whereas in the
    435. 

  435. undirected graph the weight of <i>(u,v)</i> is the same as the weight
    436. 

  436. of <i>(v,u)</i> since they are the same edge.
    437. 

  437. 

  438. <P>
    439. 

  439. <PRE>
    440. 

  440.   typedef ... DirectedGraph;
    441. 

  441.   DirectedGraph digraph(V);
    442. 

  442.   {
    443. 

  443.     boost::graph_traits&lt;DirectedGraph&gt;::vertex_descriptor u, v;
    444. 

  444.     u = vertex(0, digraph);
    445. 

  445.     v = vertex(1, digraph);
    446. 

  446.     add_edge(digraph, u, v, Weight(1.2));
    447. 

  447.     add_edge(digraph, v, u, Weight(2.4));
    448. 

  448.     boost::graph_traits&lt;DirectedGraph&gt;::edge_descriptor e1, e2;
    449. 

  449.     bool found;
    450. 

  450.     boost::tie(e1, found) = edge(u, v, digraph);
    451. 

  451.     boost::tie(e2, found) = edge(v, u, digraph);
    452. 

  452.     std::cout &lt;&lt; "in a directed graph is ";
    453. 

  453.     std::cout &lt;&lt; "(u,v) == (v,u) ? " &lt;&lt; (e1 == e2) &lt;&lt; std::endl;
    454. 

  454. 

  455.     property_map&lt;DirectedGraph, edge_weight_t&gt;::type
    456. 

  456.       weight = get(edge_weight, digraph);
    457. 

  457.     cout &lt;&lt; "weight[(u,v)] = " &lt;&lt; get(weight, e1) &lt;&lt; endl;
    458. 

  458.     cout &lt;&lt; "weight[(v,u)] = " &lt;&lt; get(weight, e2) &lt;&lt; endl;
    459. 

  459.   }
    460. 

  460.   {
    461. 

  461.     boost::graph_traits&lt;UndirectedGraph&gt;::vertex_descriptor u, v;
    462. 

  462.     u = vertex(0, undigraph);
    463. 

  463.     v = vertex(1, undigraph);
    464. 

  464.     add_edge(undigraph, u, v, Weight(3.1));
    465. 

  465.     boost::graph_traits&lt;UndirectedGraph&gt;::edge_descriptor e1, e2;
    466. 

  466.     bool found;
    467. 

  467.     boost::tie(e1, found) = edge(u, v, undigraph);
    468. 

  468.     boost::tie(e2, found) = edge(v, u, undigraph);
    469. 

  469.     std::cout &lt;&lt; "in an undirected graph is ";
    470. 

  470.     std::cout &lt;&lt; "(u,v) == (v,u) ? " &lt;&lt; (e1 == e2) &lt;&lt; std::endl;
    471. 

  471. 

  472.     property_map&lt;UndirectedGraph, edge_weight_t&gt;::type
    473. 

  473.       weight = get(edge_weight, undigraph);
    474. 

  474.     cout &lt;&lt; "weight[(u,v)] = " &lt;&lt; get(weight, e1) &lt;&lt; endl;
    475. 

  475.     cout &lt;&lt; "weight[(v,u)] = " &lt;&lt; get(weight, e2) &lt;&lt; endl;
    476. 

  476.   }
    477. 

  477. </PRE>
    478. 

  478. The output is:
    479. 

  479. <PRE>
    480. 

  480. in a directed graph is (u,v) == (v,u) ? 0
    481. 

  481. weight[(u,v)] = 1.2
    482. 

  482. weight[(v,u)] = 2.4
    483. 

  483. in an undirected graph is (u,v) == (v,u) ? 1
    484. 

  484. weight[(u,v)] = 3.1
    485. 

  485. weight[(v,u)] = 3.1
    486. 

  486. </PRE>
    487. 

  487. 

  488. 

  489. <br>
    490. 

  490. <HR>
    491. 

  491. <TABLE>
    492. 

  492. <TR valign=top>
    493. 

  493. <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
    494. 

  494. <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
    495. 

  495. </TD></TR></TABLE>
    496. 

  496. 

  497. </BODY>
    498. 

  498. </HTML> 
    499.