COIN-OR::LEMON - Graph Library

Changeset 1910:f95eea8c34b0 in lemon-0.x


Ignore:
Timestamp:
01/26/06 17:24:40 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2485
Message:

Bipartite => Bp
Upper => A
Lower => B

+ some bug fix

Files:
18 edited

Legend:

Unmodified
Added
Removed
  • demo/topology_demo.cc

    r1909 r1910  
    6060  connectedComponents(graph, compMap);
    6161
    62   graphToEps(graph, "connected_components.eps").u().
     62  graphToEps(graph, "connected_components.eps").undirected().
    6363    coords(coords).scaleToA4().enableParallel().
    6464    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
     
    116116  biNodeConnectedComponents(graph, compMap);
    117117  biNodeConnectedCutNodes(graph, cutMap);
    118   graphToEps(graph, "bi_node_connected_components.eps").u().
     118
     119  graphToEps(graph, "bi_node_connected_components.eps").undirected().
    119120    coords(coords).scaleToA4().enableParallel().
    120121    parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0).
     
    146147  biEdgeConnectedCutEdges(graph, cutMap);
    147148
    148   graphToEps(graph, "bi_edge_connected_components.eps").u().
     149  graphToEps(graph, "bi_edge_connected_components.eps").undirected().
    149150    coords(coords).scaleToA4().enableParallel().
    150151    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
     
    173174  bipartitePartitions(graph, partMap);
    174175
    175   graphToEps(graph, "bipartite_partitions.eps").u().
     176  graphToEps(graph, "bipartite_partitions.eps").undirected().
    176177    coords(coords).scaleToA4().enableParallel().
    177178    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
  • lemon/Makefile.am

    r1909 r1910  
    8989        bits/item_reader.h \
    9090        bits/item_writer.h \
     91        concept/bpugraph.h \
    9192        concept/graph.h \
    9293        concept/graph_component.h \
  • lemon/bits/alteration_notifier.h

    r1909 r1910  
    33 *
    44 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     5 * (Egervary Research Groin on Combinatorial Optimization, EGRES).
    66 *
    77 * Permission to use, modify and distribute this software is granted
     
    2121#include <algorithm>
    2222
    23 ///\ingroup graphmapfactory
     23///\ingroin graphmapfactory
    2424///\file
    2525///\brief Observer registry for graph alteration observers.
     
    2727namespace lemon {
    2828
    29   /// \addtogroup graphmapfactory
     29  /// \addtogroin graphmapfactory
    3030  /// @{
    3131
     
    502502
    503503  template <typename _Base>
    504   class AlterableUBipartiteGraphExtender : public _Base {
     504  class AlterableBpUGraphExtender : public _Base {
    505505  public:
    506506
    507507    typedef _Base Parent;
    508     typedef AlterableUBipartiteGraphExtender Graph;
     508    typedef AlterableBpUGraphExtender Graph;
    509509 
    510510    typedef typename Parent::Node Node;
    511     typedef typename Parent::LowerNode LowerNode;
    512     typedef typename Parent::UpperNode UpperNode;
     511    typedef typename Parent::BNode BNode;
     512    typedef typename Parent::ANode ANode;
    513513    typedef typename Parent::Edge Edge;
    514514    typedef typename Parent::UEdge UEdge;
     
    516516 
    517517    typedef AlterationNotifier<Node> NodeNotifier;
    518     typedef AlterationNotifier<LowerNode> LowerNodeNotifier;
    519     typedef AlterationNotifier<UpperNode> UpperNodeNotifier;
     518    typedef AlterationNotifier<BNode> BNodeNotifier;
     519    typedef AlterationNotifier<ANode> ANodeNotifier;
    520520    typedef AlterationNotifier<Edge> EdgeNotifier;
    521521    typedef AlterationNotifier<UEdge> UEdgeNotifier;
     
    524524
    525525    mutable NodeNotifier nodeNotifier;
    526     mutable LowerNodeNotifier lowerNodeNotifier;
    527     mutable UpperNodeNotifier upperNodeNotifier;
     526    mutable BNodeNotifier bNodeNotifier;
     527    mutable ANodeNotifier aNodeNotifier;
    528528    mutable EdgeNotifier edgeNotifier;
    529529    mutable UEdgeNotifier uEdgeNotifier;
     
    535535    }
    536536
    537     LowerNodeNotifier& getNotifier(LowerNode) const {
    538       return lowerNodeNotifier;
    539     }
    540 
    541     UpperNodeNotifier& getNotifier(UpperNode) const {
    542       return upperNodeNotifier;
     537    BNodeNotifier& getNotifier(BNode) const {
     538      return bNodeNotifier;
     539    }
     540
     541    ANodeNotifier& getNotifier(ANode) const {
     542      return aNodeNotifier;
    543543    }
    544544
     
    551551    }
    552552
    553     ~AlterableUBipartiteGraphExtender() {
     553    ~AlterableBpUGraphExtender() {
    554554      nodeNotifier.clear();
    555       lowerNodeNotifier.clear();
    556       upperNodeNotifier.clear();
     555      bNodeNotifier.clear();
     556      aNodeNotifier.clear();
    557557      edgeNotifier.clear();
    558558      uEdgeNotifier.clear();
  • lemon/bits/array_map.h

    r1875 r1910  
    33 *
    44 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     5 * (Egervary Research Groin on Combinatorial Optimization, EGRES).
    66 *
    77 * Permission to use, modify and distribute this software is granted
     
    2424#include <lemon/concept/maps.h>
    2525
    26 /// \ingroup graphmapfactory
     26/// \ingroin graphmapfactory
    2727/// \file
    2828/// \brief Graph maps that construct and destruct
     
    3131namespace lemon {
    3232
    33   /// \ingroup graphmapfactory
     33  /// \ingroin graphmapfactory
    3434  ///
    3535  /// \brief Graph map based on the array storage.
    3636  ///
    3737  /// The ArrayMap template class is graph map structure what
    38   /// automatically updates the map when a key is added to or erased from
     38  /// automatically indates the map when a key is added to or erased from
    3939  /// the map. This map uses the allocators to implement
    4040  /// the container functionality.
  • lemon/bits/clearable_graph_extender.h

    r1909 r1910  
    8080
    8181  template <typename _Base>
    82   class ClearableUBipartiteGraphExtender : public _Base {
     82  class ClearableBpUGraphExtender : public _Base {
    8383  public:
    8484
    8585    typedef _Base Parent;
    86     typedef ClearableUBipartiteGraphExtender Graph;
     86    typedef ClearableBpUGraphExtender Graph;
    8787
    8888    typedef typename Parent::Node Node;
    89     typedef typename Parent::LowerNode LowerNode;
    90     typedef typename Parent::UpperNode UpperNode;
     89    typedef typename Parent::BNode BNode;
     90    typedef typename Parent::ANode ANode;
    9191    typedef typename Parent::Edge Edge;
    9292    typedef typename Parent::UEdge UEdge;
     
    9696      Parent::getNotifier(UEdge()).clear();
    9797      Parent::getNotifier(Node()).clear();
    98       Parent::getNotifier(LowerNode()).clear();
    99       Parent::getNotifier(UpperNode()).clear();
     98      Parent::getNotifier(BNode()).clear();
     99      Parent::getNotifier(ANode()).clear();
    100100      Parent::clear();
    101101    }
  • lemon/bits/default_map.h

    r1909 r1910  
    33 *
    44 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     5 * (Egervary Research Groin on Combinatorial Optimization, EGRES).
    66 *
    77 * Permission to use, modify and distribute this software is granted
     
    2222#include <lemon/bits/vector_map.h>
    2323
    24 ///\ingroup graphmapfactory
     24///\ingroin graphmapfactory
    2525///\file
    2626///\brief Graph maps that construct and destruct
     
    353353
    354354  template <typename _Base>
    355   class MappableUBipartiteGraphExtender : public _Base {
     355  class MappableBpUGraphExtender : public _Base {
    356356  public:
    357357
    358358    typedef _Base Parent;
    359     typedef MappableUBipartiteGraphExtender Graph;
     359    typedef MappableBpUGraphExtender Graph;
    360360
    361361    typedef typename Parent::Node Node;
    362     typedef typename Parent::UpperNode UpperNode;
    363     typedef typename Parent::LowerNode LowerNode;
     362    typedef typename Parent::ANode ANode;
     363    typedef typename Parent::BNode BNode;
    364364    typedef typename Parent::Edge Edge;
    365365    typedef typename Parent::UEdge UEdge;
    366366   
    367367    template <typename _Value>
    368     class UpperNodeMap
    369       : public IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> > {
    370     public:
    371       typedef MappableUBipartiteGraphExtender Graph;
    372       typedef IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> >
     368    class ANodeMap
     369      : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
     370    public:
     371      typedef MappableBpUGraphExtender Graph;
     372      typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
    373373      Parent;
    374374   
    375       UpperNodeMap(const Graph& _g)
    376         : Parent(_g) {}
    377       UpperNodeMap(const Graph& _g, const _Value& _v)
    378         : Parent(_g, _v) {}
    379    
    380       UpperNodeMap& operator=(const UpperNodeMap& cmap) {
    381         return operator=<UpperNodeMap>(cmap);
     375      ANodeMap(const Graph& _g)
     376        : Parent(_g) {}
     377      ANodeMap(const Graph& _g, const _Value& _v)
     378        : Parent(_g, _v) {}
     379   
     380      ANodeMap& operator=(const ANodeMap& cmap) {
     381        return operator=<ANodeMap>(cmap);
    382382      }
    383383   
     
    387387      /// The given parameter should be conform to the ReadMap
    388388      /// concept and could be indiced by the current item set of
    389       /// the UpperNodeMap. In this case the value for each item
     389      /// the ANodeMap. In this case the value for each item
    390390      /// is assigned by the value of the given ReadMap.
    391391      template <typename CMap>
    392       UpperNodeMap& operator=(const CMap& cmap) {
    393         checkConcept<concept::ReadMap<UpperNode, _Value>, CMap>();
    394         const typename Parent::Graph* graph = Parent::getGraph();
    395         UpperNode it;
    396         for (graph->first(it); it != INVALID; graph->next(it)) {
    397           Parent::set(it, cmap[it]);
    398         }
    399         return *this;
    400       }
    401    
    402     };
    403 
    404     template <typename _Value>
    405     class LowerNodeMap
    406       : public IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> > {
    407     public:
    408       typedef MappableUBipartiteGraphExtender Graph;
    409       typedef IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> >
     392      ANodeMap& operator=(const CMap& cmap) {
     393        checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
     394        const typename Parent::Graph* graph = Parent::getGraph();
     395        ANode it;
     396        for (graph->first(it); it != INVALID; graph->next(it)) {
     397          Parent::set(it, cmap[it]);
     398        }
     399        return *this;
     400      }
     401   
     402    };
     403
     404    template <typename _Value>
     405    class BNodeMap
     406      : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
     407    public:
     408      typedef MappableBpUGraphExtender Graph;
     409      typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
    410410      Parent;
    411411   
    412       LowerNodeMap(const Graph& _g)
    413         : Parent(_g) {}
    414       LowerNodeMap(const Graph& _g, const _Value& _v)
    415         : Parent(_g, _v) {}
    416    
    417       LowerNodeMap& operator=(const LowerNodeMap& cmap) {
    418         return operator=<LowerNodeMap>(cmap);
     412      BNodeMap(const Graph& _g)
     413        : Parent(_g) {}
     414      BNodeMap(const Graph& _g, const _Value& _v)
     415        : Parent(_g, _v) {}
     416   
     417      BNodeMap& operator=(const BNodeMap& cmap) {
     418        return operator=<BNodeMap>(cmap);
    419419      }
    420420   
     
    424424      /// The given parameter should be conform to the ReadMap
    425425      /// concept and could be indiced by the current item set of
    426       /// the LowerNodeMap. In this case the value for each item
     426      /// the BNodeMap. In this case the value for each item
    427427      /// is assigned by the value of the given ReadMap.
    428428      template <typename CMap>
    429       LowerNodeMap& operator=(const CMap& cmap) {
    430         checkConcept<concept::ReadMap<LowerNode, _Value>, CMap>();
    431         const typename Parent::Graph* graph = Parent::getGraph();
    432         LowerNode it;
     429      BNodeMap& operator=(const CMap& cmap) {
     430        checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
     431        const typename Parent::Graph* graph = Parent::getGraph();
     432        BNode it;
    433433        for (graph->first(it); it != INVALID; graph->next(it)) {
    434434          Parent::set(it, cmap[it]);
     
    444444    class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
    445445    public:
    446       typedef MappableUBipartiteGraphExtender Graph;
     446      typedef MappableBpUGraphExtender Graph;
    447447
    448448      typedef Node Key;
     
    450450
    451451      /// The reference type of the map;
    452       typedef typename LowerNodeMap<_Value>::Reference Reference;
     452      typedef typename BNodeMap<_Value>::Reference Reference;
    453453      /// The pointer type of the map;
    454       typedef typename LowerNodeMap<_Value>::Pointer Pointer;
     454      typedef typename BNodeMap<_Value>::Pointer Pointer;
    455455     
    456456      /// The const value type of the map.
    457457      typedef const Value ConstValue;
    458458      /// The const reference type of the map;
    459       typedef typename LowerNodeMap<_Value>::ConstReference ConstReference;
     459      typedef typename BNodeMap<_Value>::ConstReference ConstReference;
    460460      /// The pointer type of the map;
    461       typedef typename LowerNodeMap<_Value>::ConstPointer ConstPointer;
     461      typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
    462462
    463463      typedef True ReferenceMapTag;
    464464
    465465      NodeMapBase(const Graph& _g)
    466         : graph(&_g), lowerMap(_g), upperMap(_g) {
     466        : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
    467467        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    468468      }
    469469      NodeMapBase(const Graph& _g, const _Value& _v)
    470         : graph(&_g), lowerMap(_g, _v),
    471           upperMap(_g, _v) {
     470        : graph(&_g), bNodeMap(_g, _v),
     471          aNodeMap(_g, _v) {
    472472        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    473473      }
     
    480480   
    481481      ConstReference operator[](const Key& node) const {
    482         if (Parent::upper(node)) {
    483           return upperMap[node];
     482        if (Parent::aNode(node)) {
     483          return aNodeMap[node];
    484484        } else {
    485           return lowerMap[node];
     485          return bNodeMap[node];
    486486        }
    487487      }
    488488
    489489      Reference operator[](const Key& node) {
    490         if (Parent::upper(node)) {
    491           return upperMap[node];
     490        if (Parent::aNode(node)) {
     491          return aNodeMap[node];
    492492        } else {
    493           return lowerMap[node];
     493          return bNodeMap[node];
    494494        }
    495495      }
    496496
    497497      void set(const Key& node, const Value& value) {
    498         if (Parent::upper(node)) {
    499           upperMap.set(node, value);
     498        if (Parent::aNode(node)) {
     499          aNodeMap.set(node, value);
    500500        } else {
    501           lowerMap.set(node, value);
     501          bNodeMap.set(node, value);
    502502        }
    503503      }
     
    514514    private:
    515515      const Graph* graph;
    516       LowerNodeMap<_Value> lowerMap;
    517       UpperNodeMap<_Value> upperMap;
     516      BNodeMap<_Value> bNodeMap;
     517      ANodeMap<_Value> aNodeMap;
    518518    };
    519519   
     
    524524      : public IterableMapExtender<NodeMapBase<_Value> > {
    525525    public:
    526       typedef MappableUBipartiteGraphExtender Graph;
     526      typedef MappableBpUGraphExtender Graph;
    527527      typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
    528528   
     
    562562      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
    563563    public:
    564       typedef MappableUBipartiteGraphExtender Graph;
     564      typedef MappableBpUGraphExtender Graph;
    565565      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    566566   
     
    590590      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
    591591    public:
    592       typedef MappableUBipartiteGraphExtender Graph;
     592      typedef MappableBpUGraphExtender Graph;
    593593      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
    594594      Parent;
  • lemon/bits/extendable_graph_extender.h

    r1909 r1910  
    106106
    107107  template <typename _Base>
    108   class ExtendableUBipartiteGraphExtender : public _Base {
     108  class ExtendableBpUGraphExtender : public _Base {
    109109  public:
    110110
    111111    typedef _Base Parent;
    112     typedef ExtendableUBipartiteGraphExtender Graph;
     112    typedef ExtendableBpUGraphExtender Graph;
    113113 
    114114    typedef typename Parent::Node Node;
    115     typedef typename Parent::LowerNode LowerNode;
    116     typedef typename Parent::UpperNode UpperNode;
     115    typedef typename Parent::BNode BNode;
     116    typedef typename Parent::ANode ANode;
    117117    typedef typename Parent::Edge Edge;
    118118    typedef typename Parent::UEdge UEdge;
    119119 
    120     Node addUpperNode() {
    121       Node node = Parent::addUpperNode();
    122       Parent::getNotifier(UpperNode()).add(node);
     120    Node addANode() {
     121      Node node = Parent::addANode();
     122      Parent::getNotifier(ANode()).add(node);
    123123      Parent::getNotifier(Node()).add(node);
    124124      return node;
    125125    }
    126126
    127     Node addLowerNode() {
    128       Node node = Parent::addLowerNode();
    129       Parent::getNotifier(LowerNode()).add(node);
     127    Node addBNode() {
     128      Node node = Parent::addBNode();
     129      Parent::getNotifier(BNode()).add(node);
    130130      Parent::getNotifier(Node()).add(node);
    131131      return node;
  • lemon/bits/graph_extender.h

    r1909 r1910  
    33 *
    44 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi
    5  * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
     5 * Kutatocsoport (Egervary Research Groin on Combinatorial Optimization,
    66 * EGRES).
    77 *
     
    380380
    381381  template <typename _Base>
    382   class UBipartiteGraphExtender : public _Base {
     382  class BpUGraphExtender : public _Base {
    383383  public:
    384384    typedef _Base Parent;
    385     typedef UBipartiteGraphExtender Graph;
     385    typedef BpUGraphExtender Graph;
    386386
    387387    typedef typename Parent::Node Node;
     
    394394
    395395    Node source(const UEdge& edge) const {
    396       return upperNode(edge);
     396      return aNode(edge);
    397397    }
    398398    Node target(const UEdge& edge) const {
    399       return lowerNode(edge);
     399      return bNode(edge);
    400400    }
    401401
    402402    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
    403       if (Parent::upper(node)) {
    404         Parent::firstDown(edge, node);
     403      if (Parent::aNode(node)) {
     404        Parent::firstOut(edge, node);
    405405        direction = true;
    406406      } else {
    407         Parent::firstUp(edge, node);
     407        Parent::firstIn(edge, node);
    408408        direction = static_cast<UEdge&>(edge) == INVALID;
    409409      }
     
    411411    void nextInc(UEdge& edge, bool& direction) const {
    412412      if (direction) {
    413         Parent::nextDown(edge);
    414       } else {
    415         Parent::nextUp(edge);
     413        Parent::nextOut(edge);
     414      } else {
     415        Parent::nextIn(edge);
    416416        if (edge == INVALID) direction = true;
    417417      }
     
    427427
    428428    class Edge : public UEdge {
    429       friend class UBipartiteGraphExtender;
     429      friend class BpUGraphExtender;
    430430    protected:
    431431      bool forward;
     
    462462
    463463    void firstOut(Edge& edge, const Node& node) const {
    464       if (Parent::upper(node)) {
    465         Parent::firstDown(edge, node);
     464      if (Parent::aNode(node)) {
     465        Parent::firstOut(edge, node);
    466466        edge.forward = true;
    467467      } else {
    468         Parent::firstUp(edge, node);
     468        Parent::firstIn(edge, node);
    469469        edge.forward = static_cast<UEdge&>(edge) == INVALID;
    470470      }
     
    472472    void nextOut(Edge& edge) const {
    473473      if (edge.forward) {
    474         Parent::nextDown(edge);
    475       } else {
    476         Parent::nextUp(edge);
     474        Parent::nextOut(edge);
     475      } else {
     476        Parent::nextIn(edge);
    477477        edge.forward = static_cast<UEdge&>(edge) == INVALID;
    478478      }
     
    480480
    481481    void firstIn(Edge& edge, const Node& node) const {
    482       if (Parent::lower(node)) {
    483         Parent::firstUp(edge, node);
     482      if (Parent::bNode(node)) {
     483        Parent::firstIn(edge, node);
    484484        edge.forward = true;   
    485485      } else {
    486         Parent::firstDown(edge, node);
     486        Parent::firstOut(edge, node);
    487487        edge.forward = static_cast<UEdge&>(edge) == INVALID;
    488488      }
     
    490490    void nextIn(Edge& edge) const {
    491491      if (edge.forward) {
    492         Parent::nextUp(edge);
    493       } else {
    494         Parent::nextDown(edge);
     492        Parent::nextIn(edge);
     493      } else {
     494        Parent::nextOut(edge);
    495495        edge.forward = static_cast<UEdge&>(edge) == INVALID;
    496496      }
     
    498498
    499499    Node source(const Edge& edge) const {
    500       return edge.forward ? Parent::upperNode(edge) : Parent::lowerNode(edge);
     500      return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
    501501    }
    502502    Node target(const Edge& edge) const {
    503       return edge.forward ? Parent::lowerNode(edge) : Parent::upperNode(edge);
     503      return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
    504504    }
    505505
     
    535535    }
    536536
    537     class UpperNode : public Node {
    538       friend class UBipartiteGraphExtender;
     537    class ANode : public Node {
     538      friend class BpUGraphExtender;
    539539    public:
    540       UpperNode() {}
    541       UpperNode(const Node& node) : Node(node) {
    542         LEMON_ASSERT(Parent::upper(node) || node == INVALID,
     540      ANode() {}
     541      ANode(const Node& node) : Node(node) {
     542        LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
    543543                     typename Parent::NodeSetError());
    544544      }
    545       UpperNode(Invalid) : Node(INVALID) {}
     545      ANode(Invalid) : Node(INVALID) {}
    546546    };
    547547
    548     void first(UpperNode& node) const {
    549       Parent::firstUpper(static_cast<Node&>(node));
    550     }
    551     void next(UpperNode& node) const {
    552       Parent::nextUpper(static_cast<Node&>(node));
    553     }
    554 
    555     int id(const UpperNode& node) const {
    556       return Parent::upperId(node);
    557     }
    558 
    559     class LowerNode : public Node {
    560       friend class UBipartiteGraphExtender;
     548    void first(ANode& node) const {
     549      Parent::firstANode(static_cast<Node&>(node));
     550    }
     551    void next(ANode& node) const {
     552      Parent::nextANode(static_cast<Node&>(node));
     553    }
     554
     555    int id(const ANode& node) const {
     556      return Parent::aNodeId(node);
     557    }
     558
     559    class BNode : public Node {
     560      friend class BpUGraphExtender;
    561561    public:
    562       LowerNode() {}
    563       LowerNode(const Node& node) : Node(node) {
    564         LEMON_ASSERT(Parent::lower(node) || node == INVALID,
     562      BNode() {}
     563      BNode(const Node& node) : Node(node) {
     564        LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
    565565                     typename Parent::NodeSetError());
    566566      }
    567       LowerNode(Invalid) : Node(INVALID) {}
     567      BNode(Invalid) : Node(INVALID) {}
    568568    };
    569569
    570     void first(LowerNode& node) const {
    571       Parent::firstLower(static_cast<Node&>(node));
    572     }
    573     void next(LowerNode& node) const {
    574       Parent::nextLower(static_cast<Node&>(node));
     570    void first(BNode& node) const {
     571      Parent::firstBNode(static_cast<Node&>(node));
     572    }
     573    void next(BNode& node) const {
     574      Parent::nextBNode(static_cast<Node&>(node));
    575575    }
    576576 
    577     int id(const LowerNode& node) const {
    578       return Parent::upperId(node);
     577    int id(const BNode& node) const {
     578      return Parent::aNodeId(node);
    579579    }
    580580
     
    584584      return Parent::maxNodeId();
    585585    }
    586     int maxId(LowerNode) const {
    587       return Parent::maxLowerId();
    588     }
    589     int maxId(UpperNode) const {
    590       return Parent::maxUpperId();
     586    int maxId(BNode) const {
     587      return Parent::maxBNodeId();
     588    }
     589    int maxId(ANode) const {
     590      return Parent::maxANodeId();
    591591    }
    592592    int maxId(Edge) const {
     
    601601      return Parent::nodeFromId(id);
    602602    }
    603     UpperNode fromId(int id, UpperNode) const {
    604       return Parent::fromUpperId(id);
    605     }
    606     LowerNode fromId(int id, LowerNode) const {
    607       return Parent::fromLowerId(id);
     603    ANode fromId(int id, ANode) const {
     604      return Parent::fromANodeId(id);
     605    }
     606    BNode fromId(int id, BNode) const {
     607      return Parent::fromBNodeId(id);
    608608    }
    609609    Edge fromId(int id, Edge) const {
  • lemon/bits/item_reader.h

    r1875 r1910  
    33 *
    44 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     5 * (Egervary Research Groin on Combinatorial Optimization, EGRES).
    66 *
    77 * Permission to use, modify and distribute this software is granted
     
    1515 */
    1616
    17 /// @defgroup item_io Item Readers and Writers
    18 /// @ingroup io_group
     17/// @defgroin item_io Item Readers and Writers
     18/// @ingroin io_groin
    1919/// \brief Item Readers and Writers
    2020///
     
    2323/// read some way. The module make possible to do this. 
    2424
    25 /// \ingroup item_io
     25/// \ingroin item_io
    2626/// \file
    2727/// \brief Item reader bits for lemon input.
     
    4343  class DefaultReader;
    4444
    45   /// \ingroup item_io
     45  /// \ingroin item_io
    4646  ///
    4747  /// \brief Reader class for quoted strings.
     
    158158  };
    159159
    160   /// \ingroup item_io
     160  /// \ingroin item_io
    161161  /// \brief Reader for standard containers.
    162162  ///
     
    205205  };
    206206
    207   /// \ingroup item_io
     207  /// \ingroin item_io
    208208  ///
    209209  /// \brief Reader for standard containers.
     
    253253  };
    254254
    255   /// \ingroup item_io
     255  /// \ingroin item_io
    256256  /// \brief Reader for parsed string.
    257257  ///
     
    301301  };
    302302
    303   /// \ingroup item_io
     303  /// \ingroin item_io
    304304  /// \brief Reader for read the whole line.
    305305  ///
     
    331331  };
    332332
    333   /// \ingroup item_io
     333  /// \ingroin item_io
    334334  /// \brief Reader for std::pair.
    335335  ///
     
    385385  };
    386386
    387   /// \ingroup item_io
     387  /// \ingroin item_io
    388388  ///
    389389  /// \brief The default item reader template class.
     
    472472    : public PairReader<std::pair<First, Second> > {};
    473473
    474   /// \ingroup item_io
     474  /// \ingroin item_io
    475475  ///
    476476  /// \brief The default item reader for skipping a value in the stream.
     
    481481  class DefaultSkipper : public DefaultReader<std::string> {};
    482482
    483   /// \ingroup item_io 
     483  /// \ingroin item_io 
    484484  /// \brief Standard ReaderTraits for the GraphReader class.
    485485  ///
  • lemon/bits/item_writer.h

    r1875 r1910  
    33 *
    44 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     5 * (Egervary Research Groin on Combinatorial Optimization, EGRES).
    66 *
    77 * Permission to use, modify and distribute this software is granted
     
    1515 */
    1616
    17 /// \ingroup item_io
     17/// \ingroin item_io
    1818/// \file
    1919/// \brief Item writer bits for lemon output.
     
    3535  class DefaultWriter;
    3636
    37   /// \ingroup item_io
     37  /// \ingroin item_io
    3838  /// \brief Writer class for quoted strings.
    3939  ///
     
    118118  };
    119119
    120   /// \ingroup item_io
     120  /// \ingroin item_io
    121121  /// \brief Writer class for quoted char array.
    122122  ///
     
    146146
    147147
    148   /// \ingroup item_io
     148  /// \ingroin item_io
    149149  ///
    150150  /// \brief Writer for standard containers.
     
    188188  };
    189189
    190   /// \ingroup item_io
     190  /// \ingroin item_io
    191191  ///
    192192  /// \brief Writer for standard pairs.
     
    235235  };
    236236
    237   /// \ingroup item_io
     237  /// \ingroin item_io
    238238  ///
    239239  /// \brief The default item writer template class.
     
    308308    : public PairWriter<std::pair<First, Second> > {};
    309309
    310   /// \ingroup item_io
     310  /// \ingroin item_io
    311311  /// \brief Standard WriterTraits for the section writers.
    312312  ///
  • lemon/bits/iterable_graph_extender.h

    r1909 r1910  
    271271
    272272  template <typename _Base>
    273   class IterableUBipartiteGraphExtender : public _Base {
     273  class IterableBpUGraphExtender : public _Base {
    274274  public:
    275275    typedef _Base Parent;
    276     typedef IterableUBipartiteGraphExtender Graph;
     276    typedef IterableBpUGraphExtender Graph;
    277277   
    278278    typedef typename Parent::Node Node;
    279     typedef typename Parent::UpperNode UpperNode;
    280     typedef typename Parent::LowerNode LowerNode;
     279    typedef typename Parent::ANode ANode;
     280    typedef typename Parent::BNode BNode;
    281281    typedef typename Parent::Edge Edge;
    282282    typedef typename Parent::UEdge UEdge;
     
    304304    };
    305305
    306     class UpperNodeIt : public Node {
    307       friend class IterableUBipartiteGraphExtender;
    308       const Graph* graph;
    309     public:
    310    
    311       UpperNodeIt() { }
    312    
    313       UpperNodeIt(Invalid i) : Node(INVALID) { }
    314    
    315       explicit UpperNodeIt(const Graph& _graph) : graph(&_graph) {
    316         graph->firstUpper(static_cast<Node&>(*this));
    317       }
    318 
    319       UpperNodeIt(const Graph& _graph, const Node& node)
     306    class ANodeIt : public Node {
     307      friend class IterableBpUGraphExtender;
     308      const Graph* graph;
     309    public:
     310   
     311      ANodeIt() { }
     312   
     313      ANodeIt(Invalid i) : Node(INVALID) { }
     314   
     315      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
     316        graph->firstANode(static_cast<Node&>(*this));
     317      }
     318
     319      ANodeIt(const Graph& _graph, const Node& node)
    320320        : Node(node), graph(&_graph) {}
    321321   
    322       UpperNodeIt& operator++() {
    323         graph->nextUpper(*this);
    324         return *this;
    325       }
    326     };
    327 
    328     class LowerNodeIt : public Node {
    329       friend class IterableUBipartiteGraphExtender;
    330       const Graph* graph;
    331     public:
    332    
    333       LowerNodeIt() { }
    334    
    335       LowerNodeIt(Invalid i) : Node(INVALID) { }
    336    
    337       explicit LowerNodeIt(const Graph& _graph) : graph(&_graph) {
    338         graph->firstLower(static_cast<Node&>(*this));
    339       }
    340 
    341       LowerNodeIt(const Graph& _graph, const Node& node)
     322      ANodeIt& operator++() {
     323        graph->nextANode(*this);
     324        return *this;
     325      }
     326    };
     327
     328    class BNodeIt : public Node {
     329      friend class IterableBpUGraphExtender;
     330      const Graph* graph;
     331    public:
     332   
     333      BNodeIt() { }
     334   
     335      BNodeIt(Invalid i) : Node(INVALID) { }
     336   
     337      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
     338        graph->firstBNode(static_cast<Node&>(*this));
     339      }
     340
     341      BNodeIt(const Graph& _graph, const Node& node)
    342342        : Node(node), graph(&_graph) {}
    343343   
    344       LowerNodeIt& operator++() {
    345         graph->nextLower(*this);
     344      BNodeIt& operator++() {
     345        graph->nextBNode(*this);
    346346        return *this;
    347347      }
     
    349349
    350350    class EdgeIt : public Edge {
    351       friend class IterableUBipartiteGraphExtender;
     351      friend class IterableBpUGraphExtender;
    352352      const Graph* graph;
    353353    public:
     
    372372
    373373    class UEdgeIt : public UEdge {
    374       friend class IterableUBipartiteGraphExtender;
     374      friend class IterableBpUGraphExtender;
    375375      const Graph* graph;
    376376    public:
     
    394394
    395395    class OutEdgeIt : public Edge {
    396       friend class IterableUBipartiteGraphExtender;
     396      friend class IterableBpUGraphExtender;
    397397      const Graph* graph;
    398398    public:
     
    419419
    420420    class InEdgeIt : public Edge {
    421       friend class IterableUBipartiteGraphExtender;
     421      friend class IterableBpUGraphExtender;
    422422      const Graph* graph;
    423423    public:
     
    471471 
    472472    class IncEdgeIt : public Parent::UEdge {
    473       friend class IterableUBipartiteGraphExtender;
     473      friend class IterableBpUGraphExtender;
    474474      const Graph* graph;
    475475      bool direction;
  • lemon/bits/map_extender.h

    r1875 r1910  
    33 *
    44 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     5 * (Egervary Research Groin on Combinatorial Optimization, EGRES).
    66 *
    77 * Permission to use, modify and distribute this software is granted
  • lemon/bits/static_map.h

    r1909 r1910  
    33 *
    44 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     5 * (Egervary Research Groin on Combinatorial Optimization, EGRES).
    66 *
    77 * Permission to use, modify and distribute this software is granted
     
    2828#include <lemon/concept/maps.h>
    2929
    30 /// \ingroup graphmaps
     30/// \ingroin graphmaps
    3131///
    3232///\file
     
    3535namespace lemon {
    3636
    37   /// \ingroup graphmaps
     37  /// \ingroin graphmaps
    3838  ///
    3939  /// \brief Graph map with static sized storage.
    4040  ///
    4141  /// The StaticMap template class is graph map structure what
    42   /// does not update automatically the map when a key is added to or
     42  /// does not indate automatically the map when a key is added to or
    4343  /// erased from the map rather it throws an exception. This map factory
    4444  /// uses the allocators to implement the container functionality.
     
    5555  public:
    5656
    57     /// \brief Exception class for unsupported exceptions.
    58     class UnsupportedOperation : public lemon::LogicError {
     57    /// \brief Exception class for unsinported exceptions.
     58    class UnsinportedOperation : public lemon::LogicError {
    5959    public:
    6060      virtual const char* exceptionName() const {
    61         return "lemon::StaticMap::UnsupportedOperation";
     61        return "lemon::StaticMap::UnsinportedOperation";
    6262      }
    6363    };
     
    186186     
    187187    void add(const Key&) {
    188       throw UnsupportedOperation();
     188      throw UnsinportedOperation();
    189189    }
    190190
     
    194194    /// and it overrides the erase() member function of the observer base.     
    195195    void erase(const Key&) {
    196       throw UnsupportedOperation();
     196      throw UnsinportedOperation();
    197197    }
    198198
     
    347347
    348348  template <typename _Base>
    349   class StaticMappableUBipartiteGraphExtender : public _Base {
     349  class StaticMappableBpUGraphExtender : public _Base {
    350350  public:
    351351
    352352    typedef _Base Parent;
    353     typedef StaticMappableUBipartiteGraphExtender Graph;
     353    typedef StaticMappableBpUGraphExtender Graph;
    354354
    355355    typedef typename Parent::Node Node;
    356     typedef typename Parent::UpperNode UpperNode;
    357     typedef typename Parent::LowerNode LowerNode;
     356    typedef typename Parent::ANode ANode;
     357    typedef typename Parent::BNode BNode;
    358358    typedef typename Parent::Edge Edge;
    359359    typedef typename Parent::UEdge UEdge;
    360360   
    361361    template <typename _Value>
    362     class UpperNodeMap
    363       : public IterableMapExtender<StaticMap<Graph, UpperNode, _Value> > {
    364     public:
    365       typedef StaticMappableUBipartiteGraphExtender Graph;
    366       typedef IterableMapExtender<StaticMap<Graph, UpperNode, _Value> >
     362    class ANodeMap
     363      : public IterableMapExtender<StaticMap<Graph, ANode, _Value> > {
     364    public:
     365      typedef StaticMappableBpUGraphExtender Graph;
     366      typedef IterableMapExtender<StaticMap<Graph, ANode, _Value> >
    367367      Parent;
    368368   
    369       UpperNodeMap(const Graph& _g)
    370         : Parent(_g) {}
    371       UpperNodeMap(const Graph& _g, const _Value& _v)
    372         : Parent(_g, _v) {}
    373    
    374       UpperNodeMap& operator=(const UpperNodeMap& cmap) {
    375         return operator=<UpperNodeMap>(cmap);
     369      ANodeMap(const Graph& _g)
     370        : Parent(_g) {}
     371      ANodeMap(const Graph& _g, const _Value& _v)
     372        : Parent(_g, _v) {}
     373   
     374      ANodeMap& operator=(const ANodeMap& cmap) {
     375        return operator=<ANodeMap>(cmap);
    376376      }
    377377   
     
    381381      /// The given parameter should be conform to the ReadMap
    382382      /// concept and could be indiced by the current item set of
    383       /// the UpperNodeMap. In this case the value for each item
     383      /// the ANodeMap. In this case the value for each item
    384384      /// is assigned by the value of the given ReadMap.
    385385      template <typename CMap>
    386       UpperNodeMap& operator=(const CMap& cmap) {
    387         checkConcept<concept::ReadMap<UpperNode, _Value>, CMap>();
    388         const typename Parent::Graph* graph = Parent::getGraph();
    389         UpperNode it;
    390         for (graph->first(it); it != INVALID; graph->next(it)) {
    391           Parent::set(it, cmap[it]);
    392         }
    393         return *this;
    394       }
    395    
    396     };
    397 
    398     template <typename _Value>
    399     class LowerNodeMap
    400       : public IterableMapExtender<StaticMap<Graph, LowerNode, _Value> > {
    401     public:
    402       typedef StaticMappableUBipartiteGraphExtender Graph;
    403       typedef IterableMapExtender<StaticMap<Graph, LowerNode, _Value> >
     386      ANodeMap& operator=(const CMap& cmap) {
     387        checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
     388        const typename Parent::Graph* graph = Parent::getGraph();
     389        ANode it;
     390        for (graph->first(it); it != INVALID; graph->next(it)) {
     391          Parent::set(it, cmap[it]);
     392        }
     393        return *this;
     394      }
     395   
     396    };
     397
     398    template <typename _Value>
     399    class BNodeMap
     400      : public IterableMapExtender<StaticMap<Graph, BNode, _Value> > {
     401    public:
     402      typedef StaticMappableBpUGraphExtender Graph;
     403      typedef IterableMapExtender<StaticMap<Graph, BNode, _Value> >
    404404      Parent;
    405405   
    406       LowerNodeMap(const Graph& _g)
    407         : Parent(_g) {}
    408       LowerNodeMap(const Graph& _g, const _Value& _v)
    409         : Parent(_g, _v) {}
    410    
    411       LowerNodeMap& operator=(const LowerNodeMap& cmap) {
    412         return operator=<LowerNodeMap>(cmap);
     406      BNodeMap(const Graph& _g)
     407        : Parent(_g) {}
     408      BNodeMap(const Graph& _g, const _Value& _v)
     409        : Parent(_g, _v) {}
     410   
     411      BNodeMap& operator=(const BNodeMap& cmap) {
     412        return operator=<BNodeMap>(cmap);
    413413      }
    414414   
     
    418418      /// The given parameter should be conform to the ReadMap
    419419      /// concept and could be indiced by the current item set of
    420       /// the LowerNodeMap. In this case the value for each item
     420      /// the BNodeMap. In this case the value for each item
    421421      /// is assigned by the value of the given ReadMap.
    422422      template <typename CMap>
    423       LowerNodeMap& operator=(const CMap& cmap) {
    424         checkConcept<concept::ReadMap<LowerNode, _Value>, CMap>();
    425         const typename Parent::Graph* graph = Parent::getGraph();
    426         LowerNode it;
     423      BNodeMap& operator=(const CMap& cmap) {
     424        checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
     425        const typename Parent::Graph* graph = Parent::getGraph();
     426        BNode it;
    427427        for (graph->first(it); it != INVALID; graph->next(it)) {
    428428          Parent::set(it, cmap[it]);
     
    438438    class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
    439439    public:
    440       typedef StaticMappableUBipartiteGraphExtender Graph;
     440      typedef StaticMappableBpUGraphExtender Graph;
    441441
    442442      typedef Node Key;
     
    444444
    445445      /// The reference type of the map;
    446       typedef typename LowerNodeMap<_Value>::Reference Reference;
     446      typedef typename BNodeMap<_Value>::Reference Reference;
    447447      /// The pointer type of the map;
    448       typedef typename LowerNodeMap<_Value>::Pointer Pointer;
     448      typedef typename BNodeMap<_Value>::Pointer Pointer;
    449449     
    450450      /// The const value type of the map.
    451451      typedef const Value ConstValue;
    452452      /// The const reference type of the map;
    453       typedef typename LowerNodeMap<_Value>::ConstReference ConstReference;
     453      typedef typename BNodeMap<_Value>::ConstReference ConstReference;
    454454      /// The pointer type of the map;
    455       typedef typename LowerNodeMap<_Value>::ConstPointer ConstPointer;
     455      typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
    456456
    457457      typedef True ReferenceMapTag;
    458458
    459459      NodeMapBase(const Graph& _g)
    460         : graph(&_g), lowerMap(_g), upperMap(_g) {
     460        : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
    461461        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    462462      }
    463463      NodeMapBase(const Graph& _g, const _Value& _v)
    464         : graph(&_g), lowerMap(_g, _v),
    465           upperMap(_g, _v) {
     464        : graph(&_g), bNodeMap(_g, _v),
     465          aNodeMap(_g, _v) {
    466466        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    467467      }
     
    474474   
    475475      ConstReference operator[](const Key& node) const {
    476         if (Parent::upper(node)) {
    477           return upperMap[node];
     476        if (Parent::aNode(node)) {
     477          return aNodeMap[node];
    478478        } else {
    479           return lowerMap[node];
     479          return bNodeMap[node];
    480480        }
    481481      }
    482482
    483483      Reference operator[](const Key& node) {
    484         if (Parent::upper(node)) {
    485           return upperMap[node];
     484        if (Parent::aNode(node)) {
     485          return aNodeMap[node];
    486486        } else {
    487           return lowerMap[node];
     487          return bNodeMap[node];
    488488        }
    489489      }
    490490
    491491      void set(const Key& node, const Value& value) {
    492         if (Parent::upper(node)) {
    493           upperMap.set(node, value);
     492        if (Parent::aNode(node)) {
     493          aNodeMap.set(node, value);
    494494        } else {
    495           lowerMap.set(node, value);
     495          bNodeMap.set(node, value);
    496496        }
    497497      }
     
    508508    private:
    509509      const Graph* graph;
    510       LowerNodeMap<_Value> lowerMap;
    511       UpperNodeMap<_Value> upperMap;
     510      BNodeMap<_Value> bNodeMap;
     511      ANodeMap<_Value> aNodeMap;
    512512    };
    513513   
     
    518518      : public IterableMapExtender<NodeMapBase<_Value> > {
    519519    public:
    520       typedef StaticMappableUBipartiteGraphExtender Graph;
     520      typedef StaticMappableBpUGraphExtender Graph;
    521521      typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
    522522   
     
    556556      : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
    557557    public:
    558       typedef StaticMappableUBipartiteGraphExtender Graph;
     558      typedef StaticMappableBpUGraphExtender Graph;
    559559      typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
    560560   
     
    584584      : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {
    585585    public:
    586       typedef StaticMappableUBipartiteGraphExtender Graph;
     586      typedef StaticMappableBpUGraphExtender Graph;
    587587      typedef IterableMapExtender<StaticMap<Graph, UEdge, _Value> >
    588588      Parent;
  • lemon/bits/vector_map.h

    r1875 r1910  
    33 *
    44 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     5 * (Egervary Research Groin on Combinatorial Optimization, EGRES).
    66 *
    77 * Permission to use, modify and distribute this software is granted
     
    2727#include <lemon/concept/maps.h>
    2828
    29 /// \ingroup graphmapfactory
     29/// \ingroin graphmapfactory
    3030///
    3131///\file
     
    3434namespace lemon {
    3535
    36   /// \ingroup graphmapfactory
     36  /// \ingroin graphmapfactory
    3737  ///
    3838  /// \brief Graph map based on the std::vector storage.
    3939  ///
    4040  /// The VectorMap template class is graph map structure what
    41   /// automatically updates the map when a key is added to or erased from
     41  /// automatically indates the map when a key is added to or erased from
    4242  /// the map. This map factory uses the allocators to implement
    4343  /// the container functionality. This map factory
  • lemon/concept/ugraph.h

    r1909 r1910  
    2323
    2424
    25 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
    26 #define LEMON_CONCEPT_UNDIR_GRAPH_H
     25#ifndef LEMON_CONCEPT_UGRAPH_H
     26#define LEMON_CONCEPT_UGRAPH_H
    2727
    2828#include <lemon/concept/graph_component.h>
  • lemon/full_graph.h

    r1909 r1910  
    404404
    405405
    406   class FullUBipartiteGraphBase {
     406  class FullBpUGraphBase {
    407407  protected:
    408408
    409     int _upperNodeNum;
    410     int _lowerNodeNum;
     409    int _aNodeNum;
     410    int _bNodeNum;
    411411
    412412    int _edgeNum;
     
    416416    class NodeSetError : public LogicError {
    417417      virtual const char* exceptionName() const {
    418         return "lemon::FullUBipartiteGraph::NodeSetError";
     418        return "lemon::FullBpUGraph::NodeSetError";
    419419      }
    420420    };
    421421 
    422422    class Node {
    423       friend class FullUBipartiteGraphBase;
     423      friend class FullBpUGraphBase;
    424424    protected:
    425425      int id;
     
    435435
    436436    class Edge {
    437       friend class FullUBipartiteGraphBase;
     437      friend class FullBpUGraphBase;
    438438    protected:
    439439      int id;
     
    448448    };
    449449
    450     void construct(int upperNodeNum, int lowerNodeNum) {
    451       _upperNodeNum = upperNodeNum;
    452       _lowerNodeNum = lowerNodeNum;
    453       _edgeNum = upperNodeNum * lowerNodeNum;
    454     }
    455 
    456     void firstUpper(Node& node) const {
    457       node.id = 2 * _upperNodeNum - 2;
     450    void construct(int aNodeNum, int bNodeNum) {
     451      _aNodeNum = aNodeNum;
     452      _bNodeNum = bNodeNum;
     453      _edgeNum = aNodeNum * bNodeNum;
     454    }
     455
     456    void firstANode(Node& node) const {
     457      node.id = 2 * _aNodeNum - 2;
    458458      if (node.id < 0) node.id = -1;
    459459    }
    460     void nextUpper(Node& node) const {
     460    void nextANode(Node& node) const {
    461461      node.id -= 2;
    462462      if (node.id < 0) node.id = -1;
    463463    }
    464464
    465     void firstLower(Node& node) const {
    466       node.id = 2 * _lowerNodeNum - 1;
    467     }
    468     void nextLower(Node& node) const {
     465    void firstBNode(Node& node) const {
     466      node.id = 2 * _bNodeNum - 1;
     467    }
     468    void nextBNode(Node& node) const {
    469469      node.id -= 2;
    470470    }
    471471
    472472    void first(Node& node) const {
    473       if (_upperNodeNum > 0) {
    474         node.id = 2 * _upperNodeNum - 2;
     473      if (_aNodeNum > 0) {
     474        node.id = 2 * _aNodeNum - 2;
    475475      } else {
    476         node.id = 2 * _lowerNodeNum - 1;
     476        node.id = 2 * _bNodeNum - 1;
    477477      }
    478478    }
     
    480480      node.id -= 2;
    481481      if (node.id == -2) {
    482         node.id = 2 * _lowerNodeNum - 1;
     482        node.id = 2 * _bNodeNum - 1;
    483483      }
    484484    }
     
    491491    }
    492492
    493     void firstDown(Edge& edge, const Node& node) const {
     493    void firstOut(Edge& edge, const Node& node) const {
    494494      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    495       edge.id = (node.id >> 1) * _lowerNodeNum;
    496     }
    497     void nextDown(Edge& edge) const {
     495      edge.id = (node.id >> 1) * _bNodeNum;
     496    }
     497    void nextOut(Edge& edge) const {
    498498      ++(edge.id);
    499       if (edge.id % _lowerNodeNum == 0) edge.id = -1;
    500     }
    501 
    502     void firstUp(Edge& edge, const Node& node) const {
     499      if (edge.id % _bNodeNum == 0) edge.id = -1;
     500    }
     501
     502    void firstIn(Edge& edge, const Node& node) const {
    503503      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    504504      edge.id = (node.id >> 1);
    505505    }
    506     void nextUp(Edge& edge) const {
    507       edge.id += _lowerNodeNum;
     506    void nextIn(Edge& edge) const {
     507      edge.id += _bNodeNum;
    508508      if (edge.id >= _edgeNum) edge.id = -1;
    509509    }
     
    516516    }
    517517    int maxNodeId() const {
    518       return _upperNodeNum > _lowerNodeNum ?
    519         _upperNodeNum * 2 - 2 : _lowerNodeNum * 2 - 1;
     518      return _aNodeNum > _bNodeNum ?
     519        _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
    520520    }
    521521 
     
    530530    }
    531531 
    532     static int upperId(const Node& node) {
     532    static int aNodeId(const Node& node) {
    533533      return node.id >> 1;
    534534    }
    535     static Node fromUpperId(int id, Node) {
     535    static Node fromANodeId(int id, Node) {
    536536      return Node(id << 1);
    537537    }
    538     int maxUpperId() const {
    539       return _upperNodeNum;
    540     }
    541 
    542     static int lowerId(const Node& node) {
     538    int maxANodeId() const {
     539      return _aNodeNum;
     540    }
     541
     542    static int bNodeId(const Node& node) {
    543543      return node.id >> 1;
    544544    }
    545     static Node fromLowerId(int id) {
     545    static Node fromBNodeId(int id) {
    546546      return Node((id << 1) + 1);
    547547    }
    548     int maxLowerId() const {
    549       return _lowerNodeNum;
    550     }
    551 
    552     Node upperNode(const Edge& edge) const {
    553       return Node((edge.id / _lowerNodeNum) << 1);
    554     }
    555     Node lowerNode(const Edge& edge) const {
    556       return Node(((edge.id % _lowerNodeNum) << 1) + 1);
    557     }
    558 
    559     static bool upper(const Node& node) {
     548    int maxBNodeId() const {
     549      return _bNodeNum;
     550    }
     551
     552    Node aNode(const Edge& edge) const {
     553      return Node((edge.id / _bNodeNum) << 1);
     554    }
     555    Node bNode(const Edge& edge) const {
     556      return Node(((edge.id % _bNodeNum) << 1) + 1);
     557    }
     558
     559    static bool aNode(const Node& node) {
    560560      return (node.id & 1) == 0;
    561561    }
    562562
    563     static bool lower(const Node& node) {
     563    static bool bNode(const Node& node) {
    564564      return (node.id & 1) == 1;
    565565    }
    566566
    567     static Node upperNode(int index) {
     567    static Node aNode(int index) {
    568568      return Node(index << 1);
    569569    }
    570570
    571     static Node lowerNode(int index) {
     571    static Node bNode(int index) {
    572572      return Node((index << 1) + 1);
    573573    }
     
    576576
    577577
    578   typedef StaticMappableUBipartiteGraphExtender<
    579     IterableUBipartiteGraphExtender<
    580     AlterableUBipartiteGraphExtender<
    581     UBipartiteGraphExtender <
    582     FullUBipartiteGraphBase> > > >
    583   ExtendedFullUBipartiteGraphBase;
    584 
    585 
    586   class FullUBipartiteGraph :
    587     public ExtendedFullUBipartiteGraphBase {
    588   public:
    589     typedef ExtendedFullUBipartiteGraphBase Parent;
    590     FullUBipartiteGraph(int upperNodeNum, int lowerNodeNum) {
    591       Parent::construct(upperNodeNum, lowerNodeNum);
     578  typedef StaticMappableBpUGraphExtender<
     579    IterableBpUGraphExtender<
     580    AlterableBpUGraphExtender<
     581    BpUGraphExtender <
     582    FullBpUGraphBase> > > >
     583  ExtendedFullBpUGraphBase;
     584
     585
     586  /// \ingroup graphs
     587  ///
     588  /// \brief An undirected full bipartite graph class.
     589  ///
     590  /// This is a simple and fast bipartite undirected full graph implementation.
     591  /// It is completely static, so you can neither add nor delete either
     592  /// edges or nodes.
     593  ///
     594  /// \sa FullGraph
     595  ///
     596  /// \author Balazs Dezso
     597  class FullBpUGraph :
     598    public ExtendedFullBpUGraphBase {
     599  public:
     600    typedef ExtendedFullBpUGraphBase Parent;
     601    FullBpUGraph(int aNodeNum, int bNodeNum) {
     602      Parent::construct(aNodeNum, bNodeNum);
    592603    }
    593604  };
  • lemon/graph_to_eps.h

    r1909 r1910  
    235235  char *_nodePsTextsPreamble;
    236236 
    237   bool _u;
     237  bool _undirected;
     238
    238239  bool _pleaseRemoveOsStream;
    239240
     
    273274    _showNodeText(false), _nodeTexts(false), _nodeTextSize(1),
    274275    _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0),
    275     _u(false),
     276    _undirected(false),
    276277    _pleaseRemoveOsStream(_pros), _scaleToA4(false),
    277278    _nodeTextColorType(SAME_COL), _nodeTextColors(Color(0,0,0)),
     
    330331  using T::_nodePsTextsPreamble;
    331332 
    332   using T::_u;
     333  using T::_undirected;
     334
    333335  using T::_pleaseRemoveOsStream;
    334336
     
    735737  ///Sets whether the the graph is undirected
    736738  ///
    737   GraphToEps<T> &u(bool b=true) {_u=b;return *this;}
     739  GraphToEps<T> &undirected(bool b=true) {_undirected=b;return *this;}
     740
    738741  ///Sets whether the the graph is directed
    739742
    740743  ///Sets whether the the graph is directed.
    741744  ///Use it to show the undirected edges as a pair of directed ones.
    742   GraphToEps<T> &bidir(bool b=true) {_u=!b;return *this;}
     745  GraphToEps<T> &bidir(bool b=true) {_undirected=!b;return *this;}
    743746
    744747  ///Sets the title.
     
    959962        std::vector<Edge> el;
    960963        for(EdgeIt e(g);e!=INVALID;++e)
    961           if((!_u||g.source(e)<g.target(e))&&_edgeWidths[e]>0)
     964          if((!_undirected||g.source(e)<g.target(e))&&_edgeWidths[e]>0)
    962965            el.push_back(e);
    963966        std::sort(el.begin(),el.end(),edgeLess(g));
     
    10471050      }
    10481051      else for(EdgeIt e(g);e!=INVALID;++e)
    1049         if((!_u||g.source(e)<g.target(e))&&_edgeWidths[e]>0)
     1052        if((!_undirected||g.source(e)<g.target(e))&&_edgeWidths[e]>0)
    10501053          if(_drawArrows) {
    10511054            xy<double> d(mycoords[g.target(e)]-mycoords[g.source(e)]);
  • lemon/smart_graph.h

    r1909 r1910  
    379379
    380380
    381   class SmartUBipartiteGraphBase {
     381  class SmartBpUGraphBase {
    382382  public:
    383383
    384384    class NodeSetError : public LogicError {
    385385      virtual const char* exceptionName() const {
    386         return "lemon::FullUBipartiteGraph::NodeSetError";
     386        return "lemon::SmartBpUGraph::NodeSetError";
    387387      }
    388388    };
     
    397397
    398398    struct EdgeT {
    399       int upper, next_down;
    400       int lower, next_up;
    401     };
    402 
    403     std::vector<NodeT> upperNodes;
    404     std::vector<NodeT> lowerNodes;
     399      int aNode, next_out;
     400      int bNode, next_in;
     401    };
     402
     403    std::vector<NodeT> aNodes;
     404    std::vector<NodeT> bNodes;
    405405
    406406    std::vector<EdgeT> edges;
     
    409409 
    410410    class Node {
    411       friend class SmartUBipartiteGraphBase;
     411      friend class SmartBpUGraphBase;
    412412    protected:
    413413      int id;
     
    423423
    424424    class Edge {
    425       friend class SmartUBipartiteGraphBase;
     425      friend class SmartBpUGraphBase;
    426426    protected:
    427427      int id;
     
    436436    };
    437437
    438     void firstUpper(Node& node) const {
    439       node.id = 2 * upperNodes.size() - 2;
     438    void firstANode(Node& node) const {
     439      node.id = 2 * aNodes.size() - 2;
    440440      if (node.id < 0) node.id = -1;
    441441    }
    442     void nextUpper(Node& node) const {
     442    void nextANode(Node& node) const {
    443443      node.id -= 2;
    444444      if (node.id < 0) node.id = -1;
    445445    }
    446446
    447     void firstLower(Node& node) const {
    448       node.id = 2 * lowerNodes.size() - 1;
    449     }
    450     void nextLower(Node& node) const {
     447    void firstBNode(Node& node) const {
     448      node.id = 2 * bNodes.size() - 1;
     449    }
     450    void nextBNode(Node& node) const {
    451451      node.id -= 2;
    452452    }
    453453
    454454    void first(Node& node) const {
    455       if (upperNodes.size() > 0) {
    456         node.id = 2 * upperNodes.size() - 2;
     455      if (aNodes.size() > 0) {
     456        node.id = 2 * aNodes.size() - 2;
    457457      } else {
    458         node.id = 2 * lowerNodes.size() - 1;
     458        node.id = 2 * bNodes.size() - 1;
    459459      }
    460460    }
     
    462462      node.id -= 2;
    463463      if (node.id == -2) {
    464         node.id = 2 * lowerNodes.size() - 1;
     464        node.id = 2 * bNodes.size() - 1;
    465465      }
    466466    }
     
    473473    }
    474474
    475     void firstDown(Edge& edge, const Node& node) const {
     475    void firstOut(Edge& edge, const Node& node) const {
    476476      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    477       edge.id = upperNodes[node.id >> 1].first;
    478     }
    479     void nextDown(Edge& edge) const {
    480       edge.id = edges[edge.id].next_down;
    481     }
    482 
    483     void firstUp(Edge& edge, const Node& node) const {
     477      edge.id = aNodes[node.id >> 1].first;
     478    }
     479    void nextOut(Edge& edge) const {
     480      edge.id = edges[edge.id].next_out;
     481    }
     482
     483    void firstIn(Edge& edge, const Node& node) const {
    484484      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    485       edge.id = lowerNodes[node.id >> 1].first;
    486     }
    487     void nextUp(Edge& edge) const {
    488       edge.id = edges[edge.id].next_up;
     485      edge.id = bNodes[node.id >> 1].first;
     486    }
     487    void nextIn(Edge& edge) const {
     488      edge.id = edges[edge.id].next_in;
    489489    }
    490490
     
    496496    }
    497497    int maxNodeId() const {
    498       return upperNodes.size() > lowerNodes.size() ?
    499         upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;
     498      return aNodes.size() > bNodes.size() ?
     499        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
    500500    }
    501501 
     
    510510    }
    511511 
    512     static int upperId(const Node& node) {
     512    static int aNodeId(const Node& node) {
    513513      return node.id >> 1;
    514514    }
    515     static Node fromUpperId(int id, Node) {
     515    static Node fromANodeId(int id, Node) {
    516516      return Node(id << 1);
    517517    }
    518     int maxUpperId() const {
    519       return upperNodes.size();
    520     }
    521 
    522     static int lowerId(const Node& node) {
     518    int maxANodeId() const {
     519      return aNodes.size();
     520    }
     521
     522    static int bNodeId(const Node& node) {
    523523      return node.id >> 1;
    524524    }
    525     static Node fromLowerId(int id) {
     525    static Node fromBNodeId(int id) {
    526526      return Node((id << 1) + 1);
    527527    }
    528     int maxLowerId() const {
    529       return lowerNodes.size();
    530     }
    531 
    532     Node upperNode(const Edge& edge) const {
    533       return Node(edges[edge.id].upper);
    534     }
    535     Node lowerNode(const Edge& edge) const {
    536       return Node(edges[edge.id].lower);
    537     }
    538 
    539     static bool upper(const Node& node) {
     528    int maxBNodeId() const {
     529      return bNodes.size();
     530    }
     531
     532    Node aNode(const Edge& edge) const {
     533      return Node(edges[edge.id].aNode);
     534    }
     535    Node bNode(const Edge& edge) const {
     536      return Node(edges[edge.id].bNode);
     537    }
     538
     539    static bool aNode(const Node& node) {
    540540      return (node.id & 1) == 0;
    541541    }
    542542
    543     static bool lower(const Node& node) {
     543    static bool bNode(const Node& node) {
    544544      return (node.id & 1) == 1;
    545545    }
    546546
    547     Node addUpperNode() {
     547    Node addANode() {
    548548      NodeT nodeT;
    549549      nodeT.first = -1;
    550       upperNodes.push_back(nodeT);
    551       return Node(upperNodes.size() * 2 - 2);
    552     }
    553 
    554     Node addLowerNode() {
     550      aNodes.push_back(nodeT);
     551      return Node(aNodes.size() * 2 - 2);
     552    }
     553
     554    Node addBNode() {
    555555      NodeT nodeT;
    556556      nodeT.first = -1;
    557       lowerNodes.push_back(nodeT);
    558       return Node(lowerNodes.size() * 2 - 1);
     557      bNodes.push_back(nodeT);
     558      return Node(bNodes.size() * 2 - 1);
    559559    }
    560560
     
    563563      EdgeT edgeT;
    564564      if ((source.id & 1) == 0) {
    565         edgeT.upper = source.id;
    566         edgeT.lower = target.id;
     565        edgeT.aNode = source.id;
     566        edgeT.bNode = target.id;
    567567      } else {
    568         edgeT.upper = target.id;
    569         edgeT.lower = source.id;
    570       }
    571       edgeT.next_down = upperNodes[edgeT.upper >> 1].first;
    572       upperNodes[edgeT.upper >> 1].first = edges.size();
    573       edgeT.next_up = lowerNodes[edgeT.lower >> 1].first;
    574       lowerNodes[edgeT.lower >> 1].first = edges.size();
     568        edgeT.aNode = target.id;
     569        edgeT.bNode = source.id;
     570      }
     571      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
     572      aNodes[edgeT.aNode >> 1].first = edges.size();
     573      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
     574      bNodes[edgeT.bNode >> 1].first = edges.size();
    575575      edges.push_back(edgeT);
    576576      return Edge(edges.size() - 1);
     
    578578
    579579    void clear() {
    580       upperNodes.clear();
    581       lowerNodes.clear();
     580      aNodes.clear();
     581      bNodes.clear();
    582582      edges.clear();
    583583    }
     
    586586
    587587
    588   typedef ClearableUBipartiteGraphExtender<
    589     ExtendableUBipartiteGraphExtender<
    590     MappableUBipartiteGraphExtender<
    591     IterableUBipartiteGraphExtender<
    592     AlterableUBipartiteGraphExtender<
    593     UBipartiteGraphExtender <
    594     SmartUBipartiteGraphBase> > > > > >
    595   ExtendedSmartUBipartiteGraphBase;
    596 
    597 
    598   class SmartUBipartiteGraph :
    599     public ExtendedSmartUBipartiteGraphBase {
    600   };
     588  typedef ClearableBpUGraphExtender<
     589    ExtendableBpUGraphExtender<
     590    MappableBpUGraphExtender<
     591    IterableBpUGraphExtender<
     592    AlterableBpUGraphExtender<
     593    BpUGraphExtender <
     594    SmartBpUGraphBase> > > > > >
     595  ExtendedSmartBpUGraphBase;
     596
     597  /// \ingroup graphs
     598  ///
     599  /// \brief A smart bipartite undirected graph class.
     600  ///
     601  /// This is a simple and fast bipartite undirected graph implementation.
     602  /// It is also quite memory efficient, but at the price
     603  /// that <b> it does not support node and edge deletions</b>.
     604  /// Except from this it conforms to
     605  /// the \ref concept::BpUGraph "BpUGraph" concept.
     606  /// \sa concept::BpUGraph.
     607  ///
     608  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
    601609
    602610 
Note: See TracChangeset for help on using the changeset viewer.