gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge #382 to branch 1.1
0 4 1
merge 1.1
4 files changed with 205 insertions and 8 deletions:
↑ Collapse diff ↑
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2011
6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8
 *
9
 * Permission to use, modify and distribute this software is granted
10
 * provided that this copyright notice appears in all copies. For
11
 * precise terms see the accompanying LICENSE file.
12
 *
13
 * This software is provided "AS IS" with no warranty of any kind,
14
 * express or implied, and with no claim as to its suitability for any
15
 * purpose.
16
 *
17
 */
18

	
19
#include <lemon/list_graph.h>
20
#include <lemon/lgf_reader.h>
21
#include "test_tools.h"
22

	
23
using namespace lemon;
24

	
25
char test_lgf[] =
26
  "@nodes\n"
27
  "label\n"
28
  "0\n"
29
  "1\n"
30
  "@arcs\n"
31
  "     label\n"
32
  "0 1  0\n"
33
  "1 0  1\n"
34
  "@attributes\n"
35
  "source 0\n"
36
  "target 1\n";
37

	
38
char test_lgf_nomap[] =
39
  "@nodes\n"
40
  "label\n"
41
  "0\n"
42
  "1\n"
43
  "@arcs\n"
44
  "     -\n"
45
  "0 1\n";
46

	
47
char test_lgf_bad1[] =
48
  "@nodes\n"
49
  "label\n"
50
  "0\n"
51
  "1\n"
52
  "@arcs\n"
53
  "     - another\n"
54
  "0 1\n";
55

	
56
char test_lgf_bad2[] =
57
  "@nodes\n"
58
  "label\n"
59
  "0\n"
60
  "1\n"
61
  "@arcs\n"
62
  "     label -\n"
63
  "0 1\n";
64

	
65

	
66
int main() 
67
{
68
  {
69
    ListDigraph d; 
70
    ListDigraph::Node s,t;
71
    ListDigraph::ArcMap<int> label(d);
72
    std::istringstream input(test_lgf);
73
    digraphReader(d, input).
74
      node("source", s).
75
      node("target", t).
76
      arcMap("label", label).
77
      run();
78
    check(countNodes(d) == 2,"There should be 2 nodes");
79
    check(countArcs(d) == 2,"There should be 2 arcs");
80
  }
81
  {
82
    ListGraph g;
83
    ListGraph::Node s,t;
84
    ListGraph::EdgeMap<int> label(g);
85
    std::istringstream input(test_lgf);
86
    graphReader(g, input).
87
      node("source", s).
88
      node("target", t).
89
      edgeMap("label", label).
90
      run();
91
    check(countNodes(g) == 2,"There should be 2 nodes");
92
    check(countEdges(g) == 2,"There should be 2 arcs");
93
  }
94

	
95
  {
96
    ListDigraph d; 
97
    std::istringstream input(test_lgf_nomap);
98
    digraphReader(d, input).
99
      run();
100
    check(countNodes(d) == 2,"There should be 2 nodes");
101
    check(countArcs(d) == 1,"There should be 1 arc");
102
  }
103
  {
104
    ListGraph g;
105
    std::istringstream input(test_lgf_nomap);
106
    graphReader(g, input).
107
      run();
108
    check(countNodes(g) == 2,"There should be 2 nodes");
109
    check(countEdges(g) == 1,"There should be 1 edge");
110
  }
111

	
112
  {
113
    ListDigraph d; 
114
    std::istringstream input(test_lgf_bad1);
115
    bool ok=false;
116
    try {
117
      digraphReader(d, input).
118
        run();
119
    }
120
    catch (FormatError& error) 
121
      {
122
        ok = true;
123
      }
124
    check(ok,"FormatError exception should have occured");
125
  }
126
  {
127
    ListGraph g;
128
    std::istringstream input(test_lgf_bad1);
129
    bool ok=false;
130
    try {
131
      graphReader(g, input).
132
        run();
133
    }
134
    catch (FormatError& error)
135
      {
136
        ok = true;
137
      }
138
    check(ok,"FormatError exception should have occured");
139
  }
140

	
141
  {
142
    ListDigraph d; 
143
    std::istringstream input(test_lgf_bad2);
144
    bool ok=false;
145
    try {
146
      digraphReader(d, input).
147
        run();
148
    }
149
    catch (FormatError& error)
150
      {
151
        ok = true;
152
      }
153
    check(ok,"FormatError exception should have occured");
154
  }
155
  {
156
    ListGraph g;
157
    std::istringstream input(test_lgf_bad2);
158
    bool ok=false;
159
    try {
160
      graphReader(g, input).
161
        run();
162
    }
163
    catch (FormatError& error)
164
      {
165
        ok = true;
166
      }
167
    check(ok,"FormatError exception should have occured");
168
  }
169
}
Ignore white space 6 line context
... ...
@@ -34,74 +34,85 @@
34 34
a header line. The header lines starts with an \c '@' character followed by the
35 35
type of section. The standard section types are \c \@nodes, \c
36 36
\@arcs and \c \@edges
37 37
and \@attributes. Each header line may also have an optional
38 38
\e name, which can be use to distinguish the sections of the same
39 39
type.
40 40

	
41 41
The standard sections are column oriented, each line consists of
42 42
<em>token</em>s separated by whitespaces. A token can be \e plain or
43 43
\e quoted. A plain token is just a sequence of non-whitespace characters,
44 44
while a quoted token is a
45 45
character sequence surrounded by double quotes, and it can also
46 46
contain whitespaces and escape sequences.
47 47

	
48 48
The \c \@nodes section describes a set of nodes and associated
49 49
maps. The first is a header line, its columns are the names of the
50 50
maps appearing in the following lines.
51 51
One of the maps must be called \c
52 52
"label", which plays special role in the file.
53 53
The following
54 54
non-empty lines until the next section describes nodes of the
55 55
graph. Each line contains the values of the node maps
56 56
associated to the current node.
57 57

	
58 58
\code
59 59
 @nodes
