transitive_closure.w

boost库提供标准的C++ API 配合dev c++使用,功能更加强大

  subscript_t<Container> subscript(Container& c)
  { return subscript_t<Container>(c); }
} // namespace detail
@}


Now we are ready to decompose the condensation graph into chains.  The
idea is that we want to form lists of vertices that are in a path and
that the vertices in the list should be ordered by topological number.
These lists will be stored in the \code{chains} vector below.  To
create the chains we consider each vertex in the graph in topological
order. If the vertex is not already in a chain then it will be the
start of a new chain. We then follow a path from this vertex to extend
the chain.

@d Decompose the condensation graph into chains
@{
std::vector< std::vector<cg_vertex> > chains;
{
  std::vector<cg_vertex> in_a_chain(num_vertices(CG));
  for (std::vector<cg_vertex>::iterator i = topo_order.begin();
       i != topo_order.end(); ++i) {
    cg_vertex v = *i;
    if (!in_a_chain[v]) {
      chains.resize(chains.size() + 1);
      std::vector<cg_vertex>& chain = chains.back();
      for (;;) {
        @<Extend the chain until the path dead-ends@>
      }
    }
  }
}
@<Record the chain number and chain position for each vertex@>
@}

\noindent To extend the chain we pick an adjacent vertex that is not
already in a chain. Also, the adjacent vertex chosen will be the one
with lowest topological number since the out-edges of \code{CG} are in
topological order.

@d Extend the chain until the path dead-ends
@{
chain.push_back(v);
in_a_chain[v] = true;
graph_traits<CG_t>::adjacency_iterator adj_first, adj_last;
tie(adj_first, adj_last) = adjacent_vertices(v, CG);
graph_traits<CG_t>::adjacency_iterator next
  = std::find_if(adj_first, adj_last, not1(detail::subscript(in_a_chain)));
if (next != adj_last)
  v = *next;
else
  break; // end of chain, dead-end
@}

In the next steps of the algorithm we will need to efficiently find
the chain for a vertex and the position in the chain for a vertex, so
here we compute this information and store it in two vectors:
\code{chain\_number} and \code{pos\_in\_chain}.

@d Record the chain number and chain position for each vertex
@{
std::vector<size_type> chain_number(num_vertices(CG));
std::vector<size_type> pos_in_chain(num_vertices(CG));
for (size_type i = 0; i < chains.size(); ++i)
  for (size_type j = 0; j < chains[i].size(); ++j) {
    cg_vertex v = chains[i][j];
    chain_number[v] = i;
    pos_in_chain[v] = j;
  }             
@}

Now that we have completed the chain decomposition we are ready to
write the main loop for computing the transitive closure of the
condensation graph. The output of this will be a successor set for
each vertex. Remember that the successor set is stored as a collection
of intersections with the chains. Each successor set is represented by
a vector where the $i$th element is the representative vertex for the
intersection of the set with the $i$th chain. We compute the successor
sets for every vertex in decreasing topological order. The successor
set for each vertex is the union of the successor sets of the adjacent
vertex plus the adjacent vertices themselves.

@d Compute successor sets
@{
cg_vertex inf = std::numeric_limits<cg_vertex>::max();
std::vector< std::vector<cg_vertex> > successors(num_vertices(CG),
  std::vector<cg_vertex>(chains.size(), inf));
for (std::vector<cg_vertex>::reverse_iterator i = topo_order.rbegin();
     i != topo_order.rend(); ++i) {
  cg_vertex u = *i;
  graph_traits<CG_t>::adjacency_iterator adj, adj_last;
  for (tie(adj, adj_last) = adjacent_vertices(u, CG);
       adj != adj_last; ++adj) {
    cg_vertex v = *adj;
    if (topo_number[v] < successors[u][chain_number[v]]) {
      // Succ(u) = Succ(u) U Succ(v)
      detail::union_successor_sets(successors[u], successors[v], 
        successors[u]);
      // Succ(u) = Succ(u) U {v}
      successors[u][chain_number[v]] = topo_number[v];
    }
  }
}
@}

We now rebuild the condensation graph, adding in edges to connect each
vertex to every vertex in its successor set, thereby obtaining the
transitive closure. The successor set vectors contain topological
numbers, so we map back to vertices using the \code{topo\_order}
vector.

