~ubuntu-branches/ubuntu/lucid/igraph/lucid

« back to all changes in this revision

Viewing changes to src/foreign.c

Committer: Bazaar Package Importer
Author(s): Mathieu Malaterre
Date: 2009-11-16 18:12:42 UTC
Revision ID: james.westby@ubuntu.com-20091116181242-mzv9p5fz9uj57xd1

Tags: upstream-0.5.3

Import upstream version 0.5.3

files added:

AUTHORS

COPYING

ChangeLog

INSTALL

Makefile.am

Makefile.in

NEWS

README

TODO

aclocal.m4

config.guess

config.h.in

config.sub

configure

configure.in

depcomp

doc/Makefile.in

doc/book

doc/book/Makefile.in

doc/igraph-docs.info

doc/igraph.3

examples

examples/simple

examples/simple/LINKS.NET

examples/simple/adjlist.c

examples/simple/ak-4102.max

examples/simple/bellman_ford.c

examples/simple/bellman_ford.out

examples/simple/cattributes.c

examples/simple/cattributes.out

examples/simple/cattributes2.c

examples/simple/cattributes2.out

examples/simple/d_indheap.c

examples/simple/d_indheap.out

examples/simple/dijkstra.c

examples/simple/dijkstra.out

examples/simple/dot.c

examples/simple/dot.out

examples/simple/dqueue.c

examples/simple/eigenvector_centrality.c

examples/simple/eigenvector_centrality.out

examples/simple/flow.c

examples/simple/foreign.c

examples/simple/foreign.out

examples/simple/gml.c

examples/simple/gml.out

examples/simple/graphml-hsa05010.xml

examples/simple/graphml.c

examples/simple/graphml.out

examples/simple/heap.c

examples/simple/igraph_add_edges.c

examples/simple/igraph_add_edges.out

examples/simple/igraph_add_vertices.c

examples/simple/igraph_adjacency.c

examples/simple/igraph_array.c

examples/simple/igraph_array.out

examples/simple/igraph_atlas.c

examples/simple/igraph_atlas.out

examples/simple/igraph_average_path_length.c

examples/simple/igraph_barabasi_game.c

examples/simple/igraph_bfs.c

examples/simple/igraph_bfs.out

examples/simple/igraph_bipartite_create.c

examples/simple/igraph_bipartite_create.out

examples/simple/igraph_bipartite_projection.c

examples/simple/igraph_cliques.c

examples/simple/igraph_cliques.out

examples/simple/igraph_cocitation.c

examples/simple/igraph_cocitation.out

examples/simple/igraph_community_edge_betweenness.c

examples/simple/igraph_community_edge_betweenness.out

examples/simple/igraph_community_fastgreedy.c

examples/simple/igraph_community_fastgreedy.out

examples/simple/igraph_community_label_propagation.c

examples/simple/igraph_community_label_propagation.out

examples/simple/igraph_community_leading_eigenvector.c

examples/simple/igraph_community_leading_eigenvector.out

examples/simple/igraph_complementer.c

examples/simple/igraph_complementer.out

examples/simple/igraph_compose.c

examples/simple/igraph_compose.out

examples/simple/igraph_convergence_degree.c

examples/simple/igraph_convergence_degree.out

examples/simple/igraph_convex_hull.c

examples/simple/igraph_convex_hull.out

examples/simple/igraph_copy.c

examples/simple/igraph_create.c

examples/simple/igraph_decompose.c

examples/simple/igraph_decompose.out

examples/simple/igraph_degree.c

examples/simple/igraph_degree.out

examples/simple/igraph_degree_sequence_game.c

examples/simple/igraph_delete_edges.c

examples/simple/igraph_delete_vertices.c

examples/simple/igraph_diameter.c

examples/simple/igraph_diameter.out

examples/simple/igraph_difference.c

examples/simple/igraph_difference.out

examples/simple/igraph_disjoint_union.c

examples/simple/igraph_disjoint_union.out

examples/simple/igraph_edge_betweenness.c

examples/simple/igraph_edge_betweenness.out

examples/simple/igraph_empty.c

examples/simple/igraph_erdos_renyi_game.c

examples/simple/igraph_es_adj.c

examples/simple/igraph_es_adj.out

examples/simple/igraph_es_fromto.c

examples/simple/igraph_es_fromto.out

examples/simple/igraph_es_pairs.c

examples/simple/igraph_es_path.c

examples/simple/igraph_full.c

examples/simple/igraph_get_eid.c

examples/simple/igraph_get_eid.out

examples/simple/igraph_get_eids.c

examples/simple/igraph_get_eids.out

examples/simple/igraph_get_shortest_paths.c

examples/simple/igraph_get_shortest_paths.out

examples/simple/igraph_get_shortest_paths_dijkstra.c

examples/simple/igraph_get_shortest_paths_dijkstra.out

examples/simple/igraph_girth.c

examples/simple/igraph_grg_game.c

examples/simple/igraph_growing_random_game.c

examples/simple/igraph_hashtable.c

examples/simple/igraph_hashtable.out

examples/simple/igraph_i_cutheap.c

examples/simple/igraph_i_cutheap.out

examples/simple/igraph_i_layout_sphere.c

examples/simple/igraph_independent_sets.c

examples/simple/igraph_independent_sets.out

examples/simple/igraph_intersection.c

examples/simple/igraph_intersection.out

examples/simple/igraph_is_directed.c

examples/simple/igraph_is_loop.c

examples/simple/igraph_is_loop.out

examples/simple/igraph_is_multiple.c

examples/simple/igraph_is_multiple.out

examples/simple/igraph_lattice.c

examples/simple/igraph_layout_lgl.c

examples/simple/igraph_layout_merge.c

examples/simple/igraph_layout_reingold_tilford.c

examples/simple/igraph_layout_reingold_tilford.in

examples/simple/igraph_lcf.c

examples/simple/igraph_local_transitivity.c

examples/simple/igraph_mincut.c

examples/simple/igraph_mincut.out

examples/simple/igraph_minimum_spanning_tree.c

examples/simple/igraph_minimum_spanning_tree.out

examples/simple/igraph_motifs_randesu.c

examples/simple/igraph_motifs_randesu.out

examples/simple/igraph_neighbors.c

examples/simple/igraph_neighbors.out

examples/simple/igraph_pagerank.c

examples/simple/igraph_pagerank.out

examples/simple/igraph_preference_game.c

examples/simple/igraph_psumtree.c

examples/simple/igraph_read_graph_graphdb.c

examples/simple/igraph_read_graph_graphdb.out

examples/simple/igraph_read_graph_lgl-1.lgl

examples/simple/igraph_read_graph_lgl-2.lgl

examples/simple/igraph_read_graph_lgl-3.lgl

examples/simple/igraph_read_graph_lgl.c

examples/simple/igraph_read_graph_lgl.out

examples/simple/igraph_reciprocity.c

examples/simple/igraph_rewire.c

examples/simple/igraph_rewire.out

examples/simple/igraph_ring.c

examples/simple/igraph_set.c

examples/simple/igraph_set.out

examples/simple/igraph_similarity.c

examples/simple/igraph_similarity.out

examples/simple/igraph_simplify.c

examples/simple/igraph_simplify.out

examples/simple/igraph_small.c

examples/simple/igraph_small.out

examples/simple/igraph_star.c

examples/simple/igraph_strvector.c

examples/simple/igraph_strvector.out

examples/simple/igraph_to_undirected.c

examples/simple/igraph_to_undirected.out

examples/simple/igraph_topological_sorting.c

examples/simple/igraph_topological_sorting.out

examples/simple/igraph_transitivity.c

examples/simple/igraph_tree.c

examples/simple/igraph_trie.c

examples/simple/igraph_trie.out

examples/simple/igraph_union.c

examples/simple/igraph_union.out

examples/simple/igraph_vs_nonadj.c

examples/simple/igraph_vs_nonadj.out

examples/simple/igraph_vs_seq.c

examples/simple/igraph_vs_seq.out

examples/simple/igraph_vs_vector.c

examples/simple/igraph_vs_vector.out

examples/simple/igraph_weighted_adjacency.c

examples/simple/igraph_weighted_adjacency.out

examples/simple/igraph_write_graph_lgl.c

examples/simple/igraph_write_graph_pajek.c

examples/simple/igraph_write_graph_pajek.out

examples/simple/indheap.c

examples/simple/iso_b03_m1000.A00

examples/simple/karate.gml

examples/simple/lineendings.c

examples/simple/lineendings.out

examples/simple/matrix.c

examples/simple/matrix.out

examples/simple/matrix2.c

examples/simple/matrix2.out

examples/simple/pajek1.net

examples/simple/pajek2.net

examples/simple/pajek3.net

examples/simple/pajek4.net

examples/simple/random_seed.c

examples/simple/spinglass.c

examples/simple/spmatrix.c

examples/simple/spmatrix.out

examples/simple/stack.c

examples/simple/test.gxl

examples/simple/topology.c

examples/simple/topology.out

examples/simple/vector.c

examples/simple/vector.out

examples/simple/vector2.c

examples/simple/vector2.out

examples/simple/vector_ptr.c

examples/simple/walktrap.c

examples/simple/walktrap.out

igraph.pc

igraph.pc.in

igraph_Info.plist.in

include

include/arpack.h

include/array.h

include/attributes.h

include/dqueue.h

include/error.h

include/heap.h

include/igraph.h

include/igraph_pmt.h

include/igraph_pmt_off.h

include/interrupt.h

include/matrix.h

include/stack.h

include/types.h

include/vector.h

install-sh

interfaces

interfaces/Makefile.am

interfaces/Makefile.in

interfaces/R

interfaces/R/DESCRIPTION.in

interfaces/R/Makefile.in

interfaces/R/configure.in.in

interfaces/R/src

interfaces/R/src/Makevars.win.in

interfaces/shell

interfaces/shell/Makefile.am

interfaces/shell/Makefile.in

interfaces/shell/interface.c

ltmain.sh

missing

src/DensityGrid.cpp

src/DensityGrid.h

src/DensityGrid_3d.cpp

src/DensityGrid_3d.h

src/Makefile.am

src/Makefile.in

src/NetDataTypes.cpp

src/NetDataTypes.h

src/NetRoutines.cpp

src/NetRoutines.h

src/adjlist.c

src/arpack

src/arpack.c

src/arpack.h

src/arpack/dgetv0.c

src/arpack/dlaqrb.c

src/arpack/dmout.c

src/arpack/dnaitr.c

src/arpack/dnapps.c

src/arpack/dnaup2.c

src/arpack/dnaupd.c

src/arpack/dnconv.c

src/arpack/dneigh.c

src/arpack/dneupd.c

src/arpack/dngets.c

src/arpack/dsaitr.c

src/arpack/dsapps.c

src/arpack/dsaup2.c

src/arpack/dsaupd.c

src/arpack/dsconv.c

src/arpack/dseigt.c

src/arpack/dsesrt.c

src/arpack/dseupd.c

src/arpack/dsgets.c

src/arpack/dsortc.c

src/arpack/dsortr.c

src/arpack/dstatn.c

src/arpack/dstats.c

src/arpack/dstqrb.c

src/arpack/dvout.c

src/arpack/ivout.c

src/arpack/second.c

src/arpack_internal.h

src/array.c

src/array.h

src/array.pmt

src/atlas-edges.h

src/atlas.c

src/attributes.c

src/attributes.h

src/basic_query.c

src/bfgs.c

src/bipartite.c

src/blas

src/blas/dasum.c

src/blas/daxpy.c

src/blas/dcopy.c

src/blas/ddot.c

src/blas/dgemv.c

src/blas/dger.c

src/blas/dnrm2.c

src/blas/drot.c

src/blas/dscal.c

src/blas/dswap.c

src/blas/dtrmm.c

src/blas/idamax.c

src/blas/lsame.c

src/bliss.cc

src/bliss_bignum.hh

src/bliss_defs.hh

src/bliss_eqrefhash.cc

src/bliss_eqrefhash.hh

src/bliss_graph.cc

src/bliss_graph.hh

src/bliss_heap.cc

src/bliss_heap.hh

src/bliss_kqueue.hh

src/bliss_kstack.hh

src/bliss_orbit.cc

src/bliss_orbit.hh

src/bliss_partition.cc

src/bliss_partition.hh

src/bliss_timer.cc

src/bliss_timer.hh

src/bliss_utils.cc

src/bliss_utils.hh

src/cattributes.c

src/centrality.c

src/cliques.c

src/clustertool.cpp

src/cocitation.c

src/community.c

src/components.c

src/conversion.c

src/cores.c

src/dqueue.c

src/dqueue.h

src/dqueue.pmt

src/drl_Node.h

src/drl_Node_3d.h

src/drl_graph.cpp

src/drl_graph.h

src/drl_graph_3d.cpp

src/drl_graph_3d.h

src/drl_layout.cpp

src/drl_layout.h

src/drl_layout_3d.cpp

src/drl_layout_3d.h

src/drl_parse.cpp

src/drl_parse.h

src/error.c

src/error.h

src/evolver_cit.c

src/f2c

src/f2c.h

src/f2c/d_lg10.c

src/f2c/d_sign.c

src/f2c/etime_.c

src/f2c/i_dnnt.c

src/f2c/pow_dd.c

src/f2c/pow_di.c

src/f2c/s_cmp.c

src/f2c/s_copy.c

src/fast_community.c

src/flow.c

src/foreign-gml-lexer.c

src/foreign-gml-lexer.l

src/foreign-gml-parser.c

src/foreign-gml-parser.h

src/foreign-gml-parser.y

src/foreign-graphml.c

src/foreign-lgl-lexer.c

src/foreign-lgl-lexer.l

src/foreign-lgl-parser.c

src/foreign-lgl-parser.h

src/foreign-lgl-parser.y

src/foreign-ncol-lexer.c

src/foreign-ncol-lexer.l

src/foreign-ncol-parser.c

src/foreign-ncol-parser.h

src/foreign-ncol-parser.y

src/foreign-pajek-lexer.c

src/foreign-pajek-lexer.l

src/foreign-pajek-parser.c

src/foreign-pajek-parser.h

src/foreign-pajek-parser.y

src/foreign.c

src/forestfire.c

src/games.c

src/gengraph_box_list.cpp

src/gengraph_box_list.h

src/gengraph_definitions.h

src/gengraph_degree_sequence.cpp

src/gengraph_degree_sequence.h

src/gengraph_graph_molloy_hash.cpp

src/gengraph_graph_molloy_hash.h

src/gengraph_graph_molloy_optimized.cpp

src/gengraph_graph_molloy_optimized.h

src/gengraph_hash.h

src/gengraph_header.h

src/gengraph_mr-connected.cpp

src/gengraph_powerlaw.cpp

src/gengraph_powerlaw.h

src/gengraph_qsort.h

src/gengraph_random.cpp

src/gengraph_random.h

src/gengraph_vertex_cover.h

src/gml_tree.c

src/gml_tree.h

src/heap.c

src/heap.h

src/heap.pmt

src/igraph.h

src/igraph_buckets.c

src/igraph_grid.c

src/igraph_hashtable.c

src/igraph_heap.c

src/igraph_math.h

src/igraph_pmt.h

src/igraph_pmt_off.h

src/igraph_psumtree.c

src/igraph_set.c

src/igraph_stack.c

src/igraph_strvector.c

src/igraph_trie.c

src/interrupt.c

src/interrupt.h

src/iterators.c

src/lapack

src/lapack/dgeqr2.c

src/lapack/dlabad.c

src/lapack/dlacon.c

src/lapack/dlacpy.c

src/lapack/dladiv.c

src/lapack/dlae2.c

src/lapack/dlaev2.c

src/lapack/dlaexc.c

src/lapack/dlahqr.c

src/lapack/dlaln2.c

src/lapack/dlamch.c

src/lapack/dlange.c

src/lapack/dlanhs.c

src/lapack/dlanst.c

src/lapack/dlanv2.c

src/lapack/dlapy2.c

src/lapack/dlarf.c

src/lapack/dlarfg.c

src/lapack/dlarfx.c

src/lapack/dlarnv.c

src/lapack/dlartg.c

src/lapack/dlaruv.c

src/lapack/dlascl.c

src/lapack/dlaset.c

src/lapack/dlasr.c

src/lapack/dlasrt.c

src/lapack/dlassq.c

src/lapack/dlasy2.c

src/lapack/dorm2r.c

src/lapack/dsteqr.c

src/lapack/dtrevc.c

src/lapack/dtrexc.c

src/lapack/dtrsen.c

src/lapack/dtrsyl.c

src/lapack/xerbla.c

src/layout.c

src/math.c

src/matrix.c

src/matrix.h

src/matrix.pmt

src/measure_dynamics.c

src/memory.c

src/memory.h

src/motifs.c

src/operators.c

src/other.c

src/pottsmodel_2.cpp

src/pottsmodel_2.h

src/progress.c

src/random.c

src/random.h

src/revolver_cit.c

src/revolver_grow.c

src/revolver_ml_cit.c

src/spectral_properties.c

src/spmatrix.c

src/stack.h

src/stack.pmt

src/structural_properties.c

src/structure_generators.c

src/topology.c

src/type_indexededgelist.c

src/types.h

src/vector.c

src/vector.h

src/vector.pmt

src/vector_ptr.c

src/visitors.c

src/walktrap.cpp

src/walktrap_communities.cpp

src/walktrap_communities.h

src/walktrap_graph.cpp

src/walktrap_graph.h

src/walktrap_heap.cpp

src/walktrap_heap.h

src/zeroin.c

tests

tests/Makefile.am

tests/Makefile.in