60 60
 label  coordinates  size    title
61 61
 1      (10,20)      10      "First node"
62 62
 2      (80,80)      8       "Second node"
63 63
 3      (40,10)      10      "Third node"
64 64
\endcode
65 65

	
66
The \c \@arcs section is very similar to the \c \@nodes section,
67
it again starts with a header line describing the names of the maps,
68
but the \c "label" map is not obligatory here. The following lines
69
describe the arcs. The first two tokens of each line are
70
the source and the target node of the arc, respectively, then come the map
66
The \c \@arcs section is very similar to the \c \@nodes section, it
67
again starts with a header line describing the names of the maps, but
68
the \c "label" map is not obligatory here. The following lines
69
describe the arcs. The first two tokens of each line are the source
70
and the target node of the arc, respectively, then come the map
71 71
values. The source and target tokens must be node labels.
72 72

	
73 73
\code
74 74
 @arcs
75 75
         capacity
76 76
 1   2   16
77 77
 1   3   12
78 78
 2   3   18
79 79
\endcode
80 80

	
81
If there is no map in the \c \@arcs section at all, then it must be
82
indicated by a sole '-' sign in the first line.
83

	
84
\code
85
 @arcs
86
         -
87
 1   2
88
 1   3
89
 2   3
90
\endcode
91

	
81 92
The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
82 93
also store the edge set of an undirected graph. In such case there is
83 94
a conventional method for store arc maps in the file, if two columns
84
has the same caption with \c '+' and \c '-' prefix, then these columns
95
have the same caption with \c '+' and \c '-' prefix, then these columns
85 96
can be regarded as the values of an arc map.
86 97

	
87 98
The \c \@attributes section contains key-value pairs, each line
88 99
consists of two tokens, an attribute name, and then an attribute
89 100
value. The value of the attribute could be also a label value of a
90 101
node or an edge, or even an edge label prefixed with \c '+' or \c '-',
91 102
which regards to the forward or backward directed arc of the
92 103
corresponding edge.
93 104

	
94 105
\code
95 106
 @attributes
96 107
 source 1
97 108
 target 3
98 109
 caption "LEMON test digraph"
99 110
\endcode
100 111

	
101 112
The \e LGF can contain extra sections, but there is no restriction on
102 113
the format of such sections.
103 114

	
104 115
*/
105 116
}
106 117

	
107 118
//  LocalWords:  whitespace whitespaces
Ignore white space 64 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5
 * Copyright (C) 2003-2009