@d Build the transitive closure of the condensation graph
@{
for (size_type i = 0; i < CG.size(); ++i)
  CG[i].clear();
for (size_type i = 0; i < CG.size(); ++i) 
  for (size_type j = 0; j < chains.size(); ++j) {
    size_type topo_num = successors[i][j];
    if (topo_num < inf) {
      cg_vertex v = topo_order[topo_num];
      for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k)
        CG[i].push_back(chains[j][k]);
    }
  }
@}

The last stage is to create the transitive closure graph $G^+$ based on
the transitive closure of the condensation graph $G'^+$. We do this in
two steps. First we add edges between all the vertices in one SCC to
all the vertices in another SCC when the two SCCs are adjacent in the
condensation graph. Second we add edges to connect each vertex in a
SCC to every other vertex in the SCC.

@d Build transitive closure of the original graph
@{
// Add vertices to the transitive closure graph
typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
{
  vertex_iterator i, i_end;
  for (tie(i, i_end) = vertices(g); i != i_end; ++i)
    g_to_tc_map[*i] = add_vertex(tc);
}
// Add edges between all the vertices in two adjacent SCCs
graph_traits<CG_t>::vertex_iterator si, si_end;
for (tie(si, si_end) = vertices(CG); si != si_end; ++si) {
  cg_vertex s = *si;
  graph_traits<CG_t>::adjacency_iterator i, i_end;
  for (tie(i, i_end) = adjacent_vertices(s, CG); i != i_end; ++i) {
    cg_vertex t = *i;
    for (size_type k = 0; k < components[s].size(); ++k)
      for (size_type l = 0; l < components[t].size(); ++l)
        add_edge(g_to_tc_map[components[s][k]],
                 g_to_tc_map[components[t][l]], tc);
  }
}
// Add edges connecting all vertices in a SCC
for (size_type i = 0; i < components.size(); ++i)
  if (components[i].size() > 1)
    for (size_type k = 0; k < components[i].size(); ++k)
      for (size_type l = 0; l < components[i].size(); ++l) {
        vertex u = components[i][k], v = components[i][l];
        add_edge(g_to_tc_map[u], g_to_tc_map[v], tc);
      }

// Find loopbacks in the original graph. 
// Need to add it to transitive closure.
{
  vertex_iterator i, i_end;
  for (tie(i, i_end) = vertices(g); i != i_end; ++i) 
  {
    adjacency_iterator ab, ae;
    for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab)
    {
      if (*ab == *i)
        if (components[component_number[*i]].size() == 1)
          add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
    }
  }
}
@}

\section{Appendix}

@d Warshall Transitive Closure
@{
template <typename G>
void warshall_transitive_closure(G& g)
{
  typedef typename graph_traits<G>::vertex_descriptor vertex;
  typedef typename graph_traits<G>::vertex_iterator vertex_iterator;

  function_requires< AdjacencyMatrixConcept<G> >();
  function_requires< EdgeMutableGraphConcept<G> >();

  // Matrix form:
  // for k
  //  for i
  //    if A[i,k]
  //      for j
  //        A[i,j] = A[i,j] | A[k,j]
  vertex_iterator ki, ke, ii, ie, ji, je;
  for (tie(ki, ke) = vertices(g); ki != ke; ++ki)
    for (tie(ii, ie) = vertices(g); ii != ie; ++ii) 
      if (edge(*ii, *ki, g).second)
        for (tie(ji, je) = vertices(g); ji != je; ++ji)
          if (!edge(*ii, *ji, g).second &&
            edge(*ki, *ji, g).second)
          {
            add_edge(*ii, *ji, g);
          }               
}
@}

