COIN-OR::LEMON - Graph Library

Changeset 1522:321661278137 in lemon-0.x for doc


Ignore:
Timestamp:
06/28/05 19:46:35 (14 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2008
Message:

Some corrections to graph_io.dox (mainly language corrections). Improvements on quicktour.

Location:
doc
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/graph_io.dox

    r1394 r1522  
    55\page graph-io-page Graph Input-Output
    66
    7 The standard graph IO makes possible to store graphs and additional maps
     7The standard graph IO enables to store graphs and additional maps
    88in a flexible and efficient way.
    99
    1010\section format The general file format
    1111
    12 The graph file contains at most four section in the next order:
     12The file contains at most four sections in the following order:
    1313
    1414\li nodeset
     
    1717\li edges
    1818
    19 The nodeset section starts with the \c \@nodeset line.
    20 The next line contains the names of the maps separated by whitespaces.
    21 Each following line describes a node in the graph, it contains
    22 in the right order the values of the maps. The map named "id" should contain
    23 unique values because it regarded as ID-map.
     19The nodeset section starts with the following line:
     20
     21<tt>\@nodeset</tt>
     22
     23The next line contains the names of the nodemaps, separated by whitespaces.  Each
     24following line describes a node in the graph: it contains the values of the
     25maps in the right order. The map named "id" should contain unique values
     26because it is regarded as an ID-map. For example:
    2427
    2528\code
     
    3235
    3336The edgeset section is very similar to the nodeset section, it has
    34 same coloumn oriented structure. It starts with the line \c \@edgeset
    35 The next line contains the whitespace separated list of names of the map.
     37the same coloumn oriented structure. It starts with the line
     38
     39<tt>\@edgeset</tt>
     40
     41The next line contains the whitespace separated list of names of the maps.
    3642Each of the next lines describes one edge. The first two elements in the line
    37 are the ID of the source and target node as they occur in the ID node map.
     43are the IDs of the source and target (or tail and head) node of the edge as they occur in the ID node
     44map. You can also have an optional ID map on the edges for later reference.
    3845
    3946\code
     
    4754The next section contains <em>labeled nodes</em> (i.e. nodes having a special
    4855label on them). The section starts with
    49 \c \@nodes. Each of the next lines contains a label for a node in the graph
    50 and then the ID described in the nodeset.
     56
     57<tt> \@nodes </tt>
     58
     59Each of the next lines contains a label for a node in the graph
     60and then the ID described in the nodeset section.
    5161
    5262\code
     
    6575\endcode
    6676
    67 The file ends with the \c \@end line.
    6877
    6978The file may contain empty lines and comment lines. The comment lines
    7079start with an \c # character.
    7180
    72 \code
    73 @end
    74 \endcode
     81The file ends with the
     82
     83<tt> \@end </tt>
     84
     85line.
     86
    7587
    7688\section use Using graph input-output
    77 The graph input and output based on writing and reading commands. The user
    78 adds writing and reading commands for the reader or writer class, then
     89The graph input and output is based on reading and writing commands. The user
     90adds reading and writing commands to the reader or writer class, then he
    7991calls the \c run() method that executes all the given commands.
    8092
     
    91103
    92104The \c writeNodeMap() function declares a \c NodeMap writing command in the
    93 \c GraphWriter. You should give as parameter the name of the map and the map
    94 object. The NodeMap writing command with name "id" should write a
     105\c GraphWriter. You should give a name of the map and the map
     106object as parameters. The NodeMap writing command with name "id" should write a
    95107unique map because it is regarded as ID map.
    96108
     
    110122
    111123\see IdMap, DescriptorMap 
     124
    112125\code
    113126DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
     
    118131\endcode
    119132
    120 With \c writeNode() and \c writeEdge() functions you can point out Nodes and
    121 Edges in the graph. By example, you can write out the source and target
    122 of the graph.
     133With \c writeNode() and \c writeEdge() functions you can designate Nodes and
     134Edges in the graph. For example, you can write out the source and target node
     135of a maximum flow instance.
    123136
    124137\code
     
    130143
    131144After you give all write commands you must call the \c run() member
    132 function, which execute all the writer commands.
     145function, which executes all the writing commands.
    133146
    134147\code
     
    141154If you read a graph you need not read all the maps and items just those
    142155that you need. The interface of the \c GraphReader is very similar to
    143 the GraphWriter but the reading method does not depend on the order the
     156the GraphWriter but the reading method does not depend on the order of the
    144157given commands.
    145158
    146 The reader object suppose that each not readed value does not contain
     159The reader object assumes that each not readed value does not contain
    147160whitespaces, therefore it has some extra possibilities to control how
    148161it should skip the values when the string representation contains spaces.
     
    153166
    154167The \c readNodeMap() function reads a map from the \c \@nodeset section.
    155 If there is a map that you do not want to read from the file and there is
    156 whitespace in the string represenation of the values then you should
     168If there is a map that you do not want to read from the file and there are
     169whitespaces in the string represenation of the values then you should
    157170call the \c skipNodeMap() template member function with proper parameters.
    158171
    159172\see QuotedStringReader
     173
    160174\code
    161175reader.readNodeMap("x-coord", xCoordMap);
     
    187201
    188202After you give all read commands you must call the \c run() member
    189 function, which execute all the commands.
     203function, which executes all the commands.
    190204
    191205\code
     
    193207\endcode
    194208
    195 \section types The background of the Reading and Writing
    196 The \c GraphReader should know how can read a Value from the given map.
     209\section types The background of Reading and Writing
     210The \c GraphReader should know how to read a Value from the given map.
    197211By the default implementation the input operator reads a value from
    198212the stream and the type of the readed value is the value type of the given map.
  • doc/quicktour.dox

    r1521 r1522  
    2525Some examples are the following (you will find links next to the code fragments that help to download full demo programs: save them on your computer and compile them according to the description in the page about \ref getsart How to start using LEMON):
    2626
    27 <ul>
    28 <li> First we give two examples that show how to instantiate a graph. The
    29 first one shows the methods that add nodes and edges, but one will
    30 usually use the second way which reads a graph from a stream (file).
    31 <ol>
    32 <li>The following code fragment shows how to fill a graph with data. It creates a complete graph on 4 nodes. The type Listgraph is one of the LEMON graph types: the typedefs in the beginning are for convenience and we will suppose them later as well.
    33  \code
    34   typedef ListGraph Graph;
     27<ul> <li> The first thing to discuss is the way one can create data structures
     28like graphs and maps in a program using LEMON.
     29//There are more graph types
     30//implemented in LEMON and you can implement your own graph type just as well:
     31//read more about this in the already mentioned page on \ref graphs "graphs".
     32
     33First we show how to add nodes and edges to a graph manually. We will also
     34define a map on the edges of the graph. After this we show the way one can
     35read a graph (and perhaps maps on it) from a stream (e.g. a file). Of course
     36we also have routines that write a graph (and perhaps maps) to a stream
     37(file): this will also be shown. LEMON supports the DIMACS file formats to
     38store network optimization problems, but more importantly we also have our own
     39file format that gives a more flexible way to store data related to network
     40optimization.
     41
     42<ol> <li>The following code fragment shows how to fill a graph with
     43data. It creates a complete graph on 4 nodes. The type Listgraph is one of the
     44LEMON graph types: the typedefs in the beginning are for convenience and we
     45will suppose them later as well. 
     46
     47\code
     48
     49  typedef ListGraph Graph;
    3550  typedef Graph::NodeIt NodeIt;
    3651
     
    4358    for (NodeIt j(g); j!=INVALID; ++j)
    4459      if (i != j) g.addEdge(i, j);
    45  \endcode
     60
     61\endcode
    4662
    4763See the whole program in file \ref helloworld.cc.
     
    4965    If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs".
    5066
    51 <li> The following code shows how to read a graph from a stream (e.g. a file). LEMON supports the DIMACS file format: it can read a graph instance from a file
    52 in that format (find the documentation of the DIMACS file format on the web).
     67<li> The following code shows how to read a graph from a stream (e.g. a file)
     68in the DIMACS file format (find the documentation of the DIMACS file formats on the web).
     69
    5370\code
    5471Graph g;
     
    5673readDimacs(f, g);
    5774\endcode
    58 One can also store network (graph+capacity on the edges) instances and other things in DIMACS format and use these in LEMON: to see the details read the documentation of the \ref dimacs.h "Dimacs file format reader".
     75
     76One can also store network (graph+capacity on the edges) instances and other
     77things (minimum cost flow instances etc.) in DIMACS format and use these in LEMON: to see the details read the
     78documentation of the \ref dimacs.h "Dimacs file format reader". There you will
     79also find the details about the output routines into files of the DIMACS
     80format.
     81
     82<li>We needed much greater flexibility than the DIMACS formats could give us,
     83so we worked out our own file format. Instead of any explanation let us give a
     84short example file in this format: read the detailed description of the LEMON
     85graph file format and input-output routines \ref graph-io-page here.
     86
     87So here is a file describing a graph of 10 nodes (0 to 9), two nodemaps
     88(called \c coordinates_x and \c coordinates_y), several edges, an edge map
     89called \c length and two designated nodes (called \c source and \c target).
     90
     91\todo Maybe another example would be better here.
     92
     93\code
     94@nodeset
     95id      coordinates_x   coordinates_y   
     969       447.907 578.328
     978       79.2573 909.464
     987       878.677 960.04 
     996       11.5504 938.413
     1005       327.398 815.035
     1014       427.002 954.002
     1023       148.549 753.748
     1032       903.889 326.476
     1041       408.248 577.327
     1050       189.239 92.5316
     106@edgeset
     107                length 
     1082       3       901.074
     1098       5       270.85 
     1106       9       601.553
     1115       9       285.022
     1129       4       408.091
     1133       0       719.712
     1147       5       612.836
     1150       4       933.353
     1165       0       778.871
     1175       5       0       
     1187       1       664.049
     1195       5       0       
     1200       9       560.464
     1214       8       352.36 
     1224       9       399.625
     1234       1       402.171
     1241       2       591.688
     1253       8       182.376
     1264       5       180.254
     1273       1       345.283
     1285       4       184.511
     1296       2       1112.45
     1300       1       556.624
     131@nodes
     132source  1       
     133target  8       
     134@end
     135\endcode
     136
     137Finally let us give a simple example that reads a graph from a file and writes
     138it to another.
     139
     140\todo This is to be done!
    59141
    60142</ol>
     
    63145usually solved using Dijkstra's algorithm. A utility
    64146that solves this is  the \ref lemon::Dijkstra "LEMON Dijkstra class".
    65 The following code is a simple program using the \ref lemon::Dijkstra "LEMON
    66 Dijkstra class" and it also shows how to define a map on the edges (the length
     147The following code is a simple program using the
     148\ref lemon::Dijkstra "LEMON Dijkstra class" and it also shows how to define a map on the edges (the length
    67149function):
    68150
Note: See TracChangeset for help on using the changeset viewer.