5
 * Copyright (C) 2003-2011
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
///\ingroup lemon_io
20 20
///\file
21 21
///\brief \ref lgf-format "LEMON Graph Format" reader.
22 22

	
23 23

	
24 24
#ifndef LEMON_LGF_READER_H
25 25
#define LEMON_LGF_READER_H
26 26

	
27 27
#include <iostream>
28 28
#include <fstream>
29 29
#include <sstream>
30 30

	
31 31
#include <set>
32 32
#include <map>
33 33

	
34 34
#include <lemon/core.h>
35 35

	
36 36
#include <lemon/lgf_writer.h>
37 37

	
... ...
@@ -935,64 +935,71 @@
935 935
        }
936 936

	
937 937
        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
938 938
          _node_maps[i].second->set(n, tokens[map_index[i]]);
939 939
        }
940 940

	
941 941
      }
942 942
      if (readSuccess()) {
943 943
        line.putback(c);
944 944
      }
945 945
    }
946 946

	
947 947
    void readArcs() {
948 948

	
949 949
      std::vector<int> map_index(_arc_maps.size());
950 950
      int map_num, label_index;
951 951

	
952 952
      char c;
953 953
      if (!readLine() || !(line >> c) || c == '@') {
954 954
        if (readSuccess() && line) line.putback(c);
955 955
        if (!_arc_maps.empty())
956 956
          throw FormatError("Cannot find map names");
957 957
        return;
958 958
      }
959 959
      line.putback(c);
960 960

	
961 961
      {
962 962
        std::map<std::string, int> maps;
963 963

	
964 964
        std::string map;
965 965
        int index = 0;
966 966
        while (_reader_bits::readToken(line, map)) {
967
          if(map == "-") {
968
              if(index!=0)
969
                throw FormatError("'-' is not allowed as a map name");
970
              else if (line >> std::ws >> c)
971
                throw FormatError("Extra character at the end of line");
972
              else break;
973
            }
967 974
          if (maps.find(map) != maps.end()) {
968 975
            std::ostringstream msg;
969 976
            msg << "Multiple occurence of arc map: " << map;
970 977
            throw FormatError(msg.str());
971 978
          }
972 979
          maps.insert(std::make_pair(map, index));
973 980
          ++index;
974 981
        }
975 982

	
976 983
        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
977 984
          std::map<std::string, int>::iterator jt =
978 985
            maps.find(_arc_maps[i].first);
979 986
          if (jt == maps.end()) {
980 987
            std::ostringstream msg;
981 988
            msg << "Map not found: " << _arc_maps[i].first;
982 989
            throw FormatError(msg.str());
983 990
          }
984 991
          map_index[i] = jt->second;
985 992
        }
986 993

	
987 994
        {
988 995
          std::map<std::string, int>::iterator jt = maps.find("label");
989 996
          if (jt != maps.end()) {
990 997
            label_index = jt->second;
991 998
          } else {
992 999
            label_index = -1;
993 1000
          }
994 1001
        }
995 1002
        map_num = maps.size();
996 1003
      }
997 1004

	
998 1005
      while (readLine() && line >> c && c != '@') {
... ...
@@ -1805,64 +1812,71 @@
1805 1812
        }
1806 1813

	
1807 1814
        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1808 1815
          _node_maps[i].second->set(n, tokens[map_index[i]]);
1809 1816
        }
1810 1817

	
1811 1818
      }
1812 1819
      if (readSuccess()) {
1813 1820
        line.putback(c);
1814 1821
      }
1815 1822
    }