tests/arpack.at

tests/atlocal.in

tests/attributes.at

tests/basic.at

tests/bipartite.at

tests/cliques.at

tests/community.at

tests/components.at

tests/conversion.at

tests/eigen.at

tests/flow.at

tests/foreign.at

tests/iterators.at

tests/layout.at

tests/motifs.at

tests/operators.at

tests/other.at

tests/package.m4

tests/structural_properties.at

tests/structure_generators.at

tests/testsuite

tests/testsuite.at

tests/topology.at

tests/types.at

tests/visitors.at

ylwrap

Show diffs side-by-side

added added

removed removed

src/foreign.c

/* -*- mode: C -*- */

IGraph R package.

MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary

This program is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation; either version 2 of the License, or

(at your option) any later version.

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA

02110-1301 USA

#include "igraph.h"

#include "config.h"

#include "igraph_math.h"

#include "gml_tree.h"

#include "memory.h"

#include <ctype.h> /* isspace */

#include <string.h>

#include <time.h>

/**

* \section about_loadsave

* <para>These functions can write a graph to a file, or read a graph

* from a file.</para>

* <para>Note that as \a igraph uses the traditional C streams, it is

* possible to read/write files from/to memory, at least on GNU

* operating systems supporting \quote non-standard\endquote streams.</para>

/**

* \ingroup loadsave

* \function igraph_read_graph_edgelist

* \brief Reads an edge list from a file and creates a graph.

* </para><para>

* This format is simply a series of even number integers separated by

* whitespace. The one edge (ie. two integers) per line format is thus

* not required (but recommended for readability). Edges of directed

* graphs are assumed to be in from, to order.

* \param graph Pointer to an uninitialized graph object.

* \param instream Pointer to a stream, it should be readable.

* \param n The number of vertices in the graph. If smaller than the

* largest integer in the file it will be ignored. It is thus

* safe to supply zero here.

* \param directed Logical, if true the graph is directed, if false it

* will be undirected.

* \return Error code:

* \c IGRAPH_PARSEERROR: if there is a

* problem reading the file, or the file is syntactically

* incorrect.

* Time complexity: O(|V|+|E|), the

* number of vertices plus the number of edges. It is assumed that

* reading an integer requires O(1)

* time.

int igraph_read_graph_edgelist(igraph_t *graph, FILE *instream,

igraph_integer_t n, igraph_bool_t directed) {

igraph_vector_t edges=IGRAPH_VECTOR_NULL;

long int from, to;

int c;

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

IGRAPH_CHECK(igraph_vector_reserve(&edges, 100));

/* skip all whitespace */

do {

c = getc (instream);

} while (isspace (c));

ungetc (c, instream);

while (!feof(instream)) {

int read;

IGRAPH_ALLOW_INTERRUPTION();

read=fscanf(instream, "%li", &from);

if (read != 1) {

IGRAPH_ERROR("parsing edgelist file failed", IGRAPH_PARSEERROR);

}

read=fscanf(instream, "%li", &to);

if (read != 1) {

100

IGRAPH_ERROR("parsing edgelist file failed", IGRAPH_PARSEERROR);

101

}

102

IGRAPH_CHECK(igraph_vector_push_back(&edges, from));

103

IGRAPH_CHECK(igraph_vector_push_back(&edges, to));

104

105

/* skip all whitespace */

106

do {

107

c = getc (instream);

108

} while (isspace (c));

109

ungetc (c, instream);

110

}

111

112

IGRAPH_CHECK(igraph_create(graph, &edges, n, directed));

113

igraph_vector_destroy(&edges);

114

IGRAPH_FINALLY_CLEAN(1);

115

return 0;

116

}

117

118

extern int igraph_ncol_yyparse(void);

119

extern FILE *igraph_ncol_yyin;

120

extern int igraph_i_ncol_eof;

121

long int igraph_ncol_mylineno;

122

igraph_vector_t *igraph_ncol_vector=0;

123

igraph_vector_t *igraph_ncol_weights=0;

124

igraph_trie_t *igraph_ncol_trie=0;

125

extern char *igraph_i_ncol_errmsg;

126

127

/**

128

* \ingroup loadsave

129

* \function igraph_read_graph_ncol

130

* \brief Reads a <code>.ncol</code> file used by LGL.

131

132

* Also useful for creating graphs from \quote named\endquote (and

133

* optionally weighted) edge lists.

134

135

* </para><para>

136

* This format is used by the Large Graph Layout program

137

* (http://bioinformatics.icmb.utexas.edu/lgl/), and it is simply a

138

* symbolic weighted edge list. It is a simple text file with one edge

139

* per line. An edge is defined by two symbolic vertex names separated

140

* by whitespace. (The symbolic vertex names themselves cannot contain

141

* whitespace. They might follow by an optional number, this will be

142

* the weight of the edge; the number can be negative and can be in

143

* scientific notation. If there is no weight specified to an edge it

144

* is assumed to be zero.

145

146

* </para><para>

147

* The resulting graph is always undirected.

148

* LGL cannot deal with files which contain multiple or loop edges,

149

* this is however not checked here, as \a igraph is happy with

150

* these.

151

* \param graph Pointer to an uninitialized graph object.

152

* \param instream Pointer to a stream, it should be readable.

153

* \param predefnames Pointer to the symbolic names of the vertices in

154

* the file. If \c NULL is given here then vertex ids will be

155

* assigned to vertex names in the order of their appearence in

156

* the \c .ncol file. If it is not \c NULL and some unknown

157

* vertex names are found in the \c .ncol file then new vertex

158

* ids will be assigned to them.

159

* \param names Logical value, if TRUE the symbolic names of the

160

* vertices will be added to the graph as a vertex attribute

161

* called \quote name\endquote.

162

* \param weights Logical value, if TRUE the weights of the

163

* edges is added to the graph as an edge attribute called

164

* \quote weight\endquote.

165

* \param directed Whether to create a directed graph. As this format

166

* was originally used only for undirected graphs there is no

167

* information in the file about the directedness of the graph.

168

* Set this parameter to \c IGRAPH_DIRECTED or \c

169

* IGRAPH_UNDIRECTED to create a directed or undirected graph.

170

* \return Error code:

171

* \c IGRAPH_PARSEERROR: if there is a

172

* problem reading

173

* the file, or the file is syntactically incorrect.

174

175

* Time complexity:

176

* O(|V|+|E|log(|V|)) if we neglect

177

* the time required by the parsing. As usual

178

* |V| is the number of vertices,

179

* while |E| is the number of edges.

180

181

* \sa \ref igraph_read_graph_lgl(), \ref igraph_write_graph_ncol()

182

183

184

int igraph_read_graph_ncol(igraph_t *graph, FILE *instream,

185

igraph_strvector_t *predefnames,

186

igraph_bool_t names, igraph_bool_t weights, igraph_bool_t directed) {

187

188

igraph_vector_t edges, ws;

189

igraph_trie_t trie=IGRAPH_TRIE_NULL;

190

long int no_predefined=0;

191

igraph_vector_ptr_t name, weight;

192

igraph_vector_ptr_t *pname=0, *pweight=0;

193

igraph_i_attribute_record_t namerec, weightrec;

194

const char *namestr="name", *weightstr="weight";

195

196

IGRAPH_CHECK(igraph_empty(graph, 0, directed));

197

IGRAPH_FINALLY(igraph_destroy, graph);

198

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

199

200

IGRAPH_TRIE_INIT_FINALLY(&trie, names);

201

IGRAPH_VECTOR_INIT_FINALLY(&ws, 0);

202

203

/* Add the predefined names, if any */

204

if (predefnames != 0) {

205

long int i, id, n;

206

char *key;

207

n=no_predefined=igraph_strvector_size(predefnames);

208

for (i=0; i<n; i++) {

209

igraph_strvector_get(predefnames, i, &key);

210

igraph_trie_get(&trie, key, &id);

211

if (id != i) {

212

IGRAPH_WARNING("reading NCOL file, duplicate entry in predefnames");

213

no_predefined--;

214

}

215

}

216

}

217

218

igraph_ncol_vector=&edges;

219

igraph_ncol_weights=&ws;

220

igraph_ncol_trie=&trie;

221

igraph_ncol_yyin=instream;

222

igraph_ncol_mylineno=1;

223

igraph_i_ncol_eof=0;

224

igraph_i_ncol_errmsg=0;

225

226

if (igraph_ncol_yyparse()) {

227

if (igraph_i_ncol_errmsg) {

228

IGRAPH_ERROR(igraph_i_ncol_errmsg, IGRAPH_PARSEERROR);

229

} else {

230

IGRAPH_ERROR("Cannot read NCOL file", IGRAPH_PARSEERROR);

231

}

232

}

233

234

if (predefnames != 0 &&

235

igraph_trie_size(&trie) != no_predefined) {

236

IGRAPH_WARNING("unknown vertex/vertices found, predefnames extended");

237

}

238

239

if (names) {

240

const igraph_strvector_t *namevec;

241

IGRAPH_CHECK(igraph_vector_ptr_init(&name, 1));

242

pname=&name;

243

igraph_trie_getkeys(&trie, &namevec); /* dirty */

244

namerec.name=namestr;

245

namerec.type=IGRAPH_ATTRIBUTE_STRING;

246

namerec.value=namevec;

247

VECTOR(name)[0]=&namerec;

248

}

249

250

if (weights) {

251

IGRAPH_CHECK(igraph_vector_ptr_init(&weight, 1));

252

pweight=&weight;

253

weightrec.name=weightstr;

254

weightrec.type=IGRAPH_ATTRIBUTE_NUMERIC;

255

weightrec.value=&ws;

256

VECTOR(weight)[0]=&weightrec;

257

}

258

259

IGRAPH_CHECK(igraph_add_vertices(graph, igraph_vector_max(&edges)+1, pname));

260

IGRAPH_CHECK(igraph_add_edges(graph, &edges, pweight));

261

262

if (pname) {

263

igraph_vector_ptr_destroy(pname);

264

}

265

if (pweight) {

266

igraph_vector_ptr_destroy(pweight);

267

}

268

igraph_vector_destroy(&ws);

269

igraph_trie_destroy(&trie);

270

igraph_vector_destroy(&edges);

271

IGRAPH_FINALLY_CLEAN(4);

272

273

return 0;

274

}

275

276

extern int igraph_lgl_yyparse(void);

277

extern FILE *igraph_lgl_yyin;

278

extern int igraph_i_lgl_eof;

279

long int igraph_lgl_mylineno;

280

igraph_vector_t *igraph_lgl_vector=0;

281

igraph_vector_t *igraph_lgl_weights=0;

282

igraph_trie_t *igraph_lgl_trie=0;

283

extern char *igraph_i_lgl_errmsg;

284

285

/**

286

* \ingroup loadsave

287

* \function igraph_read_graph_lgl

288

* \brief Reads a graph from an <code>.lgl</code> file

289

290

* </para><para>

291

* The <code>.lgl</code> format is used by the Large Graph

292

* Layout visualization software

293

* (http://bioinformatics.icmb.utexas.edu/lgl/), it can

294

* describe undirected optionally weighted graphs. From the LGL

295

* manual:

296

297

* \blockquote <para>The second format is the LGL file format

298

* (<code>.lgl</code> file

299

* suffix). This is yet another graph file format that tries to be as

300

* stingy as possible with space, yet keeping the edge file in a human

301

* readable (not binary) format. The format itself is like the

302

* following:

303

* \verbatim # vertex1name

304

vertex2name [optionalWeight]

305

vertex3name [optionalWeight] \endverbatim

306

* Here, the first vertex of an edge is preceded with a pound sign

307

* '#'. Then each vertex that shares an edge with that vertex is

308

* listed one per line on subsequent lines.</para> \endblockquote

309

310

* </para><para>

311

* LGL cannot handle loop and multiple edges or directed graphs, but

312

* in \a igraph it is not an error to have multiple and loop edges.

313

* \param graph Pointer to an uninitialized graph object.

314

* \param instream A stream, it should be readable.

315

* \param names Logical value, if TRUE the symbolic names of the

316

* vertices will be added to the graph as a vertex attribute

317

* called \quote name\endquote.

318

* \param weights Logical value, if TRUE the weights of the

319

* edges is added to the graph as an edge attribute called

320

* \quote weight\endquote.

321

* \return Error code:

322

* \c IGRAPH_PARSEERROR: if there is a

323

* problem reading the file, or the file is syntactically

324

* incorrect.

325

326

* Time complexity:

327

* O(|V|+|E|log(|V|)) if we neglect

328

* the time required by the parsing. As usual

329

* |V| is the number of vertices,

330

* while |E| is the number of edges.

331

332

* \sa \ref igraph_read_graph_ncol(), \ref igraph_write_graph_lgl()

333

334

335

int igraph_read_graph_lgl(igraph_t *graph, FILE *instream,

336

igraph_bool_t names, igraph_bool_t weights) {

337

338

igraph_vector_t edges=IGRAPH_VECTOR_NULL, ws=IGRAPH_VECTOR_NULL;

339

igraph_trie_t trie=IGRAPH_TRIE_NULL;

340

igraph_vector_ptr_t name, weight;

341

igraph_vector_ptr_t *pname=0, *pweight=0;

342

igraph_i_attribute_record_t namerec, weightrec;

343

const char *namestr="name", *weightstr="weight";

344

345

IGRAPH_VECTOR_INIT_FINALLY(&ws, 0);

346

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

347

IGRAPH_TRIE_INIT_FINALLY(&trie, names);

348

349

igraph_lgl_vector=&edges;

350

igraph_lgl_weights=&ws;

351

igraph_lgl_trie=&trie;

352

igraph_lgl_yyin=instream;

353

igraph_lgl_mylineno=1;

354

igraph_i_lgl_eof=0;

355

igraph_i_lgl_errmsg=0;

356

357

if (igraph_lgl_yyparse()) {

358

if (igraph_i_lgl_errmsg) {

359

IGRAPH_ERROR(igraph_i_lgl_errmsg, IGRAPH_PARSEERROR);

360

} else {

361

IGRAPH_ERROR("Cannot read LGL file", IGRAPH_PARSEERROR);

362

}

363

}

364

365

IGRAPH_CHECK(igraph_empty(graph, 0, IGRAPH_UNDIRECTED));

366

IGRAPH_FINALLY(igraph_destroy, graph);

367

368

if (names) {

369

const igraph_strvector_t *namevec;

370

IGRAPH_CHECK(igraph_vector_ptr_init(&name, 1));

371

IGRAPH_FINALLY(igraph_vector_ptr_destroy, &name);

372

pname=&name;

373

igraph_trie_getkeys(&trie, &namevec); /* dirty */

374

namerec.name=namestr;

375

namerec.type=IGRAPH_ATTRIBUTE_STRING;

376

namerec.value=namevec;

377

VECTOR(name)[0]=&namerec;

378

}

379

380

if (weights) {

381

IGRAPH_CHECK(igraph_vector_ptr_init(&weight, 1));

382

IGRAPH_FINALLY(igraph_vector_ptr_destroy, &weight);

383

pweight=&weight;

384

weightrec.name=weightstr;

385

weightrec.type=IGRAPH_ATTRIBUTE_NUMERIC;

386

weightrec.value=&ws;

387

VECTOR(weight)[0]=&weightrec;

388

}

389

390

IGRAPH_CHECK(igraph_add_vertices(graph, igraph_trie_size(&trie), pname));

391

IGRAPH_CHECK(igraph_add_edges(graph, &edges, pweight));

392

393

if (pweight) {

394

igraph_vector_ptr_destroy(pweight);

395

IGRAPH_FINALLY_CLEAN(1);

396

}

397

if (pname) {

398

igraph_vector_ptr_destroy(pname);

399

IGRAPH_FINALLY_CLEAN(1);

400

}

401

igraph_trie_destroy(&trie);

402

igraph_vector_destroy(&edges);

403

igraph_vector_destroy(&ws);

404

IGRAPH_FINALLY_CLEAN(4);

405

406

return 0;

407

}

408

409

extern int igraph_pajek_yyparse(void);

410

extern FILE *igraph_pajek_yyin;

411

extern int igraph_i_pajek_eof;

412

long int igraph_pajek_mylineno;

413

igraph_vector_t *igraph_pajek_vector=0;

414

igraph_bool_t igraph_pajek_directed;

415

long int igraph_pajek_vcount;

416

long int igraph_pajek_actfrom, igraph_pajek_actto;

417

int igraph_pajek_mode=0; /* 0 - general, 1 - vertex, 2 - edge */

418

igraph_trie_t *igraph_i_pajek_vertex_attribute_names;

419

igraph_vector_ptr_t *igraph_i_pajek_vertex_attributes;

420

igraph_trie_t *igraph_i_pajek_edge_attribute_names;

421

igraph_vector_ptr_t *igraph_i_pajek_edge_attributes;

422

long int igraph_i_pajek_vertexid=0;

423

long int igraph_i_pajek_actvertex=0;

424

long int igraph_i_pajek_actedge=0;

425

extern char *igraph_i_pajek_errmsg;

426

427

/* int vector_print(igraph_vector_t *v) { */

428

/* long int i, size=igraph_vector_size(v); */

429

/* for (i=0; i<size; i++) { */

430

/* printf("%f|", VECTOR(*v)[i]); */

431

/* } */

432

/* printf("\n"); */

433

/* return 0; */

434

/* } */

435

436

/* int strvector_print(igraph_strvector_t *sv) { */

437

/* long int i, size=igraph_strvector_size(sv); */

438

/* char *str; */

439

/* for (i=0; i<size; i++) { */

440

/* igraph_strvector_get(sv, i, &str); */

