COIN-OR::LEMON - Graph Library

Changeset 1333:2640cf6547ff in lemon-0.x for src


Ignore:
Timestamp:
04/09/05 21:35:33 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1772
Message:

Functionality changed:
The first map is the id map => The map named "id" is the id map

Documentation improvments

Location:
src/lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/graph_reader.h

    r1311 r1333  
    3535namespace lemon {
    3636
     37  /// \addtogroup io_group
     38  /// @{
    3739
    3840  /// \brief Standard ReaderTraits for the GraphReader class.
     
    4042  /// Standard ReaderTraits for the GraphReader class.
    4143  /// It defines standard reading method for all type of value.
     44  /// \author Balazs Dezso
    4245  struct DefaultReaderTraits {
    4346
    44    /// \brief Template class for reading an value.
     47    /// \brief Template class for reading an value.
    4548    ///
    4649    /// Template class for reading an value.
     50    /// \author Balazs Dezso
    4751    template <typename _Value>
    4852    struct Reader {
     
    5862    };
    5963
     64    /// \brief Returns wheter this name is an ID map name.
     65    ///
     66    /// Returns wheter this name is an ID map name.
     67    static bool idMapName(const std::string& name) {
     68      return name == "id";
     69    }
     70
    6071    /// The reader class for the not needed maps.
    6172    typedef Reader<std::string> DefaultReader;
     
    6778  /// Reader class for quoted strings. It can process the escape
    6879  /// sequences in the string.
     80  /// \author Balazs Dezso
    6981  class QuotedStringReader {
    7082  public:
     
    172184  /// \brief The graph reader class.
    173185  ///
    174   /// \ingroup io_group
    175   /// The reader class for the graph input.
     186  ///
     187  /// The given file format may contain several maps and labeled nodes or
     188  /// edges.
     189  ///
     190  /// If you read a graph you need not read all the maps and items just those
     191  /// that you need. The interface of the \c GraphReader is very similar to
     192  /// the GraphWriter but the reading method does not depend on the order the
     193  /// given commands.
     194  ///
     195  /// The reader object suppose that each not readed value does not contain
     196  /// whitespaces, therefore it has some extra possibilities to control how
     197  /// it should skip the values when the string representation contains spaces.
     198  ///
     199  /// \code
     200  /// GraphReader<ListGraph> reader(std::cin, graph);
     201  /// \endcode
     202  ///
     203  /// The \c addNodeMap() function reads a map from the \c \@nodeset section.
     204  /// If there is a map that you do not want to read from the file and there is
     205  /// whitespace in the string represenation of the values then you should
     206  /// call the \c skipNodeMap() template member function with proper
     207  /// parameters.
     208  ///
     209  /// \code
     210  /// reader.addNodeMap("x-coord", xCoordMap);
     211  /// reader.addNodeMap("y-coord", yCoordMap);
     212  ///
     213  /// reader.addNodeMap<QuotedStringReader>("label", labelMap);
     214  /// reader.skipNodeMap<QuotedStringReader>("description");
     215  ///
     216  /// reader.addNodeMap("color", colorMap);
     217  /// \endcode
     218  ///
     219  /// With the \c addEdgeMap() member function you can give an edge map
     220  /// reading command similar to the NodeMaps.
     221  ///
     222  /// \code
     223  /// reader.addEdgeMap("weight", weightMap);
     224  /// reader.addEdgeMap("label", labelMap);
     225  /// \endcode
     226  ///
     227  /// With \c addNode() and \c addEdge() functions you can read labeled Nodes
     228  /// and Edges.
     229  ///
     230  /// \code
     231  /// reader.addNode("source", sourceNode);
     232  /// reader.addNode("target", targetNode);
     233  ///
     234  /// reader.addEdge("observed", edge);
     235  /// \endcode
     236  ///
     237  /// After you give all read commands you must call the \c run() member
     238  /// function, which execute all the commands.
     239  ///
     240  /// \code
     241  /// reader.run();
     242  /// \endcode
     243  ///
    176244  /// \see DefaultReaderTraits
    177245  /// \see QuotedStringReader
    178246  /// \see \ref GraphWriter
    179247  /// \see \ref graph-io-page
     248  /// \author Balazs Dezso
    180249  template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
    181250  class GraphReader {
     
    201270    /// Destruct the graph reader.
    202271    ~GraphReader() {
    203 
    204272      for (typename NodeMapReaders::iterator it = node_map_readers.begin();
    205273           it != node_map_readers.end(); ++it) {
     
    365433        std::istringstream ls(line);   
    366434        while (ls >> id) {
    367           if (id[0] == '#') break;
    368435          typename NodeMapReaders::iterator it = node_map_readers.find(id);
    369436          if (it != node_map_readers.end()) {
     
    373440            index.push_back(&nodeSkipper);
    374441          }
    375         }
    376       }
    377 
    378       if (index.size() == 0) {
    379         throw DataFormatError("Cannot find node id map");
    380       }
    381 
    382       nodeInverter =
    383         std::auto_ptr<InverterBase<Node> >(index[0]->getInverter());
     442          if (ReaderTraits::idMapName(id) && nodeInverter.get() == 0) {
     443            nodeInverter.reset(index.back()->getInverter());
     444            index.back() = nodeInverter.get();
     445          }
     446        }
     447      }
     448
     449//       if (index.size() == 0) {
     450//      throw DataFormatError("Cannot find node id map");
     451//       }
     452
     453//       nodeInverter =
     454//      std::auto_ptr<InverterBase<Node> >(index[0]->getInverter());
    384455      std::string line;
    385456      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
    386457        Node node = graph.addNode();
    387458        std::istringstream ls(line);
    388         nodeInverter->read(ls, node);
    389         for (int i = 1; i < (int)index.size(); ++i) {
     459        for (int i = 0; i < (int)index.size(); ++i) {
    390460          index[i]->read(ls, node);
    391461        }
     
    403473        std::istringstream ls(line);   
    404474        while (ls >> id) {
    405           if (id[0] == '#') break;
    406475          typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
    407476          if (it != edge_map_readers.end()) {
     
    411480            index.push_back(&edgeSkipper);
    412481          }
    413         }
    414       }
    415 
    416       if (index.size() == 0) {
    417         throw DataFormatError("Cannot find edge id map");
    418       }
    419 
    420       edgeInverter =
    421         std::auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
     482          if (ReaderTraits::idMapName(id) && edgeInverter.get() == 0) {
     483            edgeInverter.reset(index.back()->getInverter());
     484            index.back() = edgeInverter.get();
     485          }
     486        }
     487      }
     488     
     489      if (nodeInverter.get() == 0) {
     490        throw DataFormatError("Cannot find node id map");
     491      }
     492//       if (index.size() == 0) {
     493//      throw DataFormatError("Cannot find edge id map");
     494//       }
     495
     496//       edgeInverter =
     497//      std::auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
    422498      std::string line;
    423499      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {   
     
    426502        Node target = nodeInverter->read(ls);
    427503        Edge edge = graph.addEdge(source, target);
    428         edgeInverter->read(ls, edge);
    429         for (int i = 1; i < (int)index.size(); ++i) {
     504        for (int i = 0; i < (int)index.size(); ++i) {
    430505          index[i]->read(ls, edge);
    431506        }
     
    437512                          std::auto_ptr<InverterBase<Node> >& nodeInverter) {
    438513      std::string line;
     514      if (nodeInverter.get() == 0) {
     515        throw DataFormatError("Cannot find node id map");
     516      }
    439517      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
    440518        std::istringstream ls(line);
     
    452530                          std::auto_ptr<InverterBase<Edge> >& edgeInverter) {
    453531      std::string line;
     532      if (edgeInverter.get() == 0) {
     533        throw DataFormatError("Cannot find edge id map");
     534      }
    454535      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
    455536        std::istringstream ls(line);
     
    467548      std::string line;
    468549      while (++line_num, getline(is, line)) {   
    469         int vi = line.find_first_not_of(" \t");
    470         if (vi != (int)std::string::npos && line[vi] != '#') {
     550        int vi = line.find('#');
     551        if (vi != (int)::std::string::npos) {
     552          line = line.substr(0, vi);
     553        }
     554        vi = line.find_first_not_of(" \t");
     555        if (vi != (int)std::string::npos) {
     556          std::cerr << "Line: " << line.substr(vi) << std::endl;
    471557          return line.substr(vi);
    472558        }
     
    474560      throw DataFormatError("End of stream error");
    475561    }
    476    
    477     // Inverters store and give back the Item from the id,
    478     // and may put the ids into a map.
    479562   
    480563    template <typename _Item>
    481     class InverterBase {
     564    class ReaderBase;
     565   
     566    template <typename _Item>
     567    class InverterBase : public ReaderBase<_Item> {
    482568    public:
    483569      typedef _Item Item;
    484570      virtual void read(std::istream&, const Item&) = 0;
    485571      virtual Item read(std::istream&) = 0;
     572
     573      virtual InverterBase<_Item>* getInverter() {
     574        return this;
     575      }
    486576    };
    487577
     
    652742  };
    653743
    654   /// Ready to use reader function. 
     744  /// \brief Read a graph from the input.
     745  ///
     746  /// Read a graph from the input.
     747  /// \param is The input stream.
     748  /// \param g The graph.
     749  /// \param capacity The capacity map.
     750  /// \param s The source node.
     751  /// \param t The target node.
     752  /// \param cost The cost map.
    655753  template<typename Graph, typename CapacityMap, typename CostMap>
    656754  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
     
    665763  }
    666764
     765  /// \brief Read a graph from the input.
     766  ///
     767  /// Read a graph from the input.
     768  /// \param is The input stream.
     769  /// \param g The graph.
     770  /// \param capacity The capacity map.
     771  /// \param s The source node.
     772  /// \param t The target node.
    667773  template<typename Graph, typename CapacityMap>
    668774  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
     
    675781  }
    676782
     783  /// \brief Read a graph from the input.
     784  ///
     785  /// Read a graph from the input.
     786  /// \param is The input stream.
     787  /// \param g The graph.
     788  /// \param capacity The capacity map.
     789  /// \param s The source node.
    677790  template<typename Graph, typename CapacityMap>
    678791  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
     
    684797  }
    685798
     799  /// \brief Read a graph from the input.
     800  ///
     801  /// Read a graph from the input.
     802  /// \param is The input stream.
     803  /// \param g The graph.
     804  /// \param capacity The capacity map.
    686805  template<typename Graph, typename CapacityMap>
    687806  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity) {
     
    691810  }
    692811
     812  /// \brief Read a graph from the input.
     813  ///
     814  /// Read a graph from the input.
     815  /// \param is The input stream.
     816  /// \param g The graph.
    693817  template<typename Graph>
    694818  void readGraph(std::istream& is, Graph &g) {
     
    697821  }
    698822
     823  /// @}
    699824}
    700825
  • src/lemon/graph_writer.h

    r1311 r1333  
    3838namespace lemon {
    3939
     40  /// \addtogroup io_group
     41  /// @{
     42
    4043  /// \brief Standard WriterTraits for the GraphWriter class.
    4144  ///
    4245  /// Standard WriterTraits for the GraphWriter class.
    4346  /// It defines standard writing method for all type of value.
     47  /// \author Balazs Dezso
    4448  struct DefaultWriterTraits {
    4549
     
    4751    ///
    4852    /// Template class for writing an value.
     53    /// \author Balazs Dezso
    4954    template <typename _Value>
    5055    struct Writer {
     
    6065    };
    6166
     67    /// \brief Returns wheter this name is an ID map name.
     68    ///
     69    /// Returns wheter this name is an ID map name.
     70    static bool idMapName(const std::string& name) {
     71      return name == "id";
     72    }
     73
    6274  };
    6375
     
    6779  /// Writer class for quoted strings. It can process the escape
    6880  /// sequences in the string.
     81  /// \author Balazs Dezso
    6982  class QuotedStringWriter {
    7083  public:
     
    147160  /// \brief The graph writer class.
    148161  ///
    149   ///\ingroup io_group
    150   /// The writer class for the graph output.
     162  /// The \c GraphWriter class provides the graph output. To write a graph
     163  /// you should first give writing commands for the writer. You can declare
     164  /// write command as \c NodeMap or \c EdgeMap writing and labeled Node and
     165  /// Edge writing.
     166  ///
     167  /// \code
     168  /// GraphWriter<ListGraph> writer(std::cout, graph);
     169  /// \endcode
     170  ///
     171  /// The \c addNodeMap() function declares a \c NodeMap writing command in the
     172  /// \c GraphWriter. You should give as parameter the name of the map and the
     173  /// map object. The NodeMap writing command with name "id" should write a
     174  /// unique map because it is regarded as ID map.
     175  ///
     176  /// \code
     177  /// IdMap<ListGraph, Node> nodeIdMap;
     178  /// writer.addNodeMap("id", nodeIdMap);
     179  ///
     180  /// writer.addNodeMap("x-coord", xCoordMap);
     181  /// writer.addNodeMap("y-coord", yCoordMap);
     182  /// writer.addNodeMap("color", colorMap);
     183  /// \endcode
     184  ///
     185  /// With the \c addEdgeMap() member function you can give an edge map
     186  /// writing command similar to the NodeMaps.
     187  ///
     188  /// \code
     189  /// DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> >
     190  ///   edgeDescMap(graph);
     191  /// writer.addEdgeMap("descriptor", edgeDescMap);
     192  ///
     193  /// writer.addEdgeMap("weight", weightMap);
     194  /// writer.addEdgeMap("label", labelMap);
     195  /// \endcode
     196  ///
     197  /// With \c addNode() and \c addEdge() functions you can point out Nodes and
     198  /// Edges in the graph. By example, you can write out the source and target
     199  /// of the graph.
     200  ///
     201  /// \code
     202  /// writer.addNode("source", sourceNode);
     203  /// writer.addNode("target", targetNode);
     204  ///
     205  /// writer.addEdge("observed", edge);
     206  /// \endcode
     207  ///
     208  /// After you give all write commands you must call the \c run() member
     209  /// function, which execute all the writer commands.
     210  ///
     211  /// \code
     212  /// writer.run();
     213  /// \endcode
     214  ///
    151215  /// \see DefaultWriterTraits
    152216  /// \see QuotedStringWriter
     217  /// \see IdMap
     218  /// \see DescriptorMap
    153219  /// \see \ref GraphReader
    154220  /// \see \ref graph-io-page
     221  /// \author Balazs Dezso
    155222  template <typename _Graph, typename _WriterTraits = DefaultWriterTraits>
    156223  class GraphWriter {
     
    255322    /// Executes the writer commands.
    256323    void run() {   
    257       writeNodeSet();
    258       writeEdgeSet();
    259       writeNodes();
    260       writeEdges();
     324      WriterBase<Node>* nodeWriter = 0;
     325      WriterBase<Edge>* edgeWriter = 0;
     326      writeNodeSet(nodeWriter);
     327      writeEdgeSet(nodeWriter, edgeWriter);
     328      writeNodes(nodeWriter);
     329      writeEdges(edgeWriter);
    261330      os << "@end" << std::endl;
    262331    }
    263332
    264333  private:
    265 
    266     void writeNodeSet() {
    267       if (node_map_writers.size() == 0) return;
    268       os << "@nodeset" << std::endl;
    269       for (int i = 0; i < (int)node_map_writers.size(); ++i) {
    270         os << node_map_writers[i].first << '\t';
    271       }
    272       os << std::endl;
    273       for (NodeIt it(graph); it != INVALID; ++it) {
    274         for (int i = 0; i < (int)node_map_writers.size(); ++i) {
    275           node_map_writers[i].second->write(os, it);
    276         }
    277         os << std::endl;
    278       }
    279 
    280     }
    281 
    282     void writeEdgeSet() {
    283       if (edge_map_writers.size() == 0) return;
    284       if (node_map_writers.size() == 0) {
    285         //      ErrorMessage message;
    286         //      message << "Missing node id map";
    287         //      throw IOLogicError(message);
    288       }
    289       os << "@edgeset" << std::endl;
    290       os << "\t\t";
    291       for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
    292         os << edge_map_writers[i].first << '\t';
    293       }
    294       os << std::endl;
    295       for (EdgeIt it(graph); it != INVALID; ++it) {
    296         node_map_writers[0].second->write(os, graph.source(it));
    297         node_map_writers[0].second->write(os, graph.target(it));
    298         for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
    299           edge_map_writers[i].second->write(os, it);
    300         }
    301         os << std::endl;
    302       }
    303     }
    304 
    305     void writeNodes() {
    306       if (node_writers.size() == 0) return;
    307       if (node_map_writers.size() == 0) {
    308         //      throw Exception() << "Missing node id map";
    309       }
    310       os << "@nodes" << std::endl;
    311       for (int i = 0; i < (int)node_writers.size(); ++i) {
    312         os << node_writers[i].first << '\t';
    313         node_map_writers[0].second->write(os, node_writers[i].second);
    314         os << std::endl;
    315       }
    316     }
    317 
    318     void writeEdges() {
    319       if (edge_writers.size() == 0) return;
    320       if (edge_map_writers.size() == 0) {
    321         //      throw Exception() << "Missing edge id map";
    322       }
    323       os << "@edges" << std::endl;
    324       for (int i = 0; i < (int)edge_writers.size(); ++i) {
    325         os << edge_writers[i].first << '\t';
    326         edge_map_writers[0].second->write(os, edge_writers[i].second);
    327         os << std::endl;
    328       }
    329     }
    330    
    331     // Writers
    332334
    333335    template <class _Item>
     
    359361    };
    360362
     363    void writeNodeSet(WriterBase<Node>* & nodeWriter) {
     364      if (node_map_writers.size() == 0) return;
     365      os << "@nodeset" << std::endl;
     366      for (int i = 0; i < (int)node_map_writers.size(); ++i) {
     367        const std::string& id = node_map_writers[i].first;
     368        os << id << '\t';
     369        if (WriterTraits::idMapName(id) && nodeWriter == 0) {
     370          nodeWriter = node_map_writers[i].second;
     371        }
     372      }
     373      os << std::endl;
     374      for (NodeIt it(graph); it != INVALID; ++it) {
     375        for (int i = 0; i < (int)node_map_writers.size(); ++i) {
     376          node_map_writers[i].second->write(os, it);
     377        }
     378        os << std::endl;
     379      }
     380
     381    }
     382
     383    void writeEdgeSet(WriterBase<Node>* nodeWriter,
     384                      WriterBase<Edge>* & edgeWriter) {
     385      if (nodeWriter == 0) {
     386        throw DataFormatError("Cannot find node id map");
     387      }
     388      os << "@edgeset" << std::endl;
     389      os << "\t\t";
     390      for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
     391        const std::string& id = edge_map_writers[i].first;
     392        os << id << '\t';
     393        if (WriterTraits::idMapName(id) && edgeWriter == 0) {
     394          edgeWriter = edge_map_writers[i].second;
     395        }
     396      }
     397      os << std::endl;
     398      for (EdgeIt it(graph); it != INVALID; ++it) {
     399        nodeWriter->write(os, graph.source(it));
     400        nodeWriter->write(os, graph.target(it));
     401        for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
     402          edge_map_writers[i].second->write(os, it);
     403        }
     404        os << std::endl;
     405      }
     406    }
     407
     408    void writeNodes(WriterBase<Node>* nodeWriter) {
     409      if (nodeWriter == 0) {
     410        throw DataFormatError("Cannot find node id map");
     411      }
     412      os << "@nodes" << std::endl;
     413      for (int i = 0; i < (int)node_writers.size(); ++i) {
     414        os << node_writers[i].first << '\t';
     415        nodeWriter->write(os, node_writers[i].second);
     416        os << std::endl;
     417      }
     418    }
     419
     420    void writeEdges(WriterBase<Edge>* edgeWriter) {
     421      if (edgeWriter == 0) {
     422        throw DataFormatError("Cannot find node id map");
     423      }
     424      os << "@edges" << std::endl;
     425      for (int i = 0; i < (int)edge_writers.size(); ++i) {
     426        os << edge_writers[i].first << '\t';
     427        edgeWriter->write(os, edge_writers[i].second);
     428        os << std::endl;
     429      }
     430    }
     431   
     432
    361433
    362434
     
    380452  };
    381453
    382   /// Ready to use writer function. 
     454  /// \brief Write a graph to the output.
     455  ///
     456  /// Write a graph to the output.
     457  /// \param os The output stream.
     458  /// \param g The graph.
     459  /// \param capacity The capacity map.
     460  /// \param s The source node.
     461  /// \param t The target node.
     462  /// \param cost The cost map.
    383463  template<typename Graph, typename CapacityMap, typename CostMap>
    384464  void writeGraph(std::ostream& os, const Graph &g,
     
    397477  }
    398478
    399   /// Ready to use writer function. 
     479  /// \brief Write a graph to the output.
     480  ///
     481  /// Write a graph to the output.
     482  /// \param os The output stream.
     483  /// \param g The graph.
     484  /// \param capacity The capacity map.
     485  /// \param s The source node.
     486  /// \param t The target node.
    400487  template<typename Graph, typename CapacityMap>
    401488  void writeGraph(std::ostream& os, const Graph &g,
     
    413500  }
    414501
    415   /// Ready to use writer function. 
     502  /// \brief Write a graph to the output.
     503  ///
     504  /// Write a graph to the output.
     505  /// \param os The output stream.
     506  /// \param g The graph.
     507  /// \param capacity The capacity map.
     508  /// \param s The source node.
    416509  template<typename Graph, typename CapacityMap>
    417510  void writeGraph(std::ostream& os, const Graph &g,
     
    426519    reader.run();
    427520  }
    428   /// Ready to use writer function. 
     521
     522  /// \brief Write a graph to the output.
     523  ///
     524  /// Write a graph to the output.
     525  /// \param os The output stream.
     526  /// \param g The graph.
     527  /// \param capacity The capacity map.
    429528  template<typename Graph, typename CapacityMap>
    430529  void writeGraph(std::ostream& os, const Graph &g,
     
    438537    reader.run();
    439538  }
    440   /// Ready to use writer function. 
     539
     540  /// \brief Write a graph to the output.
     541  ///
     542  /// Write a graph to the output.
     543  /// \param os The output stream.
     544  /// \param g The graph.
    441545  template<typename Graph>
    442546  void writeGraph(std::ostream& os, const Graph &g) {
     
    449553  }
    450554
     555  /// @}
    451556
    452557}
Note: See TracChangeset for help on using the changeset viewer.