1816 1823

	
1817 1824
    void readEdges() {
1818 1825

	
1819 1826
      std::vector<int> map_index(_edge_maps.size());
1820 1827
      int map_num, label_index;
1821 1828

	
1822 1829
      char c;
1823 1830
      if (!readLine() || !(line >> c) || c == '@') {
1824 1831
        if (readSuccess() && line) line.putback(c);
1825 1832
        if (!_edge_maps.empty())
1826 1833
          throw FormatError("Cannot find map names");
1827 1834
        return;
1828 1835
      }
1829 1836
      line.putback(c);
1830 1837

	
1831 1838
      {
1832 1839
        std::map<std::string, int> maps;
1833 1840

	
1834 1841
        std::string map;
1835 1842
        int index = 0;
1836 1843
        while (_reader_bits::readToken(line, map)) {
1844
          if(map == "-") {
1845
              if(index!=0)
1846
                throw FormatError("'-' is not allowed as a map name");
1847
              else if (line >> std::ws >> c)
1848
                throw FormatError("Extra character at the end of line");
1849
              else break;
1850
            }
1837 1851
          if (maps.find(map) != maps.end()) {
1838 1852
            std::ostringstream msg;
1839 1853
            msg << "Multiple occurence of edge map: " << map;
1840 1854
            throw FormatError(msg.str());
1841 1855
          }
1842 1856
          maps.insert(std::make_pair(map, index));
1843 1857
          ++index;
1844 1858
        }
1845 1859

	
1846 1860
        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1847 1861
          std::map<std::string, int>::iterator jt =
1848 1862
            maps.find(_edge_maps[i].first);
1849 1863
          if (jt == maps.end()) {
1850 1864
            std::ostringstream msg;
1851 1865
            msg << "Map not found: " << _edge_maps[i].first;
1852 1866
            throw FormatError(msg.str());
1853 1867
          }
1854 1868
          map_index[i] = jt->second;
1855 1869
        }
1856 1870

	
1857 1871
        {
1858 1872
          std::map<std::string, int>::iterator jt = maps.find("label");
1859 1873
          if (jt != maps.end()) {
1860 1874
            label_index = jt->second;
1861 1875
          } else {
1862 1876
            label_index = -1;
1863 1877
          }
1864 1878
        }
1865 1879
        map_num = maps.size();
1866 1880
      }
1867 1881

	
1868 1882
      while (readLine() && line >> c && c != '@') {
Ignore white space 6 line context
... ...
@@ -2,64 +2,65 @@
2 2
  ${PROJECT_SOURCE_DIR}
3 3
  ${PROJECT_BINARY_DIR}
4 4
)
5 5

	
6 6
LINK_DIRECTORIES(
7 7
  ${PROJECT_BINARY_DIR}/lemon
8 8
)
9 9

	
10 10
SET(TEST_WITH_VALGRIND "NO" CACHE STRING
11 11
  "Run the test with valgrind (YES/NO).")
12 12
SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")
13 13

	
14 14
SET(TESTS
15 15
  adaptors_test
16 16
  bfs_test
17 17
  circulation_test
18 18
  connectivity_test
19 19
  counter_test
20 20
  dfs_test
21 21
  digraph_test
22 22
  dijkstra_test
23 23
  dim_test
24 24
  edge_set_test
25 25
  error_test
26 26
  euler_test
27 27
  gomory_hu_test
28 28
  graph_copy_test
29 29
  graph_test
30 30
  graph_utils_test
31 31
  hao_orlin_test
32 32
  heap_test
33 33
  kruskal_test
34
  lgf_test
34 35
  maps_test
35 36
  matching_test
36 37
  min_cost_arborescence_test
37 38
  min_cost_flow_test
38 39
  path_test
39 40
  preflow_test
40 41
  radix_sort_test
41 42
  random_test
42 43
  suurballe_test
43 44
  time_measure_test
44 45
  unionfind_test
45 46
)
46 47

	
47 48
IF(LEMON_HAVE_LP)
48 49
  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
49 50
    ADD_EXECUTABLE(lp_test lp_test.cc)
50 51
  ELSE()
51 52
    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
52 53
  ENDIF()
53 54

	
54 55
  SET(LP_TEST_LIBS lemon)
55 56

	
56 57
  IF(LEMON_HAVE_GLPK)
57 58
    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})
58 59
  ENDIF()
59 60
  IF(LEMON_HAVE_CPLEX)
60 61
    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})
61 62
  ENDIF()
62 63
  IF(LEMON_HAVE_CLP)
63 64
    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})
64 65
  ENDIF()
65 66

	
Ignore white space 6 line context
1 1
EXTRA_DIST += \
2 2
	test/CMakeLists.txt
3 3

	
4 4
noinst_HEADERS += \
5 5
	test/graph_test.h \
6 6
	test/test_tools.h
7 7

	
8 8
check_PROGRAMS += \
9 9
	test/adaptors_test \
10 10
	test/bfs_test \
11 11
	test/circulation_test \
12 12
	test/connectivity_test \
13 13
	test/counter_test \
14 14
	test/dfs_test \
15 15
	test/digraph_test \
16 16
	test/dijkstra_test \
17 17
	test/dim_test \
18 18
	test/edge_set_test \
19 19
	test/error_test \
20 20
	test/euler_test \
21 21
	test/gomory_hu_test \
22 22
	test/graph_copy_test \
23 23
	test/graph_test \
24 24
	test/graph_utils_test \
25 25
	test/hao_orlin_test \
26 26
	test/heap_test \
27 27
	test/kruskal_test \
28
	test/lgf_test \
28 29
	test/maps_test \
29 30
	test/matching_test \
30 31
	test/min_cost_arborescence_test \
31 32
	test/min_cost_flow_test \
32 33
	test/path_test \
33 34
	test/preflow_test \
34 35
	test/radix_sort_test \
35 36
	test/random_test \
36 37
	test/suurballe_test \
37 38
	test/test_tools_fail \
38 39
	test/test_tools_pass \
39 40
	test/time_measure_test \
40 41
	test/unionfind_test
41 42

	
42 43
test_test_tools_pass_DEPENDENCIES = demo
43 44

	
44 45
if HAVE_LP
45 46
check_PROGRAMS += test/lp_test
46 47
endif HAVE_LP
47 48
if HAVE_MIP
48 49
check_PROGRAMS += test/mip_test
49 50
endif HAVE_MIP
50 51

	
51 52
TESTS += $(check_PROGRAMS)
52 53
XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
53 54

	
54 55
test_adaptors_test_SOURCES = test/adaptors_test.cc
55 56
test_bfs_test_SOURCES = test/bfs_test.cc
56 57
test_circulation_test_SOURCES = test/circulation_test.cc
57 58
test_counter_test_SOURCES = test/counter_test.cc
58 59
test_connectivity_test_SOURCES = test/connectivity_test.cc
59 60
test_dfs_test_SOURCES = test/dfs_test.cc
60 61
test_digraph_test_SOURCES = test/digraph_test.cc
61 62
test_dijkstra_test_SOURCES = test/dijkstra_test.cc
62 63
test_dim_test_SOURCES = test/dim_test.cc
63 64
test_edge_set_test_SOURCES = test/edge_set_test.cc
64 65
test_error_test_SOURCES = test/error_test.cc
65 66
test_euler_test_SOURCES = test/euler_test.cc
66 67
test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
67 68
test_graph_copy_test_SOURCES = test/graph_copy_test.cc
68 69
test_graph_test_SOURCES = test/graph_test.cc
69 70
test_graph_utils_test_SOURCES = test/graph_utils_test.cc
71
test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
70 72
test_heap_test_SOURCES = test/heap_test.cc
71 73
test_kruskal_test_SOURCES = test/kruskal_test.cc
72
test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
74
test_lgf_test_SOURCES = test/lgf_test.cc
73 75
test_lp_test_SOURCES = test/lp_test.cc
74 76
test_maps_test_SOURCES = test/maps_test.cc
75 77
test_mip_test_SOURCES = test/mip_test.cc
76 78
test_matching_test_SOURCES = test/matching_test.cc
77 79
test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
78 80
test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
79 81
test_path_test_SOURCES = test/path_test.cc
80 82
test_preflow_test_SOURCES = test/preflow_test.cc
81 83
test_radix_sort_test_SOURCES = test/radix_sort_test.cc
82 84
test_suurballe_test_SOURCES = test/suurballe_test.cc
83 85
test_random_test_SOURCES = test/random_test.cc
84 86
test_test_tools_fail_SOURCES = test/test_tools_fail.cc
85 87
test_test_tools_pass_SOURCES = test/test_tools_pass.cc
86 88
test_time_measure_test_SOURCES = test/time_measure_test.cc
87 89
test_unionfind_test_SOURCES = test/unionfind_test.cc
0 comments (0 inline)