441

/* printf("%s|", str); */

442

/* } */

443

/* printf("\n"); */

444

/* return 0; */

445

/* } */

446

447

/**

448

* \function igraph_read_graph_pajek

449

* \brief Reads a file in Pajek format

450

451

* \param graph Pointer to an uninitialized graph object.

452

* \param file An already opened file handler.

453

* \return Error code.

454

455

* </para><para>

456

* Only a subset of the Pajek format is implemented. This is partially

457

* because this format is not very well documented, but also because

458

* <command>igraph</command> does not support some Pajek features, like

459

* multigraphs.

460

461

* </para><para>

462

* The list of the current limitations:

463

* \olist

464

* \oli Only <filename>.net</filename> files are supported, Pajek

465

* project files (<filename>.paj</filename>) are not. These might be

466

* supported in the future if there is need for it.

467

* \oli Time events networks are not supported.

468

* \oli Hypergraphs (ie. graphs with non-binary edges) are not

469

* supported.

470

* \oli Graphs with both directed and non-directed edges are not

471

* supported, are they cannot be represented in

472

* <command>igraph</command>.

473

* \oli Bipartite or affiliation networks are not supported. They can

474

* be imported but the vertex type information is omitted.

475

* \oli Only Pajek networks are supported, permutations, hierarchies,

476

* clusters and vectors are not.

477

* \oli Graphs with multiple edge sets are not supported.

478

* \endolist

479

480

* </para><para>

481

* If there are attribute handlers installed,

482

* <command>igraph</command> also reads the vertex and edge attributes

483

* from the file. Most attributes are renamed to be more informative:

484

* `\c color' instead of `\c c', `\c xfact' instead of `\c x_fact',

485

* `\c yfact' instead of `y_fact', `\c labeldist' instead of `\c lr',

486

* `\c labeldegree2' instead of `\c lphi', `\c framewidth' instead of `\c bw',

487

* `\c fontsize'

488

* instead of `\c fos', `\c rotation' instead of `\c phi', `\c radius' instead

489

* of `\c r',

490

* `\c diamondratio' instead of `\c q', `\c labeldegree' instead of `\c la',

491

* `\c vertexsize'

492

* instead of `\c size', `\c color' instead of `\c ic', `\c framecolor' instead of

493

* `\c bc', `\c labelcolor' instead of `\c lc', these belong to vertices.

494

495

* </para><para>

496

* Edge attributes are also renamed, `\c s' to `\c arrowsize', `\c w'

497

* to `\c edgewidth', `\c h1' to `\c hook1', `\c h2' to `\c hook2',

498

* `\c a1' to `\c angle1', `\c a2' to `\c angle2', `\c k1' to

499

* `\c velocity1', `\c k2' to `\c velocity2', `\c ap' to `\c

500

* arrowpos', `\c lp' to `\c labelpos', `\c lr' to

501

* `\c labelangle', `\c lphi' to `\c labelangle2', `\c la' to `\c

502

* labeldegree', `\c fos' to

503

* `\c fontsize', `\c a' to `\c arrowtype', `\c p' to `\c

504

* linepattern', `\c l' to `\c label', `\c lc' to

505

* `\c labelcolor', `\c c' to `\c color'.

506

507

* </para><para>

508

* In addition the following vertex attributes might be added: `\c id'

509

* if there are vertex ids in the file, `\c x' and `\c y' or `\c x'

510

* and `\c y' and `\c z' if there are vertex coordinates in the file,

511

* `\c color-red', `\c color-green' and `\c color-blue' if the vertex

512

* color is given in RGB notation, `\c framecolor-red', `\c

513

* framecolor-green' and `\c framecolor-blue` if the frame color is

514

* given in RGB notation and finally `\c labelcolor-red', `\c

515

* labelcolor-green' and `\c labelcolor-blue' if the label color is

516

* given in RGB notation.

517

518

* </para><para>The following additional edge attributes might be

519

* added: `\c weight' if there are edge weights present, `\c

520

* color-red', `\c color-green' and `\c color-blue' if the edge color

521

* is given in RGB notation.

522

523

* </para><para>

524

* See the pajek homepage:

525

* http://vlado.fmf.uni-lj.si/pub/networks/pajek/ for more info on

526

* Pajek and the Pajek manual:

527

* http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.pdf for

528

* information on the Pajek file format.

529

530

* </para><para>

531

* Time complexity: O(|V|+|E|+|A|), |V| is the number of vertices, |E|

532

* the number of edges, |A| the number of attributes (vertex + edge)

533

* in the graph if there are attribute handlers installed.

534

535

* \sa \ref igraph_write_graph_pajek() for writing Pajek files, \ref

536

* igraph_read_graph_graphml() for reading GraphML files.

537

538

539

int igraph_read_graph_pajek(igraph_t *graph, FILE *instream) {

540

541

igraph_vector_t edges;

542

igraph_trie_t vattrnames;

543

igraph_vector_ptr_t vattrs;

544

igraph_trie_t eattrnames;

545

igraph_vector_ptr_t eattrs;

546

/* igraph_hashtable_t vattrhash; */

547

/* igraph_hashtable_t eattrhash; */

548

long int i, j;

549

550

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

551

552

IGRAPH_TRIE_INIT_FINALLY(&vattrnames, 1);

553

IGRAPH_VECTOR_PTR_INIT_FINALLY(&vattrs, 0);

554

IGRAPH_TRIE_INIT_FINALLY(&eattrnames, 1);

555

IGRAPH_VECTOR_PTR_INIT_FINALLY(&eattrs, 0);

556

557

igraph_pajek_vector=&edges;

558

igraph_pajek_yyin=instream;

559

560

igraph_pajek_mode=0;

561

igraph_pajek_vcount=-1;

562

igraph_i_pajek_vertexid=0;

563

igraph_i_pajek_vertex_attribute_names=&vattrnames;

564

igraph_i_pajek_vertex_attributes=&vattrs;

565

igraph_i_pajek_edge_attribute_names=&eattrnames;

566

igraph_i_pajek_edge_attributes=&eattrs;

567

igraph_i_pajek_actedge=0;

568

igraph_pajek_mylineno=1;

569

igraph_i_pajek_eof=0;

570

igraph_i_pajek_errmsg=0;

571

572

if (igraph_pajek_yyparse()) {

573

if (igraph_i_pajek_errmsg) {

574

IGRAPH_ERROR(igraph_i_pajek_errmsg, IGRAPH_PARSEERROR);

575

} else {

576

IGRAPH_ERROR("Cannot read Pajek file", IGRAPH_PARSEERROR);

577

}

578

}

579

580

if (igraph_pajek_vcount < 0)

581

IGRAPH_ERROR("invalid vertex count in Pajek file", IGRAPH_EINVAL);

582

583

for (i=0; i<igraph_vector_ptr_size(&eattrs); i++) {

584

igraph_i_attribute_record_t *rec=VECTOR(eattrs)[i];

585

if (rec->type==IGRAPH_ATTRIBUTE_NUMERIC) {

586

igraph_vector_t *vec=(igraph_vector_t*)rec->value;

587

long int origsize=igraph_vector_size(vec);

588

igraph_vector_resize(vec, igraph_i_pajek_actedge);

589

for (j=origsize; j<igraph_i_pajek_actedge; j++) {

590

VECTOR(*vec)[j] = IGRAPH_NAN;

591

}

592

} else if (rec->type==IGRAPH_ATTRIBUTE_STRING) {

593

igraph_strvector_t *strvec=(igraph_strvector_t*)rec->value;

594

long int origsize=igraph_strvector_size(strvec);

595

igraph_strvector_resize(strvec, igraph_i_pajek_actedge);

596

for (j=origsize; j<igraph_i_pajek_actedge; j++) {

597

igraph_strvector_set(strvec, j, "");

598

}

599

}

600

}

601

602

IGRAPH_CHECK(igraph_empty(graph, 0, igraph_pajek_directed));

603

IGRAPH_FINALLY(igraph_destroy, graph);

604

IGRAPH_CHECK(igraph_add_vertices(graph, igraph_pajek_vcount, &vattrs));

605

IGRAPH_CHECK(igraph_add_edges(graph, &edges, &eattrs));

606

607

for (i=0; i<igraph_vector_ptr_size(&vattrs); i++) {

608

igraph_i_attribute_record_t *rec=VECTOR(vattrs)[i];

609

if (rec->type == IGRAPH_ATTRIBUTE_NUMERIC) {

610

igraph_vector_t *vec=(igraph_vector_t*) rec->value;

611

igraph_vector_destroy(vec);

612

igraph_Free(vec);

613

} else if (rec->type==IGRAPH_ATTRIBUTE_STRING) {

614

igraph_strvector_t *strvec=(igraph_strvector_t *)rec->value;

615

igraph_strvector_destroy(strvec);

616

igraph_Free(strvec);

617

}

618

igraph_free( (char*)(rec->name));

619

igraph_Free(rec);

620

}

621

622

for (i=0; i<igraph_vector_ptr_size(&eattrs); i++) {

623

igraph_i_attribute_record_t *rec=VECTOR(eattrs)[i];

624

if (rec->type == IGRAPH_ATTRIBUTE_NUMERIC) {

625

igraph_vector_t *vec=(igraph_vector_t*) rec->value;

626

igraph_vector_destroy(vec);

627

igraph_Free(vec);

628

} else if (rec->type==IGRAPH_ATTRIBUTE_STRING) {

629

igraph_strvector_t *strvec=(igraph_strvector_t *)rec->value;

630

igraph_strvector_destroy(strvec);

631

igraph_Free(strvec);

632

}

633

igraph_free( (char*)(rec->name));

634

igraph_Free(rec);

635

}

636

637

igraph_vector_destroy(&edges);

638

igraph_vector_ptr_destroy(&eattrs);

639

igraph_trie_destroy(&eattrnames);

640

igraph_vector_ptr_destroy(&vattrs);

641

igraph_trie_destroy(&vattrnames);

642

643

IGRAPH_FINALLY_CLEAN(6);

644

return 0;

645

}

646

647

/**

648

* \function igraph_read_graph_dimacs

649

* \brief Read a graph in DIMACS format.

650

651

* This function reads the DIMACS file format, more specifically the

652

* version for network flow problems, see the files at

653

* ftp://dimacs.rutgers.edu/pub/netflow/general-info/

654

655

* </para><para>

656

* This is a line-oriented text file (ASCII) format. The first

657

* character of each line defines the type of the line. If the first

658

* character is <code>c</code> the line is a comment line and it is

659

* ignored. There is one problem line (<code>p</code> in the file, it

660

* must appear before any node and arc descriptor lines. The problem

661

* line has three fields separated by spaces: the problem type

662

* (<code>min</code>, <code>max</code> or <code>asn</code>), the

663

* number of vertices and number of edges in the graph.

664

* Exactly two node identification lines are expected

665

* (<code>n</code>), one for the source, one for the target vertex.

666

* These have two fields: the id of the vertex and the type of the

667

* vertex, either <code>s</code> (=source) or <code>t</code>

668

* (=target). Arc lines start with <code>a</code> and have three

669

* fields: the source vertex, the target vertex and the edge capacity.

670

671

* </para><para>

672

* Vertex ids are numbered from 1.

673

* \param graph Pointer to an uninitialized graph object.

674

* \param instream The file to read from.

675

* \param source Pointer to an integer, the id of the source node will

676

* be stored here. (The igraph vertex id, which is one less than

677

* the actual number in the file.) It is ignored if

678

* <code>NULL</code>.

679

* \param target Pointer to an integer, the (igraph) id of the target

680

* node will be stored here. It is ignored if <code>NULL</code>.

681

* \param capacity Pointer to an initialized vector, the capacity of

682

* the edges will be stored here if not <code>NULL</code>.

683

* \param directed Boolean, whether to create a directed graph.

684

* \return Error code.

685

686

* Time complexity: O(|V|+|E|+c), the number of vertices plus the

687

* number of edges, plus the size of the file in characters.

688

689

* \sa \ref igraph_write_graph_dimacs()

690

691

692

int igraph_read_graph_dimacs(igraph_t *graph, FILE *instream,

693

igraph_strvector_t *problem,

694

igraph_vector_t *label,

695

igraph_integer_t *source,

696

igraph_integer_t *target,

697

igraph_vector_t *capacity,

698

igraph_bool_t directed) {

699

700

igraph_vector_t edges;

701

long int no_of_nodes=-1;

702

long int no_of_edges=-1;

703

long int tsource=-1;

704

long int ttarget=-1;

705

char prob[21];

706

char c;

707

int problem_type=0;

708

709

#define PROBLEM_EDGE 1

710

#define PROBLEM_MAX 2

711

712

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

713

if (capacity) {

714

igraph_vector_clear(capacity);

715

}

716

717

while (!feof(instream)) {

718

int read;

719

char str[3];

720

721

IGRAPH_ALLOW_INTERRUPTION();

722

723

read=fscanf(instream, "%2c", str);

724

if (feof(instream)) {

725

break;

726

}

727

if (read != 1) {

728

IGRAPH_ERROR("parsing dimacs file failed", IGRAPH_PARSEERROR);

729

}

730

switch (str[0]) {

731

long int tmp, tmp2;

732

long int from, to;

733

igraph_real_t cap;

734

735

case 'c':

736

/* comment */

737

break;

738

739

case 'p':

740

if (no_of_nodes != -1) {

741

IGRAPH_ERROR("reading dimacs file failed, double 'p' line",

742

IGRAPH_PARSEERROR);

743

}

744

read=fscanf(instream, "%20s %li %li", prob,

745

&no_of_nodes, &no_of_edges);

746

if (read != 3) {

747

IGRAPH_ERROR("reading dimacs file failed", IGRAPH_PARSEERROR);

748

}

749

if (!strcmp(prob, "edge")) {

750

/* edge list */

751

problem_type=PROBLEM_EDGE;

752

if (label) {

753

long int i;

754

IGRAPH_CHECK(igraph_vector_resize(label, no_of_nodes));

755

for (i=0; i<no_of_nodes; i++) {

756

VECTOR(*label)[i]=i+1;

757

}

758

}

759

} else if (!strcmp(prob, "max")) {

760

/* maximum flow problem */

761

problem_type=PROBLEM_MAX;

762

if (capacity) {

763

IGRAPH_CHECK(igraph_vector_reserve(capacity, no_of_edges));

764

}

765

} else {

766

IGRAPH_ERROR("Unknown problem type, should be 'edge' or 'max'",

767

IGRAPH_PARSEERROR);

768

}

769

if (problem) {

770

igraph_strvector_clear(problem);

771

IGRAPH_CHECK(igraph_strvector_add(problem, prob));

772

}

773

IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges*2));

774

break;

775

776

case 'n':

777

/* for MAX this is either the source or target vertex,

778

for EDGE this is a vertex label */

779

if (problem_type == PROBLEM_MAX) {

780

str[0]='x';

781

read=fscanf(instream, "%li %1s", &tmp, str);

782

if (str[0]=='s') {

783

if (tsource != -1) {

784

IGRAPH_ERROR("reading dimacsfile: multiple source vertex line",

785

IGRAPH_PARSEERROR);

786

} else {

787

tsource=tmp;

788

}

789

} else if (str[0]=='t') {

790

if (ttarget != -1) {

791

IGRAPH_ERROR("reading dimacsfile: multiple target vertex line",

792

IGRAPH_PARSEERROR);

793

} else {

794

ttarget=tmp;

795

}

796

} else {

797

IGRAPH_ERROR("invalid node descriptor line in dimacs file",

798

IGRAPH_PARSEERROR);

799

}

800

} else {

801

read=fscanf(instream, "%li %li", &tmp, &tmp2);

802

if (label) {

803

VECTOR(*label)[tmp]=tmp2;

804

}

805

}

806

807

break;

808

809

case 'a':

810

/* This is valid only for MAX, a weighted edge */

811

if (problem_type != PROBLEM_MAX) {

812

IGRAPH_ERROR("'a' lines are allowed only in MAX problem files",

813

IGRAPH_PARSEERROR);

814

}

815

read=fscanf(instream, "%li %li %lf", &from, &to, &cap);

816

if (read != 3) {

817

IGRAPH_ERROR("reading dimacs file", IGRAPH_PARSEERROR);

818

}

819

IGRAPH_CHECK(igraph_vector_push_back(&edges, from-1));

820

IGRAPH_CHECK(igraph_vector_push_back(&edges, to-1));

821

if (capacity) {

822

IGRAPH_CHECK(igraph_vector_push_back(capacity, cap));

823

}

824

break;

825

826

case 'e':

827

/* Edge line, only in EDGE */

828

if (problem_type != PROBLEM_EDGE) {

829

IGRAPH_ERROR("'e' lines are allowed only in EDGE problem files",

830

IGRAPH_PARSEERROR);

831

}

832

read=fscanf(instream, "%li %li", &from, &to);

833

if (read != 2) {

834

IGRAPH_ERROR("reading dimacs file", IGRAPH_PARSEERROR);

835

}

836

IGRAPH_CHECK(igraph_vector_push_back(&edges, from-1));

837

IGRAPH_CHECK(igraph_vector_push_back(&edges, to-1));

838

break;

839

840

default:

841

IGRAPH_ERROR("unknown line type in dimacs file", IGRAPH_PARSEERROR);

842

}

843

844

/* Go to next line */

845

while (!feof(instream) && (c=getc(instream)) != '\n') ;

846

}

847

848

if (source) {

849

*source=tsource-1;

850

}

851

if (target) {

852

*target=ttarget-1;

853

}

854

855

IGRAPH_CHECK(igraph_create(graph, &edges, no_of_nodes, directed));

856

igraph_vector_destroy(&edges);

857

858

IGRAPH_FINALLY_CLEAN(1);

859

860

return 0;

861

}

862

863

int igraph_i_read_graph_graphdb_getword(FILE *instream) {

864

int b1, b2;

865

unsigned char c1, c2;

866

b1 = fgetc(instream);

867

b2 = fgetc(instream);

868

if (b1 != EOF) {

869

c1=b1; c2=b2;

870

return c1 | (c2<<8);

871

} else {

872

return -1;

873

}

874

}

875

876

/**

877

* \function igraph_read_graph_graphdb

878

* \brief Read a graph in the binary graph database format.

879

880

* This is a binary format, used in the graph database

881

* for isomorphism testing (http://amalfi.dis.unina.it/graph/)

882

* From the graph database homepage

883

* (http://amalfi.dis.unina.it/graph/db/doc/graphdbat-2.html):

884

* </para>

885

886

* \blockquote <para>

887

* The graphs are stored in a compact binary format, one graph per

888

* file. The file is composed of 16 bit words, which are represented

889

* using the so-called little-endian convention, i.e. the least

890

* significant byte of the word is stored first.</para>

891

892

* <para>

893

* Then, for each node, the file contains the list of edges coming

894

* out of the node itself. The list is represented by a word encoding

895

* its length, followed by a word for each edge, representing the

896

* destination node of the edge. Node numeration is 0-based, so the

897

* first node of the graph has index 0.</para> \endblockquote

898

899

* <para>

900

* Only unlabelled graphs are implemented.

901

* \param graph Pointer to an uninitialized graph object.

902

* \param instream The stream to read from.

903

* \param directed Logical scalar, whether to create a directed graph.

904

* \return Error code.

905

906

* Time complexity: O(|V|+|E|), the number of vertices plus the

907

* number of edges.

908

909

910

int igraph_read_graph_graphdb(igraph_t *graph, FILE *instream,

911

igraph_bool_t directed) {

912

913

igraph_vector_t edges;

914

long int nodes;

915

long int i, j;

916

igraph_bool_t end=0;

917

918

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

919

920

nodes=igraph_i_read_graph_graphdb_getword(instream);

921

if (nodes<0) {

922

IGRAPH_ERROR("Can't read from file", IGRAPH_EFILE);

923

}

924

for (i=0; !end && i<nodes; i++) {

925

long int len=igraph_i_read_graph_graphdb_getword(instream);

926

if (len<0) {

927

end=1;

928

break;

929

}

930

for (j=0; ! end && j<len; j++) {

931

long int to=igraph_i_read_graph_graphdb_getword(instream);

932

if (to<0) {

933

end=1;

934

break;

935

}

936

IGRAPH_CHECK(igraph_vector_push_back(&edges, i));

937

IGRAPH_CHECK(igraph_vector_push_back(&edges, to));

938

}

939

}

940

941

if (end) {

942

IGRAPH_ERROR("Truncated graphdb file", IGRAPH_EFILE);

943

}

944

945

IGRAPH_CHECK(igraph_create(graph, &edges, nodes, directed));

946

igraph_vector_destroy(&edges);

947

948

IGRAPH_FINALLY_CLEAN(1);

949

return 0;

950

}

951

952

extern int igraph_gml_yyparse(void);

953

extern FILE *igraph_gml_yyin;

954

extern int igraph_gml_eof;

955

extern igraph_gml_tree_t *igraph_i_gml_parsed_tree;

956

long int igraph_gml_mylineno;

957

extern char *igraph_i_gml_errmsg;

958

959

void igraph_i_gml_destroy_attrs(igraph_vector_ptr_t **ptr) {

960

long int i;

961

igraph_vector_ptr_t *vec;

962

for (i=0; i<3; i++) {

963

long int j;

964

vec=ptr[i];

965

for (j=0; j<igraph_vector_ptr_size(vec); j++) {

966

igraph_i_attribute_record_t *atrec=VECTOR(*vec)[j];

967

if (atrec->type == IGRAPH_ATTRIBUTE_NUMERIC) {

968

igraph_vector_t *value=(igraph_vector_t*)atrec->value;

969

igraph_vector_destroy(value);

970

igraph_Free(value);

971

} else {

972

igraph_strvector_t *value=(igraph_strvector_t*)atrec->value;

973

igraph_strvector_destroy(value);

974

igraph_Free(value);

975

}

976

igraph_Free(atrec->name);

977

igraph_Free(atrec);

978

}

979

igraph_vector_ptr_destroy(vec);

980

}

981

}

982

983

igraph_real_t igraph_i_gml_toreal(igraph_gml_tree_t *node, long int pos) {

984

985

igraph_real_t value=0.0;

986

int type=igraph_gml_tree_type(node, pos);

987

988

switch (type) {

989

case IGRAPH_I_GML_TREE_INTEGER:

990

value=igraph_gml_tree_get_integer(node, pos);

991

break;

992

case IGRAPH_I_GML_TREE_REAL:

993

value=igraph_gml_tree_get_real(node, pos);

994

break;

995

default:

996

IGRAPH_ERROR("Internal error while parsing GML file", IGRAPH_FAILURE);

997

break;

998

}

999

1000

return value;

1001

}

1002

1003

const char *igraph_i_gml_tostring(igraph_gml_tree_t *node, long int pos) {

1004

1005

int type=igraph_gml_tree_type(node, pos);

1006

static char tmp[256];

1007

const char *p=tmp;

1008

long int i;

1009

igraph_real_t d;

1010

1011

switch (type) {

1012

case IGRAPH_I_GML_TREE_INTEGER:

1013

i=igraph_gml_tree_get_integer(node, pos);

1014

snprintf(tmp, sizeof(tmp)/sizeof(char), "%li", i);

1015

break;

1016

case IGRAPH_I_GML_TREE_REAL:

1017

d=igraph_gml_tree_get_real(node, pos);

1018

snprintf(tmp, sizeof(tmp)/sizeof(char), "%g", d);

1019

break;

1020

case IGRAPH_I_GML_TREE_STRING:

1021

p=igraph_gml_tree_get_string(node, pos);

1022

break;

1023

default:

1024

break;

1025

}

1026

1027

return p;

1028

}

1029

1030

/**

1031

* \function igraph_read_graph_gml

1032

* \brief Read a graph in GML format.

1033

1034

* GML is a simple textual format, see

1035

* http://www.infosun.fim.uni-passau.de/Graphlet/GML/ for details.

1036

1037

* </para><para>

1038

* Although all syntactically correct GML can be parsed,

1039

* we implement only a subset of this format, some attributes might be

1040

* ignored. Here is a list of all the differences:

1041

* \olist

1042

* \oli Only <code>node</code> and <code>edge</code> attributes are

1043

* used, and only if they have a simple type: integer, real or

1044

* string. So if an attribute is an array or a record, then it is

1045

* ignored. This is also true if only some values of the

1046

* attribute are complex.

1047

* \oli Top level attributes except for <code>Version</code> and the

1048

* first <code>graph</code> attribute are completely ignored.

1049

* \oli Graph attributes except for <code>node</code> and

1050

* <code>edge</code> are completely ignored.

1051

* \oli There is no maximum line length.

1052

* \oli There is no maximum keyword length.

1053

* \oli Character entities in strings are not interpreted.

1054

* \oli We allow <code>inf</code> (infinity) and <code>nan</code>

1055

* (not a number) as a real number. This is case insensitive, so

1056

* <code>nan</code>, <code>NaN</code> and <code>NAN</code> are equal.

1057

* \endolist

1058

1059

* </para><para> Please contact us if you cannot live with these

1060

* limitations of the GML parser.

1061

* \param graph Pointer to an uninitialized graph object.

1062

* \param instream The stream to read the GML file from.

1063

* \return Error code.

1064

1065

* Time complexity: should be proportional to the length of the file.

1066

1067

* \sa \ref igraph_read_graph_graphml() for a more modern format,

1068

* \ref igraph_write_graph_gml() for writing GML files.

1069

1070

1071

int igraph_read_graph_gml(igraph_t *graph, FILE *instream) {

1072

1073

long int i, p;

1074

long int no_of_nodes=0, no_of_edges=0;

1075

igraph_trie_t trie;

1076

igraph_vector_t edges;

1077

igraph_bool_t directed=IGRAPH_UNDIRECTED;

1078

igraph_gml_tree_t *gtree;

1079

long int gidx;

1080

igraph_trie_t vattrnames;

1081

igraph_trie_t eattrnames;

1082

igraph_trie_t gattrnames;

1083

igraph_vector_ptr_t gattrs=IGRAPH_VECTOR_PTR_NULL,

1084

vattrs=IGRAPH_VECTOR_PTR_NULL, eattrs=IGRAPH_VECTOR_PTR_NULL;

1085

igraph_vector_ptr_t *attrs[3];

1086

long int edgeptr=0;

1087

1088

attrs[0]=&gattrs; attrs[1]=&vattrs; attrs[2]=&eattrs;

1089

1090

igraph_gml_yyin=instream;

1091

igraph_gml_mylineno=1;

1092

igraph_gml_eof=0;

1093

igraph_i_gml_errmsg=0;

1094

1095

i=igraph_gml_yyparse();

1096

if (i != 0) {

1097

if (igraph_i_gml_errmsg) {

1098

IGRAPH_ERROR(igraph_i_gml_errmsg, IGRAPH_PARSEERROR);

1099

} else {

1100

IGRAPH_ERROR("Cannot read GML file", IGRAPH_PARSEERROR);

1101

}

1102

}

1103

1104

IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);

1105

1106

/* Check version, if present, integer and not '1' then ignored */

1107

i=igraph_gml_tree_find(igraph_i_gml_parsed_tree, "Version", 0);

1108

if (i>=0 &&

1109

igraph_gml_tree_type(igraph_i_gml_parsed_tree, i)==IGRAPH_I_GML_TREE_INTEGER &&

1110

igraph_gml_tree_get_integer(igraph_i_gml_parsed_tree, i) != 1) {

1111

igraph_gml_tree_destroy(igraph_i_gml_parsed_tree);

1112

IGRAPH_ERROR("Unknown GML version", IGRAPH_UNIMPLEMENTED);

1113

/* RETURN HERE!!!! */

1114

}

1115

1116

/* get the graph */

1117

gidx=igraph_gml_tree_find(igraph_i_gml_parsed_tree, "graph", 0);

1118

if (gidx==-1) {

1119

IGRAPH_ERROR("No 'graph' object in GML file", IGRAPH_PARSEERROR);

1120

}

1121

if (igraph_gml_tree_type(igraph_i_gml_parsed_tree, gidx) !=

1122

IGRAPH_I_GML_TREE_TREE) {

1123

IGRAPH_ERROR("Invalid type for 'graph' object in GML file", IGRAPH_PARSEERROR);

1124

}

1125

gtree=igraph_gml_tree_get_tree(igraph_i_gml_parsed_tree, gidx);

1126

1127

IGRAPH_FINALLY(igraph_i_gml_destroy_attrs, &attrs);

1128

igraph_vector_ptr_init(&gattrs, 0);

1129

igraph_vector_ptr_init(&vattrs, 0);

1130

igraph_vector_ptr_init(&eattrs, 0);

1131

1132

IGRAPH_TRIE_INIT_FINALLY(&trie, 0);

1133

IGRAPH_TRIE_INIT_FINALLY(&vattrnames, 0);

1134

IGRAPH_TRIE_INIT_FINALLY(&eattrnames, 0);

1135

IGRAPH_TRIE_INIT_FINALLY(&gattrnames, 0);

1136

1137

/* Is is directed? */

1138

i=igraph_gml_tree_find(gtree, "directed", 0);

1139

if (i>=0 && igraph_gml_tree_type(gtree, i)==IGRAPH_I_GML_TREE_INTEGER) {

1140

if (igraph_gml_tree_get_integer(gtree, i) == 1) {

1141

directed=IGRAPH_DIRECTED;

1142

}

1143

}

1144

1145

/* Now we go over all objects in the graph and collect the attribute names and

1146

types. Plus we collect node ids. We also do some checks. */

1147

for (i=0; i<igraph_gml_tree_length(gtree); i++) {

1148

long int j;

1149

char cname[100];

1150

const char *name=igraph_gml_tree_name(gtree, i);

1151

if (!strcmp(name, "node")) {

1152

igraph_gml_tree_t *node;

1153

igraph_bool_t hasid;

1154

no_of_nodes++;

1155

if (igraph_gml_tree_type(gtree, i) != IGRAPH_I_GML_TREE_TREE) {

1156

IGRAPH_ERROR("'node' is not a list", IGRAPH_PARSEERROR);

1157

}

1158

node=igraph_gml_tree_get_tree(gtree, i);

1159

hasid=0;

1160

for (j=0; j<igraph_gml_tree_length(node); j++) {

1161

const char *name=igraph_gml_tree_name(node, j);

1162

long int trieid, triesize=igraph_trie_size(&vattrnames);

1163

IGRAPH_CHECK(igraph_trie_get(&vattrnames, name, &trieid));

1164

if (trieid==triesize) {

1165

/* new attribute */

1166

igraph_i_attribute_record_t *atrec=igraph_Calloc(1, igraph_i_attribute_record_t);

1167

int type=igraph_gml_tree_type(node, j);

1168

if (!atrec) {

1169

IGRAPH_ERROR("Cannot read GML file", IGRAPH_ENOMEM);

1170

}

1171

IGRAPH_CHECK(igraph_vector_ptr_push_back(&vattrs, atrec));

1172

atrec->name=strdup(name);

1173

if (type==IGRAPH_I_GML_TREE_INTEGER || type==IGRAPH_I_GML_TREE_REAL) {

1174

atrec->type=IGRAPH_ATTRIBUTE_NUMERIC;

1175

} else {

1176

atrec->type=IGRAPH_ATTRIBUTE_STRING;

1177

}

1178

} else {

1179

/* already seen, should we update type? */

1180

igraph_i_attribute_record_t *atrec=VECTOR(vattrs)[trieid];

1181

int type1=atrec->type;

1182

int type2=igraph_gml_tree_type(node, j);

1183

if (type1==IGRAPH_ATTRIBUTE_NUMERIC && type2==IGRAPH_I_GML_TREE_STRING) {

1184

atrec->type=IGRAPH_ATTRIBUTE_STRING;

1185

}

1186

}

1187

/* check id */

1188

if (!hasid && !strcmp(name, "id")) {

1189

long int id;

1190

if (igraph_gml_tree_type(node, j) != IGRAPH_I_GML_TREE_INTEGER) {

1191

IGRAPH_ERROR("Non-integer node id in GML file", IGRAPH_PARSEERROR);

1192

}

1193

id=igraph_gml_tree_get_integer(node, j);

1194

snprintf(cname, sizeof(cname)/sizeof(char)-1, "%li", id);

1195

IGRAPH_CHECK(igraph_trie_get(&trie, cname, &id));

1196

hasid=1;

1197

}

1198

}

1199

if (!hasid) {

1200

IGRAPH_ERROR("Node without 'id' while parsing GML file", IGRAPH_PARSEERROR);

1201

}

1202

} else if (!strcmp(name, "edge")) {

1203

igraph_gml_tree_t *edge;

1204

igraph_bool_t has_source=0, has_target=0;

1205

no_of_edges++;

1206

if (igraph_gml_tree_type(gtree, i) != IGRAPH_I_GML_TREE_TREE) {

1207

IGRAPH_ERROR("'edge' is not a list", IGRAPH_PARSEERROR);

1208

}

1209

edge=igraph_gml_tree_get_tree(gtree, i);

1210

has_source=has_target=0;

1211

for (j=0; j<igraph_gml_tree_length(edge); j++) {

1212

const char *name=igraph_gml_tree_name(edge, j);

1213

if (!strcmp(name, "source")) {

1214

has_source=1;

1215

if (igraph_gml_tree_type(edge, j) != IGRAPH_I_GML_TREE_INTEGER) {

1216

IGRAPH_ERROR("Non-integer 'source' for an edge in GML file",

1217

IGRAPH_PARSEERROR);

1218

}

1219

} else if (!strcmp(name, "target")) {

1220

has_target=1;

1221

if (igraph_gml_tree_type(edge, j) != IGRAPH_I_GML_TREE_INTEGER) {

1222

IGRAPH_ERROR("Non-integer 'source' for an edge in GML file",

1223

IGRAPH_PARSEERROR);

1224

}

1225

} else {

1226

long int trieid, triesize=igraph_trie_size(&eattrnames);

1227

IGRAPH_CHECK(igraph_trie_get(&eattrnames, name, &trieid));

1228

if (trieid==triesize) {

1229

/* new attribute */

1230

igraph_i_attribute_record_t *atrec=igraph_Calloc(1, igraph_i_attribute_record_t);

1231

int type=igraph_gml_tree_type(edge, j);

1232

if (!atrec) {

1233

IGRAPH_ERROR("Cannot read GML file", IGRAPH_ENOMEM);

1234

}

1235

IGRAPH_CHECK(igraph_vector_ptr_push_back(&eattrs, atrec));

1236

atrec->name=strdup(name);

1237

if (type==IGRAPH_I_GML_TREE_INTEGER || type==IGRAPH_I_GML_TREE_REAL) {

1238

atrec->type=IGRAPH_ATTRIBUTE_NUMERIC;

1239

} else {

1240

atrec->type=IGRAPH_ATTRIBUTE_STRING;

1241

}

1242

} else {

1243

/* already seen, should we update type? */

1244

igraph_i_attribute_record_t *atrec=VECTOR(eattrs)[trieid];

1245

int type1=atrec->type;

1246

int type2=igraph_gml_tree_type(edge, j);

1247

if (type1==IGRAPH_ATTRIBUTE_NUMERIC && type2==IGRAPH_I_GML_TREE_STRING) {

1248

atrec->type=IGRAPH_ATTRIBUTE_STRING;

1249

}

1250

}

1251

}

1252

} /* for */

1253

if (!has_source) {

1254

IGRAPH_ERROR("No 'source' for edge in GML file", IGRAPH_PARSEERROR);

1255

}

1256

if (!has_target) {

1257

IGRAPH_ERROR("No 'target' for edge in GML file", IGRAPH_PARSEERROR);

1258

}

1259

} else {

1260

/* anything to do? Maybe add as graph attribute.... */

1261

}

1262

}

1263

1264

/* check vertex id uniqueness */

1265

if (igraph_trie_size(&trie) != no_of_nodes) {

1266

IGRAPH_ERROR("Node 'id' not unique", IGRAPH_PARSEERROR);

1267

}

1268

1269

/* now we allocate the vectors and strvectors for the attributes */

1270

for (i=0; i<igraph_vector_ptr_size(&vattrs); i++) {

1271

igraph_i_attribute_record_t *atrec=VECTOR(vattrs)[i];

1272

int type=atrec->type;

1273

if (type == IGRAPH_ATTRIBUTE_NUMERIC) {

1274

igraph_vector_t *p=igraph_Calloc(1, igraph_vector_t);

1275

atrec->value=p;

1276

IGRAPH_CHECK(igraph_vector_init(p, no_of_nodes));

1277

} else if (type == IGRAPH_ATTRIBUTE_STRING) {

1278

igraph_strvector_t *p=igraph_Calloc(1, igraph_strvector_t);

1279

atrec->value=p;

1280

IGRAPH_CHECK(igraph_strvector_init(p, no_of_nodes));

1281

} else {

1282

IGRAPH_WARNING("A composite attribute ignored");

1283

}

1284

}

1285

1286

for (i=0; i<igraph_vector_ptr_size(&eattrs); i++) {

1287

igraph_i_attribute_record_t *atrec=VECTOR(eattrs)[i];

1288

int type=atrec->type;

1289

if (type == IGRAPH_ATTRIBUTE_NUMERIC) {

1290

igraph_vector_t *p=igraph_Calloc(1, igraph_vector_t);

1291

atrec->value=p;

1292

IGRAPH_CHECK(igraph_vector_init(p, no_of_edges));

1293

} else if (type == IGRAPH_ATTRIBUTE_STRING) {

1294

igraph_strvector_t *p=igraph_Calloc(1, igraph_strvector_t);

1295

atrec->value=p;

1296

IGRAPH_CHECK(igraph_strvector_init(p, no_of_edges));

1297

} else {

1298

IGRAPH_WARNING("A composite attribute ignored");

1299

}

1300

}

1301

1302

/* Ok, now the edges, attributes too */

1303

IGRAPH_CHECK(igraph_vector_resize(&edges, no_of_edges*2));

1304

p=-1;

1305

while ( (p=igraph_gml_tree_find(gtree, "edge", p+1)) != -1) {

1306

igraph_gml_tree_t *edge;

1307

long int from, to, fromidx=0, toidx=0;

1308

char name[100];

1309

long int j;

1310

edge=igraph_gml_tree_get_tree(gtree, p);

1311

for (j=0; j<igraph_gml_tree_length(edge); j++) {

1312

const char *n=igraph_gml_tree_name(edge, j);

1313

if (!strcmp(n, "source")) {

1314

fromidx=igraph_gml_tree_find(edge, "source", 0);

1315

} else if (!strcmp(n, "target")) {

1316

toidx=igraph_gml_tree_find(edge, "target", 0);

1317

} else {

1318

long int edgeid=edgeptr/2;

1319

long int trieidx;

1320

igraph_i_attribute_record_t *atrec;

1321

int type;

1322

igraph_trie_get(&eattrnames, n, &trieidx);

1323

atrec=VECTOR(eattrs)[trieidx];

1324

type=atrec->type;

1325

if (type==IGRAPH_ATTRIBUTE_NUMERIC) {

1326

igraph_vector_t *v=(igraph_vector_t *)atrec->value;

1327

VECTOR(*v)[edgeid]=igraph_i_gml_toreal(edge, j);

1328

} else if (type==IGRAPH_ATTRIBUTE_STRING) {

1329

igraph_strvector_t *v=(igraph_strvector_t *)atrec->value;

1330

const char *value=igraph_i_gml_tostring(edge, j);

1331

IGRAPH_CHECK(igraph_strvector_set(v, edgeid, value));

1332

}

1333

}

1334

}

1335

from=igraph_gml_tree_get_integer(edge, fromidx);

1336

to=igraph_gml_tree_get_integer(edge, toidx);

1337

snprintf(name, sizeof(name)/sizeof(char)-1, "%li", from);

1338

IGRAPH_CHECK(igraph_trie_get(&trie, name, &from));

1339

snprintf(name, sizeof(name)/sizeof(char)-1, "%li", to);

1340

IGRAPH_CHECK(igraph_trie_get(&trie, name, &to));

1341

if (igraph_trie_size(&trie) != no_of_nodes) {

1342

IGRAPH_ERROR("Unkown node id found at an edge", IGRAPH_PARSEERROR);

1343

}

1344

VECTOR(edges)[edgeptr++]=from;

1345

VECTOR(edges)[edgeptr++]=to;

1346

}

1347

1348

/* and add vertex attributes */

1349

for (i=0; i<igraph_gml_tree_length(gtree); i++) {

1350

const char *n;

1351

char name[100];

1352

long int j, k;

1353

n=igraph_gml_tree_name(gtree, i);

1354

if (!strcmp(n, "node")) {

1355

igraph_gml_tree_t *node=igraph_gml_tree_get_tree(gtree, i);

1356

long int iidx=igraph_gml_tree_find(node, "id", 0);

1357

long int id=igraph_gml_tree_get_integer(node, iidx);

1358

snprintf(name, sizeof(name)/sizeof(char)-1, "%li", id);

1359

igraph_trie_get(&trie, name, &id);

1360

for (j=0; j<igraph_gml_tree_length(node); j++) {

1361

const char *aname=igraph_gml_tree_name(node, j);

1362

igraph_i_attribute_record_t *atrec;

1363

int type;

1364

igraph_trie_get(&vattrnames, aname, &k);

1365

atrec=VECTOR(vattrs)[k];

1366

type=atrec->type;

1367

if (type==IGRAPH_ATTRIBUTE_NUMERIC) {

1368

igraph_vector_t *v=(igraph_vector_t *)atrec->value;

1369

VECTOR(*v)[id]=igraph_i_gml_toreal(node, j);

1370

} else if (type==IGRAPH_ATTRIBUTE_STRING) {

1371

igraph_strvector_t *v=(igraph_strvector_t *)atrec->value;

1372

const char *value=igraph_i_gml_tostring(node, j);

1373

IGRAPH_CHECK(igraph_strvector_set(v, id, value));

1374

}

1375

}

1376

}

1377

}

1378

1379

igraph_gml_tree_destroy(igraph_i_gml_parsed_tree);

1380

1381

igraph_trie_destroy(&trie);

1382

igraph_trie_destroy(&gattrnames);

1383

igraph_trie_destroy(&vattrnames);

1384

igraph_trie_destroy(&eattrnames);

1385

IGRAPH_FINALLY_CLEAN(4);

1386

1387

IGRAPH_CHECK(igraph_empty_attrs(graph, 0, directed, 0)); /* TODO */

1388

IGRAPH_CHECK(igraph_add_vertices(graph, no_of_nodes, &vattrs));

1389

IGRAPH_CHECK(igraph_add_edges(graph, &edges, &eattrs));

1390

1391

igraph_i_gml_destroy_attrs(attrs);

1392

igraph_vector_destroy(&edges);

1393

IGRAPH_FINALLY_CLEAN(2);

1394

1395

return 0;

1396

}

1397

1398

/**

1399

* \ingroup loadsave

1400

* \function igraph_write_graph_edgelist

1401

* \brief Writes the edge list of a graph to a file.

1402

1403

* </para><para>

1404

* One edge is written per line, separated by a single space.

1405

* For directed graphs edges are written in from, to order.

1406

* \param graph The graph object to write.

1407

* \param outstream Pointer to a stream, it should be writable.

1408

* \return Error code:

1409

* \c IGRAPH_EFILE if there is an error writing the

1410

* file.

1411

1412

* Time complexity: O(|E|), the

1413

* number of edges in the graph. It is assumed that writing an

1414

* integer to the file requires O(1)

1415

* time.

1416

1417

1418

int igraph_write_graph_edgelist(const igraph_t *graph, FILE *outstream) {

1419

1420

igraph_eit_t it;

1421

1422

IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(IGRAPH_EDGEORDER_FROM),

1423

&it));

1424

IGRAPH_FINALLY(igraph_eit_destroy, &it);

1425

1426

while (!IGRAPH_EIT_END(it)) {

1427

igraph_integer_t from, to;

1428

int ret;

1429

igraph_edge(graph, IGRAPH_EIT_GET(it), &from, &to);

1430

ret=fprintf(outstream, "%li %li\n",

1431

(long int) from,

1432

(long int) to);

1433

if (ret < 0) {

1434

IGRAPH_ERROR("Write error", IGRAPH_EFILE);

1435

}

1436

IGRAPH_EIT_NEXT(it);

1437

}

1438

1439

igraph_eit_destroy(&it);

1440

IGRAPH_FINALLY_CLEAN(1);

1441

return 0;

1442

}

1443

1444

/**

1445

* \ingroup loadsave

1446

* \function igraph_write_graph_ncol

1447

* \brief Writes the graph to a file in <code>.ncol</code> format

1448

1449

* </para><para>

1450

* <code>.ncol</code> is a format used by LGL, see \ref

1451

* igraph_read_graph_ncol() for details.

1452

1453

* </para><para>

1454

* Note that having multiple or loop edges in an

1455

* <code>.ncol</code> file breaks the LGL software but

1456

* \a igraph does not check for this condition.

1457

* \param graph The graph to write.

1458

* \param outstream The stream object to write to, it should be

1459

* writable.

1460

* \param names The name of the vertex attribute, if symbolic names

1461

* are written to the file. If not, supply 0 here.

1462

* \param weights The name of the edge attribute, if they are also

1463

* written to the file. If you don't want weights, supply 0

1464

* here.

1465

* \return Error code:

1466

* \c IGRAPH_EFILE if there is an error writing the

1467

* file.

1468

1469

* Time complexity: O(|E|), the

1470

* number of edges. All file operations are expected to have time

1471

* complexity O(1).

1472

1473

* \sa \ref igraph_read_graph_ncol(), \ref igraph_write_graph_lgl()

1474

1475

1476

int igraph_write_graph_ncol(const igraph_t *graph, FILE *outstream,

1477

const char *names, const char *weights) {

1478

igraph_eit_t it;

1479

igraph_attribute_type_t nametype, weighttype;

1480

1481

IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(IGRAPH_EDGEORDER_FROM),

1482

&it));

1483

IGRAPH_FINALLY(igraph_eit_destroy, &it);

1484

1485

/* Check if we have the names attribute */

1486

if (names && !igraph_i_attribute_has_attr(graph, IGRAPH_ATTRIBUTE_VERTEX,

1487

names)) {

1488

names=0;

1489

IGRAPH_WARNING("names attribute does not exists");

1490

}

1491

if (names) {

1492

IGRAPH_CHECK(igraph_i_attribute_gettype(graph, &nametype,

1493

IGRAPH_ATTRIBUTE_VERTEX, names));

1494

}

1495

if (names && nametype != IGRAPH_ATTRIBUTE_NUMERIC &&

1496

nametype != IGRAPH_ATTRIBUTE_STRING) {

1497

IGRAPH_WARNING("ignoring names attribute, unknown attribute type");

1498

names=0;

1499

}

1500

1501

/* Check the weights as well */

1502

if (weights && !igraph_i_attribute_has_attr(graph, IGRAPH_ATTRIBUTE_EDGE,

1503

weights)) {

1504

weights=0;

1505

IGRAPH_WARNING("weights attribute does not exists");

1506

}

1507

if (weights) {

1508

IGRAPH_CHECK(igraph_i_attribute_gettype(graph, &weighttype,

1509

IGRAPH_ATTRIBUTE_EDGE, weights));

1510

}

1511

if (weights && weighttype != IGRAPH_ATTRIBUTE_NUMERIC) {

1512

IGRAPH_WARNING("ignoring weights attribute, unknown attribute type");

1513

weights=0;

1514

}

1515

1516

if (names==0 && weights ==0) {

1517

/* No names, no weights */

1518

while (!IGRAPH_EIT_END(it)) {

1519

igraph_integer_t from, to;

1520

int ret;

1521

igraph_edge(graph, IGRAPH_EIT_GET(it), &from, &to);

1522

ret=fprintf(outstream, "%li %li\n",

1523

(long int) from,

1524

(long int) to);

1525

if (ret<0) {

1526

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1527

}

1528

IGRAPH_EIT_NEXT(it);

1529

}

1530

} else if (weights==0) {

1531

/* No weights, but use names */

1532

igraph_strvector_t nvec;

1533

IGRAPH_CHECK(igraph_strvector_init(&nvec, igraph_vcount(graph)));

1534

IGRAPH_FINALLY(igraph_strvector_destroy, &nvec);

1535

IGRAPH_CHECK(igraph_i_attribute_get_string_vertex_attr(graph, names,

1536

igraph_vss_all(),

1537

&nvec));

1538

while (!IGRAPH_EIT_END(it)) {

1539

igraph_integer_t edge=IGRAPH_EIT_GET(it);

1540

igraph_integer_t from, to;

1541

int ret=0;

1542

char *str1, *str2;

1543

igraph_edge(graph, edge, &from, &to);

1544

igraph_strvector_get(&nvec, from, &str1);

1545

igraph_strvector_get(&nvec, to, &str2);

1546

ret=fprintf(outstream, "%s %s\n", str1, str2);

1547

if (ret<0) {

1548

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1549

}

1550

IGRAPH_EIT_NEXT(it);

1551

}

1552

igraph_strvector_destroy(&nvec);

1553

IGRAPH_FINALLY_CLEAN(1);

1554

} else if (names==0) {

1555

/* No names but weights */

1556

igraph_vector_t wvec;

1557

IGRAPH_VECTOR_INIT_FINALLY(&wvec, igraph_ecount(graph));

1558

IGRAPH_CHECK(igraph_i_attribute_get_numeric_edge_attr(graph, weights,

1559

igraph_ess_all(IGRAPH_EDGEORDER_FROM),

1560

&wvec));

1561

while (!IGRAPH_EIT_END(it)) {

1562

igraph_integer_t edge=IGRAPH_EIT_GET(it);

1563

igraph_integer_t from, to;

1564

int ret=0;

1565

igraph_edge(graph, edge, &from, &to);

1566

ret=fprintf(outstream, "%li %li %f\n",

1567

(long int)from, (long int)to, VECTOR(wvec)[(long int)edge]);

1568

if (ret<0) {

1569

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1570

}

1571

IGRAPH_EIT_NEXT(it);

1572

}

1573

igraph_vector_destroy(&wvec);

1574

IGRAPH_FINALLY_CLEAN(1);

1575

} else {

1576

/* Both names and weights */

1577

igraph_strvector_t nvec;

1578

igraph_vector_t wvec;

1579

IGRAPH_VECTOR_INIT_FINALLY(&wvec, igraph_ecount(graph));

1580

IGRAPH_CHECK(igraph_strvector_init(&nvec, igraph_vcount(graph)));

1581

IGRAPH_FINALLY(igraph_strvector_destroy, &nvec);

1582

IGRAPH_CHECK(igraph_i_attribute_get_numeric_edge_attr(graph, weights,

1583

igraph_ess_all(IGRAPH_EDGEORDER_FROM),

1584

&wvec));

1585

IGRAPH_CHECK(igraph_i_attribute_get_string_vertex_attr(graph, names,

1586

igraph_vss_all(),

1587

&nvec));

1588

while (!IGRAPH_EIT_END(it)) {

1589

igraph_integer_t edge=IGRAPH_EIT_GET(it);

1590

igraph_integer_t from, to;

1591

int ret=0;

1592

char *str1, *str2;

1593

igraph_edge(graph, edge, &from, &to);

1594

igraph_strvector_get(&nvec, from, &str1);

1595

igraph_strvector_get(&nvec, to, &str2);

1596

ret=fprintf(outstream, "%s %s ", str1, str2);

1597

if (ret<0) {

1598

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1599

}

1600

ret=fprintf(outstream, "%f\n", VECTOR(wvec)[(long int)edge]);

1601

if (ret<0) {

1602

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1603

}

1604

IGRAPH_EIT_NEXT(it);

1605

}

1606

igraph_strvector_destroy(&nvec);

1607

igraph_vector_destroy(&wvec);

1608

IGRAPH_FINALLY_CLEAN(2);

1609

}

1610

1611

igraph_eit_destroy(&it);

1612

IGRAPH_FINALLY_CLEAN(1);

1613

return 0;

1614

}

1615

1616

