COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1909:2d806130e700 in lemon-0.x for lemon/topology.h


Ignore:
Timestamp:
01/26/06 16:42:13 (18 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2484
Message:

Undir -> U transition

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/topology.h

    r1875 r1909  
    2525
    2626#include <lemon/concept/graph.h>
    27 #include <lemon/concept/undir_graph.h>
     27#include <lemon/concept/ugraph.h>
    2828#include <lemon/concept_check.h>
    2929
    … …  
    5050  /// \return %True when there is path between any two nodes in the graph.
    5151  /// \note By definition, the empty graph is connected.
    52   template <typename UndirGraph>
    53   bool connected(const UndirGraph& graph) {
    54     checkConcept<concept::UndirGraph, UndirGraph>();
    55     typedef typename UndirGraph::NodeIt NodeIt;
     52  template <typename UGraph>
     53  bool connected(const UGraph& graph) {
     54    checkConcept<concept::UGraph, UGraph>();
     55    typedef typename UGraph::NodeIt NodeIt;
    5656    if (NodeIt(graph) == INVALID) return true;
    57     Dfs<UndirGraph> dfs(graph);
     57    Dfs<UGraph> dfs(graph);
    5858    dfs.run(NodeIt(graph));
    5959    for (NodeIt it(graph); it != INVALID; ++it) {
    … …  
    7575  /// \note By definition, the empty graph consists
    7676  /// of zero connected components.
    77   template <typename UndirGraph>
    78   int countConnectedComponents(const UndirGraph &graph) {
    79     checkConcept<concept::UndirGraph, UndirGraph>();
    80     typedef typename UndirGraph::Node Node;
    81     typedef typename UndirGraph::Edge Edge;
     77  template <typename UGraph>
     78  int countConnectedComponents(const UGraph &graph) {
     79    checkConcept<concept::UGraph, UGraph>();
     80    typedef typename UGraph::Node Node;
     81    typedef typename UGraph::Edge Edge;
    8282
    8383    typedef NullMap<Node, Edge> PredMap;
    … …  
    8585
    8686    int compNum = 0;
    87     typename Bfs<UndirGraph>::
     87    typename Bfs<UGraph>::
    8888      template DefPredMap<PredMap>::
    8989      template DefDistMap<DistMap>::
    … …  
    9797
    9898    bfs.init();
    99     for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
     99    for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
    100100      if (!bfs.reached(n)) {
    101101        bfs.addSource(n);
    … …  
    123123  /// \return The number of components
    124124  ///
    125   template <class UndirGraph, class NodeMap>
    126   int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {
    127     checkConcept<concept::UndirGraph, UndirGraph>();
    128     typedef typename UndirGraph::Node Node;
    129     typedef typename UndirGraph::Edge Edge;
     125  template <class UGraph, class NodeMap>
     126  int connectedComponents(const UGraph &graph, NodeMap &compMap) {
     127    checkConcept<concept::UGraph, UGraph>();
     128    typedef typename UGraph::Node Node;
     129    typedef typename UGraph::Edge Edge;
    130130    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
    131131
    … …  
    134134
    135135    int compNum = 0;
    136     typename Bfs<UndirGraph>::
     136    typename Bfs<UGraph>::
    137137      template DefPredMap<PredMap>::
    138138      template DefDistMap<DistMap>::
    … …  
    146146   
    147147    bfs.init();
    148     for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
     148    for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
    149149      if(!bfs.reached(n)) {
    150150        bfs.addSource(n);
    … …  
    485485      typedef typename Graph::Node Node;
    486486      typedef typename Graph::Edge Edge;
    487       typedef typename Graph::UndirEdge UndirEdge;
     487      typedef typename Graph::UEdge UEdge;
    488488
    489489      CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum)
    … …  
    543543      typedef typename Graph::Node Node;
    544544      typedef typename Graph::Edge Edge;
    545       typedef typename Graph::UndirEdge UndirEdge;
     545      typedef typename Graph::UEdge UEdge;
    546546
    547547      BiNodeConnectedComponentsVisitor(const Graph& graph,
    … …  
    613613      typename Graph::template NodeMap<int> _retMap;
    614614      typename Graph::template NodeMap<Edge> _predMap;
    615       std::stack<UndirEdge> _edgeStack;
     615      std::stack<UEdge> _edgeStack;
    616616      int _num;
    617617    };
    … …  
    623623      typedef typename Graph::Node Node;
    624624      typedef typename Graph::Edge Edge;
    625       typedef typename Graph::UndirEdge UndirEdge;
     625      typedef typename Graph::UEdge UEdge;
    626626
    627627      BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
    … …  
    689689      typename Graph::template NodeMap<int> _retMap;
    690690      typename Graph::template NodeMap<Node> _predMap;
    691       std::stack<UndirEdge> _edgeStack;
     691      std::stack<UEdge> _edgeStack;
    692692      int _num;
    693693      bool rootCut;
    … …  
    696696  }
    697697
    698   template <typename UndirGraph>
    699   int countBiNodeConnectedComponents(const UndirGraph& graph);
     698  template <typename UGraph>
     699  int countBiNodeConnectedComponents(const UGraph& graph);
    700700
    701701  /// \ingroup topology
    … …  
    710710  /// \return %True when the graph bi-node-connected.
    711711  /// \todo Make it faster.
    712   template <typename UndirGraph>
    713   bool biNodeConnected(const UndirGraph& graph) {
     712  template <typename UGraph>
     713  bool biNodeConnected(const UGraph& graph) {
    714714    return countBiNodeConnectedComponents(graph) == 1;
    715715  }
    … …  
    726726  /// \param graph The graph.
    727727  /// \return The number of components.
    728   template <typename UndirGraph>
    729   int countBiNodeConnectedComponents(const UndirGraph& graph) {
    730     checkConcept<concept::UndirGraph, UndirGraph>();
    731     typedef typename UndirGraph::NodeIt NodeIt;
     728  template <typename UGraph>
     729  int countBiNodeConnectedComponents(const UGraph& graph) {
     730    checkConcept<concept::UGraph, UGraph>();
     731    typedef typename UGraph::NodeIt NodeIt;
    732732
    733733    using namespace _topology_bits;
    734734
    735     typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor;
     735    typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor;
    736736
    737737    int compNum = 0;
    738738    Visitor visitor(graph, compNum);
    739739
    740     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     740    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
    741741    dfs.init();
    742742   
    … …  
    763763  ///
    764764  /// \param graph The graph.
    765   /// \retval compMap A writable undir edge map. The values will be set from 0
     765  /// \retval compMap A writable uedge map. The values will be set from 0
    766766  /// to the number of the biconnected components minus one. Each values
    767767  /// of the map will be set exactly once, the values of a certain component
    … …  
    769769  /// \return The number of components.
    770770  ///
    771   template <typename UndirGraph, typename UndirEdgeMap>
    772   int biNodeConnectedComponents(const UndirGraph& graph,
    773                                 UndirEdgeMap& compMap) {
    774     checkConcept<concept::UndirGraph, UndirGraph>();
    775     typedef typename UndirGraph::NodeIt NodeIt;
    776     typedef typename UndirGraph::UndirEdge UndirEdge;
    777     checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>();
     771  template <typename UGraph, typename UEdgeMap>
     772  int biNodeConnectedComponents(const UGraph& graph,
     773                                UEdgeMap& compMap) {
     774    checkConcept<concept::UGraph, UGraph>();
     775    typedef typename UGraph::NodeIt NodeIt;
     776    typedef typename UGraph::UEdge UEdge;
     777    checkConcept<concept::WriteMap<UEdge, int>, UEdgeMap>();
    778778
    779779    using namespace _topology_bits;
    780780
    781     typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
     781    typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor;
    782782   
    783783    int compNum = 0;
    784784    Visitor visitor(graph, compMap, compNum);
    785785
    786     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     786    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
    787787    dfs.init();
    788788   
    … …  
    810810  /// the node separate two or more components.
    811811  /// \return The number of the cut nodes.
    812   template <typename UndirGraph, typename NodeMap>
    813   int biNodeConnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {
    814     checkConcept<concept::UndirGraph, UndirGraph>();
    815     typedef typename UndirGraph::Node Node;
    816     typedef typename UndirGraph::NodeIt NodeIt;
     812  template <typename UGraph, typename NodeMap>
     813  int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) {
     814    checkConcept<concept::UGraph, UGraph>();
     815    typedef typename UGraph::Node Node;
     816    typedef typename UGraph::NodeIt NodeIt;
    817817    checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
    818818
    819819    using namespace _topology_bits;
    820820
    821     typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
     821    typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor;
    822822   
    823823    int cutNum = 0;
    824824    Visitor visitor(graph, cutMap, cutNum);
    825825
    826     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     826    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
    827827    dfs.init();
    828828   
    … …  
    843843      typedef typename Graph::Node Node;
    844844      typedef typename Graph::Edge Edge;
    845       typedef typename Graph::UndirEdge UndirEdge;
     845      typedef typename Graph::UEdge UEdge;
    846846
    847847      CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum)
    … …  
    899899      typedef typename Graph::Node Node;
    900900      typedef typename Graph::Edge Edge;
    901       typedef typename Graph::UndirEdge UndirEdge;
     901      typedef typename Graph::UEdge UEdge;
    902902
    903903      BiEdgeConnectedComponentsVisitor(const Graph& graph,
    … …  
    966966      typedef typename Graph::Node Node;
    967967      typedef typename Graph::Edge Edge;
    968       typedef typename Graph::UndirEdge UndirEdge;
     968      typedef typename Graph::UEdge UEdge;
    969969
    970970      BiEdgeConnectedCutEdgesVisitor(const Graph& graph,
    … …  
    10231023  }
    10241024
    1025   template <typename UndirGraph>
    1026   int countbiEdgeConnectedComponents(const UndirGraph& graph);
     1025  template <typename UGraph>
     1026  int countbiEdgeConnectedComponents(const UGraph& graph);
    10271027
    10281028  /// \ingroup topology
    … …  
    10371037  /// \return The number of components.
    10381038  /// \todo Make it faster.
    1039   template <typename UndirGraph>
    1040   bool biEdgeConnected(const UndirGraph& graph) {
     1039  template <typename UGraph>
     1040  bool biEdgeConnected(const UGraph& graph) {
    10411041    return countBiEdgeConnectedComponents(graph) == 1;
    10421042  }
    … …  
    10531053  /// \param graph The undirected graph.
    10541054  /// \return The number of components.
    1055   template <typename UndirGraph>
    1056   int countBiEdgeConnectedComponents(const UndirGraph& graph) {
    1057     checkConcept<concept::UndirGraph, UndirGraph>();
    1058     typedef typename UndirGraph::NodeIt NodeIt;
     1055  template <typename UGraph>
     1056  int countBiEdgeConnectedComponents(const UGraph& graph) {
     1057    checkConcept<concept::UGraph, UGraph>();
     1058    typedef typename UGraph::NodeIt NodeIt;
    10591059
    10601060    using namespace _topology_bits;
    10611061
    1062     typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor;
     1062    typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor;
    10631063   
    10641064    int compNum = 0;
    10651065    Visitor visitor(graph, compNum);
    10661066
    1067     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     1067    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
    10681068    dfs.init();
    10691069   
    … …  
    10961096  /// \return The number of components.
    10971097  ///
    1098   template <typename UndirGraph, typename NodeMap>
    1099   int biEdgeConnectedComponents(const UndirGraph& graph, NodeMap& compMap) {
    1100     checkConcept<concept::UndirGraph, UndirGraph>();
    1101     typedef typename UndirGraph::NodeIt NodeIt;
    1102     typedef typename UndirGraph::Node Node;
     1098  template <typename UGraph, typename NodeMap>
     1099  int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) {
     1100    checkConcept<concept::UGraph, UGraph>();
     1101    typedef typename UGraph::NodeIt NodeIt;
     1102    typedef typename UGraph::Node Node;
    11031103    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
    11041104
    11051105    using namespace _topology_bits;
    11061106
    1107     typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
     1107    typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor;
    11081108   
    11091109    int compNum = 0;
    11101110    Visitor visitor(graph, compMap, compNum);
    11111111
    1112     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     1112    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
    11131113    dfs.init();
    11141114   
    … …  
    11371137  /// edge is a cut edge.
    11381138  /// \return The number of cut edges.
    1139   template <typename UndirGraph, typename UndirEdgeMap>
    1140   int biEdgeConnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) {
    1141     checkConcept<concept::UndirGraph, UndirGraph>();
    1142     typedef typename UndirGraph::NodeIt NodeIt;
    1143     typedef typename UndirGraph::UndirEdge UndirEdge;
    1144     checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>();
     1139  template <typename UGraph, typename UEdgeMap>
     1140  int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) {
     1141    checkConcept<concept::UGraph, UGraph>();
     1142    typedef typename UGraph::NodeIt NodeIt;
     1143    typedef typename UGraph::UEdge UEdge;
     1144    checkConcept<concept::WriteMap<UEdge, bool>, UEdgeMap>();
    11451145
    11461146    using namespace _topology_bits;
    11471147
    1148     typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
     1148    typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor;
    11491149   
    11501150    int cutNum = 0;
    11511151    Visitor visitor(graph, cutMap, cutNum);
    11521152
    1153     DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
     1153    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
    11541154    dfs.init();
    11551155   
    … …  
    13271327  /// \return %True when there is no circle in the graph.
    13281328  /// \see dag
    1329   template <typename UndirGraph>
    1330   bool acyclic(const UndirGraph& graph) {
    1331     checkConcept<concept::UndirGraph, UndirGraph>();
    1332     typedef typename UndirGraph::Node Node;
    1333     typedef typename UndirGraph::NodeIt NodeIt;
    1334     typedef typename UndirGraph::Edge Edge;
    1335     Dfs<UndirGraph> dfs(graph);
     1329  template <typename UGraph>
     1330  bool acyclic(const UGraph& graph) {
     1331    checkConcept<concept::UGraph, UGraph>();
     1332    typedef typename UGraph::Node Node;
     1333    typedef typename UGraph::NodeIt NodeIt;
     1334    typedef typename UGraph::Edge Edge;
     1335    Dfs<UGraph> dfs(graph);
    13361336    dfs.init();
    13371337    for (NodeIt it(graph); it != INVALID; ++it) {
    … …  
    13601360  /// \param graph The undirected graph.
    13611361  /// \return %True when the graph is acyclic and connected.
    1362   template <typename UndirGraph>
    1363   bool tree(const UndirGraph& graph) {
    1364     checkConcept<concept::UndirGraph, UndirGraph>();
    1365     typedef typename UndirGraph::Node Node;
    1366     typedef typename UndirGraph::NodeIt NodeIt;
    1367     typedef typename UndirGraph::Edge Edge;
    1368     Dfs<UndirGraph> dfs(graph);
     1362  template <typename UGraph>
     1363  bool tree(const UGraph& graph) {
     1364    checkConcept<concept::UGraph, UGraph>();
     1365    typedef typename UGraph::Node Node;
     1366    typedef typename UGraph::NodeIt NodeIt;
     1367    typedef typename UGraph::Edge Edge;
     1368    Dfs<UGraph> dfs(graph);
    13691369    dfs.init();
    13701370    dfs.addSource(NodeIt(graph));
    … …  
    13981398  ///
    13991399  /// \author Balazs Attila Mihaly 
    1400   template<typename UndirGraph>
    1401   inline bool bipartite(const UndirGraph &graph){
    1402     checkConcept<concept::UndirGraph, UndirGraph>();
    1403    
    1404     typedef typename UndirGraph::NodeIt NodeIt;
    1405     typedef typename UndirGraph::EdgeIt EdgeIt;
    1406    
    1407     Bfs<UndirGraph> bfs(graph);
     1400  template<typename UGraph>
     1401  inline bool bipartite(const UGraph &graph){
     1402    checkConcept<concept::UGraph, UGraph>();
     1403   
     1404    typedef typename UGraph::NodeIt NodeIt;
     1405    typedef typename UGraph::EdgeIt EdgeIt;
     1406   
     1407    Bfs<UGraph> bfs(graph);
    14081408    bfs.init();
    14091409    for(NodeIt i(graph);i!=INVALID;++i){
    … …  
    14351435  /// \image html bipartite_partitions.png
    14361436  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
    1437   template<typename UndirGraph, typename NodeMap>
    1438   inline bool bipartitePartitions(const UndirGraph &graph, NodeMap &partMap){
    1439     checkConcept<concept::UndirGraph, UndirGraph>();
    1440    
    1441     typedef typename UndirGraph::Node Node;
    1442     typedef typename UndirGraph::NodeIt NodeIt;
    1443     typedef typename UndirGraph::EdgeIt EdgeIt;
     1437  template<typename UGraph, typename NodeMap>
     1438  inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
     1439    checkConcept<concept::UGraph, UGraph>();
     1440   
     1441    typedef typename UGraph::Node Node;
     1442    typedef typename UGraph::NodeIt NodeIt;
     1443    typedef typename UGraph::EdgeIt EdgeIt;
    14441444 
    1445     Bfs<UndirGraph> bfs(graph);
     1445    Bfs<UGraph> bfs(graph);
    14461446    bfs.init();
    14471447    for(NodeIt i(graph);i!=INVALID;++i){
Note: See TracChangeset for help on using the changeset viewer.