COIN-OR::LEMON - Graph Library

Changeset 1540:7d028a73d7f2 in lemon-0.x for doc


Ignore:
Timestamp:
07/05/05 16:36:10 (19 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2034
Message:

Documented Balazs's stuff. Quite enough of that.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/graph_io.dox

    r1532 r1540  
    55\page graph-io-page Graph Input-Output
    66
    7 The standard graph IO enables to store graphs and additional maps
    8 in a flexible and efficient way.
     7The standard graph IO enables one to store graphs and additional maps
     8(i.e. functions on the nodes or edges) in a flexible and efficient way.
     9Before you read this page you should be familiar with LEMON
     10\ref graphs "graphs" and \ref maps-page "maps".
    911
    1012\section format The general file format
     
    1820\li attributes
    1921
    20 The nodeset section starts with the following line:
     22Some of these sections can be omitted, but you will basicly need the nodeset
     23section (unless your graph has no nodes at all) and the edgeset section
     24(unless your graph has no edges at all).
     25
     26The nodeset section describes the nodes of your graph: it identifies the nodes
     27and gives the maps defined on them, if any. It starts with the
     28following line:
    2129
    2230<tt>\@nodeset</tt>
     
    2533following line describes a node in the graph: it contains the values of the
    2634maps in the right order. The map named "id" should contain unique values
    27 because it is regarded as an ID-map. For example:
     35because it is regarded as an ID-map. These ids need not be numbers but they
     36must identify the nodes uniquely for later reference. For example:
    2837
    2938\code
     
    4049<tt>\@edgeset</tt>
    4150
    42 The next line contains the whitespace separated list of names of the maps.
    43 Each of the next lines describes one edge. The first two elements in the line
    44 are the IDs of the source and target (or tail and head) node of the edge as they occur in the ID node
    45 map. You can also have an optional ID map on the edges for later reference.
     51The next line contains the whitespace separated list of names of the edge
     52maps.  Each of the next lines describes one edge. The first two elements in
     53the line are the IDs of the source and target (or tail and head) nodes of the
     54edge as they occur in the ID node map of the nodeset section. You can also
     55have an optional ID map on the edges for later reference (which has to be
     56unique in this case).
    4657
    4758\code
     
    5364\endcode
    5465
    55 The next section contains <em>labeled nodes</em> (i.e. nodes having a special
     66The \e nodes section contains <em>labeled (distinguished) nodes</em>
     67(i.e. nodes having a special
    5668label on them). The section starts with
    5769
     
    5971
    6072Each of the next lines contains a label for a node in the graph
    61 and then the ID described in the nodeset section.
     73and then the ID as described in the \e nodeset section.
    6274
    6375\code
     
    6779\endcode
    6880
    69 The last section describes the <em>labeled edges</em>
     81The last section describes the <em>labeled (distinguished) edges</em>
    7082(i.e. edges having a special label on them). It starts with \c \@edges
    7183and then each line contains the name of the edge and the ID.
    7284
    7385\code
    74 @nodes
     86@edges
    7587observed c
    7688\endcode
     
    8193
    8294The attributes section can handle some information about the graph. It
    83 contains in each line an key and the mapped value to key. The key should
    84 be a string without whitespace, the value can be from various type.
     95contains key-value pairs in each line (a key and the mapped value to key). The
     96key should be a string without whitespaces, the value can be of various types.
    8597
    8698\code
     
    92104\endcode
    93105
    94 \code
    95 @end
    96 \endcode
    97 =======
    98 The file ends with the
    99 
    100106<tt> \@end </tt>
    101107
     
    104110
    105111\section use Using graph input-output
    106 The graph input and output is based on reading and writing  commands. The user
    107 adds reading and writing commands to the reader or writer class, then he
    108 calls the \c run() method that executes all the given commands.
     112
     113The easiest way of using graph input and output is using the versions of the
     114  public \ref readGraph() and \ref writeGraph() functions; if you don't need
     115  very sophisticated behaviour then you might be satisfied with
     116  those. Otherwise go on reading this page.
     117
     118The graph input and output is based on <em> reading and writing
     119commands</em>. The user gives reading and writing commands to the reader or
     120writer class, then he calls the \c run() method that executes all the given
     121commands.
    109122
    110123\subsection write Writing a graph
     
    112125The \c GraphWriter class provides the graph output. To write a graph
    113126you should first give writing commands to the writer. You can declare
    114 write command as \c NodeMap or \c EdgeMap writing and labeled Node and
     127writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
    115128Edge writing.
    116129
     
    120133
    121134The \c writeNodeMap() function declares a \c NodeMap writing command in the
    122 \c GraphWriter. You should give a name of the map and the map
     135\c GraphWriter. You should give a name to the map and the map
    123136object as parameters. The NodeMap writing command with name "id" should write a
    124 unique map because it is regarded as ID map.
     137unique map because it will be regarded as an ID map.
    125138
    126139\see IdMap, DescriptorMap 
     
    175188\subsection reading Reading a graph
    176189
    177 The given file format may contain several maps and labeled nodes or edges.
     190The file to be read may contain several maps and labeled nodes or edges.
    178191If you read a graph you need not read all the maps and items just those
    179192that you need. The interface of the \c GraphReader is very similar to
     
    189202\endcode
    190203
    191 The \c readNodeMap() function reads a map from the \c \@nodeset section.
     204The \c readNodeMap() function reads a map from the \c nodeset section.
    192205If there is a map that you do not want to read from the file and there are
    193206whitespaces in the string represenation of the values then you should
     
    240253\endcode
    241254
     255\anchor rwbackground
    242256\section types Background of Reading and Writing
     257
     258
    243259To read a map (on the nodes or edges)
    244260the \c GraphReader should know how to read a Value from the given map.
     
    247263When the reader should skip a value in the stream, because you do not
    248264want to store it in a map, the reader skips a character sequence without
    249 whitespace.
     265whitespaces.
    250266
    251267If you want to change the functionality of the reader, you can use
     
    265281
    266282For example, the \c "strings" nodemap contains strings and you do not need
    267 the value of the string just the length. Then you can implement own Reader
     283the value of the string just the length. Then you can implement an own Reader
    268284struct.
    269285
     
    285301special template parameter to the GraphReader class. By default, the
    286302template parameter is \c DefaultReaderTraits. A reader traits class
    287 should provide an inner template class Reader for each type, and an
     303should provide an inner template class Reader for each type, and a
    288304DefaultReader for skipping a value.
    289305
    290 The specialization of  writing should be very similar to that of reading.
    291 
    292 \section undir Undir graphs
    293 
    294 In the undir graph format there is an \c undiredgeset section instead of
    295 the \c edgeset section. The first line of the section describes the
    296 undirected egdes' names and all next lines describes one undirected edge
    297 with the the incident nodes and the values of the map.
    298 
    299 The format handles the directed edge maps as a syntactical sugar, if there
    300 is two map which names are the same with a \c '+' and a \c '-' prefix
    301 then it can be read as an directed map.
     306The specialization of  writing is very similar to that of reading.
     307
     308\section undir Undirected graphs
     309
     310In a file describing an undirected graph (undir graph, for short) you find an
     311\c undiredgeset section instead of the \c edgeset section. The first line of
     312the section describes the names of the maps on the undirected egdes and all
     313next lines describe one undirected edge with the the incident nodes and the
     314values of the map.
     315
     316The format handles directed edge maps as a syntactical sugar???, if there
     317are two maps with names being the same with a \c '+' and a \c '-' prefix
     318then this will be read as a directed map.
    302319
    303320\code
     
    309326\endcode
    310327
    311 The \c edges section changed to \c undiredges section. This section
     328The \c edges section is changed to \c undiredges section. This section
    312329describes labeled edges and undirected edges. The directed edge label
    313 should start with a \c '+' and a \c '-' prefix what decide the direction
     330should start with a \c '+' or a \c '-' prefix to decide the direction
    314331of the edge.
    315332
     
    338355\section advanced Advanced features
    339356
    340 The graph reader and writer classes gives an easy way to read and write
    341 graphs. But sometimes we want more advanced features. This way we can
    342 use the more general lemon reader and writer interface.
    343 
    344 The lemon format is an section oriented file format. It contains one or
    345 more section, each starts with a line with \c \@ first character.
     357The graph reader and writer classes give an easy way to read and write
     358graphs. But sometimes we want more advanced features. In this case we can
     359use the more general <tt>lemon reader and writer</tt> interface.
     360
     361The LEMON file format is a section oriented file format. It contains one or
     362more sections, each starting with a line identifying its type
     363(the word starting with the \c \@  character).
    346364The content of the section this way cannot contain line with \c \@ first
    347365character. The file may contains comment lines with \c # first character.
     
    352370
    353371There are default section readers and writers for reading and writing
    354 item sets, and labeled items in the graph. These reads and writes
     372item sets, and labeled items in the graph. These read and write
    355373the format described above. Other type of data can be handled with own
    356374section reader and writer classes which are inherited from the
     
    393411The other advanced stuff of the generalized file format is that
    394412multiple edgesets can be stored to the same nodeset. It can be used
    395 by example as a network traffic matrix.
    396 
    397 In example there is a network with symmetric links and there are assymetric
     413for example as a network traffic matrix.
     414
     415In our example there is a network with symmetric links and there are assymetric
    398416traffic request on the network. This construction can be stored in an
    399 undirected graph and in an directed NewEdgeSetAdaptor class. The example
     417undirected graph and in a directed NewEdgeSetAdaptor class. The example
    400418shows the input with the LemonReader class:
    401419
     
    418436Because the GraphReader and the UndirGraphReader can be converted
    419437to LemonReader and it can resolve the ID's of the items, the previous
    420 result can be achived with the UndirGraphReader class also.
     438result can be achived with the UndirGraphReader class, too.
    421439
    422440
Note: See TracChangeset for help on using the changeset viewer.