/**

1617

* \ingroup loadsave

1618

* \function igraph_write_graph_lgl

1619

* \brief Writes the graph to a file in <code>.lgl</code> format

1620

1621

* </para><para>

1622

* <code>.lgl</code> is a format used by LGL, see \ref

1623

* igraph_read_graph_lgl() for details.

1624

1625

* </para><para>

1626

* Note that having multiple or loop edges in an

1627

* <code>.lgl</code> file breaks the LGL software but \a igraph

1628

* does not check for this condition.

1629

* \param graph The graph to write.

1630

* \param outstream The stream object to write to, it should be

1631

* writable.

1632

* \param names The name of the vertex attribute, if symbolic names

1633

* are written to the file. If not supply 0 here.

1634

* \param weights The name of the edge attribute, if they are also

1635

* written to the file. If you don't want weights supply 0

1636

* here.

1637

* \param isolates Logical, if TRUE isolated vertices are also written

1638

* to the file. If FALSE they will be omitted.

1639

* \return Error code:

1640

* \c IGRAPH_EFILE if there is an error

1641

* writing the file.

1642

1643

* Time complexity: O(|E|), the

1644

* number of edges if \p isolates is

1645

* FALSE, O(|V|+|E|) otherwise. All

1646

* file operations are expected to have time complexity

1647

* O(1).

1648

1649

* \sa \ref igraph_read_graph_ncol(), \ref igraph_write_graph_lgl()

1650

1651

1652

int igraph_write_graph_lgl(const igraph_t *graph, FILE *outstream,

1653

const char *names, const char *weights,

1654

igraph_bool_t isolates) {

1655

igraph_eit_t it;

1656

long int actvertex=-1;

1657

igraph_attribute_type_t nametype, weighttype;

1658

1659

IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(IGRAPH_EDGEORDER_FROM),

1660

&it));

1661

IGRAPH_FINALLY(igraph_eit_destroy, &it);

1662

1663

/* Check if we have the names attribute */

1664

if (names && !igraph_i_attribute_has_attr(graph, IGRAPH_ATTRIBUTE_VERTEX,

1665

names)) {

1666

names=0;

1667

IGRAPH_WARNING("names attribute does not exists");

1668

}

1669

if (names) {

1670

IGRAPH_CHECK(igraph_i_attribute_gettype(graph, &nametype,

1671

IGRAPH_ATTRIBUTE_VERTEX, names));

1672

}

1673

if (names && nametype != IGRAPH_ATTRIBUTE_NUMERIC &&

1674

nametype != IGRAPH_ATTRIBUTE_STRING) {

1675

IGRAPH_WARNING("ignoring names attribute, unknown attribute type");

1676

names=0;

1677

}

1678

1679

/* Check the weights as well */

1680

if (weights && !igraph_i_attribute_has_attr(graph, IGRAPH_ATTRIBUTE_EDGE,

1681

weights)) {

1682

weights=0;

1683

IGRAPH_WARNING("weights attribute does not exists");

1684

}

1685

if (weights) {

1686

IGRAPH_CHECK(igraph_i_attribute_gettype(graph, &weighttype,

1687

IGRAPH_ATTRIBUTE_EDGE, weights));

1688

}

1689

if (weights && weighttype != IGRAPH_ATTRIBUTE_NUMERIC) {

1690

IGRAPH_WARNING("ignoring weights attribute, unknown attribute type");

1691

weights=0;

1692

}

1693

1694

if (names==0 && weights==0) {

1695

/* No names, no weights */

1696

while (!IGRAPH_EIT_END(it)) {

1697

igraph_integer_t from, to;

1698

int ret;

1699

igraph_edge(graph, IGRAPH_EIT_GET(it), &from, &to);

1700

if (from==actvertex) {

1701

ret=fprintf(outstream, "%li\n", (long int)to);

1702

} else {

1703

actvertex=from;

1704

ret=fprintf(outstream, "# %li\n%li\n", (long int)from, (long int)to);

1705

}

1706

if (ret<0) {

1707

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1708

}

1709

IGRAPH_EIT_NEXT(it);

1710

}

1711

} else if (weights==0) {

1712

/* No weights but use names */

1713

igraph_strvector_t nvec;

1714

IGRAPH_CHECK(igraph_strvector_init(&nvec, igraph_vcount(graph)));

1715

IGRAPH_FINALLY(igraph_strvector_destroy, &nvec);

1716

IGRAPH_CHECK(igraph_i_attribute_get_string_vertex_attr(graph, names,

1717

igraph_vss_all(),

1718

&nvec));

1719

while (!IGRAPH_EIT_END(it)) {

1720

igraph_integer_t edge=IGRAPH_EIT_GET(it);

1721

igraph_integer_t from, to;

1722

int ret=0;

1723

char *str1, *str2;

1724

igraph_edge(graph, edge, &from, &to);

1725

igraph_strvector_get(&nvec, to, &str2);

1726

1727

if (from==actvertex) {

1728

ret=fprintf(outstream, "%s\n", str2);

1729

} else {

1730

actvertex=from;

1731

igraph_strvector_get(&nvec, from, &str1);

1732

ret=fprintf(outstream, "# %s\n%s\n", str1, str2);

1733

}

1734

if (ret<0) {

1735

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1736

}

1737

IGRAPH_EIT_NEXT(it);

1738

}

1739

IGRAPH_FINALLY_CLEAN(1);

1740

} else if (names==0) {

1741

igraph_strvector_t wvec;

1742

IGRAPH_CHECK(igraph_strvector_init(&wvec, igraph_ecount(graph)));

1743

IGRAPH_FINALLY(igraph_strvector_destroy, &wvec);

1744

IGRAPH_CHECK(igraph_i_attribute_get_string_edge_attr(graph, weights,

1745

igraph_ess_all(IGRAPH_EDGEORDER_FROM),

1746

&wvec));

1747

/* No names but weights */

1748

while (!IGRAPH_EIT_END(it)) {

1749

igraph_integer_t edge=IGRAPH_EIT_GET(it);

1750

igraph_integer_t from, to;

1751

int ret=0;

1752

char *str1;

1753

igraph_edge(graph, edge, &from, &to);

1754

igraph_strvector_get(&wvec, edge, &str1);

1755

if (from==actvertex) {

1756

ret=fprintf(outstream, "%li %s\n", (long)to, str1);

1757

} else {

1758

actvertex=from;

1759

ret=fprintf(outstream, "# %li\n%li %s\n", (long)from, (long)to, str1);

1760

}

1761

if (ret<0) {

1762

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1763

}

1764

IGRAPH_EIT_NEXT(it);

1765

}

1766

igraph_strvector_destroy(&wvec);

1767

IGRAPH_FINALLY_CLEAN(1);

1768

} else {

1769

/* Both names and weights */

1770

igraph_strvector_t nvec, wvec;

1771

IGRAPH_CHECK(igraph_strvector_init(&wvec, igraph_ecount(graph)));

1772

IGRAPH_FINALLY(igraph_strvector_destroy, &wvec);

1773

IGRAPH_CHECK(igraph_strvector_init(&nvec, igraph_vcount(graph)));

1774

IGRAPH_FINALLY(igraph_strvector_destroy, &nvec);

1775

IGRAPH_CHECK(igraph_i_attribute_get_string_edge_attr(graph, weights,

1776

igraph_ess_all(IGRAPH_EDGEORDER_FROM),

1777

&wvec));

1778

IGRAPH_CHECK(igraph_i_attribute_get_string_vertex_attr(graph, names,

1779

igraph_vss_all(),

1780

&nvec));

1781

while (!IGRAPH_EIT_END(it)) {

1782

igraph_integer_t edge=IGRAPH_EIT_GET(it);

1783

igraph_integer_t from, to;

1784

int ret=0;

1785

char *str1, *str2, *str3;

1786

igraph_edge(graph, edge, &from, &to);

1787

igraph_strvector_get(&nvec, to, &str2);

1788

igraph_strvector_get(&wvec, edge, &str3);

1789

if (from==actvertex) {

1790

ret=fprintf(outstream, "%s ", str2);

1791

} else {

1792

actvertex=from;

1793

igraph_strvector_get(&nvec, from, &str1);

1794

ret=fprintf(outstream, "# %s\n%s ", str1, str2);

1795

}

1796

if (ret<0) {

1797

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1798

}

1799

ret=fprintf(outstream, "%s\n", str3);

1800

if (ret<0) {

1801

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1802

}

1803

IGRAPH_EIT_NEXT(it);

1804

}

1805

igraph_strvector_destroy(&nvec);

1806

igraph_strvector_destroy(&wvec);

1807

IGRAPH_FINALLY_CLEAN(2);

1808

}

1809

1810

if (isolates) {

1811

long int nov=igraph_vcount(graph);

1812

long int i;

1813

int ret=0;

1814

igraph_vector_t deg;

1815

igraph_strvector_t nvec;

1816

char *str;

1817

1818

IGRAPH_VECTOR_INIT_FINALLY(&deg, 1);

1819

IGRAPH_CHECK(igraph_strvector_init(&nvec, 1));

1820

IGRAPH_FINALLY(igraph_strvector_destroy, &nvec);

1821

for (i=0; i<nov; i++) {

1822

igraph_degree(graph, &deg, igraph_vss_1(i), IGRAPH_ALL, IGRAPH_LOOPS);

1823

if (VECTOR(deg)[0]==0) {

1824

if (names==0) {

1825

ret=fprintf(outstream, "# %li\n", i);

1826

} else {

1827

IGRAPH_CHECK(igraph_i_attribute_get_string_vertex_attr(graph, names,

1828

igraph_vss_1(i),

1829

&nvec));

1830

igraph_strvector_get(&nvec, 0, &str);

1831

ret=fprintf(outstream, "# %s\n", str);

1832

}

1833

}

1834

if (ret<0) {

1835

IGRAPH_ERROR("Write failed", IGRAPH_EFILE);

1836

}

1837

}

1838

igraph_strvector_destroy(&nvec);

1839

igraph_vector_destroy(&deg);

1840

IGRAPH_FINALLY_CLEAN(2);

1841

}

1842

1843

igraph_eit_destroy(&it);

1844

IGRAPH_FINALLY_CLEAN(1);

1845

return 0;

1846

}

1847

1848

/* Order matters here! */

1849

#define V_ID 0

1850

#define V_X 1

1851

#define V_Y 2

1852

#define V_Z 3

1853

#define V_SHAPE 4

1854

#define V_XFACT 5

1855

#define V_YFACT 6

1856

#define V_COLOR_RED 7

1857

#define V_COLOR_GREEN 8

1858

#define V_COLOR_BLUE 9

1859

#define V_FRAMECOLOR_RED 10

1860

#define V_FRAMECOLOR_GREEN 11

1861

#define V_FRAMECOLOR_BLUE 12

1862

#define V_LABELCOLOR_RED 13

1863

#define V_LABELCOLOR_GREEN 14

1864

#define V_LABELCOLOR_BLUE 15

1865

#define V_LABELDIST 16

1866

#define V_LABELDEGREE2 17

1867

#define V_FRAMEWIDTH 18

1868

#define V_FONTSIZE 19

1869

#define V_ROTATION 20

1870

#define V_RADIUS 21

1871

#define V_DIAMONDRATIO 22

1872

#define V_LABELDEGREE 23

1873

#define V_VERTEXSIZE 24

1874

#define V_FONT 25

1875

#define V_URL 26

1876

#define V_COLOR 27

1877

#define V_FRAMECOLOR 28

1878

#define V_LABELCOLOR 29

1879

#define V_LAST 30

1880

1881

#define E_WEIGHT 0

1882

#define E_COLOR_RED 1

1883

#define E_COLOR_GREEN 2

1884

#define E_COLOR_BLUE 3

1885

#define E_ARROWSIZE 4

1886

#define E_EDGEWIDTH 5

1887

#define E_HOOK1 6

1888

#define E_HOOK2 7

1889

#define E_ANGLE1 8

1890

#define E_ANGLE2 9

1891

#define E_VELOCITY1 10

1892

#define E_VELOCITY2 11

1893

#define E_ARROWPOS 12

1894

#define E_LABELPOS 13

1895

#define E_LABELANGLE 14

1896

#define E_LABELANGLE2 15

1897

#define E_LABELDEGREE 16

1898

#define E_FONTSIZE 17

1899

#define E_ARROWTYPE 18

1900

#define E_LINEPATTERN 19

1901

#define E_LABEL 20

1902

#define E_LABELCOLOR 21

1903

#define E_COLOR 22

1904

#define E_LAST 23

1905

1906

/**

1907

* \function igraph_write_graph_pajek

1908

* \brief Writes a graph to a file in Pajek format.

1909

1910

* </para><para>

1911

* The Pajek vertex and edge parameters (like color) are determined by

1912

* the attributes of the vertices and edges, of course this requires

1913

* an attribute handler to be installed. The names of the

1914

* corresponding vertex and edge attributes are listed at \ref

1915

* igraph_read_graph_pajek(), eg. the `\c color' vertex attributes

1916

* determines the color (`\c c' in Pajek) parameter.

1917

* \param graph The graph object to write.

1918

* \param outstream The file to write to. It should be opened and

1919

* writable. Make sure that you open the file in binary format if you use MS Windows,

1920

* otherwise end of line characters will be messed up. (igraph will be able

1921

* to read back these messed up files, but Pajek won't.)

1922

* \return Error code.

1923

1924

* Time complexity: O(|V|+|E|+|A|), |V| is the number of vertices, |E|

1925

* is the number of edges, |A| the number of attributes (vertex +

1926

* edge) in the graph if there are attribute handlers installed.

1927

1928

* \sa \ref igraph_read_graph_pajek() for reading Pajek graphs, \ref

1929

* igraph_write_graph_graphml() for writing a graph in GraphML format,

1930

* this suites <command>igraph</command> graphs better.

1931

1932

1933

int igraph_write_graph_pajek(const igraph_t *graph, FILE *outstream) {

1934

long int no_of_nodes=igraph_vcount(graph);

1935

long int i, j;

1936

1937

igraph_attribute_type_t vtypes[V_LAST], etypes[E_LAST];

1938

igraph_bool_t write_vertex_attrs=0;

1939

1940

/* Same order as the #define's */

1941

const char *vnames[] = { "id", "x", "y", "z", "shape", "xfact", "yfact",

1942

"color-red", "color-green", "color-blue",

1943

"framecolor-red", "framecolor-green",

1944

"framecolor-blue", "labelcolor-red",

1945

"labelcolor-green", "labelcolor-blue",

1946

"labeldist", "labeldegree2", "framewidth",

1947

"fontsize", "rotation", "radius",

1948

"diamondratio", "labeldegree", "vertexsize",

1949

"font", "url", "color", "framecolor",

1950

"labelcolor" };

1951

1952

const char *vnumnames[] = { "xfact", "yfact", "labeldist",

1953

"labeldegree2", "framewidth", "fontsize",

1954

"rotation", "radius", "diamondratio",

1955

"labeldegree", "vertexsize" };

1956

const char *vnumnames2[]= { "x_fact", "y_fact", "lr", "lphi", "bw",

1957

"fos", "phi", "r", "q", "la", "size" };

1958

const char *vstrnames[] = { "font", "url", "color", "framecolor",

1959

"labelcolor" };

1960

const char *vstrnames2[]= { "font", "url", "ic", "bc", "lc" };

1961

1962

const char *enames[] = { "weight", "color-red", "color-green", "color-blue",

1963

"arrowsize", "edgewidth", "hook1", "hook2",

1964

"angle1", "angle2", "velocity1", "velocity2",

1965

"arrowpos", "labelpos", "labelangle",

1966

"labelangle2", "labeldegree", "fontsize",

1967

"arrowtype", "linepattern", "label", "labelcolor",

1968

"color" };

1969

const char *enumnames[] = { "arrowsize", "edgewidth", "hook1", "hook2",

1970

"angle1", "angle2", "velocity1", "velocity2",

1971

"arrowpos", "labelpos", "labelangle",

1972

"labelangle2", "labeldegree", "fontsize" };

1973

const char *enumnames2[]= { "s", "w", "h1", "h2", "a1", "a2", "k1", "k2",

1974

"ap", "lp", "lr", "lphi", "la", "fos" };

1975

const char *estrnames[] = { "arrowtype", "linepattern", "label",

1976

"labelcolor", "color" };

1977

const char *estrnames2[]= { "a", "p", "l", "lc", "c" };

1978

1979

const char *newline="\x0d\x0a";

1980

1981

igraph_es_t es;

1982

igraph_eit_t eit;

1983

1984

igraph_vector_t numv;

1985

igraph_strvector_t strv;

1986

1987

igraph_vector_t ex_numa;

1988

igraph_vector_t ex_stra;

1989

igraph_vector_t vx_numa;

1990

igraph_vector_t vx_stra;

1991

1992

IGRAPH_VECTOR_INIT_FINALLY(&numv, 1);

1993

IGRAPH_STRVECTOR_INIT_FINALLY(&strv, 1);

1994

1995

IGRAPH_VECTOR_INIT_FINALLY(&ex_numa, 0);

1996

IGRAPH_VECTOR_INIT_FINALLY(&ex_stra, 0);

1997

IGRAPH_VECTOR_INIT_FINALLY(&vx_numa, 0);

1998

IGRAPH_VECTOR_INIT_FINALLY(&vx_stra, 0);

1999

2000

/* Write header */

2001

if (fprintf(outstream, "*Vertices %li%s", no_of_nodes, newline) < 0) {

2002

IGRAPH_ERROR("Cannot write pajek file", IGRAPH_EFILE);

2003

}

2004

2005

/* Check the vertex attributes */

2006

memset(vtypes, 0, sizeof(vtypes[0])*V_LAST);

2007

for (i=0; i<V_LAST; i++) {

2008

if (igraph_i_attribute_has_attr(graph, IGRAPH_ATTRIBUTE_VERTEX,

2009

vnames[i])) {

2010

igraph_i_attribute_gettype(graph, &vtypes[i], IGRAPH_ATTRIBUTE_VERTEX,

2011

vnames[i]);

2012

write_vertex_attrs=1;

2013

} else {

2014

vtypes[i]=-1;

2015

}

2016

}

2017

for (i=0; i<sizeof(vnumnames)/sizeof(const char*); i++) {

2018

igraph_attribute_type_t type;

2019

if (igraph_i_attribute_has_attr(graph, IGRAPH_ATTRIBUTE_VERTEX,

2020

vnumnames[i])) {

2021

igraph_i_attribute_gettype(graph, &type, IGRAPH_ATTRIBUTE_VERTEX,

2022

vnumnames[i]);

2023

if (type==IGRAPH_ATTRIBUTE_NUMERIC) {

2024

IGRAPH_CHECK(igraph_vector_push_back(&vx_numa, i));

2025

}

2026

}

2027

}

2028

for (i=0; i<sizeof(vstrnames)/sizeof(const char*); i++) {

2029

igraph_attribute_type_t type;

2030

if (igraph_i_attribute_has_attr(graph, IGRAPH_ATTRIBUTE_VERTEX,

2031

vstrnames[i])) {

2032

igraph_i_attribute_gettype(graph, &type, IGRAPH_ATTRIBUTE_VERTEX,

2033

vstrnames[i]);

2034

if (type==IGRAPH_ATTRIBUTE_STRING) {

2035

IGRAPH_CHECK(igraph_vector_push_back(&vx_stra, i));

2036

}

2037

}

2038

}

2039

2040

/* Write vertices */

2041

if (write_vertex_attrs) {

2042

for (i=0; i<no_of_nodes; i++) {

2043

2044

/* vertex id */

2045

fprintf(outstream, "%li", i+1);

2046

if (vtypes[V_ID] == IGRAPH_ATTRIBUTE_NUMERIC) {

2047

igraph_i_attribute_get_numeric_vertex_attr(graph, vnames[V_ID],

2048

igraph_vss_1(i), &numv);

2049

fprintf(outstream, " \"%g\"", VECTOR(numv)[0]);

2050

} else if (vtypes[V_ID] == IGRAPH_ATTRIBUTE_STRING) {

2051

char *s;

2052

igraph_i_attribute_get_string_vertex_attr(graph, vnames[V_ID],

2053

igraph_vss_1(i), &strv);

2054

igraph_strvector_get(&strv, 0, &s);

2055

fprintf(outstream, " \"%s\"", s);

2056

}

2057

2058

/* coordinates */

2059

if (vtypes[V_X] == IGRAPH_ATTRIBUTE_NUMERIC &&

2060

vtypes[V_Y] == IGRAPH_ATTRIBUTE_NUMERIC) {

2061

igraph_i_attribute_get_numeric_vertex_attr(graph, vnames[V_X],

2062

igraph_vss_1(i), &numv);

2063

fprintf(outstream, " %g", VECTOR(numv)[0]);

2064

igraph_i_attribute_get_numeric_vertex_attr(graph, vnames[V_Y],

2065

igraph_vss_1(i), &numv);

2066

fprintf(outstream, " %g", VECTOR(numv)[0]);

2067

if (vtypes[V_Z] == IGRAPH_ATTRIBUTE_NUMERIC) {

2068

igraph_i_attribute_get_numeric_vertex_attr(graph, vnames[V_Z],

2069

igraph_vss_1(i), &numv);

2070

fprintf(outstream, " %g", VECTOR(numv)[0]);

2071

}

2072

}

2073

2074

/* shape */

2075

if (vtypes[V_SHAPE] == IGRAPH_ATTRIBUTE_STRING) {

2076

char *s;

2077

igraph_i_attribute_get_string_vertex_attr(graph, vnames[V_SHAPE],

2078

igraph_vss_1(i), &strv);

2079

igraph_strvector_get(&strv, 0, &s);

2080

fprintf(outstream, " %s", s);

2081

}

2082

2083

/* numeric parameters */

2084

for (j=0; j<igraph_vector_size(&vx_numa); j++) {

2085

int idx=VECTOR(vx_numa)[j];

2086

igraph_i_attribute_get_numeric_vertex_attr(graph, vnumnames[idx],

2087

igraph_vss_1(i), &numv);

2088

fprintf(outstream, " %s %g", vnumnames2[idx], VECTOR(numv)[0]);

2089

}

2090

2091

/* string parameters */

2092

for (j=0; j<igraph_vector_size(&vx_stra); j++) {

2093

int idx=VECTOR(vx_numa)[j];

2094

char *s;

2095

igraph_i_attribute_get_string_vertex_attr(graph, vstrnames[idx],

2096

igraph_vss_1(i), &strv);

2097

igraph_strvector_get(&strv, 0, &s);

2098

fprintf(outstream, " %s \"%s\"", vstrnames2[idx], s);

2099

}

2100

2101

/* trailing newline */

2102

fprintf(outstream, "%s", newline);

2103

}

2104

}

2105

2106

/* edges header */

2107

if (igraph_is_directed(graph)) {

2108

fprintf(outstream, "*Arcs%s", newline);

2109

} else {

2110

fprintf(outstream, "*Edges%s", newline);

2111

}

2112

2113

IGRAPH_CHECK(igraph_es_all(&es, IGRAPH_EDGEORDER_ID));

2114

IGRAPH_FINALLY(igraph_es_destroy, &es);

2115

IGRAPH_CHECK(igraph_eit_create(graph, es, &eit));

2116

IGRAPH_FINALLY(igraph_eit_destroy, &eit);

2117

2118

/* Check edge attributes */

2119

for (i=0; i<E_LAST; i++) {

2120

if (igraph_i_attribute_has_attr(graph, IGRAPH_ATTRIBUTE_EDGE,

2121

enames[i])) {

2122

igraph_i_attribute_gettype(graph, &etypes[i], IGRAPH_ATTRIBUTE_EDGE,

2123

enames[i]);

2124

} else {

2125

etypes[i]=-1;

2126

}

2127

}

2128

for (i=0; i<sizeof(enumnames)/sizeof(const char*); i++) {

2129

igraph_attribute_type_t type;

2130

if (igraph_i_attribute_has_attr(graph, IGRAPH_ATTRIBUTE_EDGE,

2131

enumnames[i])) {

2132

igraph_i_attribute_gettype(graph, &type, IGRAPH_ATTRIBUTE_EDGE,

2133

enumnames[i]);

2134

if (type==IGRAPH_ATTRIBUTE_NUMERIC) {

2135

IGRAPH_CHECK(igraph_vector_push_back(&ex_numa, i));

2136

}

2137

}

2138

}

2139

for (i=0; i<sizeof(estrnames)/sizeof(const char*); i++) {

2140

igraph_attribute_type_t type;

2141

if (igraph_i_attribute_has_attr(graph, IGRAPH_ATTRIBUTE_EDGE,

2142

estrnames[i])) {

2143

igraph_i_attribute_gettype(graph, &type, IGRAPH_ATTRIBUTE_EDGE,

2144

estrnames[i]);

2145

if (type==IGRAPH_ATTRIBUTE_STRING) {

2146

IGRAPH_CHECK(igraph_vector_push_back(&ex_stra, i));

2147

}

2148

}

2149

}

2150

2151

for (i=0; !IGRAPH_EIT_END(eit); IGRAPH_EIT_NEXT(eit), i++) {

2152

long int edge=IGRAPH_EIT_GET(eit);

2153

igraph_integer_t from, to;

2154

igraph_edge(graph, edge, &from, &to);

2155

fprintf(outstream, "%li %li", (long int) from+1, (long int) to+1);

2156

2157

/* Weights */

2158

if (etypes[E_WEIGHT] == IGRAPH_ATTRIBUTE_NUMERIC) {

2159

igraph_i_attribute_get_numeric_edge_attr(graph, enames[E_WEIGHT],

2160

igraph_ess_1(edge), &numv);

2161

fprintf(outstream, " %g", VECTOR(numv)[0]);

2162

}

2163

2164

/* numeric parameters */

2165

for (j=0; j<igraph_vector_size(&ex_numa); j++) {

2166

int idx=VECTOR(ex_numa)[j];

2167

igraph_i_attribute_get_numeric_edge_attr(graph, enumnames[idx],

2168

igraph_ess_1(edge), &numv);

2169

fprintf(outstream, " %s %g", enumnames2[idx], VECTOR(numv)[0]);

2170

}

2171

2172

/* string parameters */

2173

for (j=0; j<igraph_vector_size(&ex_stra); j++) {

2174

int idx=VECTOR(ex_stra)[j];

2175

char *s;

2176

igraph_i_attribute_get_string_edge_attr(graph, estrnames[idx],

2177

igraph_ess_1(edge), &strv);

2178

igraph_strvector_get(&strv, 0, &s);

2179

fprintf(outstream, " %s \"%s\"", estrnames2[idx], s);

2180

}

2181

2182

/* trailing newline */

2183

fprintf(outstream, "%s", newline);

2184

}

2185

2186

igraph_eit_destroy(&eit);

2187

igraph_es_destroy(&es);

2188

igraph_vector_destroy(&ex_numa);

2189

igraph_vector_destroy(&ex_stra);

2190

igraph_vector_destroy(&vx_numa);

2191

igraph_vector_destroy(&vx_stra);

2192

igraph_strvector_destroy(&strv);

2193

igraph_vector_destroy(&numv);

2194

IGRAPH_FINALLY_CLEAN(8);

2195

return 0;

2196

}

2197

2198

/**

2199

* \function igraph_write_graph_dimacs

2200

* \brief Write a graph in DIMACS format.

2201

2202

* This function writes a graph to an output stream in DIMACS format,

2203

* describing a maximum flow problem.

2204

* See ftp://dimacs.rutgers.edu/pub/netflow/general-info/

2205

2206

* </para><para>

2207

* This file format is discussed in the documentation of \ref

2208

* igraph_read_graph_dimacs(), see that for more information.

2209

2210

* \param graph The graph to write to the stream.

2211

* \param outstream The stream.

2212

* \param source Integer, the id of the source vertex for the maximum

2213

* flow.

2214

* \param target Integer, the id of the target vertex.

2215

* \param capacity Pointer to an initialized vector containing the

2216

* edge capacity values.

2217

* \return Error code.

2218

2219

* Time complexity: O(|E|), the number of edges in the graph.

2220

2221

* \sa igraph_read_graph_dimacs()

2222

2223

2224

int igraph_write_graph_dimacs(const igraph_t *graph, FILE *outstream,

2225

long int source, long int target,

2226

const igraph_vector_t *capacity) {

2227

2228

long int no_of_nodes=igraph_vcount(graph);

2229

long int no_of_edges=igraph_ecount(graph);

2230

igraph_eit_t it;

2231

long int i=0;

2232

int ret;

2233

2234

if (igraph_vector_size(capacity) != no_of_edges) {

2235

IGRAPH_ERROR("invalid capacity vector length", IGRAPH_EINVAL);

2236

}

2237

2238

IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(IGRAPH_EDGEORDER_ID),

2239

&it));

2240

IGRAPH_FINALLY(igraph_eit_destroy, &it);

2241

2242

ret=fprintf(outstream,

2243

"c created by igraph\np max %li %li\nn %li s\nn %li t\n",

2244

no_of_nodes, no_of_edges, source+1, target+1);

2245

if (ret < 0) {

2246

IGRAPH_ERROR("Write error", IGRAPH_EFILE);

2247

}

2248

2249

2250

while (!IGRAPH_EIT_END(it)) {

2251

igraph_integer_t from, to, cap;

2252

igraph_edge(graph, IGRAPH_EIT_GET(it), &from, &to);

2253

cap=VECTOR(*capacity)[i++];

2254

ret=fprintf(outstream, "a %li %li %g\n",

2255

(long int) from+1, (long int) to+1, cap);

2256

if (ret < 0) {

2257

IGRAPH_ERROR("Write error", IGRAPH_EFILE);

2258

}

2259

IGRAPH_EIT_NEXT(it);

2260

}

2261

2262

igraph_eit_destroy(&it);

2263

IGRAPH_FINALLY_CLEAN(1);

2264

return 0;

2265

}

2266

2267

int igraph_i_gml_convert_to_key(const char *orig, char **key) {

2268

static int no=1;

2269

char strno[50];

2270

long int i, len=strlen(orig), newlen=0, plen=0;

2271

igraph_bool_t pref=0;

2272

/* do we need a prefix? */

2273

if (len==0 || !isalpha(orig[0])) {

2274

pref=1; no++;

2275

snprintf(strno, sizeof(strno)-1, "igraph");

2276

plen=newlen=strlen(strno);

2277

}

2278

for (i=0; i<len; i++) {

2279

if (isalnum(orig[i])) { newlen++; }

2280

}

2281

*key=igraph_Calloc(newlen+1, char);

2282

if (! *key) {

2283

IGRAPH_ERROR("Writing GML file failed", IGRAPH_ENOMEM);

2284

}

2285

memcpy(*key, strno, plen*sizeof(char));

2286

for (i=0; i<len; i++) {

2287

if (isalnum(orig[i])) {

2288

(*key)[plen++] = orig[i];

2289

}

2290

}

2291

(*key)[newlen]='\0';

2292

2293

return 0;

2294

}

2295

2296

#define CHECK(cmd) do { ret=cmd; if (ret<0) IGRAPH_ERROR("Write failed", IGRAPH_EFILE); } while (0)

2297

2298

/**

2299

* \function igraph_write_graph_gml

2300

* \brief Write the graph to a stream in GML format

2301

2302

* GML is a quite general textual format, see

2303

* http://www.infosun.fim.uni-passau.de/Graphlet/GML/ for details.

2304

2305

* </para><para> The graph, vertex and edges attributes are written to the

2306

* file as well, if they are numeric of string.

2307

2308

* </para><para> As igraph is more forgiving about attribute names, it might

2309

* be neccessary to simplify the them before writing to the GML file.

2310

* This way we'll have a syntactically correct GML file. The following

2311

* simple procedure is performed on each attribute name: first the alphanumeric

2312

* characters are extracted, the others are ignored. Then if the first character

2313

* is not a letter then the attribute name is prefixed with <quote>igraph</quote>.

2314

* Note that this might result identical names for two attributes, igraph

2315

* does not check this.

2316

2317

* </para><para> The <quote>id</quote> vertex attribute is treated specially.

2318

* If the <parameter>id</parameter> argument is not 0 then it should be a numeric

2319

* vector with the vertex ids and the <quote>id</quote> vertex attribute is

2320

* ignored (if there is one). If <parameter>id</parameter> is 0 and there is a

2321

* numeric <quote>id</quote> vertex attribute that is used instead. If ids

2322

* are not specified in either way then the regular igraph vertex ids are used.

2323

2324

* </para><para> Note that whichever way vertex ids are specified, their

2325

* uniqueness is not checked.

2326

2327

* </para><para> If the graph has edge attributes named <quote>source</quote>

2328

* or <quote>target</quote> they're silently ignored. GML uses these attributes

2329

* to specify the edges, so we cannot write them to the file. Rename them

2330

* before calling this function if you want to preserve them.

2331

* \param graph The graph to write to the stream.

2332

* \param outstream The stream to write the file to.

2333

* \param id Either <code>NULL</code> or a numeric vector with the vertex ids.

2334

* See details above.

2335

* \param creator An optional string to write to the stream in the creator line.

2336

* If this is 0 then the current date and time is added.

2337

* \return Error code.

2338

2339

* Time complexity: should be proportional to the number of characters written

2340

* to the file.

2341

2342

* \sa \ref igraph_read_graph_gml() for reading GML files,

2343

* \ref igraph_read_graph_graphml() for a more modern format.

2344

2345

2346

int igraph_write_graph_gml(const igraph_t *graph, FILE *outstream,

2347

const igraph_vector_t *id, const char *creator) {

2348

int ret;

2349

igraph_strvector_t gnames, vnames, enames;

2350

igraph_vector_t gtypes, vtypes, etypes;

2351

igraph_vector_t numv;

2352

igraph_strvector_t strv;

2353

long int i;

2354

long int no_of_nodes=igraph_vcount(graph);

2355

long int no_of_edges=igraph_ecount(graph);

2356

2357

igraph_vector_t v_myid;

2358

const igraph_vector_t *myid=id;

2359

2360

time_t curtime=time(0);

2361

char *timestr=ctime(&curtime);

2362

timestr[strlen(timestr)-1]='\0'; /* nicely remove \n */

2363

2364

CHECK(fprintf(outstream,

2365

"Creator \"igraph version %s %s\"\nVersion 1\ngraph\n[\n",

2366

PACKAGE_VERSION, creator ? creator : timestr));

2367

2368

IGRAPH_STRVECTOR_INIT_FINALLY(&gnames, 0);

2369

IGRAPH_STRVECTOR_INIT_FINALLY(&vnames, 0);

2370

IGRAPH_STRVECTOR_INIT_FINALLY(&enames, 0);

2371

IGRAPH_VECTOR_INIT_FINALLY(&gtypes, 0);

2372

IGRAPH_VECTOR_INIT_FINALLY(&vtypes, 0);

2373

IGRAPH_VECTOR_INIT_FINALLY(&etypes, 0);

2374

IGRAPH_CHECK(igraph_i_attribute_get_info(graph,

2375

&gnames, &gtypes,

2376

&vnames, &vtypes,

2377

&enames, &etypes));

2378

2379

IGRAPH_VECTOR_INIT_FINALLY(&numv, 1);

2380

