1.1 --- a/lemon/ugraph_adaptor.h Tue May 16 16:59:57 2006 +0000
1.2 +++ b/lemon/ugraph_adaptor.h Tue May 16 17:13:42 2006 +0000
1.3 @@ -879,6 +879,11 @@
1.4 return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
1.5 }
1.6
1.7 + /// \brief Base of direct undirected graph adaptor
1.8 + ///
1.9 + /// Base class of the direct undirected graph adaptor. All public member
1.10 + /// of this class can be used with the DirUGraphAdaptor too.
1.11 + /// \sa DirUGraphAdaptor
1.12 template <typename _UGraph, typename _DirectionMap>
1.13 class DirUGraphAdaptorBase {
1.14 public:
1.15 @@ -889,10 +894,20 @@
1.16 typedef typename _UGraph::Node Node;
1.17 typedef typename _UGraph::UEdge Edge;
1.18
1.19 + /// \brief Reverse edge
1.20 + ///
1.21 + /// It reverse the given edge. It simply negate the direction in the map.
1.22 void reverseEdge(const Edge& edge) {
1.23 direction->set(edge, !(*direction)[edge]);
1.24 }
1.25
1.26 + /// \brief Returns the original direction in the undirected graph.
1.27 + ///
1.28 + /// Returns the original direction in the undirected graph.
1.29 + bool direction(const Edge& edge) const {
1.30 + return (*direction)[edge];
1.31 + }
1.32 +
1.33 void first(Node& i) const { graph->first(i); }
1.34 void first(Edge& i) const { graph->first(i); }
1.35 void firstIn(Edge& i, const Node& n) const {
1.36 @@ -1057,12 +1072,78 @@
1.37 ///
1.38 /// \brief A directed graph is made from an undirected graph by an adaptor
1.39 ///
1.40 - /// This adaptor gives a direction for each uedge in the undirected graph.
1.41 - /// The direction of the edges stored in the DirectionMap. This map is
1.42 - /// a bool map on the undirected edges. If the uedge is mapped to true
1.43 - /// then the direction of the directed edge will be the same as the
1.44 - /// default direction of the uedge. The edges can be easily reverted
1.45 - /// by the reverseEdge member in the adaptor.
1.46 + /// This adaptor gives a direction for each uedge in the undirected
1.47 + /// graph. The direction of the edges stored in the
1.48 + /// DirectionMap. This map is a bool map on the undirected edges. If
1.49 + /// the uedge is mapped to true then the direction of the directed
1.50 + /// edge will be the same as the default direction of the uedge. The
1.51 + /// edges can be easily reverted by the \ref
1.52 + /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the
1.53 + /// adaptor.
1.54 + ///
1.55 + /// It can be used to solve orientation problems on directed graphs.
1.56 + /// By example how can we orient an undirected graph to get the minimum
1.57 + /// number of strongly connected components. If we orient the edges with
1.58 + /// the dfs algorithm out from the source then we will get such an
1.59 + /// orientation.
1.60 + ///
1.61 + /// We use the \ref DfsVisitor "visitor" interface of the
1.62 + /// \ref DfsVisit "dfs" algorithm:
1.63 + ///\code
1.64 + /// template <typename DirMap>
1.65 + /// class OrientVisitor : public DfsVisitor<UGraph> {
1.66 + /// public:
1.67 + ///
1.68 + /// OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
1.69 + /// : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
1.70 + ///
1.71 + /// void discover(const Edge& edge) {
1.72 + /// _processed.set(edge, true);
1.73 + /// _dirMap.set(edge, _ugraph.direction(edge));
1.74 + /// }
1.75 + ///
1.76 + /// void examine(const Edge& edge) {
1.77 + /// if (_processed[edge]) return;
1.78 + /// _processed.set(edge, true);
1.79 + /// _dirMap.set(edge, _ugraph.direction(edge));
1.80 + /// }
1.81 + ///
1.82 + /// private:
1.83 + /// const UGraph& _ugraph;
1.84 + /// DirMap& _dirMap;
1.85 + /// UGraph::UEdgeMap<bool> _processed;
1.86 + /// };
1.87 + ///\endcode
1.88 + ///
1.89 + /// And now we can use the orientation:
1.90 + ///\code
1.91 + /// UGraph::UEdgeMap<bool> dmap(ugraph);
1.92 + ///
1.93 + /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
1.94 + /// Visitor visitor(ugraph, dmap);
1.95 + ///
1.96 + /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
1.97 + ///
1.98 + /// dfs.run();
1.99 + ///
1.100 + /// typedef DirUGraphAdaptor<UGraph> DGraph;
1.101 + /// DGraph dgraph(ugraph, dmap);
1.102 + ///
1.103 + /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1.104 + /// countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");
1.105 + ///\endcode
1.106 + ///
1.107 + /// The number of the bi-connected components is a lower bound for
1.108 + /// the number of the strongly connected components in the directed
1.109 + /// graph because if we contract the bi-connected components to
1.110 + /// nodes we will get a tree therefore we cannot orient edges in
1.111 + /// both direction between bi-connected components. In the other way
1.112 + /// the algorithm will orient one component to be strongly
1.113 + /// connected. The two relations proof that the assertion will
1.114 + /// be always true and the found solution is optimal.
1.115 + ///
1.116 + /// \sa DirUGraphAdaptorBase
1.117 + /// \sa dirUGraphAdaptor
1.118 template<typename _Graph,
1.119 typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
1.120 class DirUGraphAdaptor :
1.121 @@ -1075,12 +1156,19 @@
1.122 protected:
1.123 DirUGraphAdaptor() { }
1.124 public:
1.125 +
1.126 + /// \brief Constructor of the adaptor
1.127 + ///
1.128 + /// Constructor of the adaptor
1.129 DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
1.130 setGraph(_graph);
1.131 setDirectionMap(_direction_map);
1.132 }
1.133 };
1.134
1.135 + /// \brief Just gives back a DirUGraphAdaptor
1.136 + ///
1.137 + /// Just gives back a DirUGraphAdaptor
1.138 template<typename UGraph, typename DirectionMap>
1.139 DirUGraphAdaptor<const UGraph, DirectionMap>
1.140 dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {