1.1 --- a/demo/Makefile.am Thu Sep 14 19:02:52 2006 +0000
1.2 +++ b/demo/Makefile.am Thu Sep 14 19:11:24 2006 +0000
1.3 @@ -21,6 +21,7 @@
1.4 demo/coloring \
1.5 demo/grid_ugraph_demo \
1.6 demo/topology_demo \
1.7 + demo/topological_ordering \
1.8 demo/simann_maxcut_demo \
1.9 demo/disjoint_paths_demo \
1.10 demo/strongly_connected_orientation
1.11 @@ -78,6 +79,8 @@
1.12
1.13 demo_topology_demo_SOURCES = demo/topology_demo.cc
1.14
1.15 +demo_topological_ordering_SOURCES = demo/topological_ordering.cc
1.16 +
1.17 demo_simann_maxcut_demo_SOURCES = demo/simann_maxcut_demo.cc
1.18
1.19 demo_disjoint_paths_demo_SOURCES = demo/disjoint_paths_demo.cc
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/demo/topological_ordering.cc Thu Sep 14 19:11:24 2006 +0000
2.3 @@ -0,0 +1,115 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2006
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +///\ingroup demos
2.23 +///\file
2.24 +///\brief Demonstrating the Dfs class with topological ordering
2.25 +///
2.26 +///\include topological_ordering.cc
2.27 +
2.28 +#include <iostream>
2.29 +#include <string>
2.30 +#include <list>
2.31 +#include <lemon/list_graph.h>
2.32 +#include <lemon/maps.h>
2.33 +#include <lemon/dfs.h>
2.34 +
2.35 +using namespace lemon;
2.36 +
2.37 +
2.38 +template< typename GR >
2.39 +class SerializingWriteMap
2.40 +{
2.41 +public:
2.42 + typedef typename GR::Node Key;
2.43 + typedef bool Value;
2.44 + typedef std::list<Key> OrderedList;
2.45 +
2.46 + OrderedList order;
2.47 +
2.48 + SerializingWriteMap( const GR& gr ) {}
2.49 +
2.50 + void set( const Key& k, const Value& v ) {
2.51 + if( v ) order.push_front(k);
2.52 + }
2.53 +
2.54 + Value operator[] ( const Key& ) {
2.55 + return false;
2.56 + }
2.57 +};
2.58 +
2.59 +
2.60 +int main( int argc, char *argv[] )
2.61 +{
2.62 + std::cout << "Topological Ordering demo" << std::endl;
2.63 +
2.64 + // Create and build the graph
2.65 + ListGraph gr;
2.66 + ListGraph::NodeMap<std::string> label(gr);
2.67 + typedef ListGraph::Node Node;
2.68 +
2.69 + // This DAG example for topological ordering is from the book New Algorithms
2.70 + // (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)
2.71 + {
2.72 + Node belt = gr.addNode();
2.73 + Node trousers = gr.addNode();
2.74 + Node necktie = gr.addNode();
2.75 + Node coat = gr.addNode();
2.76 + Node socks = gr.addNode();
2.77 + Node shirt = gr.addNode();
2.78 + Node shoe = gr.addNode();
2.79 + Node watch = gr.addNode();
2.80 + Node pants = gr.addNode();
2.81 +
2.82 + label[belt] = "Belt";
2.83 + label[trousers] = "Trousers";
2.84 + label[necktie] = "Necktie";
2.85 + label[coat] = "Coat";
2.86 + label[socks] = "Socks";
2.87 + label[shirt] = "Shirt";
2.88 + label[shoe] = "Shoe";
2.89 + label[watch] = "Watch";
2.90 + label[pants] = "Pants";
2.91 +
2.92 + // Here we use a directed edge to indicate precedenc.
2.93 + // The source must precede the target.
2.94 + gr.addEdge( socks, shoe );
2.95 + gr.addEdge( pants, shoe );
2.96 + gr.addEdge( pants, trousers );
2.97 + gr.addEdge( trousers, shoe );
2.98 + gr.addEdge( trousers, belt );
2.99 + gr.addEdge( belt, coat );
2.100 + gr.addEdge( shirt, belt );
2.101 + gr.addEdge( shirt, necktie );
2.102 + gr.addEdge( necktie, coat );
2.103 + }
2.104 +
2.105 + // Calculate topological order
2.106 + Dfs<ListGraph, Dfs<ListGraph>::DefProcessedMapTraits<SerializingWriteMap<ListGraph> > > dfs(gr);
2.107 + SerializingWriteMap<ListGraph> list(gr);
2.108 + dfs.processedMap(list);
2.109 + dfs.run();
2.110 +
2.111 + // Write out the result
2.112 + std::cout << "One possible order to dress up:";
2.113 + for( SerializingWriteMap<ListGraph>::OrderedList::iterator it = list.order.begin(); it != list.order.end(); ++it )
2.114 + std::cout << " " << label[*it];
2.115 + std::cout << std::endl;
2.116 +
2.117 + return 0;
2.118 +}
3.1 --- a/doc/Makefile.am Thu Sep 14 19:02:52 2006 +0000
3.2 +++ b/doc/Makefile.am Thu Sep 14 19:11:24 2006 +0000
3.3 @@ -16,6 +16,7 @@
3.4 doc/graph_io.dox \
3.5 doc/graphs.dox \
3.6 doc/groups.dox \
3.7 + doc/lemon_file_format.dox \
3.8 doc/license.dox \
3.9 doc/mainpage.dox \
3.10 doc/maps.dox \
3.11 @@ -24,6 +25,7 @@
3.12 doc/named-param.dox \
3.13 doc/namespaces.dox \
3.14 doc/quicktour.dox \
3.15 + doc/read_write_bg.dox \
3.16 doc/ugraphs.dox
3.17
3.18 doc:
4.1 --- a/doc/algorithms.dox Thu Sep 14 19:02:52 2006 +0000
4.2 +++ b/doc/algorithms.dox Thu Sep 14 19:11:24 2006 +0000
4.3 @@ -1,5 +1,130 @@
4.4 +namespace lemon {
4.5 /**
4.6 \page algorithms Algorithms
4.7
4.8 -Place-holder page for algorithms.
4.9 +\section algo_bfs_dfs Bfs/Dfs
4.10 +Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
4.11 +implementations of the well known algorithms. The algorithms are placed most cases in
4.12 +separated files named after the algorithm itself but lower case as all other header file names.
4.13 +For example the next Bfs class is in the \c lemon/bfs.h.
4.14 +
4.15 +\subsection Bfs
4.16 +The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
4.17 +The class has two template parameters: \b GR and \TR.<br>
4.18 +GR is the graph the algorithm runs on. It has \ref lemon::ListGraph "ListGraph" as default type.
4.19 +TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
4.20 +wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
4.21 +
4.22 +To use the class, declare it!
4.23 +\code
4.24 +Bfs<ListUGraph> bfs(gr);
4.25 +\endcode
4.26 +Note the lack of second template argument because of the default parameter.
4.27 +
4.28 +It provides a simple but powerful interface to control the execution.
4.29 +\code
4.30 +int dist = bfs.run(s,t);
4.31 +\endcode
4.32 +It finds the shortest path from node \c s to node \c t and returns it, or zero
4.33 +if there is no path from \c s to \c t.<br>
4.34 +If you want the shortest path from a specified node to all other node, just write:
4.35 +\code
4.36 +bfs.run(s);
4.37 +\endcode
4.38 +Now the distances and path information are stored in maps which you can access with
4.39 +member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
4.40 +Or more directly whit other member functions like \c predNode(). Once the algorithm
4.41 +is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
4.42 +"predNode()" can be called.
4.43 +
4.44 +For an example let's say we want to print the shortest path of those nodes which
4.45 +are in a certain distance.
4.46 +\code
4.47 +bfs.run(s);
4.48 +
4.49 +for( ListUGraph::NodeIt n(gr); n != INVALID; ++n ) {
4.50 + if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
4.51 + std::cout << gr.id(n);
4.52 +
4.53 + Node prev = bfs.prevNode(n);
4.54 + while( prev != INVALID ) {
4.55 + std::cout << "<-" << gr.id(prev);
4.56 + prev = bfs.prevNode(n);
4.57 + }
4.58 +
4.59 + std::cout << std::endl;
4.60 + }
4.61 +}
4.62 +\endcode
4.63 +
4.64 +\subsubsection bfs_adv_control Advanced control
4.65 +In the previous code we only used \c run(). Now we introduce the way you can directly
4.66 +control the execution of the algorithm.
4.67 +
4.68 +First you have to initialize the variables with \ref lemon::Bfs::init "init()".
4.69 +\code
4.70 + bfs.init();
4.71 +\endcode
4.72 +
4.73 +Then you add one or more source nodes to the queue. They will be processed, as they would
4.74 +be reached by the algorithm before. And yes - you can add more sources during the execution.
4.75 +\code
4.76 + bfs.addSource(node_1);
4.77 + bfs.addSource(node_2);
4.78 + ...
4.79 +\endcode
4.80 +
4.81 +And finally you can start the process with \ref lemon::Bfs::start "start()", or
4.82 +you can write your own loop to process the nodes one-by-one.
4.83 +
4.84 +\todo demo for bfs advanced control
4.85 +
4.86 +\subsection Dfs
4.87 +Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
4.88 +to demonstrate Dfs's capabilities.
4.89 +
4.90 +We will see a program, which solves the problem of <b>topological ordering</b>.
4.91 +We need to know in which order we should put on our clothes. The program will do the following:
4.92 +<ol>
4.93 +<li>We run the dfs algorithm to all nodes.
4.94 +<li>Put every node into a list when processed completely.
4.95 +<li>Write out the list in reverse order.
4.96 +</ol>
4.97 +
4.98 +\dontinclude topological_ordering.cc
4.99 +First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
4.100 +will be done through it.
4.101 +\skip SerializingWriteMap
4.102 +\until };
4.103 +The class meets the \ref lemon::WriteMap "WriteMap" concept. In it's \c set() method the only thing
4.104 +we need to do is insert the key - that is the node who's processing just finished - into the beginning
4.105 +of the list.
4.106 +
4.107 +First we declare the needed data structures: the graph and a map to store the nodes' label.
4.108 +\skip ListGraph
4.109 +\until label
4.110 +
4.111 +Now we build a graph. But keep in mind that it must be DAG because cyclic graphs has no topological
4.112 +ordering.
4.113 +\skip belt
4.114 +\until trousers
4.115 +We label them...
4.116 +\skip label
4.117 +\until trousers
4.118 +Then add directed edges which represent the precedences between those items.
4.119 +\skip trousers, belt
4.120 +\until );
4.121 +
4.122 +See how easy is to access the internal information of this algorithm trough maps.
4.123 +We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
4.124 +\skip Dfs
4.125 +\until run
4.126 +
4.127 +And now comes the third part. Write out the list in reverse order. But the list was
4.128 +composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
4.129 +\skip std
4.130 +\until endl
4.131 +
4.132 +The program is to be found in the \ref demo directory: \ref topological_ordering.cc
4.133 */
4.134 +}
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/doc/lemon_file_format.dox Thu Sep 14 19:11:24 2006 +0000
5.3 @@ -0,0 +1,270 @@
5.4 +namespace lemon {
5.5 +/*!
5.6 +
5.7 +
5.8 +\page lemon_file_format LEMON Graph File Format
5.9 +
5.10 +The standard graph IO enables one to store graphs and additional maps
5.11 +(i.e. functions on the nodes or edges) in a flexible and efficient way.
5.12 +Before you read this page you should be familiar with LEMON
5.13 +\ref graphs "graphs" and \ref maps-page "maps".
5.14 +
5.15 +\section format The general file format
5.16 +
5.17 +The file contains sections in the following order:
5.18 +
5.19 +\li nodeset
5.20 +\li edgeset
5.21 +\li nodes
5.22 +\li edges
5.23 +\li attributes
5.24 +
5.25 +Some of these sections can be omitted, but you will basicly need the nodeset
5.26 +section (unless your graph has no nodes at all) and the edgeset section
5.27 +(unless your graph has no edges at all).
5.28 +
5.29 +The nodeset section describes the nodes of your graph: it identifies the nodes
5.30 +and gives the maps defined on them, if any. It starts with the
5.31 +following line:
5.32 +
5.33 +<tt>\@nodeset</tt>
5.34 +
5.35 +The next line contains the names of the nodemaps, separated by whitespaces. Each
5.36 +following line describes a node in the graph: it contains the values of the
5.37 +maps in the right order. The map named "label" should contain unique values
5.38 +because it is regarded as a label map. These labels need not be numbers but they
5.39 +must identify the nodes uniquely for later reference. For example:
5.40 +
5.41 +\code
5.42 +@nodeset
5.43 +label x-coord y-coord color
5.44 +3 1.0 4.0 blue
5.45 +5 2.3 5.7 red
5.46 +12 7.8 2.3 green
5.47 +\endcode
5.48 +
5.49 +The edgeset section is very similar to the nodeset section, it has
5.50 +the same coloumn oriented structure. It starts with the line
5.51 +
5.52 +<tt>\@edgeset</tt>
5.53 +
5.54 +The next line contains the whitespace separated list of names of the edge
5.55 +maps. Each of the next lines describes one edge. The first two elements in
5.56 +the line are the labels of the source and target (or tail and head) nodes of the
5.57 +edge as they occur in the label node map of the nodeset section. You can also
5.58 +have an optional label map on the edges for later reference (which has to be
5.59 +unique in this case).
5.60 +
5.61 +\code
5.62 +@edgeset
5.63 + label weight note
5.64 +3 5 a 4.3 a-edge
5.65 +5 12 c 2.6 c-edge
5.66 +3 12 g 3.4 g-edge
5.67 +\endcode
5.68 +
5.69 +The \e nodes section contains <em>labeled (distinguished) nodes</em>
5.70 +(i.e. nodes having a special
5.71 +label on them). The section starts with
5.72 +
5.73 +<tt> \@nodes </tt>
5.74 +
5.75 +Each of the next lines contains a label for a node in the graph
5.76 +and then the label as described in the \e nodeset section.
5.77 +
5.78 +\code
5.79 +@nodes
5.80 +source 3
5.81 +target 12
5.82 +\endcode
5.83 +
5.84 +The last section describes the <em>labeled (distinguished) edges</em>
5.85 +(i.e. edges having a special label on them). It starts with \c \@edges
5.86 +and then each line contains the name of the edge and the label.
5.87 +
5.88 +\code
5.89 +@edges
5.90 +observed c
5.91 +\endcode
5.92 +
5.93 +
5.94 +The file may contain empty lines and comment lines. The comment lines
5.95 +start with an \c # character.
5.96 +
5.97 +The attributes section can handle some information about the graph. It
5.98 +contains key-value pairs in each line (a key and the mapped value to key). The
5.99 +key should be a string without whitespaces, the value can be of various types.
5.100 +
5.101 +\code
5.102 +@attributes
5.103 +title "Four colored planar graph"
5.104 +author "Balazs DEZSO"
5.105 +copyright "Lemon Library"
5.106 +version 12
5.107 +\endcode
5.108 +
5.109 +Finally, the file should be closed with \c \@end line.
5.110 +
5.111 +
5.112 +\section use Using graph input-output
5.113 +
5.114 +
5.115 +The graph input and output is based on <em> reading and writing
5.116 +commands</em>. The user gives reading and writing commands to the reader or
5.117 +writer class, then he calls the \c run() method that executes all the given
5.118 +commands.
5.119 +
5.120 +\subsection write Writing a graph
5.121 +
5.122 +The \ref lemon::GraphWriter "GraphWriter" template class
5.123 +provides the graph output. To write a graph
5.124 +you should first give writing commands to the writer. You can declare
5.125 +writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
5.126 +Edge writing.
5.127 +
5.128 +\code
5.129 +GraphWriter<ListGraph> writer(std::cout, graph);
5.130 +\endcode
5.131 +
5.132 +The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()"
5.133 +function declares a \c NodeMap writing command in the
5.134 +\ref lemon::GraphWriter "GraphWriter".
5.135 +You should give a name to the map and the map
5.136 +object as parameters. The NodeMap writing command with name "label" should write a
5.137 +unique map because it will be regarded as a label map.
5.138 +
5.139 +\see IdMap, DescriptorMap
5.140 +
5.141 +\code
5.142 +IdMap<ListGraph, Node> nodeLabelMap;
5.143 +writer.writeNodeMap("label", nodeLabelMap);
5.144 +
5.145 +writer.writeNodeMap("x-coord", xCoordMap);
5.146 +writer.writeNodeMap("y-coord", yCoordMap);
5.147 +writer.writeNodeMap("color", colorMap);
5.148 +\endcode
5.149 +
5.150 +With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
5.151 +member function you can give an edge map
5.152 +writing command similar to the NodeMaps.
5.153 +
5.154 +\see IdMap, DescriptorMap
5.155 +
5.156 +\code
5.157 +DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
5.158 +writer.writeEdgeMap("descriptor", edgeDescMap);
5.159 +
5.160 +writer.writeEdgeMap("weight", weightMap);
5.161 +writer.writeEdgeMap("note", noteMap);
5.162 +\endcode
5.163 +
5.164 +With \ref lemon::GraphWriter::writeNode() "writeNode()"
5.165 +and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
5.166 +functions you can designate Nodes and
5.167 +Edges in the graph. For example, you can write out the source and target node
5.168 +of a maximum flow instance.
5.169 +
5.170 +\code
5.171 +writer.writeNode("source", sourceNode);
5.172 +writer.writeNode("target", targetNode);
5.173 +
5.174 +writer.writeEdge("observed", edge);
5.175 +\endcode
5.176 +
5.177 +With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
5.178 +function you can write an attribute to the file.
5.179 +
5.180 +\code
5.181 +writer.writeAttribute("author", "Balazs DEZSO");
5.182 +writer.writeAttribute("version", 12);
5.183 +\endcode
5.184 +
5.185 +After you give all write commands you must call the
5.186 +\ref lemon::GraphWriter::run() "run()" member
5.187 +function, which executes all the writing commands.
5.188 +
5.189 +\code
5.190 +writer.run();
5.191 +\endcode
5.192 +
5.193 +\subsection reading Reading a graph
5.194 +
5.195 +The file to be read may contain several maps and labeled nodes or edges.
5.196 +If you read a graph you need not read all the maps and items just those
5.197 +that you need. The interface of the \ref lemon::GraphReader "GraphReader"
5.198 +is very similar to
5.199 +the \ref lemon::GraphWriter "GraphWriter"
5.200 +but the reading method does not depend on the order of the
5.201 +given commands.
5.202 +
5.203 +The reader object assumes that each not read value does not contain
5.204 +whitespaces, therefore it has some extra possibilities to control how
5.205 +it should skip the values when the string representation contains spaces.
5.206 +
5.207 +\code
5.208 +GraphReader<ListGraph> reader(std::cin, graph);
5.209 +\endcode
5.210 +
5.211 +The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
5.212 +function reads a map from the \c nodeset section.
5.213 +If there is a map that you do not want to read from the file and there are
5.214 +whitespaces in the string represenation of the values then you should
5.215 +call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
5.216 +template member function with proper parameters.
5.217 +
5.218 +\see QuotedStringReader
5.219 +
5.220 +\code
5.221 +reader.readNodeMap("x-coord", xCoordMap);
5.222 +reader.readNodeMap("y-coord", yCoordMap);
5.223 +
5.224 +reader.readNodeMap<QuotedStringReader>("label", labelMap);
5.225 +reader.skipNodeMap<QuotedStringReader>("description");
5.226 +
5.227 +reader.readNodeMap("color", colorMap);
5.228 +\endcode
5.229 +
5.230 +With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
5.231 +member function you can give an edge map
5.232 +reading command similar to the NodeMaps.
5.233 +
5.234 +\code
5.235 +reader.readEdgeMap("weight", weightMap);
5.236 +reader.readEdgeMap("label", labelMap);
5.237 +\endcode
5.238 +
5.239 +With \ref lemon::GraphReader::readNode() "readNode()"
5.240 +and \ref lemon::GraphReader::readEdge() "readEdge()"
5.241 +functions you can read labeled Nodes and
5.242 +Edges.
5.243 +
5.244 +\code
5.245 +reader.readNode("source", sourceNode);
5.246 +reader.readNode("target", targetNode);
5.247 +
5.248 +reader.readEdge("observed", edge);
5.249 +\endcode
5.250 +
5.251 +With \ref lemon::GraphReader::readAttribute() "readAttribute()"
5.252 +function you can read an attribute from the file.
5.253 +
5.254 +\code
5.255 +std::string author;
5.256 +writer.readAttribute("author", author);
5.257 +int version;
5.258 +writer.writeAttribute("version", version);
5.259 +\endcode
5.260 +
5.261 +After you give all read commands you must call the
5.262 +\ref lemon::GraphReader::run() "run()" member
5.263 +function, which executes all the commands.
5.264 +
5.265 +\code
5.266 +reader.run();
5.267 +\endcode
5.268 +
5.269 +If you want to lear more, read the \ref read_write_bg "background technics".
5.270 +
5.271 +\author Balazs Dezso
5.272 +*/
5.273 +}
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/doc/read_write_bg.dox Thu Sep 14 19:11:24 2006 +0000
6.3 @@ -0,0 +1,219 @@
6.4 +namespace lemon {
6.5 +/*!
6.6 +\page read_write_bg Background of Reading and Writing
6.7 +
6.8 +To read a map (on the nodes or edges)
6.9 +the \ref lemon::GraphReader "GraphReader"
6.10 +should know how to read a Value from the given map.
6.11 +By the default implementation the input operator reads a value from
6.12 +the stream and the type of the read value is the value type of the given map.
6.13 +When the reader should skip a value in the stream, because you do not
6.14 +want to store it in a map, the reader skips a character sequence without
6.15 +whitespaces.
6.16 +
6.17 +If you want to change the functionality of the reader, you can use
6.18 +template parameters to specialize it. When you give a reading
6.19 +command for a map you can give a Reader type as template parameter.
6.20 +With this template parameter you can control how the Reader reads
6.21 +a value from the stream.
6.22 +
6.23 +The reader has the next structure:
6.24 +\code
6.25 +struct TypeReader {
6.26 + typedef TypeName Value;
6.27 +
6.28 + void read(std::istream& is, Value& value);
6.29 +};
6.30 +\endcode
6.31 +
6.32 +For example, the \c "strings" nodemap contains strings and you do not need
6.33 +the value of the string just the length. Then you can implement an own Reader
6.34 +struct.
6.35 +
6.36 +\code
6.37 +struct LengthReader {
6.38 + typedef int Value;
6.39 +
6.40 + void read(std::istream& is, Value& value) {
6.41 + std::string tmp;
6.42 + is >> tmp;
6.43 + value = tmp.length();
6.44 + }
6.45 +};
6.46 +...
6.47 +reader.readNodeMap<LengthReader>("strings", lengthMap);
6.48 +\endcode
6.49 +
6.50 +The global functionality of the reader class can be changed by giving a
6.51 +special template parameter to the GraphReader class. By default, the
6.52 +template parameter is \c DefaultReaderTraits. A reader traits class
6.53 +should provide a nested template class Reader for each type, and a
6.54 +DefaultReader for skipping a value.
6.55 +
6.56 +The specialization of writing is very similar to that of reading.
6.57 +
6.58 +\section u Undirected graphs
6.59 +
6.60 +In a file describing an undirected graph (ugraph, for short) you find an
6.61 +\c uedgeset section instead of the \c edgeset section. The first line of
6.62 +the section describes the names of the maps on the undirected egdes and all
6.63 +next lines describe one undirected edge with the the incident nodes and the
6.64 +values of the map.
6.65 +
6.66 +The format handles directed edge maps as a syntactical sugar???, if there
6.67 +are two maps with names being the same with a \c '+' and a \c '-' prefix
6.68 +then this will be read as a directed map.
6.69 +
6.70 +\code
6.71 +@uedgeset
6.72 + label capacity +flow -flow
6.73 +32 2 1 4.3 2.0 0.0
6.74 +21 21 5 2.6 0.0 2.6
6.75 +21 12 8 3.4 0.0 0.0
6.76 +\endcode
6.77 +
6.78 +The \c edges section is changed to \c uedges section. This section
6.79 +describes labeled edges and undirected edges. The directed edge label
6.80 +should start with a \c '+' or a \c '-' prefix to decide the direction
6.81 +of the edge.
6.82 +
6.83 +\code
6.84 +@uedges
6.85 +uedge 1
6.86 ++edge 5
6.87 +-back 5
6.88 +\endcode
6.89 +
6.90 +There are similar classes to the \ref lemon::GraphReader "GraphReader" and
6.91 +\ref lemon::GraphWriter "GraphWriter" which
6.92 +handle the undirected graphs. These classes are
6.93 +the \ref lemon::UGraphReader "UGraphReader"
6.94 +and \ref lemon::UGraphWriter "UGraphWriter".
6.95 +
6.96 +The \ref lemon::UGraphReader::readUEdgeMap() "readUEdgeMap()"
6.97 +function reads an undirected map and the
6.98 +\ref lemon::UGraphReader::readUEdge() "readUEdge()"
6.99 +reads an undirected edge from the file,
6.100 +
6.101 +\code
6.102 +reader.readUEdgeMap("capacity", capacityMap);
6.103 +reader.readEdgeMap("flow", flowMap);
6.104 +...
6.105 +reader.readUEdge("u_edge", u_edge);
6.106 +reader.readEdge("edge", edge);
6.107 +\endcode
6.108 +
6.109 +\section advanced Advanced features
6.110 +
6.111 +The graph reader and writer classes give an easy way to read and write
6.112 +graphs. But sometimes we want more advanced features. In this case we can
6.113 +use the more general <tt>lemon reader and writer</tt> interface.
6.114 +
6.115 +The LEMON file format is a section oriented file format. It contains one or
6.116 +more sections, each starting with a line identifying its type
6.117 +(the word starting with the \c \@ character).
6.118 +The content of the section this way cannot contain line with \c \@ first
6.119 +character. The file may contains comment lines with \c # first character.
6.120 +
6.121 +The \ref lemon::LemonReader "LemonReader"
6.122 +and \ref lemon::LemonWriter "LemonWriter"
6.123 +gives a framework to read and
6.124 +write sections. There are various section reader and section writer
6.125 +classes which can be attached to a \ref lemon::LemonReader "LemonReader"
6.126 +or a \ref lemon::LemonWriter "LemonWriter".
6.127 +
6.128 +There are default section readers and writers for reading and writing
6.129 +item sets, and labeled items in the graph. These read and write
6.130 +the format described above. Other type of data can be handled with own
6.131 +section reader and writer classes which are inherited from the
6.132 +\c LemonReader::SectionReader or the
6.133 +\ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
6.134 +classes.
6.135 +
6.136 +The next example defines a special section reader which reads the
6.137 +\c \@description sections into a string:
6.138 +
6.139 +\code
6.140 +class DescriptionReader : LemonReader::SectionReader {
6.141 +protected:
6.142 + virtual bool header(const std::string& line) {
6.143 + std::istringstream ls(line);
6.144 + std::string head;
6.145 + ls >> head;
6.146 + return head == "@description";
6.147 + }
6.148 +
6.149 + virtual void read(std::istream& is) {
6.150 + std::string line;
6.151 + while (getline(is, line)) {
6.152 + desc += line;
6.153 + }
6.154 + }
6.155 +public:
6.156 +
6.157 + typedef LemonReader::SectionReader Parent;
6.158 +
6.159 + DescriptionReader(LemonReader& reader) : Parent(reader) {}
6.160 +
6.161 + const std::string& description() const {
6.162 + return description;
6.163 + }
6.164 +
6.165 +private:
6.166 + std::string desc;
6.167 +};
6.168 +\endcode
6.169 +
6.170 +The other advanced stuff of the generalized file format is that
6.171 +multiple edgesets can be stored to the same nodeset. It can be used
6.172 +for example as a network traffic matrix.
6.173 +
6.174 +In our example there is a network with symmetric links and there are assymetric
6.175 +traffic request on the network. This construction can be stored in an
6.176 +undirected graph and in a directed \c ListEdgeSet class. The example
6.177 +shows the input with the \ref lemon::LemonReader "LemonReader" class:
6.178 +
6.179 +\code
6.180 +ListUGraph network;
6.181 +ListUGraph::UEdgeMap<double> capacity;
6.182 +ListEdgeSet<ListUGraph> traffic(network);
6.183 +ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
6.184 +
6.185 +LemonReader reader(std::cin);
6.186 +NodeSetReader<ListUGraph> nodesetReader(reader, network);
6.187 +UEdgeSetReader<ListUGraph>
6.188 + uEdgesetReader(reader, network, nodesetReader);
6.189 +uEdgesetReader.readEdgeMap("capacity", capacity);
6.190 +EdgeSetReader<ListEdgeSet<ListUGraph> >
6.191 + edgesetReader(reader, traffic, nodesetReader, "traffic");
6.192 +edgesetReader.readEdgeMap("request", request);
6.193 +
6.194 +reader.run();
6.195 +\endcode
6.196 +
6.197 +Because both the \ref lemon::GraphReader "GraphReader"
6.198 +and the \ref lemon::UGraphReader "UGraphReader" can be converted
6.199 +to \ref lemon::LemonReader "LemonReader"
6.200 +and it can resolve the label's of the items, the previous
6.201 +result can be achived with the \ref lemon::UGraphReader "UGraphReader"
6.202 +class, too.
6.203 +
6.204 +
6.205 +\code
6.206 +ListUGraph network;
6.207 +ListUGraph::UEdgeSet<double> capacity;
6.208 +ListEdgeSet<ListUGraph> traffic(network);
6.209 +ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
6.210 +
6.211 +UGraphReader<ListUGraph> reader(std::cin, network);
6.212 +reader.readEdgeMap("capacity", capacity);
6.213 +EdgeSetReader<ListEdgeSet<ListUGraph> >
6.214 + edgesetReader(reader, traffic, reader, "traffic");
6.215 +edgesetReader.readEdgeMap("request", request);
6.216 +
6.217 +reader.run();
6.218 +\endcode
6.219 +
6.220 +\author Balazs Dezso
6.221 +*/
6.222 +}
7.1 --- a/doc/tutorial.dox Thu Sep 14 19:02:52 2006 +0000
7.2 +++ b/doc/tutorial.dox Thu Sep 14 19:11:24 2006 +0000
7.3 @@ -1,3 +1,4 @@
7.4 +namespace lemon {
7.5 /**
7.6 \page Tutorial LEMON Tutorial
7.7
7.8 @@ -15,24 +16,27 @@
7.9 <LI>\ref basic_ListGraph
7.10 <LI>\ref maps1
7.11 </UL>
7.12 - <LI><A href="#file">Lemon Graph File Format</A>
7.13 + <LI>\ref lemon_file_format
7.14 + <UL>
7.15 + <LI>\ref read_write_bg
7.16 + </UL>
7.17 <LI>\ref algorithms
7.18 <UL>
7.19 - <LI><A href="#bfs_dfs">Bfs/Dfs</A>
7.20 - <LI><A href="#dijkstra">Dijkstra</A>
7.21 - <LI><A href="#kruskal">Kruskal</A>
7.22 + <LI>\ref algo_bfs_dfs
7.23 + <LI>Dijkstra
7.24 + <LI>Kruskal
7.25 </UL>
7.26 <LI>\ref maps2
7.27 <UL>
7.28 <LI>\ref custom_maps
7.29 - <LI><A href="#map_adaptors">Map Adaptors</A>
7.30 - <LI><A href="#special_maps">Special Purpose Maps</a>
7.31 + <LI>Map Adaptors
7.32 + <LI>Special Purpose Maps
7.33 </UL>
7.34 - <LI><A href="#show">Show a graph</A>
7.35 - <LI><A href="#misc">Miscellaneous Tool</A>
7.36 + <LI>Show a graph
7.37 + <LI>Miscellaneous Tool
7.38 <UL>
7.39 - <LI><A href="#lp">LP solver</A>
7.40 - <LI><A href="#simann">Simulated Annealing</A>
7.41 + <LI>LP solver
7.42 + <LI>Simulated Annealing
7.43 </UL>
7.44 </OL>
7.45
7.46 @@ -42,3 +46,4 @@
7.47 are all available in \c demo directory, so feel free to look at them after the
7.48 sections.
7.49 */
7.50 +}