IGRAPH_STRVECTOR_INIT_FINALLY(&strv, 1);

2381

2382

/* Check whether there is an 'id' node attribute if the supplied is 0 */

2383

if (!id) {

2384

igraph_bool_t found=0;

2385

for (i=0; i<igraph_vector_size(&vtypes); i++) {

2386

char *n;

2387

igraph_strvector_get(&vnames, i, &n);

2388

if (!strcmp(n, "id") && VECTOR(vtypes)[i]==IGRAPH_ATTRIBUTE_NUMERIC) {

2389

found=1; break;

2390

}

2391

}

2392

if (found) {

2393

IGRAPH_VECTOR_INIT_FINALLY(&v_myid, no_of_nodes);

2394

IGRAPH_CHECK(igraph_i_attribute_get_numeric_vertex_attr(graph, "id",

2395

igraph_vss_all(),

2396

&v_myid));

2397

myid=&v_myid;

2398

}

2399

}

2400

2401

/* directedness */

2402

CHECK(fprintf(outstream, " directed %i\n", igraph_is_directed(graph) ? 1 : 0));

2403

2404

/* Graph attributes first */

2405

for (i=0; i<igraph_vector_size(&gtypes); i++) {

2406

char *name, *newname;

2407

igraph_strvector_get(&gnames, i, &name);

2408

IGRAPH_CHECK(igraph_i_gml_convert_to_key(name, &newname));

2409

if (VECTOR(gtypes)[i] == IGRAPH_ATTRIBUTE_NUMERIC) {

2410

IGRAPH_CHECK(igraph_i_attribute_get_numeric_graph_attr(graph, name, &numv));

2411

CHECK(fprintf(outstream, " %s %g\n", newname, VECTOR(numv)[0]));

2412

igraph_Free(newname);

2413

} else if (VECTOR(gtypes)[i] == IGRAPH_ATTRIBUTE_STRING) {

2414

char *s;

2415

IGRAPH_CHECK(igraph_i_attribute_get_string_graph_attr(graph, name, &strv));

2416

igraph_strvector_get(&strv, 0, &s);

2417

CHECK(fprintf(outstream, " %s \"%s\"\n", newname, s));

2418

igraph_Free(newname);

2419

} else {

2420

igraph_Free(newname);

2421

IGRAPH_WARNING("A non-numeric, non-string graph attribute ignored");

2422

}

2423

}

2424

2425

/* Now come the vertices */

2426

for (i=0; i<no_of_nodes; i++) {

2427

long int j;

2428

CHECK(fprintf(outstream, " node\n [\n"));

2429

/* id */

2430

CHECK(fprintf(outstream, " id %li\n", myid ? (long int)VECTOR(*myid)[i] : i));

2431

/* other attributes */

2432

for (j=0; j<igraph_vector_size(&vtypes); j++) {

2433

int type=VECTOR(vtypes)[j];

2434

char *name, *newname;

2435

igraph_strvector_get(&vnames, j, &name);

2436

if (!strcmp(name, "id")) { continue; }

2437

IGRAPH_CHECK(igraph_i_gml_convert_to_key(name, &newname));

2438

if (type==IGRAPH_ATTRIBUTE_NUMERIC) {

2439

IGRAPH_CHECK(igraph_i_attribute_get_numeric_vertex_attr(graph, name,

2440

igraph_vss_1(i),

2441

&numv));

2442

CHECK(fprintf(outstream, " %s %g\n", newname, VECTOR(numv)[0]));

2443

} else if (type==IGRAPH_ATTRIBUTE_STRING) {

2444

char *s;

2445

IGRAPH_CHECK(igraph_i_attribute_get_string_vertex_attr(graph, name,

2446

igraph_vss_1(i),

2447

&strv));

2448

igraph_strvector_get(&strv, 0, &s);

2449

CHECK(fprintf(outstream, " %s \"%s\"\n", newname, s));

2450

}

2451

igraph_Free(newname);

2452

}

2453

CHECK(fprintf(outstream, " ]\n"));

2454

}

2455

2456

/* The edges too */

2457

for (i=0; i<no_of_edges; i++) {

2458

long int from=IGRAPH_FROM(graph, i);

2459

long int to=IGRAPH_TO(graph, i);

2460

long int j;

2461

CHECK(fprintf(outstream, " edge\n [\n"));

2462

/* source and target */

2463

CHECK(fprintf(outstream, " source %li\n",

2464

myid ? (long int)VECTOR(*myid)[from] : from));

2465

CHECK(fprintf(outstream, " target %li\n",

2466

myid ? (long int)VECTOR(*myid)[to] : to));

2467

2468

/* other attributes */

2469

for (j=0; j<igraph_vector_size(&etypes); j++) {

2470

int type=VECTOR(etypes)[j];

2471

char *name, *newname;

2472

igraph_strvector_get(&enames, j, &name);

2473

if (!strcmp(name, "source") || !strcmp(name, "target")) { continue; }

2474

IGRAPH_CHECK(igraph_i_gml_convert_to_key(name, &newname));

2475

if (type==IGRAPH_ATTRIBUTE_NUMERIC) {

2476

IGRAPH_CHECK(igraph_i_attribute_get_numeric_edge_attr(graph, name,

2477

igraph_ess_1(i),

2478

&numv));

2479

CHECK(fprintf(outstream, " %s %g\n", newname, VECTOR(numv)[0]));

2480

} else if (type==IGRAPH_ATTRIBUTE_STRING) {

2481

char *s;

2482

IGRAPH_CHECK(igraph_i_attribute_get_string_edge_attr(graph, name,

2483

igraph_ess_1(i),

2484

&strv));

2485

igraph_strvector_get(&strv, 0, &s);

2486

CHECK(fprintf(outstream, " %s \"%s\"\n", newname, s));

2487

}

2488

igraph_Free(newname);

2489

}

2490

CHECK(fprintf(outstream, " ]\n"));

2491

}

2492

2493

CHECK(fprintf(outstream, "]\n"));

2494

2495

if (&v_myid == myid) {

2496

igraph_vector_destroy(&v_myid);

2497

IGRAPH_FINALLY_CLEAN(1);

2498

}

2499

2500

igraph_strvector_destroy(&strv);

2501

igraph_vector_destroy(&numv);

2502

igraph_vector_destroy(&etypes);

2503

igraph_vector_destroy(&vtypes);

2504

igraph_vector_destroy(&gtypes);

2505

igraph_strvector_destroy(&enames);

2506

igraph_strvector_destroy(&vnames);

2507

igraph_strvector_destroy(&gnames);

2508

IGRAPH_FINALLY_CLEAN(8);

2509

2510

return 0;

2511

}

2512

2513

int igraph_i_dot_escape(const char *orig, char **result) {

2514

/* do we have to escape the string at all? */

2515

long int i, j, len=strlen(orig), newlen=0;

2516

igraph_bool_t need_quote=0, is_number=1;

2517

for (i=0; i<len; i++) {

2518

if (isdigit(orig[i])) { newlen++; }

2519

else if (orig[i] == '-' && i==0) { newlen++; }

2520

else if (orig[i] == '.') {

2521

if (is_number) { newlen++; }

2522

else { need_quote=1; newlen++; }

2523

} else if (orig[i] == '_') {

2524

is_number=0; newlen++;

2525

} else if (orig[i] == '\\') {

2526

need_quote=1; is_number=0; newlen+=2; /* will be escaped */

2527

} else if (orig[i] == '"') {

2528

need_quote=1; is_number=0; newlen+=2; /* will be escaped */

2529

} else if (isalpha(orig[i])) {

2530

is_number=0; newlen++;

2531

} else {

2532

is_number=0; need_quote=1; newlen++;

2533

}

2534

}

2535

if (is_number && orig[len-1] == '.') is_number=0;

2536

if (!is_number && isdigit(orig[0])) need_quote=1;

2537

2538

if (is_number || !need_quote) {

2539

*result=strdup(orig);

2540

if (!*result) IGRAPH_ERROR("Writing DOT file failed", IGRAPH_ENOMEM);

2541

} else {

2542

*result=igraph_Calloc(newlen+3, char);

2543

(*result)[0]='"';

2544

(*result)[newlen+1]='"';

2545

(*result)[newlen+2]='\0';

2546

for (i=0, j=1; i<len; i++) {

2547

if (orig[i] == '\\' || orig[i] == '"') (*result)[j++] = '\\';

2548

(*result)[j++] = orig[i];

2549

}

2550

}

2551

2552

return 0;

2553

}

2554

2555

/**

2556

* \function igraph_write_graph_dot

2557

* \brief Write the graph to a stream in DOT format

2558

2559

* DOT is the format used by the widely known GraphViz software, see

2560

* http://www.graphviz.org for details. The grammar of the DOT format

2561

* can be found here: http://www.graphviz.org/doc/info/lang.html

2562

2563

* </para><para>This is only a preliminary implementation, only the vertices

2564

* and the edges are written but not the attributes or any visualization

2565

* information.

2566

2567

* \param graph The graph to write to the stream.

2568

* \param outstream The stream to write the file to.

2569

2570

* Time complexity: should be proportional to the number of characters written

2571

* to the file.

2572

2573

* \sa \ref igraph_write_graph_graphml() for a more modern format.

2574

2575

int igraph_write_graph_dot(const igraph_t *graph, FILE* outstream) {

2576

int ret;

2577

long int i, j;

2578

long int no_of_nodes=igraph_vcount(graph);

2579

long int no_of_edges=igraph_ecount(graph);

2580

char edgeop[3];

2581

igraph_strvector_t gnames, vnames, enames;

2582

igraph_vector_t gtypes, vtypes, etypes;

2583

igraph_vector_t numv;

2584

igraph_strvector_t strv;

2585

2586

IGRAPH_STRVECTOR_INIT_FINALLY(&gnames, 0);

2587

IGRAPH_STRVECTOR_INIT_FINALLY(&vnames, 0);

2588

IGRAPH_STRVECTOR_INIT_FINALLY(&enames, 0);

2589

IGRAPH_VECTOR_INIT_FINALLY(&gtypes, 0);

2590

IGRAPH_VECTOR_INIT_FINALLY(&vtypes, 0);

2591

IGRAPH_VECTOR_INIT_FINALLY(&etypes, 0);

2592

IGRAPH_CHECK(igraph_i_attribute_get_info(graph,

2593

&gnames, &gtypes,

2594

&vnames, &vtypes,

2595

&enames, &etypes));

2596

2597

IGRAPH_VECTOR_INIT_FINALLY(&numv, 1);

2598

IGRAPH_STRVECTOR_INIT_FINALLY(&strv, 1);

2599

2600

CHECK(fprintf(outstream, "/* Created by igraph %s */\n",

2601

PACKAGE_VERSION));

2602

2603

if (igraph_is_directed(graph)) {

2604

CHECK(fprintf(outstream, "digraph {\n"));

2605

strcpy(edgeop, "->");

2606

} else {

2607

CHECK(fprintf(outstream, "graph {\n"));

2608

strcpy(edgeop, "--");

2609

}

2610

2611

/* Write the graph attributes */

2612

if (igraph_vector_size(&gtypes)>0) {

2613

CHECK(fprintf(outstream, " graph [\n"));

2614

for (i=0; i<igraph_vector_size(&gtypes); i++) {

2615

char *name, *newname;

2616

igraph_strvector_get(&gnames, i, &name);

2617

IGRAPH_CHECK(igraph_i_dot_escape(name, &newname));

2618

if (VECTOR(gtypes)[i] == IGRAPH_ATTRIBUTE_NUMERIC) {

2619

IGRAPH_CHECK(igraph_i_attribute_get_numeric_graph_attr(graph, name, &numv));

2620

if (VECTOR(numv)[0] == (long)VECTOR(numv)[0])

2621

CHECK(fprintf(outstream, " %s=%ld\n", newname, (long)VECTOR(numv)[0]));

2622

else

2623

CHECK(fprintf(outstream, " %s=%f\n", newname, VECTOR(numv)[0]));

2624

igraph_Free(newname);

2625

} else if (VECTOR(gtypes)[i] == IGRAPH_ATTRIBUTE_STRING) {

2626

char *s, *news;

2627

IGRAPH_CHECK(igraph_i_attribute_get_string_graph_attr(graph, name, &strv));

2628

igraph_strvector_get(&strv, 0, &s);

2629

IGRAPH_CHECK(igraph_i_dot_escape(s, &news));

2630

CHECK(fprintf(outstream, " %s=%s\n", newname, news));

2631

igraph_Free(newname);

2632

igraph_Free(news);

2633

} else {

2634

IGRAPH_WARNING("A non-numeric, non-string graph attribute ignored");

2635

}

2636

}

2637

CHECK(fprintf(outstream, " ];\n"));

2638

}

2639

2640

/* Write the vertices */

2641

if (igraph_vector_size(&vtypes) > 0) {

2642

for (i=0; i<no_of_nodes; i++) {

2643

CHECK(fprintf(outstream, " %ld [\n", i));

2644

for (j=0; j<igraph_vector_size(&vtypes); j++) {

2645

char *name, *newname;

2646

igraph_strvector_get(&vnames, j, &name);

2647

IGRAPH_CHECK(igraph_i_dot_escape(name, &newname));

2648

if (VECTOR(vtypes)[j] == IGRAPH_ATTRIBUTE_NUMERIC) {

2649

IGRAPH_CHECK(igraph_i_attribute_get_numeric_vertex_attr(graph, name, igraph_vss_1(i), &numv));

2650

if (VECTOR(numv)[0] == (long)VECTOR(numv)[0])

2651

CHECK(fprintf(outstream, " %s=%ld\n", newname, (long)VECTOR(numv)[0]));

2652

else

2653

CHECK(fprintf(outstream, " %s=%f\n", newname, VECTOR(numv)[0]));

2654

igraph_Free(newname);

2655

} else if (VECTOR(vtypes)[j] == IGRAPH_ATTRIBUTE_STRING) {

2656

char *s, *news;

2657

IGRAPH_CHECK(igraph_i_attribute_get_string_vertex_attr(graph, name, igraph_vss_1(i), &strv));

2658

igraph_strvector_get(&strv, 0, &s);

2659

IGRAPH_CHECK(igraph_i_dot_escape(s, &news));

2660

CHECK(fprintf(outstream, " %s=%s\n", newname, news));

2661

igraph_Free(newname);

2662

igraph_Free(news);

2663

} else {

2664

IGRAPH_WARNING("A non-numeric, non-string graph attribute ignored");

2665

}

2666

}

2667

CHECK(fprintf(outstream, " ];\n"));

2668

}

2669

} else {

2670

for (i=0; i<no_of_nodes; i++)

2671

CHECK(fprintf(outstream, " %ld;\n", i));

2672

}

2673

CHECK(fprintf(outstream, "\n"));

2674

2675

/* Write the edges */

2676

if (igraph_vector_size(&etypes) > 0) {

2677

for (i=0; i<no_of_edges; i++) {

2678

long int from=IGRAPH_FROM(graph, i);

2679

long int to=IGRAPH_TO(graph, i);

2680

CHECK(fprintf(outstream, " %ld %s %ld [\n", from, edgeop, to));

2681

for (j=0; j<igraph_vector_size(&etypes); j++) {

2682

char *name, *newname;

2683

igraph_strvector_get(&enames, j, &name);

2684

IGRAPH_CHECK(igraph_i_dot_escape(name, &newname));

2685

if (VECTOR(etypes)[j] == IGRAPH_ATTRIBUTE_NUMERIC) {

2686

IGRAPH_CHECK(igraph_i_attribute_get_numeric_edge_attr(graph, name, igraph_ess_1(i), &numv));

2687

if (VECTOR(numv)[0] == (long)VECTOR(numv)[0])

2688

CHECK(fprintf(outstream, " %s=%ld\n", newname, (long)VECTOR(numv)[0]));

2689

else

2690

CHECK(fprintf(outstream, " %s=%f\n", newname, VECTOR(numv)[0]));

2691

igraph_Free(newname);

2692

} else if (VECTOR(etypes)[j] == IGRAPH_ATTRIBUTE_STRING) {

2693

char *s, *news;

2694

IGRAPH_CHECK(igraph_i_attribute_get_string_edge_attr(graph, name, igraph_ess_1(i), &strv));

2695

igraph_strvector_get(&strv, 0, &s);

2696

IGRAPH_CHECK(igraph_i_dot_escape(s, &news));

2697

CHECK(fprintf(outstream, " %s=%s\n", newname, news));

2698

igraph_Free(newname);

2699

igraph_Free(news);

2700

} else {

2701

IGRAPH_WARNING("A non-numeric, non-string graph attribute ignored");

2702

}

2703

}

2704

CHECK(fprintf(outstream, " ];\n"));

2705

}

2706

} else {

2707

for (i=0; i<no_of_edges; i++) {

2708

long int from=IGRAPH_FROM(graph, i);

2709

long int to=IGRAPH_TO(graph, i);

2710

CHECK(fprintf(outstream, " %ld %s %ld;\n", from, edgeop, to));

2711

}

2712

}

2713

CHECK(fprintf(outstream, "}\n"));

2714

2715

igraph_strvector_destroy(&strv);

2716

igraph_vector_destroy(&numv);

2717

igraph_vector_destroy(&etypes);

2718

igraph_vector_destroy(&vtypes);

2719

igraph_vector_destroy(&gtypes);

2720

igraph_strvector_destroy(&enames);

2721

igraph_strvector_destroy(&vnames);

2722

igraph_strvector_destroy(&gnames);

2723

IGRAPH_FINALLY_CLEAN(8);

2724

2725

return 0;

2726

}

2727

2728

#undef CHECK

Older »