COIN-OR::LEMON - Graph Library

Changeset 1192:b84e68af8248 in lemon for lemon/lgf_reader.h


Ignore:
Timestamp:
11/25/10 22:45:29 (9 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

LGF reader and writer for bipartite graphs (#69)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/lgf_reader.h

    r1110 r1192  
    21292129  }
    21302130
     2131  template <typename BGR>
     2132  class BpGraphReader;
     2133
     2134  template <typename TBGR>
     2135  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is = std::cin);
     2136  template <typename TBGR>
     2137  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn);
     2138  template <typename TBGR>
     2139  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
     2140
     2141  /// \ingroup lemon_io
     2142  ///
     2143  /// \brief \ref lgf-format "LGF" reader for bipartite graphs
     2144  ///
     2145  /// This utility reads an \ref lgf-format "LGF" file.
     2146  ///
     2147  /// It can be used almost the same way as \c GraphReader, but it
     2148  /// reads the red and blue nodes from separate sections, and these
     2149  /// sections can contain different set of maps.
     2150  ///
     2151  /// The red and blue maps are read from the corresponding
     2152  /// sections. If a map is defined with the same name in both of
     2153  /// these sections, then it can be read as a node map.
     2154  template <typename BGR>
     2155  class BpGraphReader {
     2156  public:
     2157
     2158    typedef BGR Graph;
     2159
     2160  private:
     2161
     2162    TEMPLATE_BPGRAPH_TYPEDEFS(BGR);
     2163
     2164    std::istream* _is;
     2165    bool local_is;
     2166    std::string _filename;
     2167
     2168    BGR& _graph;
     2169
     2170    std::string _nodes_caption;
     2171    std::string _edges_caption;
     2172    std::string _attributes_caption;
     2173
     2174    typedef std::map<std::string, Node> NodeIndex;
     2175    NodeIndex _node_index;
     2176    typedef std::map<std::string, Edge> EdgeIndex;
     2177    EdgeIndex _edge_index;
     2178
     2179    typedef std::vector<std::pair<std::string,
     2180      _reader_bits::MapStorageBase<Node>*> > NodeMaps;
     2181    NodeMaps _red_maps;
     2182    NodeMaps _blue_maps;
     2183
     2184    typedef std::vector<std::pair<std::string,
     2185      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
     2186    EdgeMaps _edge_maps;
     2187
     2188    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
     2189      Attributes;
     2190    Attributes _attributes;
     2191
     2192    bool _use_nodes;
     2193    bool _use_edges;
     2194
     2195    bool _skip_nodes;
     2196    bool _skip_edges;
     2197
     2198    int line_num;
     2199    std::istringstream line;
     2200
     2201  public:
     2202
     2203    /// \brief Constructor
     2204    ///
     2205    /// Construct an undirected graph reader, which reads from the given
     2206    /// input stream.
     2207    BpGraphReader(BGR& graph, std::istream& is = std::cin)
     2208      : _is(&is), local_is(false), _graph(graph),
     2209        _use_nodes(false), _use_edges(false),
     2210        _skip_nodes(false), _skip_edges(false) {}
     2211
     2212    /// \brief Constructor
     2213    ///
     2214    /// Construct an undirected graph reader, which reads from the given
     2215    /// file.
     2216    BpGraphReader(BGR& graph, const std::string& fn)
     2217      : _is(new std::ifstream(fn.c_str())), local_is(true),
     2218        _filename(fn), _graph(graph),
     2219        _use_nodes(false), _use_edges(false),
     2220        _skip_nodes(false), _skip_edges(false) {
     2221      if (!(*_is)) {
     2222        delete _is;
     2223        throw IoError("Cannot open file", fn);
     2224      }
     2225    }
     2226
     2227    /// \brief Constructor
     2228    ///
     2229    /// Construct an undirected graph reader, which reads from the given
     2230    /// file.
     2231    BpGraphReader(BGR& graph, const char* fn)
     2232      : _is(new std::ifstream(fn)), local_is(true),
     2233        _filename(fn), _graph(graph),
     2234        _use_nodes(false), _use_edges(false),
     2235        _skip_nodes(false), _skip_edges(false) {
     2236      if (!(*_is)) {
     2237        delete _is;
     2238        throw IoError("Cannot open file", fn);
     2239      }
     2240    }
     2241
     2242    /// \brief Destructor
     2243    ~BpGraphReader() {
     2244      for (typename NodeMaps::iterator it = _red_maps.begin();
     2245           it != _red_maps.end(); ++it) {
     2246        delete it->second;
     2247      }
     2248
     2249      for (typename NodeMaps::iterator it = _blue_maps.begin();
     2250           it != _blue_maps.end(); ++it) {
     2251        delete it->second;
     2252      }
     2253
     2254      for (typename EdgeMaps::iterator it = _edge_maps.begin();
     2255           it != _edge_maps.end(); ++it) {
     2256        delete it->second;
     2257      }
     2258
     2259      for (typename Attributes::iterator it = _attributes.begin();
     2260           it != _attributes.end(); ++it) {
     2261        delete it->second;
     2262      }
     2263
     2264      if (local_is) {
     2265        delete _is;
     2266      }
     2267
     2268    }
     2269
     2270  private:
     2271    template <typename TBGR>
     2272    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is);
     2273    template <typename TBGR>
     2274    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph,
     2275                                             const std::string& fn);
     2276    template <typename TBGR>
     2277    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
     2278
     2279    BpGraphReader(BpGraphReader& other)
     2280      : _is(other._is), local_is(other.local_is), _graph(other._graph),
     2281        _use_nodes(other._use_nodes), _use_edges(other._use_edges),
     2282        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
     2283
     2284      other._is = 0;
     2285      other.local_is = false;
     2286
     2287      _node_index.swap(other._node_index);
     2288      _edge_index.swap(other._edge_index);
     2289
     2290      _red_maps.swap(other._red_maps);
     2291      _blue_maps.swap(other._blue_maps);
     2292      _edge_maps.swap(other._edge_maps);
     2293      _attributes.swap(other._attributes);
     2294
     2295      _nodes_caption = other._nodes_caption;
     2296      _edges_caption = other._edges_caption;
     2297      _attributes_caption = other._attributes_caption;
     2298
     2299    }
     2300
     2301    BpGraphReader& operator=(const BpGraphReader&);
     2302
     2303  public:
     2304
     2305    /// \name Reading Rules
     2306    /// @{
     2307
     2308    /// \brief Node map reading rule
     2309    ///
     2310    /// Add a node map reading rule to the reader.
     2311    template <typename Map>
     2312    BpGraphReader& nodeMap(const std::string& caption, Map& map) {
     2313      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
     2314      _reader_bits::MapStorageBase<Node>* red_storage =
     2315        new _reader_bits::MapStorage<Node, Map>(map);
     2316      _red_maps.push_back(std::make_pair(caption, red_storage));
     2317      _reader_bits::MapStorageBase<Node>* blue_storage =
     2318        new _reader_bits::MapStorage<Node, Map>(map);
     2319      _blue_maps.push_back(std::make_pair(caption, blue_storage));
     2320      return *this;
     2321    }
     2322
     2323    /// \brief Node map reading rule
     2324    ///
     2325    /// Add a node map reading rule with specialized converter to the
     2326    /// reader.
     2327    template <typename Map, typename Converter>
     2328    BpGraphReader& nodeMap(const std::string& caption, Map& map,
     2329                           const Converter& converter = Converter()) {
     2330      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
     2331      _reader_bits::MapStorageBase<Node>* red_storage =
     2332        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
     2333      _red_maps.push_back(std::make_pair(caption, red_storage));
     2334      _reader_bits::MapStorageBase<Node>* blue_storage =
     2335        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
     2336      _blue_maps.push_back(std::make_pair(caption, blue_storage));
     2337      return *this;
     2338    }
     2339
     2340    /// Add a red map reading rule to the reader.
     2341    template <typename Map>
     2342    BpGraphReader& redMap(const std::string& caption, Map& map) {
     2343      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
     2344      _reader_bits::MapStorageBase<Node>* storage =
     2345        new _reader_bits::MapStorage<Node, Map>(map);
     2346      _red_maps.push_back(std::make_pair(caption, storage));
     2347      return *this;
     2348    }
     2349
     2350    /// \brief Red map reading rule
     2351    ///
     2352    /// Add a red map reading rule with specialized converter to the
     2353    /// reader.
     2354    template <typename Map, typename Converter>
     2355    BpGraphReader& redMap(const std::string& caption, Map& map,
     2356                          const Converter& converter = Converter()) {
     2357      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
     2358      _reader_bits::MapStorageBase<Node>* storage =
     2359        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
     2360      _red_maps.push_back(std::make_pair(caption, storage));
     2361      return *this;
     2362    }
     2363
     2364    /// Add a blue map reading rule to the reader.
     2365    template <typename Map>
     2366    BpGraphReader& blueMap(const std::string& caption, Map& map) {
     2367      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
     2368      _reader_bits::MapStorageBase<Node>* storage =
     2369        new _reader_bits::MapStorage<Node, Map>(map);
     2370      _blue_maps.push_back(std::make_pair(caption, storage));
     2371      return *this;
     2372    }
     2373
     2374    /// \brief Blue map reading rule
     2375    ///
     2376    /// Add a blue map reading rule with specialized converter to the
     2377    /// reader.
     2378    template <typename Map, typename Converter>
     2379    BpGraphReader& blueMap(const std::string& caption, Map& map,
     2380                           const Converter& converter = Converter()) {
     2381      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
     2382      _reader_bits::MapStorageBase<Node>* storage =
     2383        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
     2384      _blue_maps.push_back(std::make_pair(caption, storage));
     2385      return *this;
     2386    }
     2387
     2388    /// \brief Edge map reading rule
     2389    ///
     2390    /// Add an edge map reading rule to the reader.
     2391    template <typename Map>
     2392    BpGraphReader& edgeMap(const std::string& caption, Map& map) {
     2393      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
     2394      _reader_bits::MapStorageBase<Edge>* storage =
     2395        new _reader_bits::MapStorage<Edge, Map>(map);
     2396      _edge_maps.push_back(std::make_pair(caption, storage));
     2397      return *this;
     2398    }
     2399
     2400    /// \brief Edge map reading rule
     2401    ///
     2402    /// Add an edge map reading rule with specialized converter to the
     2403    /// reader.
     2404    template <typename Map, typename Converter>
     2405    BpGraphReader& edgeMap(const std::string& caption, Map& map,
     2406                          const Converter& converter = Converter()) {
     2407      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
     2408      _reader_bits::MapStorageBase<Edge>* storage =
     2409        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
     2410      _edge_maps.push_back(std::make_pair(caption, storage));
     2411      return *this;
     2412    }
     2413
     2414    /// \brief Arc map reading rule
     2415    ///
     2416    /// Add an arc map reading rule to the reader.
     2417    template <typename Map>
     2418    BpGraphReader& arcMap(const std::string& caption, Map& map) {
     2419      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
     2420      _reader_bits::MapStorageBase<Edge>* forward_storage =
     2421        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
     2422      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
     2423      _reader_bits::MapStorageBase<Edge>* backward_storage =
     2424        new _reader_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map);
     2425      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
     2426      return *this;
     2427    }
     2428
     2429    /// \brief Arc map reading rule
     2430    ///
     2431    /// Add an arc map reading rule with specialized converter to the
     2432    /// reader.
     2433    template <typename Map, typename Converter>
     2434    BpGraphReader& arcMap(const std::string& caption, Map& map,
     2435                          const Converter& converter = Converter()) {
     2436      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
     2437      _reader_bits::MapStorageBase<Edge>* forward_storage =
     2438        new _reader_bits::GraphArcMapStorage<BGR, true, Map, Converter>
     2439        (_graph, map, converter);
     2440      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
     2441      _reader_bits::MapStorageBase<Edge>* backward_storage =
     2442        new _reader_bits::GraphArcMapStorage<BGR, false, Map, Converter>
     2443        (_graph, map, converter);
     2444      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
     2445      return *this;
     2446    }
     2447
     2448    /// \brief Attribute reading rule
     2449    ///
     2450    /// Add an attribute reading rule to the reader.
     2451    template <typename Value>
     2452    BpGraphReader& attribute(const std::string& caption, Value& value) {
     2453      _reader_bits::ValueStorageBase* storage =
     2454        new _reader_bits::ValueStorage<Value>(value);
     2455      _attributes.insert(std::make_pair(caption, storage));
     2456      return *this;
     2457    }
     2458
     2459    /// \brief Attribute reading rule
     2460    ///
     2461    /// Add an attribute reading rule with specialized converter to the
     2462    /// reader.
     2463    template <typename Value, typename Converter>
     2464    BpGraphReader& attribute(const std::string& caption, Value& value,
     2465                             const Converter& converter = Converter()) {
     2466      _reader_bits::ValueStorageBase* storage =
     2467        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
     2468      _attributes.insert(std::make_pair(caption, storage));
     2469      return *this;
     2470    }
     2471
     2472    /// \brief Node reading rule
     2473    ///
     2474    /// Add a node reading rule to reader.
     2475    BpGraphReader& node(const std::string& caption, Node& node) {
     2476      typedef _reader_bits::MapLookUpConverter<Node> Converter;
     2477      Converter converter(_node_index);
     2478      _reader_bits::ValueStorageBase* storage =
     2479        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
     2480      _attributes.insert(std::make_pair(caption, storage));
     2481      return *this;
     2482    }
     2483
     2484    /// \brief Edge reading rule
     2485    ///
     2486    /// Add an edge reading rule to reader.
     2487    BpGraphReader& edge(const std::string& caption, Edge& edge) {
     2488      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
     2489      Converter converter(_edge_index);
     2490      _reader_bits::ValueStorageBase* storage =
     2491        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
     2492      _attributes.insert(std::make_pair(caption, storage));
     2493      return *this;
     2494    }
     2495
     2496    /// \brief Arc reading rule
     2497    ///
     2498    /// Add an arc reading rule to reader.
     2499    BpGraphReader& arc(const std::string& caption, Arc& arc) {
     2500      typedef _reader_bits::GraphArcLookUpConverter<BGR> Converter;
     2501      Converter converter(_graph, _edge_index);
     2502      _reader_bits::ValueStorageBase* storage =
     2503        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
     2504      _attributes.insert(std::make_pair(caption, storage));
     2505      return *this;
     2506    }
     2507
     2508    /// @}
     2509
     2510    /// \name Select Section by Name
     2511    /// @{
     2512
     2513    /// \brief Set \c \@nodes section to be read
     2514    ///
     2515    /// Set \c \@nodes section to be read.
     2516    BpGraphReader& nodes(const std::string& caption) {
     2517      _nodes_caption = caption;
     2518      return *this;
     2519    }
     2520
     2521    /// \brief Set \c \@edges section to be read
     2522    ///
     2523    /// Set \c \@edges section to be read.
     2524    BpGraphReader& edges(const std::string& caption) {
     2525      _edges_caption = caption;
     2526      return *this;
     2527    }
     2528
     2529    /// \brief Set \c \@attributes section to be read
     2530    ///
     2531    /// Set \c \@attributes section to be read.
     2532    BpGraphReader& attributes(const std::string& caption) {
     2533      _attributes_caption = caption;
     2534      return *this;
     2535    }
     2536
     2537    /// @}
     2538
     2539    /// \name Using Previously Constructed Node or Edge Set
     2540    /// @{
     2541
     2542    /// \brief Use previously constructed node set
     2543    ///
     2544    /// Use previously constructed node set, and specify the node
     2545    /// label map.
     2546    template <typename Map>
     2547    BpGraphReader& useNodes(const Map& map) {
     2548      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
     2549      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
     2550      _use_nodes = true;
     2551      _writer_bits::DefaultConverter<typename Map::Value> converter;
     2552      for (NodeIt n(_graph); n != INVALID; ++n) {
     2553        _node_index.insert(std::make_pair(converter(map[n]), n));
     2554      }
     2555      return *this;
     2556    }
     2557
     2558    /// \brief Use previously constructed node set
     2559    ///
     2560    /// Use previously constructed node set, and specify the node
     2561    /// label map and a functor which converts the label map values to
     2562    /// \c std::string.
     2563    template <typename Map, typename Converter>
     2564    BpGraphReader& useNodes(const Map& map,
     2565                            const Converter& converter = Converter()) {
     2566      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
     2567      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
     2568      _use_nodes = true;
     2569      for (NodeIt n(_graph); n != INVALID; ++n) {
     2570        _node_index.insert(std::make_pair(converter(map[n]), n));
     2571      }
     2572      return *this;
     2573    }
     2574
     2575    /// \brief Use previously constructed edge set
     2576    ///
     2577    /// Use previously constructed edge set, and specify the edge
     2578    /// label map.
     2579    template <typename Map>
     2580    BpGraphReader& useEdges(const Map& map) {
     2581      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
     2582      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
     2583      _use_edges = true;
     2584      _writer_bits::DefaultConverter<typename Map::Value> converter;
     2585      for (EdgeIt a(_graph); a != INVALID; ++a) {
     2586        _edge_index.insert(std::make_pair(converter(map[a]), a));
     2587      }
     2588      return *this;
     2589    }
     2590
     2591    /// \brief Use previously constructed edge set
     2592    ///
     2593    /// Use previously constructed edge set, and specify the edge
     2594    /// label map and a functor which converts the label map values to
     2595    /// \c std::string.
     2596    template <typename Map, typename Converter>
     2597    BpGraphReader& useEdges(const Map& map,
     2598                            const Converter& converter = Converter()) {
     2599      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
     2600      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
     2601      _use_edges = true;
     2602      for (EdgeIt a(_graph); a != INVALID; ++a) {
     2603        _edge_index.insert(std::make_pair(converter(map[a]), a));
     2604      }
     2605      return *this;
     2606    }
     2607
     2608    /// \brief Skip the reading of node section
     2609    ///
     2610    /// Omit the reading of the node section. This implies that each node
     2611    /// map reading rule will be abandoned, and the nodes of the graph
     2612    /// will not be constructed, which usually cause that the edge set
     2613    /// could not be read due to lack of node name
     2614    /// could not be read due to lack of node name resolving.
     2615    /// Therefore \c skipEdges() function should also be used, or
     2616    /// \c useNodes() should be used to specify the label of the nodes.
     2617    BpGraphReader& skipNodes() {
     2618      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
     2619      _skip_nodes = true;
     2620      return *this;
     2621    }
     2622
     2623    /// \brief Skip the reading of edge section
     2624    ///
     2625    /// Omit the reading of the edge section. This implies that each edge
     2626    /// map reading rule will be abandoned, and the edges of the graph
     2627    /// will not be constructed.
     2628    BpGraphReader& skipEdges() {
     2629      LEMON_ASSERT(!_skip_edges, "Skip edges already set");
     2630      _skip_edges = true;
     2631      return *this;
     2632    }
     2633
     2634    /// @}
     2635
     2636  private:
     2637
     2638    bool readLine() {
     2639      std::string str;
     2640      while(++line_num, std::getline(*_is, str)) {
     2641        line.clear(); line.str(str);
     2642        char c;
     2643        if (line >> std::ws >> c && c != '#') {
     2644          line.putback(c);
     2645          return true;
     2646        }
     2647      }
     2648      return false;
     2649    }
     2650
     2651    bool readSuccess() {
     2652      return static_cast<bool>(*_is);
     2653    }
     2654
     2655    void skipSection() {
     2656      char c;
     2657      while (readSuccess() && line >> c && c != '@') {
     2658        readLine();
     2659      }
     2660      if (readSuccess()) {
     2661        line.putback(c);
     2662      }
     2663    }
     2664
     2665    void readRedNodes() {
     2666
     2667      std::vector<int> map_index(_red_maps.size());
     2668      int map_num, label_index;
     2669
     2670      char c;
     2671      if (!readLine() || !(line >> c) || c == '@') {
     2672        if (readSuccess() && line) line.putback(c);
     2673        if (!_red_maps.empty())
     2674          throw FormatError("Cannot find map names");
     2675        return;
     2676      }
     2677      line.putback(c);
     2678
     2679      {
     2680        std::map<std::string, int> maps;
     2681
     2682        std::string map;
     2683        int index = 0;
     2684        while (_reader_bits::readToken(line, map)) {
     2685          if (maps.find(map) != maps.end()) {
     2686            std::ostringstream msg;
     2687            msg << "Multiple occurence of red map: " << map;
     2688            throw FormatError(msg.str());
     2689          }
     2690          maps.insert(std::make_pair(map, index));
     2691          ++index;
     2692        }
     2693
     2694        for (int i = 0; i < static_cast<int>(_red_maps.size()); ++i) {
     2695          std::map<std::string, int>::iterator jt =
     2696            maps.find(_red_maps[i].first);
     2697          if (jt == maps.end()) {
     2698            std::ostringstream msg;
     2699            msg << "Map not found: " << _red_maps[i].first;
     2700            throw FormatError(msg.str());
     2701          }
     2702          map_index[i] = jt->second;
     2703        }
     2704
     2705        {
     2706          std::map<std::string, int>::iterator jt = maps.find("label");
     2707          if (jt != maps.end()) {
     2708            label_index = jt->second;
     2709          } else {
     2710            label_index = -1;
     2711          }
     2712        }
     2713        map_num = maps.size();
     2714      }
     2715
     2716      while (readLine() && line >> c && c != '@') {
     2717        line.putback(c);
     2718
     2719        std::vector<std::string> tokens(map_num);
     2720        for (int i = 0; i < map_num; ++i) {
     2721          if (!_reader_bits::readToken(line, tokens[i])) {
     2722            std::ostringstream msg;
     2723            msg << "Column not found (" << i + 1 << ")";
     2724            throw FormatError(msg.str());
     2725          }
     2726        }
     2727        if (line >> std::ws >> c)
     2728          throw FormatError("Extra character at the end of line");
     2729
     2730        Node n;
     2731        if (!_use_nodes) {
     2732          n = _graph.addRedNode();
     2733          if (label_index != -1)
     2734            _node_index.insert(std::make_pair(tokens[label_index], n));
     2735        } else {
     2736          if (label_index == -1)
     2737            throw FormatError("Label map not found");
     2738          typename std::map<std::string, Node>::iterator it =
     2739            _node_index.find(tokens[label_index]);
     2740          if (it == _node_index.end()) {
     2741            std::ostringstream msg;
     2742            msg << "Node with label not found: " << tokens[label_index];
     2743            throw FormatError(msg.str());
     2744          }
     2745          n = it->second;
     2746        }
     2747
     2748        for (int i = 0; i < static_cast<int>(_red_maps.size()); ++i) {
     2749          _red_maps[i].second->set(n, tokens[map_index[i]]);
     2750        }
     2751
     2752      }
     2753      if (readSuccess()) {
     2754        line.putback(c);
     2755      }
     2756    }
     2757
     2758    void readBlueNodes() {
     2759
     2760      std::vector<int> map_index(_blue_maps.size());
     2761      int map_num, label_index;
     2762
     2763      char c;
     2764      if (!readLine() || !(line >> c) || c == '@') {
     2765        if (readSuccess() && line) line.putback(c);
     2766        if (!_blue_maps.empty())
     2767          throw FormatError("Cannot find map names");
     2768        return;
     2769      }
     2770      line.putback(c);
     2771
     2772      {
     2773        std::map<std::string, int> maps;
     2774
     2775        std::string map;
     2776        int index = 0;
     2777        while (_reader_bits::readToken(line, map)) {
     2778          if (maps.find(map) != maps.end()) {
     2779            std::ostringstream msg;
     2780            msg << "Multiple occurence of blue map: " << map;
     2781            throw FormatError(msg.str());
     2782          }
     2783          maps.insert(std::make_pair(map, index));
     2784          ++index;
     2785        }
     2786
     2787        for (int i = 0; i < static_cast<int>(_blue_maps.size()); ++i) {
     2788          std::map<std::string, int>::iterator jt =
     2789            maps.find(_blue_maps[i].first);
     2790          if (jt == maps.end()) {
     2791            std::ostringstream msg;
     2792            msg << "Map not found: " << _blue_maps[i].first;
     2793            throw FormatError(msg.str());
     2794          }
     2795          map_index[i] = jt->second;
     2796        }
     2797
     2798        {
     2799          std::map<std::string, int>::iterator jt = maps.find("label");
     2800          if (jt != maps.end()) {
     2801            label_index = jt->second;
     2802          } else {
     2803            label_index = -1;
     2804          }
     2805        }
     2806        map_num = maps.size();
     2807      }
     2808
     2809      while (readLine() && line >> c && c != '@') {
     2810        line.putback(c);
     2811
     2812        std::vector<std::string> tokens(map_num);
     2813        for (int i = 0; i < map_num; ++i) {
     2814          if (!_reader_bits::readToken(line, tokens[i])) {
     2815            std::ostringstream msg;
     2816            msg << "Column not found (" << i + 1 << ")";
     2817            throw FormatError(msg.str());
     2818          }
     2819        }
     2820        if (line >> std::ws >> c)
     2821          throw FormatError("Extra character at the end of line");
     2822
     2823        Node n;
     2824        if (!_use_nodes) {
     2825          n = _graph.addBlueNode();
     2826          if (label_index != -1)
     2827            _node_index.insert(std::make_pair(tokens[label_index], n));
     2828        } else {
     2829          if (label_index == -1)
     2830            throw FormatError("Label map not found");
     2831          typename std::map<std::string, Node>::iterator it =
     2832            _node_index.find(tokens[label_index]);
     2833          if (it == _node_index.end()) {
     2834            std::ostringstream msg;
     2835            msg << "Node with label not found: " << tokens[label_index];
     2836            throw FormatError(msg.str());
     2837          }
     2838          n = it->second;
     2839        }
     2840
     2841        for (int i = 0; i < static_cast<int>(_blue_maps.size()); ++i) {
     2842          _blue_maps[i].second->set(n, tokens[map_index[i]]);
     2843        }
     2844
     2845      }
     2846      if (readSuccess()) {
     2847        line.putback(c);
     2848      }
     2849    }
     2850
     2851    void readEdges() {
     2852
     2853      std::vector<int> map_index(_edge_maps.size());
     2854      int map_num, label_index;
     2855
     2856      char c;
     2857      if (!readLine() || !(line >> c) || c == '@') {
     2858        if (readSuccess() && line) line.putback(c);
     2859        if (!_edge_maps.empty())
     2860          throw FormatError("Cannot find map names");
     2861        return;
     2862      }
     2863      line.putback(c);
     2864
     2865      {
     2866        std::map<std::string, int> maps;
     2867
     2868        std::string map;
     2869        int index = 0;
     2870        while (_reader_bits::readToken(line, map)) {
     2871          if (maps.find(map) != maps.end()) {
     2872            std::ostringstream msg;
     2873            msg << "Multiple occurence of edge map: " << map;
     2874            throw FormatError(msg.str());
     2875          }
     2876          maps.insert(std::make_pair(map, index));
     2877          ++index;
     2878        }
     2879
     2880        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
     2881          std::map<std::string, int>::iterator jt =
     2882            maps.find(_edge_maps[i].first);
     2883          if (jt == maps.end()) {
     2884            std::ostringstream msg;
     2885            msg << "Map not found: " << _edge_maps[i].first;
     2886            throw FormatError(msg.str());
     2887          }
     2888          map_index[i] = jt->second;
     2889        }
     2890
     2891        {
     2892          std::map<std::string, int>::iterator jt = maps.find("label");
     2893          if (jt != maps.end()) {
     2894            label_index = jt->second;
     2895          } else {
     2896            label_index = -1;
     2897          }
     2898        }
     2899        map_num = maps.size();
     2900      }
     2901
     2902      while (readLine() && line >> c && c != '@') {
     2903        line.putback(c);
     2904
     2905        std::string source_token;
     2906        std::string target_token;
     2907
     2908        if (!_reader_bits::readToken(line, source_token))
     2909          throw FormatError("Red node not found");
     2910
     2911        if (!_reader_bits::readToken(line, target_token))
     2912          throw FormatError("Blue node not found");
     2913
     2914        std::vector<std::string> tokens(map_num);
     2915        for (int i = 0; i < map_num; ++i) {
     2916          if (!_reader_bits::readToken(line, tokens[i])) {
     2917            std::ostringstream msg;
     2918            msg << "Column not found (" << i + 1 << ")";
     2919            throw FormatError(msg.str());
     2920          }
     2921        }
     2922        if (line >> std::ws >> c)
     2923          throw FormatError("Extra character at the end of line");
     2924
     2925        Edge e;
     2926        if (!_use_edges) {
     2927
     2928          typename NodeIndex::iterator it;
     2929
     2930          it = _node_index.find(source_token);
     2931          if (it == _node_index.end()) {
     2932            std::ostringstream msg;
     2933            msg << "Item not found: " << source_token;
     2934            throw FormatError(msg.str());
     2935          }
     2936          Node source = it->second;
     2937          if (!_graph.red(source)) {
     2938            std::ostringstream msg;
     2939            msg << "Item is not red node: " << source_token;
     2940            throw FormatError(msg.str());
     2941          }
     2942
     2943          it = _node_index.find(target_token);
     2944          if (it == _node_index.end()) {
     2945            std::ostringstream msg;
     2946            msg << "Item not found: " << target_token;
     2947            throw FormatError(msg.str());
     2948          }
     2949          Node target = it->second;
     2950          if (!_graph.blue(target)) {
     2951            std::ostringstream msg;
     2952            msg << "Item is not red node: " << source_token;
     2953            throw FormatError(msg.str());
     2954          }
     2955
     2956          e = _graph.addEdge(source, target);
     2957          if (label_index != -1)
     2958            _edge_index.insert(std::make_pair(tokens[label_index], e));
     2959        } else {
     2960          if (label_index == -1)
     2961            throw FormatError("Label map not found");
     2962          typename std::map<std::string, Edge>::iterator it =
     2963            _edge_index.find(tokens[label_index]);
     2964          if (it == _edge_index.end()) {
     2965            std::ostringstream msg;
     2966            msg << "Edge with label not found: " << tokens[label_index];
     2967            throw FormatError(msg.str());
     2968          }
     2969          e = it->second;
     2970        }
     2971
     2972        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
     2973          _edge_maps[i].second->set(e, tokens[map_index[i]]);
     2974        }
     2975
     2976      }
     2977      if (readSuccess()) {
     2978        line.putback(c);
     2979      }
     2980    }
     2981
     2982    void readAttributes() {
     2983
     2984      std::set<std::string> read_attr;
     2985
     2986      char c;
     2987      while (readLine() && line >> c && c != '@') {
     2988        line.putback(c);
     2989
     2990        std::string attr, token;
     2991        if (!_reader_bits::readToken(line, attr))
     2992          throw FormatError("Attribute name not found");
     2993        if (!_reader_bits::readToken(line, token))
     2994          throw FormatError("Attribute value not found");
     2995        if (line >> c)
     2996          throw FormatError("Extra character at the end of line");
     2997
     2998        {
     2999          std::set<std::string>::iterator it = read_attr.find(attr);
     3000          if (it != read_attr.end()) {
     3001            std::ostringstream msg;
     3002            msg << "Multiple occurence of attribute: " << attr;
     3003            throw FormatError(msg.str());
     3004          }
     3005          read_attr.insert(attr);
     3006        }
     3007
     3008        {
     3009          typename Attributes::iterator it = _attributes.lower_bound(attr);
     3010          while (it != _attributes.end() && it->first == attr) {
     3011            it->second->set(token);
     3012            ++it;
     3013          }
     3014        }
     3015
     3016      }
     3017      if (readSuccess()) {
     3018        line.putback(c);
     3019      }
     3020      for (typename Attributes::iterator it = _attributes.begin();
     3021           it != _attributes.end(); ++it) {
     3022        if (read_attr.find(it->first) == read_attr.end()) {
     3023          std::ostringstream msg;
     3024          msg << "Attribute not found: " << it->first;
     3025          throw FormatError(msg.str());
     3026        }
     3027      }
     3028    }
     3029
     3030  public:
     3031
     3032    /// \name Execution of the Reader
     3033    /// @{
     3034
     3035    /// \brief Start the batch processing
     3036    ///
     3037    /// This function starts the batch processing
     3038    void run() {
     3039
     3040      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
     3041
     3042      bool red_nodes_done = _skip_nodes;
     3043      bool blue_nodes_done = _skip_nodes;
     3044      bool edges_done = _skip_edges;
     3045      bool attributes_done = false;
     3046
     3047      line_num = 0;
     3048      readLine();
     3049      skipSection();
     3050
     3051      while (readSuccess()) {
     3052        try {
     3053          char c;
     3054          std::string section, caption;
     3055          line >> c;
     3056          _reader_bits::readToken(line, section);
     3057          _reader_bits::readToken(line, caption);
     3058
     3059          if (line >> c)
     3060            throw FormatError("Extra character at the end of line");
     3061
     3062          if (section == "red_nodes" && !red_nodes_done) {
     3063            if (_nodes_caption.empty() || _nodes_caption == caption) {
     3064              readRedNodes();
     3065              red_nodes_done = true;
     3066            }
     3067          } else if (section == "blue_nodes" && !blue_nodes_done) {
     3068            if (_nodes_caption.empty() || _nodes_caption == caption) {
     3069              readBlueNodes();
     3070              blue_nodes_done = true;
     3071            }
     3072          } else if ((section == "edges" || section == "arcs") &&
     3073                     !edges_done) {
     3074            if (_edges_caption.empty() || _edges_caption == caption) {
     3075              readEdges();
     3076              edges_done = true;
     3077            }
     3078          } else if (section == "attributes" && !attributes_done) {
     3079            if (_attributes_caption.empty() || _attributes_caption == caption) {
     3080              readAttributes();
     3081              attributes_done = true;
     3082            }
     3083          } else {
     3084            readLine();
     3085            skipSection();
     3086          }
     3087        } catch (FormatError& error) {
     3088          error.line(line_num);
     3089          error.file(_filename);
     3090          throw;
     3091        }
     3092      }
     3093
     3094      if (!red_nodes_done) {
     3095        throw FormatError("Section @red_nodes not found");
     3096      }
     3097
     3098      if (!blue_nodes_done) {
     3099        throw FormatError("Section @blue_nodes not found");
     3100      }
     3101
     3102      if (!edges_done) {
     3103        throw FormatError("Section @edges not found");
     3104      }
     3105
     3106      if (!attributes_done && !_attributes.empty()) {
     3107        throw FormatError("Section @attributes not found");
     3108      }
     3109
     3110    }
     3111
     3112    /// @}
     3113
     3114  };
     3115
     3116  /// \ingroup lemon_io
     3117  ///
     3118  /// \brief Return a \ref BpGraphReader class
     3119  ///
     3120  /// This function just returns a \ref BpGraphReader class.
     3121  ///
     3122  /// With this function a graph can be read from an
     3123  /// \ref lgf-format "LGF" file or input stream with several maps and
     3124  /// attributes. For example, there is bipartite weighted matching problem
     3125  /// on a graph, i.e. a graph with a \e weight map on the edges. This
     3126  /// graph can be read with the following code:
     3127  ///
     3128  ///\code
     3129  ///ListBpGraph graph;
     3130  ///ListBpGraph::EdgeMap<int> weight(graph);
     3131  ///bpGraphReader(graph, std::cin).
     3132  ///  edgeMap("weight", weight).
     3133  ///  run();
     3134  ///\endcode
     3135  ///
     3136  /// For a complete documentation, please see the \ref BpGraphReader
     3137  /// class documentation.
     3138  /// \warning Don't forget to put the \ref BpGraphReader::run() "run()"
     3139  /// to the end of the parameter list.
     3140  /// \relates BpGraphReader
     3141  /// \sa bpGraphReader(TBGR& graph, const std::string& fn)
     3142  /// \sa bpGraphReader(TBGR& graph, const char* fn)
     3143  template <typename TBGR>
     3144  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is) {
     3145    BpGraphReader<TBGR> tmp(graph, is);
     3146    return tmp;
     3147  }
     3148
     3149  /// \brief Return a \ref BpGraphReader class
     3150  ///
     3151  /// This function just returns a \ref BpGraphReader class.
     3152  /// \relates BpGraphReader
     3153  /// \sa bpGraphReader(TBGR& graph, std::istream& is)
     3154  template <typename TBGR>
     3155  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn) {
     3156    BpGraphReader<TBGR> tmp(graph, fn);
     3157    return tmp;
     3158  }
     3159
     3160  /// \brief Return a \ref BpGraphReader class
     3161  ///
     3162  /// This function just returns a \ref BpGraphReader class.
     3163  /// \relates BpGraphReader
     3164  /// \sa bpGraphReader(TBGR& graph, std::istream& is)
     3165  template <typename TBGR>
     3166  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char* fn) {
     3167    BpGraphReader<TBGR> tmp(graph, fn);
     3168    return tmp;
     3169  }
     3170
    21313171  class SectionReader;
    21323172
Note: See TracChangeset for help on using the changeset viewer.