ceph/src/boost/libs/graph/doc/edge_coloring.html

   1 <HTML>
   2 <!--
   3   ~~ Copyright (c) Maciej Piechotka 2013
   4   ~~
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8 -->
   9
  10
  11 <Head>
  12 <Title>Boost Graph Library: Edge Coloring</Title>
  13 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  14         ALINK="#ff0000">
  15 <IMG SRC="../../../boost.png"
  16      ALT="C++ Boost" width="277" height="86">
  17
  18 <BR Clear>
  19
  20 <H1>
  21 <!-- <img src="figs/python.gif" alt="(Python)"/> -->
  22 <TT>edge_coloring</TT>
  23 </H1>
  24
  25
  26 <P>
  27 <DIV ALIGN="LEFT">
  28 <TABLE CELLPADDING=3 border>
  29 <TR><TH ALIGN="LEFT"><B>Graphs:</B></TH>
  30 <TD ALIGN="LEFT">undirected, loop-free</TD>
  31 </TR>
  32 <TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
  33 <TD ALIGN="LEFT">color</TD>
  34 </TR>
  35 <TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
  36 <TD ALIGN="LEFT">time: <i>O(|E| |V|)</i> </TD>
  37 </TR>
  38 </TABLE>
  39 </DIV>
  40
  41
  42 <pre>
  43   template &lt;class Graph, class ColorMap&gt;
  44   typename boost::property_traits<ColorMap>::value_type
  45   edge_coloring(const Graph &amp;g, ColorMap color);
  46 </pre>
  47
  48 <p>Computes an edge coloring for the vertices in the graph, using
  49 an algorithm proposed by Misra et al. []. Given edges ordered
  50 e<sub>1</sub>, e<sub>2</sub>, ..., e<sub>n</sub> it assignes a
  51 colors c<sub>1</sub>, c<sub>2</sub>, ..., c<sub>n</sub> in a way
  52 that no vertex connects with 2 edges of the same color. Furthermore
  53 at most m + 1 colors are used.
  54
  55 <!-- King, I.P. An automatic reordering scheme for simultaneous equations derived from network analysis. Int. J. Numer. Methods Engrg. 2 (1970), 523-533 -->
  56
  57 <h3>Where defined</h3>
  58 <a href="../../../boost/graph/edge_coloring.hpp"><tt>boost/graph/edge_coloring.hpp</tt></a>
  59
  60 <h3>Parameters</h3>
  61
  62 IN: <tt>const Graph&amp; g</tt>
  63 <blockquote>
  64   The graph object on which the algorithm will be applied. The type
  65   <tt>Graph</tt> must be a model of <a href="EdgeListGraph.html">
  66   Edge List Graph</a> and <a href="IncidenceGraph.html">Incidence
  67   Graph</a>.
  68 </blockquote>
  69
  70 OUT: <tt>ColorMap color</tt>
  71 <blockquote>
  72   This property map records the colors of each edges. It must be a
  73   model of <A HREF="../../property_map/doc/ReadWritePropertyMap.html">
  74   Read/Write Property Map</A> whose key type is the same as the edge
  75   descriptor type of the graph and whose value type is an integral type
  76   that can store all values smaller or equal to m.
  77 </blockquote>
  78
  79
  80 <h3>Example</h3>
  81
  82 See <A
  83 href="../example/edge_coloring.cpp"><tt>example/king_ordering.cpp</tt></A>.
  84
  85 <h3>See Also</h3>
  86
  87 <A href="./sequential_vertex_coloring.html">sequential vertex ordering</tt></A>.
  88
  89 <br>
  90 <HR>
  91 <TABLE>
  92 <TR valign=top>
  93 <TD nowrap>Copyright &copy; 2013</TD><TD>
  94 Maciej Piechotka (<A HREF="mailto:uzytkownik2@gmail.com">uzytkownik2@gmail.com</A>)
  95 </TD></TR></TABLE>
  96
  97 </BODY>
  98 </HTML>