@d Warren Transitive Closure
@{
template <typename G>
void warren_transitive_closure(G& g)
{
  using namespace boost;
  typedef typename graph_traits<G>::vertex_descriptor vertex;
  typedef typename graph_traits<G>::vertex_iterator vertex_iterator;

  function_requires< AdjacencyMatrixConcept<G> >();
  function_requires< EdgeMutableGraphConcept<G> >();

  // Make sure second loop will work  
  if (num_vertices(g) == 0)
    return;

  // for i = 2 to n
  //    for k = 1 to i - 1 
  //      if A[i,k]
  //        for j = 1 to n
  //          A[i,j] = A[i,j] | A[k,j]

  vertex_iterator ic, ie, jc, je, kc, ke;
  for (tie(ic, ie) = vertices(g), ++ic; ic != ie; ++ic)
    for (tie(kc, ke) = vertices(g); *kc != *ic; ++kc)
      if (edge(*ic, *kc, g).second)
        for (tie(jc, je) = vertices(g); jc != je; ++jc)
          if (!edge(*ic, *jc, g).second &&
            edge(*kc, *jc, g).second)
          {
            add_edge(*ic, *jc, g);
          }

  //  for i = 1 to n - 1
  //    for k = i + 1 to n
  //      if A[i,k]
  //        for j = 1 to n
  //          A[i,j] = A[i,j] | A[k,j]

  for (tie(ic, ie) = vertices(g), --ie; ic != ie; ++ic)
    for (kc = ic, ke = ie, ++kc; kc != ke; ++kc)
      if (edge(*ic, *kc, g).second)
        for (tie(jc, je) = vertices(g); jc != je; ++jc)
          if (!edge(*ic, *jc, g).second &&
            edge(*kc, *jc, g).second)
          {
            add_edge(*ic, *jc, g);
          }                     
}
@}


The following indent command was run on the output files before
they were checked into the Boost CVS repository.

@e indentation
@{
indent -nut -npcs -i2 -br -cdw -ce transitive_closure.hpp
@}

@o transitive_closure.hpp
@{
// Copyright (C) 2001 Vladimir Prus <ghost@@cs.msu.su>
// Copyright (C) 2001 Jeremy Siek <jsiek@@cs.indiana.edu>
// Permission to copy, use, modify, sell and distribute this software is
// granted, provided this copyright notice appears in all copies and 
// modified version are clearly marked as such. This software is provided
// "as is" without express or implied warranty, and with no claim as to its
// suitability for any purpose.

// NOTE: this final is generated by libs/graph/doc/transitive_closure.w

#ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
#define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP

#include <vector>
#include <functional>
#include <boost/compose.hpp>
#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/named_function_params.hpp>

namespace boost {

  @<Union of successor sets@>
  @<Subscript function object@>
  @<Transitive Closure Function@>
  @<The All Defaults Interface@>
  @<Construct Default G to TC Vertex Mapping@>
  @<The Named Parameter Interface@>

  @<Warshall Transitive Closure@>

  @<Warren Transitive Closure@>

} // namespace boost

#endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
@}

@o transitive_closure.cpp
@{
// Copyright (c) Jeremy Siek 2001
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appears in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Silicon Graphics makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.

// NOTE: this final is generated by libs/graph/doc/transitive_closure.w

#include <boost/graph/transitive_closure.hpp>
#include <boost/graph/graphviz.hpp>

int main(int, char*[])
{
  using namespace boost;
  typedef property<vertex_name_t, char> Name;
  typedef property<vertex_index_t, std::size_t,
    Name> Index;
  typedef adjacency_list<listS, listS, directedS, Index> graph_t;
  typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
  graph_t G;
  std::vector<vertex_t> verts(4);
  for (int i = 0; i < 4; ++i)
    verts[i] = add_vertex(Index(i, Name('a' + i)), G);
  add_edge(verts[1], verts[2], G);
  add_edge(verts[1], verts[3], G);
  add_edge(verts[2], verts[1], G);
  add_edge(verts[3], verts[2], G);
  add_edge(verts[3], verts[0], G);

  std::cout << "Graph G:" << std::endl;
  print_graph(G, get(vertex_name, G));

  adjacency_list<> TC;
  transitive_closure(G, TC);

  std::cout << std::endl << "Graph G+:" << std::endl;
  char name[] = "abcd";
  print_graph(TC, name);
  std::cout << std::endl;

  std::ofstream out("tc-out.dot");
  write_graphviz(out, TC, make_label_writer(name));

  return 0;
}
@}

\bibliographystyle{abbrv}
\bibliography{jtran,ggcl,optimization,generic-programming,cad}

\end{document}
% LocalWords:  Siek Prus Succ typename GraphTC VertexIndexMap const tc typedefs
% LocalWords:  typedef iterator adjacency SCC num scc CG cg resize SCCs di ch
% LocalWords:  traversal ith namespace topo inserter  gx hy struct pos inf max
% LocalWords:  rbegin vec si hpp ifndef endif jtran ggcl