COIN-OR::LEMON - Graph Library

Changeset 2101:439b7f21ccc4 in lemon-0.x


Ignore:
Timestamp:
06/19/06 15:44:06 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2787
Message:

Improvement:

The item sets are written in the order sorted by the labels.

It solves the problem if we read a graph from a file and
then write it back then the nodes will be reversed.
It can be switched off with the LemonWriter? interface.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/lemon_writer.h

    r2084 r2101  
    4848  namespace _writer_bits {
    4949   
     50    template <typename T>
     51    bool operator<(T, T) {
     52      throw DataFormatError("Label is not comparable");
     53    }
     54
     55    template <typename T>
     56    struct Less {
     57      bool operator()(const T& p, const T& q) const {
     58        return p < q;
     59      }
     60    };
     61
     62    template <typename Map>
     63    struct ComposeLess {
     64      ComposeLess(const Map& _map) : map(_map), less() {}
     65
     66      bool operator()(const typename Map::Key& p,
     67                      const typename Map::Key& q) const {
     68        return less(map[p], map[q]);
     69      }
     70      const Map& map;
     71      Less<typename Map::Value> less;
     72    };
     73
    5074    template <typename Item>
    5175    class ItemLabelWriter {
     
    176200
    177201      virtual void write(std::ostream& os, const Item& item) const = 0;
     202      virtual void sortByMap(std::vector<Item>&) const = 0;
    178203    };
    179204
     
    198223        Value value = map[item];
    199224        writer.write(os, value);
     225      }
     226
     227      virtual void sortByMap(std::vector<Item>& items) const {
     228        ComposeLess<Map> less(map);
     229        std::sort(items.begin(), items.end(), less);
    200230      }
    201231
     
    395425  /// \c writeLabel() member will be called with a node it will write it's
    396426  /// label. Otherwise if the \c _forceLabelMap constructor parameter is true
    397   /// then the label map will be the id in the graph.
     427  /// then the label map will be the id in the graph. In addition if the
     428  /// the \c _sortByLabel is true then the writer will write the edges
     429  /// sorted by the labels.
    398430  ///
    399431  /// \relates LemonWriter
     
    412444    /// attach it into the given LemonWriter. If the \c _forceLabelMap
    413445    /// parameter is true then the writer will write own label map when
    414     /// the user does not give "label" named map.
     446    /// the user does not give "label" named map. In addition if the
     447    /// the \c _sortByLabel is true then the writer will write the edges
     448    /// sorted by the labels.
    415449    NodeSetWriter(LemonWriter& _writer, const Graph& _graph,
    416450                  const std::string& _name = std::string(),
    417                   bool _forceLabelMap = true)
     451                  bool _forceLabelMap = true, bool _sortByLabel = true)
    418452      : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap),
    419         graph(_graph), name(_name) {}
     453        sortByLabel(_sortByLabel), graph(_graph), name(_name) {}
    420454
    421455    /// \brief Destructor.
     
    478512        }
    479513      }
     514      std::vector<Node> items;
     515      for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
     516        items.push_back(it);
     517      }
     518      if (sortByLabel) {
     519        if (labelMap) {
     520          labelMap->sortByMap(items);
     521        } else {
     522          typedef IdMap<Graph, Node> Map;
     523          Map map(graph);
     524          _writer_bits::ComposeLess<Map> less(map);
     525          std::sort(items.begin(), items.end(), less);
     526        }
     527      }
    480528      if (forceLabelMap) {
    481529        os << "label\t";
     
    485533      }
    486534      os << std::endl;
    487       for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
     535      for (typename std::vector<Node>::iterator it = items.begin();
     536           it != items.end(); ++it) {
    488537        if (forceLabelMap) {
    489           os << graph.id(it) << '\t';
     538          os << graph.id(*it) << '\t';
    490539        }
    491540        for (int i = 0; i < (int)writers.size(); ++i) {
    492           writers[i].second->write(os, it);
     541          writers[i].second->write(os, *it);
    493542          os << '\t';
    494543        }
     
    530579    _writer_bits::MapWriterBase<Node>* labelMap;
    531580    bool forceLabelMap;
     581    bool sortByLabel;
    532582   
    533583    const Graph& graph;   
     
    552602  /// \c writeLabel() member will be called with an edge it will write it's
    553603  /// label. Otherwise if the \c _forceLabelMap constructor parameter is true
    554   /// then the label map will be the id in the graph.
     604  /// then the label map will be the id in the graph. In addition if the
     605  /// the \c _sortByLabel is true then the writer will write the edges
     606  /// sorted by the labels.
    555607  ///
    556608  /// The edgeset writer needs a node label writer to identify which nodes
     
    571623    /// \brief Constructor.
    572624    ///
    573     /// Constructor for EdgeSetWriter. It creates the EdgeSetWriter and
    574     /// attach it into the given LemonWriter. It will write node labels by
    575     /// the \c _nodeLabelWriter. If the \c _forceLabelMap parameter is true
    576     /// then the writer will write own label map if the user does not give
    577     /// "label" named map.
     625    /// Constructor for EdgeSetWriter. It creates the EdgeSetWriter
     626    /// and attach it into the given LemonWriter. It will write node
     627    /// labels by the \c _nodeLabelWriter. If the \c _forceLabelMap
     628    /// parameter is true then the writer will write own label map if
     629    /// the user does not give "label" named map. In addition if the
     630    /// the \c _sortByLabel is true then the writer will write the
     631    /// edges sorted by the labels.
    578632    template <typename NodeLabelWriter>
    579633    EdgeSetWriter(LemonWriter& _writer, const Graph& _graph,
    580634                  const NodeLabelWriter& _nodeLabelWriter,
    581635                  const std::string& _name = std::string(),
    582                   bool _forceLabelMap = true)
     636                  bool _forceLabelMap = true, bool _sortByLabel = true)
    583637      : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap),
    584         graph(_graph), name(_name) {
     638        sortByLabel(_sortByLabel), graph(_graph), name(_name) {
    585639      checkConcept<_writer_bits::ItemLabelWriter<Node>, NodeLabelWriter>();
    586640      nodeLabelWriter.reset(new _writer_bits::
     
    650704        }
    651705      }
     706      std::vector<Edge> items;
     707      for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
     708        items.push_back(it);
     709      }
     710      if (sortByLabel) {
     711        if (labelMap) {
     712          labelMap->sortByMap(items);
     713        } else {
     714          typedef IdMap<Graph, Edge> Map;
     715          Map map(graph);
     716          _writer_bits::ComposeLess<Map> less(map);
     717          std::sort(items.begin(), items.end(), less);
     718        }
     719      }
    652720      os << "\t\t";
    653721      if (forceLabelMap) {
     
    658726      }
    659727      os << std::endl;
    660       for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
    661         nodeLabelWriter->write(os, graph.source(it));
     728      for (typename std::vector<Edge>::iterator it = items.begin();
     729           it != items.end(); ++it) {
     730        nodeLabelWriter->write(os, graph.source(*it));
    662731        os << '\t';
    663         nodeLabelWriter->write(os, graph.target(it));
     732        nodeLabelWriter->write(os, graph.target(*it));
    664733        os << '\t';
    665734        if (forceLabelMap) {
    666           os << graph.id(it) << '\t';
     735          os << graph.id(*it) << '\t';
    667736        }
    668737        for (int i = 0; i < (int)writers.size(); ++i) {
    669           writers[i].second->write(os, it);
     738          writers[i].second->write(os, *it);
    670739          os << '\t';
    671740        }
     
    707776    _writer_bits::MapWriterBase<Edge>* labelMap;
    708777    bool forceLabelMap;
     778    bool sortByLabel;
    709779   
    710780    const Graph& graph;   
     
    732802  /// difference.
    733803  ///
    734   /// If the edgeset contains an \c "label" named map then it will be regarded
    735   /// as label map. This map should contain only unique values and when the
    736   /// \c writeLabel() member will be called with an undirected edge it will
    737   /// write it's label. Otherwise if the \c _forceLabelMap constructor
    738   /// parameter is true then the label map will be the id in the graph.
     804  /// If the edgeset contains an \c "label" named map then it will be
     805  /// regarded as label map. This map should contain only unique
     806  /// values and when the \c writeLabel() member will be called with
     807  /// an undirected edge it will write it's label. Otherwise if the \c
     808  /// _forceLabelMap constructor parameter is true then the label map
     809  /// will be the id in the graph.  In addition if the the \c
     810  /// _sortByLabel is true then the writer will write the edges sorted
     811  /// by the labels.
    739812  ///
    740813  /// The undirected edgeset writer needs a node label writer to identify
     
    757830    ///
    758831    /// Constructor for UEdgeSetWriter. It creates the UEdgeSetWriter
    759     /// and attach it into the given LemonWriter. It will write node labels by
    760     /// the \c _nodeLabelWriter. If the \c _forceLabelMap parameter is true
    761     /// then the writer will write own label map if the user does not give
    762     /// "label" named map.
     832    /// and attach it into the given LemonWriter. It will write node
     833    /// labels by the \c _nodeLabelWriter. If the \c _forceLabelMap
     834    /// parameter is true then the writer will write own label map if
     835    /// the user does not give "label" named map. In addition if the
     836    /// the \c _sortByLabel is true then the writer will write the
     837    /// edges sorted by the labels.
    763838    template <typename NodeLabelWriter>
    764839    UEdgeSetWriter(LemonWriter& _writer, const Graph& _graph,
    765840                       const NodeLabelWriter& _nodeLabelWriter,
    766841                       const std::string& _name = std::string(),
    767                        bool _forceLabelMap = true)
     842                       bool _forceLabelMap = true, bool _sortByLabel = true)
    768843      : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap),
    769         graph(_graph), name(_name) {
     844        sortByLabel(_sortByLabel), graph(_graph), name(_name) {
    770845      checkConcept<_writer_bits::ItemLabelWriter<Node>, NodeLabelWriter>();
    771846      nodeLabelWriter.reset(new _writer_bits::
     
    859934        }
    860935      }
     936      std::vector<UEdge> items;
     937      for (typename Graph::UEdgeIt it(graph); it != INVALID; ++it) {
     938        items.push_back(it);
     939      }
     940      if (sortByLabel) {
     941        if (labelMap) {
     942          labelMap->sortByMap(items);
     943        } else {
     944          typedef IdMap<Graph, UEdge> Map;
     945          Map map(graph);
     946          _writer_bits::ComposeLess<Map> less(map);
     947          std::sort(items.begin(), items.end(), less);
     948        }
     949      }
    861950      os << "\t\t";
    862951      if (forceLabelMap) {
     
    867956      }
    868957      os << std::endl;
    869       for (typename Graph::UEdgeIt it(graph); it != INVALID; ++it) {
    870         nodeLabelWriter->write(os, graph.source(it));
     958      for (typename std::vector<Edge>::iterator it = items.begin();
     959           it != items.end(); ++it) {
     960        nodeLabelWriter->write(os, graph.source(*it));
    871961        os << '\t';
    872         nodeLabelWriter->write(os, graph.target(it));
     962        nodeLabelWriter->write(os, graph.target(*it));
    873963        os << '\t';
    874964        if (forceLabelMap) {
    875           os << graph.id(it) << '\t';
     965          os << graph.id(*it) << '\t';
    876966        }
    877967        for (int i = 0; i < (int)writers.size(); ++i) {
    878           writers[i].second->write(os, it);
     968          writers[i].second->write(os, *it);
    879969          os << '\t';
    880970        }
     
    9371027    _writer_bits::MapWriterBase<UEdge>* labelMap;
    9381028    bool forceLabelMap;
     1029    bool sortByLabel;
    9391030   
    9401031    const Graph& graph;   
Note: See TracChangeset for help on using the changeset viewer.