ext/OGDF/ogdf/fileformats/simple_graph_load.h

   1 /*
   2  * $Revision: 2583 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of simple graph loaders.
  11  *
  12  * \author Markus Chimani, Carsten Gutwenger, Karsten Klein
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42 #ifdef _MSC_VER
  43 #pragma once
  44 #endif
  45
  46 #ifndef OGDF_SIMPLE_GRAPH_LOAD_H
  47 #define OGDF_SIMPLE_GRAPH_LOAD_H
  48
  49 #include <ogdf/basic/Graph.h>
  50 #include <ogdf/basic/GridLayout.h>
  51
  52
  53 namespace ogdf {
  54
  55 /** @name Simple graph formats (without layout)
  56  *  These functions load graphs stored in some common, simple text-based file formats. They just read
  57  *  the graph structure and not any layout specific data.
  58  */
  59 ///@{
  60
  61 //! Loads a graph \a G stored in the Rome-Graph-format from an input stream \a is.
  62 /**
  63  * The Rome format contains (in this order) n "node-lines", 1 "separator-line", m "edge-lines".
  64  * These lines are as follows (whereby all IDs are integer numbers):
  65  *  - <b>node-line:</b> <i>NodeId</i> <tt>0</TT>
  66  *  - <b>separator-line:</b> starts with a <tt>#</tt>-sign
  67  *  - <b>edge-line:</b> <i>EdgeId</i> <tt>0</tt> <i>SourceNodeId</i> <i>TargetNodeId</i>
  68  *
  69  * @param G is assigned the loaded graph.
  70  * @param is is the input stream from which the graph is read.
  71  * \return true if the graph was loaded successfully, false otherwise.
  72  *
  73  * \warning
  74  * This is a very simple implementation only usable for very properly formatted files!
  75  */
  76 OGDF_EXPORT bool loadRomeGraph(Graph &G, istream &is);
  77
  78 //! Loads a graph \a G stored in the Rome-Graph-format from a file \a fileName.
  79 /**
  80  * @param G is assigned the loaded graph.
  81  * @param fileName is the name of the file from which the graph is read.
  82  * \return true if the graph was loaded successfully, false otherwise.
  83  *
  84  * \see loadRomeGraph(Graph &, istream&)
  85  */
  86 OGDF_EXPORT bool loadRomeGraph(Graph &G, const char *fileName);
  87
  88 /** \brief Loads a graph \a G stored in the chaco file format from an input stream \a is.
  89  *
  90  * Graphs stored in the chaco file format are typically used in graph partitioning and
  91  * use the file extension .graph.
  92  *
  93  * The first line contains two integers separated by spacing: \#nodes \#edges
  94  * A third entry indicates node and edge weights (not supported here yet).
  95  * Each of the following \#nodes lines from 1 to \#nodes contains the space
  96  * separated index list of the adjacent nodes for the node associated with
  97  * that line (where node indices are from 1 to n).
  98  * Macro SIMPLE_LOAD_BUFFER_SIZE defines the length of the line read buffer
  99  * and should be adjusted according to the maximum read size.
 100  *
 101  * @param G is assigned the loaded graph.
 102  * @param is is the input stream from which the graph is read.
 103  * \return true if the graph was loaded successfully, false otherwise.
 104  */
 105 OGDF_EXPORT bool loadChacoGraph(Graph &G, istream &is);
 106
 107 //! Loads a graph \a G stored in the chaco file format from a file \a fileName.
 108 /**
 109  * @param G is assigned the loaded graph.
 110  * @param fileName is the name of the file from which the graph is read.
 111  * \return true if the graph was loaded successfully, false otherwise.
 112  *
 113  * \see loadChacoGraph(Graph &, istream&)
 114  */
 115 OGDF_EXPORT bool loadChacoGraph(Graph &G, const char *fileName);
 116
 117 //! Loads a graph \a G stored in a simple format from an input stream \a is.
 118 /**
 119  * Simple format has a leading line stating the name of the graph
 120  * and a following line stating the size of the graph.
 121  *
 122  * <pre>
 123  * *BEGIN unknown_name.numN.numE
 124  * *GRAPH numN numE UNDIRECTED UNWEIGHTED
 125  * </pre>
 126  *
 127  * @param G is assigned the loaded graph.
 128  * @param is is the input stream from which the graph is read.
 129  * \return true if the graph was loaded successfully, false otherwise.
 130  * */
 131 OGDF_EXPORT bool loadSimpleGraph(Graph &G, istream &is);
 132
 133 //! Loads a graph \a G stored in a simple format from a file \a fileName.
 134 /**
 135  * This format is used e.g. for the graphs from Petra Mutzel's Ph.D. Thesis.
 136  *
 137  * @param G is assigned the loaded graph.
 138  * @param fileName is the name of the file from which the graph is read.
 139  * \return true if the graph was loaded successfully, false otherwise.
 140  *
 141  * \see loadSimpleGraph(Graph &G, istream &is)
 142  */
 143 OGDF_EXPORT bool loadSimpleGraph(Graph &G, const char *fileName);
 144
 145 //! Loads a graph \a G stored in the Y-graph-format from file stream (one line) \a lineStream.
 146 /**
 147  * This format is e.g. produced by NAUTY (http://www.cs.sunysb.edu/~algorith/implement/nauty/implement.shtml)
 148  *
 149  * Details  on the format, as given in NAUTYs graph generator (see above link):
 150  * "[A] graph occupies one line with a terminating newline.
 151  * Except for the newline, each byte has the format  01xxxxxx, where
 152  * each "x" represents one bit of data.
 153  *
 154  * First byte:  xxxxxx is the number of vertices n
 155  *
 156  * Other ceiling(n(n-1)/12) bytes:  These contain the upper triangle of
 157  * the adjacency matrix in column major order.  That is, the entries
 158  * appear in the order (0,1),(0,2),(1,2),(0,3),(1,3),(2,3),(0,4),... .
 159  * The bits are used in left to right order within each byte.
 160  * Any unused bits on the end are set to zero.
 161  */
 162 OGDF_EXPORT bool loadYGraph(Graph &G, FILE *lineStream);
 163
 164 ///@}
 165
 166 /** @name Simple graph formats (with layout)
 167  *  These functions load and save graphs in some common, simple text-based file formats,
 168  *  which also store layout specific data in some limited way.
 169  */
 170 ///@{
 171
 172 //! Loads a graph \a G with layout \a gl stored in GD-Challenge-format from stream \a is.
 173 /**
 174  * @param G is assigned the loaded graph.
 175  * @param gl is assigned the grid layout.
 176  * @param is is the input stream from which the graph is read.
 177  * \return true if the graph was loaded successfully, false otherwise.
 178  */
 179 OGDF_EXPORT bool loadChallengeGraph(Graph &G, GridLayout &gl, istream &is);
 180
 181 //! Loads a graph \a G with layout \a gl stored in GD-Challenge-format from file \a fileName.
 182 /**
 183  * @param G is assigned the loaded graph.
 184  * @param gl is assigned the grid layout.
 185  * @param fileName is the name of the file from which the graph is read.
 186  * \return true if the graph was loaded successfully, false otherwise.
 187  */
 188 OGDF_EXPORT bool loadChallengeGraph(Graph &G, GridLayout &gl, const char *fileName);
 189
 190 //! Writes graph \a G with layout \a gl in GD-Challenge-format to stream \a os.
 191 /**
 192  * @param G is the graph to be stored.
 193  * @param gl is the grid layout to be stored.
 194  * @param os is the output stream to which the graph is written.
 195  * \return true if the graph was stored successfully, false otherwise.
 196  */
 197 OGDF_EXPORT bool saveChallengeGraph(const Graph &G, const GridLayout &gl, ostream &os);
 198
 199 //! Writes graph \a G with layout \a gl in GD-Challenge-format to file \a fileName.
 200 /**
 201  * @param G is the graph to be stored.
 202  * @param gl is the grid layout to be stored.
 203  * @param fileName is the name of the file to which the graph is written.
 204  * \return true if the graph was stored successfully, false otherwise.
 205  */
 206 OGDF_EXPORT bool saveChallengeGraph(const Graph &G, const GridLayout &gl, const char *fileName);
 207
 208 ///@}
 209
 210 /** @name Simple graph formats (with subgraph)
 211  *  These functions load and store graphs in a simple text-based file format that also specifies
 212  *  a subgraph (given as a list of edges).
 213  */
 214 ///@{
 215
 216 //! Loads graph \a G with subgraph defined by \a delEdges from stream \a is.
 217 /**
 218  * @param G is assigned the loaded graph.
 219  * @param delEdges is assigned the edges of the subgraph.
 220  * @param is is the input stream from which the graph is read.
 221  * \return true if the graph was loaded successfully, false otherwise.
 222  */
 223 OGDF_EXPORT bool loadEdgeListSubgraph(Graph &G, List<edge> &delEdges, istream &is);
 224
 225 //! Loads graph \a G with subgraph defined by \a delEdges from file \a fileName.
 226 /**
 227  * @param G is assigned the loaded graph.
 228  * @param delEdges is assigned the edges of the subgraph.
 229  * @param fileName is the name of the file from which the graph is read.
 230  * \return true if the graph was loaded successfully, false otherwise.
 231  */
 232 OGDF_EXPORT bool loadEdgeListSubgraph(Graph &G, List<edge> &delEdges, const char *fileName);
 233
 234 //! Writes graph \a G with subgraph defined by \a delEdges to stream \a os.
 235 /**
 236  * @param G is the graph to be stored.
 237  * @param delEdges specifies the edges of the subgraph to be stored.
 238  * @param os is the output stream to which the graph is written.
 239  * \return true if the graph was stored successfully, false otherwise.
 240  */
 241 OGDF_EXPORT bool saveEdgeListSubgraph(const Graph &G, const List<edge> &delEdges, ostream &os);
 242
 243 //! Writes graph \a G with subgraph defined by \a delEdges to file \a fileName.
 244 /**
 245  * @param G is the graph to be stored.
 246  * @param delEdges specifies the edges of the subgraph to be stored.
 247  * @param fileName is the name of the file to which the graph is written.
 248  * \return true if the graph was stored successfully, false otherwise.
 249  */
 250 OGDF_EXPORT bool saveEdgeListSubgraph(const Graph &G, const List<edge> &delEdges, const char *fileName);
 251
 252 ///@}
 253
 254 /** @name Hypergraphs
 255  *  These functions load hypergraphs stored in file formats used for electrical circuits.
 256  *  The hypergraphs are directly transformed into their point-based expansions (and hence stored
 257  *  in a usual Graph and not a Hypergraph).
 258  */
 259 ///@{
 260
 261 //! Loads a hypergraph in the BENCH-format from input stream \a is.
 262 /**
 263  * A hypergraph in OGDF is represented by its point-based expansion, i.e., for each
 264  * hyperedge <i>h</i> we have a corresponding hypernode <i>n</i>. All nodes originally
 265  * incident to <i>h</i> are incident to <i>n</i>, i.e., have regular edges to <i>n</i>.
 266  *
 267  * @param G is assigned the graph (point-based expansion of the hypergraph).
 268  * @param hypernodes is assigned the list of nodes which have to be interpreted as hypernodes.
 269  * @param shell if 0 only the BENCH-hypergraph is loaded. Otherwise we extend the loaded graph
 270  *        by a simple edge <i>e=(i,o)</i> and two hyperedges: one hyperedges groups all input nodes and
 271  *        <i>i</i> together, the other hyperedge groups all output edges and <i>o</i>.
 272  *        These additional edges are then also collocated in shell.
 273  * @param is is the input stream from which the hypergraph is read.
 274  *
 275  * \warning
 276  * This is a very simple implementation only usable for very properly formatted files!
 277  */
 278 OGDF_EXPORT bool loadBenchHypergraph(Graph &G, List<node>& hypernodes, List<edge> *shell, istream &is);
 279
 280 //! Loads a hypergraph in the BENCH-format from the specified file.
 281 /**
 282  * @param G is assigned the graph (point-based expansion of the hypergraph).
 283  * @param hypernodes is assigned the list of nodes which have to be interpreted as hypernodes.
 284  * @param shell if 0 only the BENCH-hypergraph is loaded. Otherwise we extend the loaded graph
 285  *        by a simple edge <i>e=(i,o)</i> and two hyperedges: one hyperedges groups all input nodes and
 286  *        <i>i</i> together, the other hyperedge groups all output edges and <i>o</i>.
 287  *        These additional edges are then also collocated in shell.
 288  * @param fileName is the name of the file from which the hypergraph is read.
 289  *
 290  * \see loadBenchHypergraph(Graph &G, List<node>& hypernodes, List<edge>* shell, istream &is)
 291  */
 292 OGDF_EXPORT bool loadBenchHypergraph(Graph &G, List<node>& hypernodes, List<edge> *shell, const char *fileName);
 293
 294 //! Loads a hypergraph in the PLA-format from input stream \a is.
 295 /**
 296  * A hypergraph in OGDF is represented by its point-based expansion, i.e., for each
 297  * hyperedge <i>h</i> we have a corresponding hypernode <i>n</i>. All nodes originally
 298  * incident to <i>h</i> are incident to <i>n</i>, i.e., have regular edges to <i>n</i>.
 299  *
 300  * @param G is assigned the graph (point-based expansion of the hypergraph).
 301  * @param hypernodes is assigned the list of nodes which have to be interpreted as hypernodes.
 302  * @param shell if 0 only the PLA-hypergraph is loaded. Otherwise we extend the loaded graph
 303  *        by a simple edge <i>e=(i,o)</i> and two hyperedges: one hyperedges groups all input nodes and
 304  *        <i>i</i> together, the other hyperedge groups all output edges and <i>o</i>.
 305  *        These additional edges are then also collocated in shell.
 306  * @param is is the input stream from which the hypergraph is read.
 307  *
 308  * \warning
 309  * This is a very simple implementation only usable for very properly formatted files!
 310  */
 311 OGDF_EXPORT bool loadPlaHypergraph(Graph &G, List<node>& hypernodes, List<edge> *shell, istream &is);
 312
 313 //! Loads a hypergraph in the PLA-format from file \a fileName.
 314 /**
 315  * @param G is assigned the graph (point-based expansion of the hypergraph).
 316  * @param hypernodes is assigned the list of nodes which have to be interpreted as hypernodes.
 317  * @param shell if 0 only the PLA-hypergraph is loaded. Otherwise we extend the loaded graph
 318  *        by a simple edge <i>e=(i,o)</i> and two hyperedges: one hyperedges groups all input nodes and
 319  *        <i>i</i> together, the other hyperedge groups all output edges and <i>o</i>.
 320  *        These additional edges are then also collocated in shell.
 321  * @param fileName is the name of the file from which the hypergraph is read.
 322  *
 323  * \see loadPlaHypergraph(Graph &G, List<node>& hypernodes, List<edge> *shell, istream &is)
 324  */
 325 OGDF_EXPORT bool loadPlaHypergraph(Graph &G, List<node>& hypernodes, List<edge>* shell, const char *fileName);
 326
 327 ///@}
 328
 329
 330 }
 331
 332 #endif //OGDF_SIMPLE_GRAPH_LOAD_H