1 2igraph 0.6.5 3============ 4 5Released February 24, 2013 6 7The version number is not a mistake, we jump to 0.6.5 from 0.6, 8for technical reasons. 9 10R: new features and bug fixes 11----------------------------- 12 13- Added a vertex shape API for defining new vertex shapes, and also 14 a couple of new vertex shapes. 15- Added the get.data.frame() function, opposite of graph.data.frame(). 16- Added bipartite support to the Pajek reader and writer, closes bug 17 \#1042298. 18- `degree.sequence.game()` has a new method now: "simple_no_multiple". 19- Added the is.degree.sequence() and is.graphical.degree.sequence() 20 functions. 21- rewire() has a new method: "loops", that can create loop edges. 22- Walktrap community detection now handles isolates. 23- layout.mds() returns a layout matrix now. 24- layout.mds() uses LAPACK instead of ARPACK. 25- Handle the '~' character in write.graph and read.graph. Bug 26 \#1066986. 27- Added k.regular.game(). 28- Use vertex names to plot if no labels are specified in the function 29 call or as vetex attributes. Fixes issue \#1085431. 30- power.law.fit() can now use a C implementation. 31 32- Fixed a bug in barabasi.game() when out.seq was an empty vector. 33- Fixed a bug that made functions with a progress bar fail if called 34 from another package. 35- Fixed a bug when creating graphs from a weighted integer adjacency 36 matrix via graph.adjacency(). Bug \#1019624. 37- Fixed overflow issues in centralization calculations. 38- Fixed a minimal.st.separators() bug, some vertex sets were incorrectly 39 reported as separators. Bug \#1033045. 40- Fixed a bug that mishandled vertex colors in VF2 isomorphism 41 functions. Bug \#1032819. 42- Pajek exporter now always quotes strings, thanks to Elena Tea Russo. 43- Fixed a bug with handling small edge weights in shortest paths 44 calculation in shortest.paths() (Dijkstra's algorithm.) Thanks to 45 Martin J Reed. 46- Weighted transitivity uses V(graph) as 'vids' if it is NULL. 47- Fixed a bug when 'pie' vertices were drawn together with other 48 vertex shapes. 49- Speed up printing graphs. 50- Speed up attribute queries and other basic operations, by avoiding 51 copying of the graph. Bug \#1043616. 52- Fixed a bug in the NCV setting for ARPACK functions. It cannot be 53 bigger than the matrix size. 54- layout.merge()'s DLA mode has better defaults now. 55- Fixed a bug in layout.mds() that resulted vertices on top of each 56 other. 57- Fixed a bug in layout.spring(), it was not working properly. 58- Fixed layout.svd(), which was completely defunct. 59- Fixed a bug in layout.graphopt() that caused warnings and on 60 some platforms crashes. 61- Fixed community.to.membership(). Bug \#1022850. 62- Fixed a graph.incidence() crash if it was called with a non-matrix 63 argument. 64- Fixed a get.shortest.paths bug, when output was set to "both". 65- Motif finding functions return NA for isomorphism classes that are 66 not motifs (i.e. not connected). Fixes bug \#1050859. 67- Fixed get.adjacency() when attr is given, and the attribute has some 68 complex type. Bug \#1025799. 69- Fixed attribute name in graph.adjacency() for dense matrices. Bug 70 \#1066952. 71- Fixed erratic behavior of alpha.centrality(). 72- Fixed igraph indexing, when attr is given. Bug \#1073705. 73- Fixed a bug when calculating the largest cliques of a directed 74 graph. Bug \#1073800. 75- Fixed a bug in the maximal clique search, closes \#1074402. 76- Warn for negative weights when calculating PageRank. 77- Fixed dense, unweighted graph.adjacency when diag=FALSE. Closes 78 issue \#1077425. 79- Fixed a bug in eccentricity() and radius(), the results were often 80 simply wrong. 81- Fixed a bug in get.all.shortest.paths() when some edges had zero weight. 82- graph.data.frame() is more careful when vertex names are numbers, to 83 avoid their scientific notation. Fixes issue \#1082221. 84- Better check for NAs in vertex names. Fixes issue \#1087215 85- Fixed some potential crashes in the DrL layout generator. 86- Fixed a bug in the Reingold-Tilford layout when the graph is 87 directed and mode != ALL. 88- Eliminate gap between vertex and edge when plotting an edge without an arrow. 89 Fixes \#1118448. 90- Fixed a bug in has.multiple() that resulted in false negatives for 91 some undirected graphs. 92- Fixed a crash in weighted betweenness calculation. 93- R plotting: fixed a bug that caused misplaced arrows at rectangle 94 vertex shapes. 95 96Python news and fixes 97--------------------- 98 99- Added bipartite support to the Pajek reader and writer, closes bug 100 \#1042298. 101- Graph.Degree_Sequence() has a new method now: "no_multiple". 102- Added the is_degree_sequence() and is_graphical_degree_sequence() 103 functions. 104- rewire() has a new mode: "loops", that can create loop edges. 105- Walktrap community detection now handles isolates. 106- Added Graph.K_Regular(). 107- power_law_fit() now uses a C implementation. 108- Added support for setting the frame (stroke) width of vertices using the 109 frame_width attribute or the vertex_frame_width keyword argument in plot() 110- Improved Inkscape-friendly SVG output from Graph.write_svg(), thanks to drlog 111- Better handling of named vertices in Graph.delete_vertices() 112- Added experimental Gephi graph streaming support; see igraph.remote.gephi and 113 igraph.drawing.graph.GephiGraphStreamingDrawer 114- Nicer __repr__ output for Flow and Cut instances 115- Arrows are now placed correctly around diamond-shaped nodes on plots 116- Added Graph.TupleList, a function that allows one to create graphs with 117 edge attributes quickly from a list of tuples. 118- plot() now also supports .eps as an extension, not only .ps 119 120- Fixed overflow issues in centralization calculations. 121- Fixed a bug that mishandled vertex colors in VF2 isomorphism 122 functions. Bug \#1032819. 123- Pajek exporter now always quotes strings, thanks to Elena Tea Russo. 124- Fixed a bug with handling small edge weights in shortest paths 125 calculation in Graph.shortest_paths() (Dijkstra's algorithm.) Thanks to 126 Martin J Reed. 127- Fixed a bug in the NCV setting for ARPACK functions. It cannot be 128 bigger than the matrix size. 129- Fixed a bug in Graph.layout_mds() that resulted vertices on top of each 130 other. 131- Motif finding functions return nan for isomorphism classes that are 132 not motifs (i.e. not connected). Fixes bug \#1050859. 133- Fixed a bug when calculating the largest cliques of a directed 134 graph. Bug \#1073800. 135- Warn for negative weights when calculating PageRank. 136- Fixed a bug in Graph.eccentricity() and Graph.radius(), the results were often 137 simply wrong. 138- Fixed a bug in Graph.get.all.shortest.paths() when some edges had zero weight. 139- Fixed some potential crashes in the DrL layout generator. 140- Fixed a bug in the Reingold-Tilford layout when the graph is 141 directed and mode != ALL. 142- Fixed a bug in Graph.layout_sugiyama() when the graph had no edges. 143- Fixed a bug in Graph.community_label_propagation() when initial labels 144 contained -1 entries. Issue \#1105460. 145- Repaired the DescartesCoordinateSystem class (which is not used too frequently 146 anyway) 147- Fixed a bug that caused segfaults when an igraph Graph was used in a thread 148 forked from the main Python interpreter thread 149- Fixed a bug that affected file handles created from Python strings in the 150 C layer 151- Fixed a bug in has_multiple() that resulted in false negatives 152 for some undirected graphs. 153- Fixed a crash in weighted betweenness calculation. 154 155C library news and changes 156-------------------------- 157 158- Added bipartite support to the Pajek reader and writer, closes bug 159 \#1042298. 160- igraph_layout_mds() uses LAPACK instead of ARPACK. 161- igraph_degree_sequence_game has a new method: 162 IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE. 163- Added the igraph_is_degree_sequence() and 164 igraph_is_graphical_degree_sequence() functions. 165- igraph_rewire() has a new method: IGRAPH_REWIRING_SIMPLE_LOOPS, 166 that can create loops. 167- Walktrap community detection now handles isolates. 168- Added igraph_k_regular_game(). 169- Added igraph_power_law_fit. 170 171- Fixed a bug in igraph_barabasi_game when outseq was an empty vector. 172- Fixed overflow issues in centralization calculations. 173- Fixed an invalid return value of igraph_vector_ptr_pop_back. 174- Fixed a igraph_all_minimal_st_separators() bug, some vertex sets 175 were incorrectly reported as separators. Bug \#1033045. 176- Pajek exporter now always quotes strings, thanks to Elena Tea Russo. 177- Fixed a bug with handling small edge weights in 178 igraph_shortest_paths_dijkstra(), thanks to Martin J Reed. 179- Fixed a bug in the NCV setting for ARPACK functions. It cannot be 180 bigger than the matrix size. 181- igraph_layout_merge_dla uses better default parameter values now. 182- Fixed a bug in igraph_layout_mds() that resulted vertices on top of 183 each other. 184- Attribute handler table is not thread-local any more. 185- Motif finding functions return IGRAPH_NAN for isomorphism classes 186 that are not motifs (i.e. not connected). Fixes bug \#1050859. 187- Fixed a bug when calculating the largest cliques of a directed 188 graph. Bug \#1073800. 189- Fix a bug in degree_sequence_game(), in_seq can be an empty vector as 190 well instead of NULL, for an undirected graph. 191- Fixed a bug in the maximal clique search, closes \#1074402. 192- Warn for negative weights when calculating PageRank. 193- Fixed a bug in igraph_eccentricity() (and also igraph_radius()), 194 the results were often simply wrong. 195- Fixed a bug in igraph_get_all_shortest_paths_dijkstra() when edges 196 had zero weight. 197- Fixed some potential crashes in the DrL layout generator. 198- Fixed a bug in the Reingold-Tilford layout when the graph is 199 directed and mode != ALL. 200- Fixed a bug in igraph_has_multiple() that resulted in false negatives 201 for some undirected graphs. 202- Fixed a crash in weighted betweenness calculation. 203 204igraph 0.6 205========== 206 207Released June 11, 2012 208 209See also the release notes at 210http://igraph.sf.net/relnotes-0.6.html 211 212R: Major new features 213--------------------- 214 215- Vertices and edges are numbered from 1 instead of 0. 216 Note that this makes most of the old R igraph code incompatible 217 with igraph 0.6. If you want to use your old code, please use 218 the igraph0 package. See more at http://igraph.sf.net/relnotes-0.6.html. 219- The '\[' and '\[\[' operators can now be used on igraph graphs, 220 for '\[' the graph behaves as an adjacency matrix, for '[[' is 221 is treated as an adjacency list. It is also much simpler to 222 manipulate the graph structure, i.e. add/remove edges and vertices, 223 with some new operators. See more at ?graph.structure. 224- In all functions that take a vector or list of vertices or edges, 225 vertex/edge names can be given instead of the numeric ids. 226- New package 'igraphdata', contains a number of data sets that can 227 be used directly in igraph. 228- Igraph now supports loading graphs from the Nexus online data 229 repository, see nexus.get(), nexus.info(), nexus.list() and 230 nexus.search(). 231- All the community structure finding algorithm return a 'communities' 232 object now, which has a bunch of useful operations, see 233 ?communities for details. 234- Vertex and edge attributes are handled much better now. They 235 are kept whenever possible, and can be combined via a flexible API. 236 See ?attribute.combination. 237- R now prints igraph graphs to the screen in a more structured and 238 informative way. The output of summary() was also updated 239 accordingly. 240 241R: Other new features 242--------------------- 243 244- It is possible to mark vertex groups on plots, via 245 shading. Communities and cohesive blocks are plotted using this by 246 default. 247- Some igraph demos are now available, see a list via 248 'demo(package="igraph")'. 249- igraph now tries to select the optimal layout algorithm, when 250 plotting a graph. 251- Added a simple console, using Tcl/Tk. It contains a text area 252 for status messages and also a status bar. See igraph.console(). 253- Reimplemented igraph options support, see igraph.options() and 254 getIgraphOpt(). 255- Igraph functions can now print status messages. 256 257R: New or updated functions 258--------------------------- 259 260Community detection 261------------------- 262- The multi-level modularity optimization community structure detection 263 algorithm by Blondel et al. was added, see multilevel.community(). 264- Distance between two community structures: compare.communities(). 265- Community structure via exact modularity optimization, 266 optimal.community(). 267- Hierarchical random graphs and community finding, porting the code 268 from Aaron Clauset. See hrg.game(), hrg.fit(), etc. 269- Added the InfoMAP community finding method, thanks to Emmanuel 270 Navarro for the code. See infomap.community(). 271 272Shortest paths 273-------------- 274- Eccentricity (eccentricity()), and radius (radius()) calculations. 275- Shortest path calculations with get.shortest.paths() can now 276 return the edges along the shortest paths. 277- get.all.shortest.paths() now supports edge weights. 278 279Centrality 280---------- 281- Centralization scores for degree, closeness, betweenness and 282 eigenvector centrality. See centralization.scores(). 283- Personalized Page-Rank scores, see page.rank(). 284- Subgraph centrality, subgraph.centrality(). 285- Authority (authority.score()) and hub (hub.score()) scores support 286 edge weights now. 287- Support edge weights in betweenness and closeness calculations. 288- bonpow(), Bonacich's power centrality and alpha.centrality(), 289 Alpha centrality calculations now use sparse matrices by default. 290- Eigenvector centrality calculation, evcent() now works for 291 directed graphs. 292- Betweenness calculation can now use arbitrarily large integers, 293 this is required for some lattice-like graphs to avoid overflow. 294 295Input/output and file formats 296----------------------------- 297- Support the DL file format in graph.read(). See 298 http://www.analytictech.com/networks/dataentry.htm. 299- Support writing the LEDA file format in write.graph(). 300 301Plotting and layouts 302-------------------- 303- Star layout: layout.star(). 304- Layout based on multidimensional scaling, layout.mds(). 305- New layouts layout.grid() and layout.grid.3d(). 306- Sugiyama layout algorithm for layered directed acyclic graphs, 307 layout.sugiyama(). 308 309Graph generators 310---------------- 311- New graph generators: static.fitness.game(), static.power.law.game(). 312- barabasi.game() was rewritten and it supports three algorithms now, 313 the default algorithm does not generate multiple or loop edges. 314 The graph generation process can now start from a supplied graph. 315- The Watts-Strogatz graph generator, igraph_watts_strogatz() can 316 now create graphs without loop edges. 317 318Others 319------ 320- Added the Spectral Coarse Graining algorithm, see scg(). 321- The cohesive.blocks() function was rewritten in C, it is much faster 322 now. It has a nicer API, too. See demo("cohesive"). 323- Added generic breadth-first and depth-first search implementations 324 with many callbacks, graph.bfs() and graph_dfs(). 325- Support vertex and edge coloring in the VF2 (sub)graph isomorphism 326 functions (graph.isomorphic.vf2(), graph.count.isomorphisms.vf2(), 327 graph.get.isomorphisms.vf2(), graph.subisomorphic.vf2(), 328 graph.count.subisomorphisms.vf2(), graph.get.subisomorphisms.vf2()). 329- Assortativity coefficient, assortativity(), assortativity.nominal() 330 and assortativity.degree(). 331- Vertex operators that work by vertex names: 332 graph.intersection.by.name(), graph.union.by.name(), 333 graph.difference.by.name(). Thanks to Magnus Torfason for 334 contributing his code! 335- Function to calculate a non-induced subraph: subgraph.edges(). 336- More comprehensive maximum flow and minimum cut calculation, 337 see functions graph.maxflow(), graph.mincut(), stCuts(), stMincuts(). 338- Check whether a directed graph is a DAG, is.dag(). 339- has.multiple() to decide whether a graph has multiple edges. 340- Added a function to calculate a diversity score for the vertices, 341 graph.diversity(). 342- Graph Laplacian calculation (graph.laplacian()) supports edge 343 weights now. 344- Biconnected component calculation, biconnected.components() 345 now returns the components themselves. 346- bipartite.projection() calculates multiplicity of edges. 347- Maximum cardinality search: maximum.cardinality.search() and 348 chordality test: is.chordal() 349- Convex hull computation, convex.hull(). 350- Contract vertices, contract.vertices(). 351 352New in the Python interface 353--------------------------- 354 355TODO 356 357Major changes in the Python interface 358------------------------------------- 359 360TODO 361 362New in the C layer 363------------------ 364 365- Maximum cardinality search: igraph_maximum_cardinality_search() and 366 chordality test: igraph_is_chordal(). 367- Support the DL file format, igraph_read_graph_dl(). See 368 http://www.analytictech.com/networks/dataentry.htm. 369- Added generic breadth-first and depth-first search implementations 370 with many callbacks (igraph_bfs(), igraph_dfs()). 371- Centralization scores for degree, closeness, betweenness and 372 eigenvector centrality, see igraph_centralization(). 373- Added igraph_sparsemat_t, a type that implements sparse 374 matrices based on the CXSparse library by Tim Davis. 375 See http://www.cise.ufl.edu/research/sparse/CXSparse/. 376- Personalized Page-Rank scores, igraph_personalized_pagerank() and 377 igraph_personalized_pagerank_vs(). 378- Assortativity coefficient, igraph_assortativity(), 379 igraph_assortativity_nominal(), and igraph_assortativity_degree(). 380- The multi-level modularity optimization community structure detection 381 algorithm by Blondel et al. was added, see igraph_community_multilevel(). 382- Added the igraph_version() function. 383- Star layout: igraph_layout_star(). 384- Function to calculate a non-induced subraph: igraph_subgraph_edges(). 385- Distance between two community structures: igraph_compare_communities(). 386- Community structure via exact modularity optimization, 387 igraph_community_optimal_community(). 388- More comprehensive maximum flow and minimum cut calculation, 389 see functions igraph_maxflow(), igraph_mincut(), 390 igraph_all_st_cuts(), igraph_all_st_mincuts(). 391- Layout based on multidimensional scaling, igraph_layout_mds(). 392- It is now possible to access the random number generator(s) via an 393 API. Multiple RNGs can be used, from external sources as well. 394 The default RNG is MT19937. 395- Added igraph_get_all_shortest_paths_dijkstra, for calculating all 396 non-negatively weighted shortest paths. 397- Check whether a directed graph is a DAG, igraph_is_dag(). 398- Cohesive blocking, a'la Moody & White, igraph_cohesive_blocks(). 399- Igraph functions can now print status messages, see igraph_status() 400 and related functions. 401- Support writing the LEDA file format, igraph_write_graph_leda(). 402- Contract vertices, igraph_contract_vertices(). 403- The C reference manual has now a lot of example programs. 404- Hierarchical random graphs and community finding, porting the code 405 from Aaron Clauset. See igraph_hrg_game(), igraph_hrg_fit(), etc. 406- igraph_has_multiple() to decide whether a graph has multiple edges. 407- New layouts igraph_layout_grid() and igraph_layout_grid_3d(). 408- igraph_integer_t is really an integer now, it used to be a double. 409- igraph_minimum_spanning_tree(), calls either the weighted or 410 the unweighted implementation. 411- Eccentricity (igraph_eccentricity()), and radius (igraph_radius()) 412 calculations. 413- Several game theory update rules, written by Minh Van Nguyen. See 414 igraph_deterministic_optimal_imitation(), 415 igraph_stochastic_imitation(), igraph_roulette_wheel_imitation(), 416 igraph_moran_process(), 417- Sugiyama layout algorithm for layered directed acyclic graphs, 418 igraph_layout_sugiyama(). 419- New graph generators: igraph_static_fitness_game(), 420 igraph_static_power_law_game(). 421- Added the InfoMAP community finding method, thanks to Emmanuel 422 Navarro for the code. See igraph_community_infomap(). 423- Added the Spectral Coarse Graining algorithm, see igraph_scg(). 424- Added a function to calculate a diversity score for the vertices, 425 igraph_diversity(). 426 427Major changes in the C layer 428---------------------------- 429 430- Authority (igraph_authority_score()) and hub (igraph_hub_score()) scores 431 support edge weights now. 432- Graph Laplacian calculation (igraph_laplacian()) supports edge 433 weights now. 434- Support edge weights in betweenness (igraph_betweenness()) and closeness 435 (igraph_closeness()) calculations. 436- Support vertex and edge coloring in the VF2 graph isomorphism 437 algorithm (igraph_isomorphic_vf2(), igraph_count_isomorphisms_vf2(), 438 igraph_get_isomorphisms_vf2(), igraph_subisomorphic_vf2(), 439 igraph_count_subisomorphisms_vf2(), igraph_get_subisomorphisms_vf2()). 440- Added print operations for the igraph_vector*_t, igraph_matrix*_t and 441 igraph_strvector_t types. 442- Biconnected component calculation (igraph_biconnected_components()) 443 can now return the components themselves. 444- Eigenvector centrality calculation, igraph_eigenvector_centrality() 445 now works for directed graphs. 446- Shortest path calculations with get_shortest_paths() and 447 get_shortest_paths_dijkstra() can now return the edges along the paths. 448- Betweenness calculation can now use arbitrarily large integers, 449 this is required for some lattice-like graphs to avoid overflow. 450- igraph_bipartite_projection() calculates multiplicity of edges. 451- igraph_barabasi_game() was rewritten and it supports three 452 algorithms now, the default algorithm does not generate multiple or 453 loop edges. 454- The Watts-Strogatz graph generator, igraph_watts_strogatz() can 455 now create graphs without loop edges. 456- igraph should be now thread-safe, on architectures that support 457 thread-local storage (Linux and Windows: yes, Mac OSX: no). 458 459We also fixed numerous bugs, too many to include them here, sorry. 460You may look at our bug tracker at https://bugs.launchpad.net/igraph 461to check whether a bug was fixed or not. Thanks for all the people 462reporting bugs. Special thanks to Minh Van Nguyen for a lot of bug 463reports, documentation fixes and contributed code! 464 465igraph 0.5.3 466============ 467 468Released November 22, 2009 469 470Bugs corrected in the R interface 471--------------------------------- 472- Some small changes to make 'R CMD check' clean 473- Fixed a bug in graph.incidence, the 'directed' and 'mode' arguments 474 were not handled correctly 475- Betweenness and edge betweenness functions work for graphs with 476 many shortest paths now (up to the limit of long long int) 477- When compiling the package, the configure script fails if there is 478 no C compiler available 479- igraph.from.graphNEL creates the right number of loop edges now 480- Fixed a bug in bipartite.projection() that caused occasional crashes 481 on some systems 482 483New in the Python interface 484--------------------------- 485- Added support for weighted diameter 486- get_eid() considers edge directions by default from now on 487- Fixed a memory leak in the attribute handler 488- 'NaN' and 'inf' are treated correctly now 489 490Bugs corrected in the C layer 491----------------------------- 492- Betweenness and edge betweenness functions work for graphs with 493 many shortest paths now (up to the limit of long long int) 494- The configure script fails if there is no C compiler available 495- Fixed a bug in igraph_community_spinglass, when csize was a NULL 496 pointer, but membership was not 497- Fixed a bug in igraph_bipartite_projection that caused occasional 498 crashes on some systems 499 500igraph 0.5.2 501============ 502 503Released April 10, 2009 504 505See also the release notes at 506http://igraph.sf.net/relnotes-0.5.2.html 507 508New in the R interface 509---------------------- 510 511- Added progress bar support to beweenness() and 512 betweenness.estimate(), layout.drl() 513- Speeded up betweenness estimation 514- Speeded up are.connected() 515- Johnson's shortest paths algorithm added 516- shortest.paths() has now an 'algorithm' argument to choose from the 517 various implementations manually 518- Always quote symbolic vertex names when printing graphs or edges 519- Average nearest neighbor degree calculation, graph.knn() 520- Weighted degree (also called strength) calculation, graph.strength() 521- Some new functions to support bipartite graphs: graph.bipartite(), 522 is.bipartite(), get.indicence(), graph.incidence(), 523 bipartite.projection(), bipartite.projection.size() 524- Support for plotting curved edges with plot.igraph() and tkplot() 525- Added support for weighted graphs in alpha.centrality() 526- Added the label propagation community detection algorithm by 527 Raghavan et al., label.propagation.community() 528- cohesive.blocks() now has a 'cutsetHeuristic' argument to choose 529 between two cutset algorithms 530- Added a function to "unfold" a tree, unfold.tree() 531- New tkplot() arguments to change the drawing area 532- Added a minimal GUI, invoke it with tkigraph() 533- The DrL layout generator, layout.drl() has a three dimensional mode 534 now. 535 536Bugs corrected in the R interface 537--------------------------------- 538 539- Fixed a bug in VF2 graph isomorphism functions 540- Fixed a bug when a sparse adjacency matrix was requested in 541 get.adjacency() and the graph was named 542- VL graph generator in degree.sequence.game() checks now that 543 the sum of the degrees is even 544- Many fixes for supporting various compilers, e.g. GCC 4.4 and Sun's 545 C compiler 546- Fixed memory leaks in graph.automorphisms(), Bellman-Ford 547 shortest.paths(), independent.vertex.sets() 548- Fix a bug when a graph was imported from LGL and exported to NCOL 549 format (\#289596) 550- cohesive.blocks() creates its temporary file in the session 551 temporary directory 552- write.graph() and read.graph() now give error messages when unknown 553 arguments are given 554- The GraphML reader checks the name of the attributes to avoid adding 555 a duplicate 'id' attribute 556- It is possible to change the 'ncv' ARPACK parameter for 557 leading.eigenvector.community() 558- Fixed a bug in path.length.hist(), 'unconnected' was wrong 559 for unconnected and undirected graphs 560- Better handling of attribute assingment via iterators, this is now 561 also clarified in the manual 562- Better error messages for unknown vertex shapes 563- Make R package unload cleanly if unloadNamespace() is used 564- Fixed a bug in plotting square shaped vertices (\#325244) 565- Fixed a bug in graph.adjacency() when the matrix is a sparse matrix 566 of class "dgTMatrix" 567 568New in the Python interface 569--------------------------- 570 571- Speeded up betweenness estimation 572- Johnson's shortest paths algorithm added (selected automatically 573 by Graph.shortest_paths() if needed) 574- Weighted degree (also called strength) calculation, Graph.strength() 575- Some new methods to support bipartite graphs: Graph.Bipartite(), 576 Graph.is_bipartite(), Graph.get_indicence(), Graph.Incidence(), 577 Graph.bipartite_projection(), Graph.bipartite_projection_size() 578- Added the label propagation community detection algorithm by 579 Raghavan et al., Graph.community_label_propagation() 580- Added a function to "unfold" a tree, Graph.unfold_tree() 581- setup.py script improvements 582- Graph plotting now supports edge_arrow_size and edge_arrow_width 583- Added Graph.Formula to create small graphs from a simple notation 584- VertexSeq and EdgeSeq objects can now be indexed by slices 585 586New in the C layer 587------------------ 588 589- Added progress bar support to igraph_betweenness() and 590 igraph_betweenness_estimate(), igraph_layout_drl() 591- Speeded up igraph_betweenness_estimate(), igraph_get_eid(), 592 igraph_are_connected(), igraph_get_eids() 593- Added igraph_get_eid2() 594- Johnson's shortest path algorithm added: 595 igraph_shortest_paths_johnson() 596- Average nearest neighbor degree calculation, 597 igraph_avg_nearest_neighbor_degree() 598- Weighted degree (also called strength) calculation, 599 igraph_strength() 600- Some functions to support bipartite graphs: igraph_full_bipartite(), 601 igraph_bipartite_projection(), igraph_create_bipartite(), 602 igraph_incidence(), igraph_get_incidence(), 603 igraph_bipartite_projection_size(), igraph_is_bipartite() 604- Added the label propagation community detection algorithm by 605 Raghavan et al., igraph_community_label_propagation() 606- Added an example that shows how to set the random number generator's 607 seed from C (examples/simple/random_seed.c) 608- Added a function to "unfold" a tree, igraph_unfold_tree() 609- C attribute handler updates: added functions to query many 610 vertices/edges at once 611- Three dimensional DrL layout, igraph_layout_drl_3d() 612 613Bugs corrected in the C layer 614----------------------------- 615 616- Fixed a bug in igraph_isomorphic_function_vf2(), affecting all VF2 617 graph isomorphism functions 618- VL graph generator in igraph_degree_sequence_game() checks now that 619 the sum of the degrees is even 620- Many small corrections to make igraph compile with Microsoft Visual 621 Studio 2003, 2005 and 2008 622- Many fixes for supporting various compilers, e.g. GCC 4.4 and Sun's 623 C compiler 624- Fix a bug when a graph was imported from LGL and exported to NCOL 625 format (\#289596) 626- Fixed memory leaks in igraph_automorphisms(), 627 igraph_shortest_paths_bellman_ford(), 628 igraph_independent_vertex_sets() 629- The GraphML reader checks the name of the attributes to avoid adding 630 a duplicate 'id' attribute 631- It is possible to change the 'ncv' ARPACK parameter for 632 igraph_community_leading_eigenvector() 633- Fixed a bug in igraph_path_length_hist(), 'unconnected' was wrong 634 for unconnected and undirected graphs. 635 636igraph 0.5.1 637============ 638 639Released July 14, 2008 640 641See also the release notes at 642http://igraph.sf.net/relnotes-0.5.1.html 643 644New in the R interface 645---------------------- 646 647- A new layout generator called DrL. 648- Uniform sampling of random connected undirected graphs with a 649 given degree sequence. 650- Edge labels are plotted at 1/3 of the edge, this is better if 651 the graph has mutual edges. 652- Initial and experimental vertex shape support in 'plot'. 653- New function, 'graph.adjlist' creates igraph graphs from 654 adjacency lists. 655- Conversion to/from graphNEL graphs, from the 'graph' R package. 656- Fastgreedy community detection can utilize edge weights now, this 657 was missing from the R interface. 658- The 'arrow.width' graphical parameter was added. 659- graph.data.frame has a new argument 'vertices'. 660- graph.adjacency and get.adjacency support sparse matrices, 661 the 'Matrix' package is required to use this functionality. 662- graph.adjacency adds column/row names as 'name' attribute. 663- Weighted shortest paths using Dijkstra's or the Belmann-Ford 664 algorithm. 665- Shortest path functions return 'Inf' for unreachable vertices. 666- New function 'is.mutual' to find mutual edges in a directed graph. 667- Added inverse log-weighted similarity measure (a.k.a. Adamic/Adar 668 similarity). 669- preference.game and asymmetric.preference.game were 670 rewritten, they are O(|V|+|E|) now, instead of O(|V|^2). 671- Edge weight support in function 'get.shortest.paths', it uses 672 Dijkstra's algorithm. 673 674Bugs corrected in the R interface 675--------------------------------- 676 677- A bug was corrected in write.pajek.bgraph. 678- Several bugs were corrected in graph.adjacency. 679- Pajek reader bug corrected, used to segfault if '\*Vertices' 680 was missing. 681- Directedness is handled correctly when writing GML files. 682 (But note that 'correct' conflicts the standard here.) 683- Corrected a bug when calculating weighted, directed PageRank on an 684 undirected graph. (Which does not make sense anyway.) 685- Several bugs were fixed in the Reingold-Tilford layout to avoid 686 edge crossings. 687- A bug was fixed in the GraphML reader, when the value of a graph 688 attribute was not specified. 689- Fixed a bug in the graph isomorphism routine for small (3-4 vertices) 690 graphs. 691- Corrected the random sampling implementation (igraph_random_sample), 692 now it always generates unique numbers. This affects the 693 Gnm Erdos-Renyi generator, it always generates simple graphs now. 694- The basic igraph constructor (igraph_empty_attrs, all functions 695 are expected to call this internally) now checks whether the number 696 of vertices is finite. 697- The LGL, NCOL and Pajek graph readers handle errors properly now. 698- The non-symmetric ARPACK solver returns results in a consistent form 699 now. 700- The fast greedy community detection routine now checks that the graph 701 is simple. 702- The LGL and NCOL parsers were corrected to work with all 703 kinds of end-of-line encodings. 704- Hub & authority score calculations initialize ARPACK parameters now. 705- Fixed a bug in the Walktrap community detection routine, when applied 706 to unconnected graphs. 707- Several small memory leaks were removed, and a big one from the Spinglass 708 community structure detection function 709 710New in the Python interface 711--------------------------- 712 713- A new layout generator called DrL. 714- Uniform sampling of random connected undirected graphs with a 715 given degree sequence. 716- Methods parameters accepting igraph.IN, igraph.OUT and igraph.ALL 717 constants now also accept these as strings ("in", "out" and "all"). 718 Prefix matches also allowed as long as the prefix match is unique. 719- Graph.shortest_paths() now supports edge weights (Dijkstra's and 720 Bellman-Ford algorithm implemented) 721- Graph.get_shortest_paths() also supports edge weights 722 (only Dijkstra's algorithm yet) 723- Added Graph.is_mutual() to find mutual edges in a directed graph. 724- Added inverse log-weighted similarity measure (a.k.a. Adamic/Adar 725 similarity). 726- preference.game and asymmetric.preference.game were 727 rewritten, they are O(|V|+|E|) now, instead of O(|V|^2). 728- ARPACK options can now be modified from the Python interface 729 (thanks to Kurt Jacobson) 730- Layout.to_radial() added -- now you can create a top-down tree 731 layout by the Reingold-Tilford algorithm and then turn it to a 732 radial tree layout 733- Added Graph.write_pajek() to save graphs in Pajek format 734- Some vertex and edge related methods can now also be accessed via 735 the methods of VertexSeq and EdgeSeq, restricted to the current 736 vertex/edge sequence of course 737- Visualisations now support triangle shaped vertices 738- Added Graph.mincut() 739- Added Graph.Weighted_Adjacency() to create graphs from weighted 740 adjacency matrices 741- Kamada-Kawai and Fruchterman-Reingold layouts now accept initial 742 vertex positions 743- Graph.Preference() and Graph.Asymmetric_Preference() were 744 rewritten, they are O(|V|+|E|) now, instead of O(|V|^2). 745 746Bugs corrected in the Python interface 747-------------------------------------- 748 749- Graph.constraint() now properly returns floats instead of integers 750 (thanks to Eytan Bakshy) 751- Graphs given by adjacency matrices are now finally loaded and saved 752 properly 753- Graph.Preference() now accepts floats in type distributions 754- A small bug in Graph.community_edge_betweenness() corrected 755- Some bugs in numeric attribute handling resolved 756- VertexSeq and EdgeSeq objects can now be subsetted by lists and 757 tuples as well 758- Fixed a bug when dealing with extremely small layout sizes 759- Eigenvector centality now always return positive values 760- Graph.authority_score() now really returns the authority scores 761 instead of the hub scores (blame copypasting) 762- Pajek reader bug corrected, used to segfault if '\*Vertices' 763 was missing. 764- Directedness is handled correctly when writing GML files. 765 (But note that 'correct' conflicts the standard here.) 766- Corrected a bug when calculating weighted, directed PageRank on an 767 undirected graph. (Which does not make sense anyway.) 768- Several bugs were fixed in the Reingold-Tilford layout to avoid 769 edge crossings. 770- A bug was fixed in the GraphML reader, when the value of a graph 771 attribute was not specified. 772- Fixed a bug in the graph isomorphism routine for small (3-4 vertices) 773 graphs. 774- Corrected the random sampling implementation (igraph_random_sample), 775 now it always generates unique numbers. This affects the 776 Gnm Erdos-Renyi generator, it always generates simple graphs now. 777- The LGL, NCOL and Pajek graph readers handle errors properly now. 778- The non-symmetric ARPACK solver returns results in a consistent form 779 now. 780- The fast greedy community detection routine now checks that the graph 781 is simple. 782- The LGL and NCOL parsers were corrected to work with all 783 kinds of end-of-line encodings. 784- Hub & authority score calculations initialize ARPACK parameters now. 785- Fixed a bug in the Walktrap community detection routine, when applied 786 to unconnected graphs. 787- Several small memory leaks were removed, and a big one from the Spinglass 788 community structure detection function 789 790New in the C layer 791------------------ 792 793- A new layout generator called DrL. 794- Uniform sampling of random connected undirected graphs with a 795 given degree sequence. 796- Some stochastic test results are ignored (for spinglass community 797 detection, some Erdos-Renyi generator tests) 798- Weighted shortest paths, Dijkstra's algorithm. 799- The unweigthed shortest path routine returns 'Inf' for unreachable 800 vertices. 801- New function, igraph_adjlist can create igraph graphs from 802 adjacency lists. 803- New function, igraph_weighted_adjacency can create weighted graphs 804 from weight matrices. 805- New function, igraph_is_mutual to search for mutual edges. 806- Added inverse log-weighted similarity measure (a.k.a. Adamic/Adar 807 similarity). 808- igraph_preference_game and igraph_asymmetric_preference_game were 809 rewritten, they are O(|V|+|E|) now, instead of O(|V|^2). 810- The Bellman-Ford shortest path algorithm was added. 811- Added weighted variant of igraph_get_shortest_paths, based on 812 Dijkstra's algorithm. 813- Several small memory leaks were removed, and a big one from the Spinglass 814 community structure detection function 815 816Bugs corrected in the C layer 817----------------------------- 818 819- Several bugs were corrected in the (still experimental) C attribute 820 handler. 821- Pajek reader bug corrected, used to segfault if '\*Vertices' 822 was missing. 823- Directedness is handled correctly when writing GML files. 824 (But note that 'correct' conflicts the standard here.) 825- Corrected a bug when calculating weighted, directed PageRank on an 826 undirected graph. (Which does not make sense anyway.) 827- Some code polish to make igraph compile with GCC 4.3 828- Several bugs were fixed in the Reingold-Tilford layout to avoid 829 edge crossings. 830- A bug was fixed in the GraphML reader, when the value of a graph 831 attribute was not specified. 832- Fixed a bug in the graph isomorphism routine for small (3-4 vertices) 833 graphs. 834- Corrected the random sampling implementation (igraph_random_sample), 835 now it always generates unique numbers. This affects the 836 Gnm Erdos-Renyi generator, it always generates simple graphs now. 837- The basic igraph constructor (igraph_empty_attrs, all functions 838 are expected to call this internally) now checks whether the number 839 of vertices is finite. 840- The LGL, NCOL and Pajek graph readers handle errors properly now. 841- The non-symmetric ARPACK solver returns results in a consistent form 842 now. 843- The fast greedy community detection routine now checks that the graph 844 is simple. 845- The LGL and NCOL parsers were corrected to work with all 846 kinds of end-of-line encodings. 847- Hub & authority score calculations initialize ARPACK parameters now.x 848- Fixed a bug in the Walktrap community detection routine, when applied 849 to unconnected graphs. 850 851igraph 0.5 852========= 853 854Released February 14, 2008 855 856See also the release notes at http://igraph.sf.net/relnotes-0.5.html 857 858New in the R interface 859---------------------- 860 861- The 'rescale', 'asp' and 'frame' graphical parameters were added 862- Create graphs from a formula notation (graph.formula) 863- Handle graph attributes properly 864- Calculate the actual minimum cut for undirected graphs 865- Adjacency lists, get.adjlist and get.adjedgelist added 866- Eigenvector centrality computation is much faster now 867- Proper R warnings, instead of writing the warning to the terminal 868- R checks graphical parameters now, the unknown ones are not just 869 ignored, but an error message is given 870- plot.igraph has an 'add' argument now to compose plots with multiple 871 graphs 872- plot.igraph supports the 'main' and 'sub' arguments 873- layout.norm is public now, it can normalize a layout 874- It is possible to supply startup positions to layout generators 875- Always free memory when CTRL+C/ESC is pressed, in all operating 876 systems 877- plot.igraph can plot square vertices now, see the 'shape' parameter 878- graph.adjacency rewritten when creating weighted graphs 879- We use match.arg whenever possible. This means that character scalar 880 options can be abbreviated and they are always case insensitive 881 882- VF2 graph isomorphism routines can check subgraph isomorphism now, 883 and they are able to return matching(s) 884- The BLISS graph isomorphism algorithm is included in igraph now. See 885 canonical.permutation, graph.isomorphic.bliss 886- We use ARPACK for eigenvalue/eigenvector calculation. This means that the 887 following functions were rewritten: page.rank, 888 leading.eigenvector.community.\*, evcent. New functions based on 889 ARPACK: hub.score, authority.score, arpack. 890- Edge weights for Fruchterman-Reingold layout (layout.fruchterman.reingold). 891- Line graph calculation (line.graph) 892- Kautz and de Bruijn graph generators (graph.kautz, graph.de.bruijn) 893- Support for writing graphs in DOT format 894- Jaccard and Dice similarity coefficients added (similarity.jaccard, 895 similarity.dice) 896- Counting the multiplicity of edges (count.multiple) 897- The graphopt layout algorithm was added, layout.graphopt 898- Generation of "famous" graphs (graph.famous). 899- Create graphs from LCF notation (graph.cf). 900- Dyad census and triad cencus functions (dyad.census, triad.census) 901- Cheking for simple graphs (is.simple) 902- Create full citation networks (graph.full.citation) 903- Create a histogram of path lengths (path.length.hist) 904- Forest fire model added (forest.fire.game) 905- DIMACS reader can handle different file types now 906- Biconnected components and articulation points (biconnected.components, 907 articulation.points) 908- Kleinberg's hub and authority scores (hub.score, authority.score) 909- as.undirected handles attributes now 910- Geometric random graph generator (grg.game) can return the 911 coordinates of the vertices 912- Function added to convert leading eigenvector community structure result to 913 a membership vector (community.le.to.membership) 914- Weighted fast greedy community detection 915- Weighted page rank calculation 916- Functions for estimating closeness, betweenness, edge betweenness by 917 introducing a cutoff for path lengths (closeness.estimate, 918 betweenness.estimate, edge.betweenness.estimate) 919- Weighted modularity calculation 920- Function for permuting vertices (permute.vertices) 921- Betweenness and closeness calculations are speeded up 922- read.graph can handle all possible line terminators now (\r, \n, \r\n, \n\r) 923- Error handling was rewritten for walktrap community detection, 924 the calculation can be interrupted now 925- The maxflow/mincut functions allow to supply NULL pointer for edge 926 capacities, implying unit capacities for all edges 927 928Bugs corrected in the R interface 929--------------------------------- 930 931- Fixed a bug in cohesive.blocks, cohesive blocks were sometimes not 932 calculated correctly 933 934New in the Python interface 935--------------------------- 936 937- Added shell interface: igraph can now be invoked by calling the script called 938 igraph from the command line. The script launches the Python interpreter and 939 automatically imports igraph functions into the main namespace 940- Pickling (serialization) support for Graph objects 941- Plotting functionality based on the Cairo graphics library (so you need to 942 install python-cairo if you want to use it). Currently the following 943 objects can be plotted: graphs, adjacency matrices and dendrograms. Some 944 crude support for plotting histograms is also implemented. Plots can be 945 saved in PNG, SVG and PDF formats. 946- Unified Graph.layout method for accessing layout algorithms 947- Added interfaces to walktrap community detection and the BLISS isomorphism 948 algorithm 949- Added dyad and triad census functionality and motif counting 950- VertexSeq and EdgeSeq objects can now be restricted to subsets of the 951 whole network (e.g., you can select vertices/edges based on attributes, 952 degree, centrality and so on) 953 954New in the C library 955-------------------- 956 957- Many types (stack, matrix, dqueue, etc.) are templates now 958 They were also rewritten to provide a better organized interface 959- VF2 graph isomorphism routines can check subgraph isomorphism now, 960 and they are able to return matching(s) 961- The BLISS graph isomorphism algorithm is included in igraph now. See 962 igraph_canonical_permutation, igraph_isomorphic_bliss 963- We use ARPACK for eigenvalue/eigenvector calculation. This means that the 964 following functions were rewritten: igraph_pagerank, 965 igraph_community_leading_eigenvector_\*. New functions based on 966 ARPACK: igraph_eigenvector_centrality, igraph_hub_score, 967 igraph_authority_score, igraph_arpack_rssolve, igraph_arpack_rnsolve 968- Experimental C attribute interface added. I.e. it is possible to use 969 graph/vertex/edge attributes from C code now. 970 971- Edge weights for Fruchterman-Reingold layout. 972- Line graph calculation. 973- Kautz and de Bruijn graph generators 974- Support for writing graphs in DOT format 975- Jaccard and Dice similarity coefficients added 976- igraph_count_multiple added 977- igraph_is_loop and igraph_is_multiple "return" boolean vectors 978- The graphopt layout algorithm was added, igraph_layout_graphopt 979- Generation of "famous" graphs, igraph_famous 980- Create graphs from LCF notation, igraph_lcf, igraph_lcf_vector 981- igraph_add_edge adds a single edge to the graph 982- Dyad census and triad cencus functions added 983- igraph_is_simple added 984- progress handlers are allowed to stop calculation 985- igraph_full_citation to create full citation networks 986- igraph_path_length_hist, create a histogram of path lengths 987- forest fire model added 988- DIMACS reader can handle different file types now 989- Adjacency list types made public now (igraph_adjlist_t, igraph_adjedgelist_t) 990- Biconnected components and articulation points can be computed 991- Eigenvector centrality computation 992- Kleinberg's hub and authority scores 993- igraph_to_undirected handles attributes now 994- Geometric random graph generator can return the coordinates of the vertices 995- Function added to convert leading eigenvector community structure result to 996 a membership vector (igraph_le_community_to_membership) 997- Weighted fast greedy community detection 998- Weighted page rank calculation 999- Functions for estimating closeness, betweenness, edge betweenness by 1000 introducing a cutoff for path lengths 1001- Weighted modularity calculation 1002- igraph_permute_vertices added 1003- Betweenness ans closeness calculations are speeded up 1004- Startup positions can be supplied to the Kamada-Kawai layout 1005 algorithms 1006- igraph_read_graph_\* functions can handle all possible line 1007 terminators now (\r, \n, \r\n, \n\r) 1008- Error handling was rewritten for walktrap community detection, 1009 the calculation can be interrupted now 1010- The maxflow/mincut functions allow to supply a null pointer for edge 1011 capacities, implying unit capacities for all edges 1012 1013Bugs corrected in the C library 1014------------------------------- 1015 1016- Memory leak fixed in adjacency list handling 1017- Memory leak fixed in maximal independent vertex set calculation 1018- Fixed a bug when rewiring undirected graphs with igraph_rewire 1019- Fixed edge betweenness community structure detection for unconnected graphs 1020- Make igraph compile with Sun Studio 1021- Betweenness bug fixed, when not computing for all vertices 1022- memory usage of clique finding reduced 1023- Corrected bugs for motif counts when not all motifs were counted, 1024 but a 'cut' vector was used 1025- Bugs fixed in trait games and cited type game 1026- Accept underscore as letter in GML files 1027- GML file directedness notation reversed, more logical this way 1028 1029igraph 0.4.5 1030========= 1031 1032Released January 1, 2008 1033 1034New: 1035- Cohesive block finding in the R interface, thanks to Peter McMahan 1036 for contributing his code. See James Moody and Douglas R. White, 1037 2003, in Structural Cohesion and Embeddedness: A Hierarchical 1038 Conception of Social Groups American Sociological Review 68(1):1-25 1039- Biconnected components and articulation points. 1040- R interface: better printing of attributes. 1041- R interface: graph attributes can be used via '$'. 1042 1043New in the C library: 1044- igraph_vector_bool_t data type. 1045 1046Bug fixed: 1047- Erdos-Renyi random graph generators rewritten. 1048 1049igraph 0.4.4 1050========= 1051 1052Released October 3, 2007 1053 1054This release should work seemlessly with the new R 2.6.0 version. 1055Some other bugs were also fixed: 1056- A bug was fixed in the Erdos-Renyi graph generator, which sometimes 1057 added an extra vertex. 1058- MSVC compilation issues were fixed. 1059- MinGW compilation fixes. 1060 1061igraph 0.4.3 1062========= 1063 1064Released August 13, 2007 1065 1066The next one in the sequence of bugfix releases. Thanks to many people 1067sending bug reports. Here are the changes: 1068- Some memory leaks removed when using attributes from R or Python. 1069- GraphML parser: entities and character data in multiple chunks are now handled correctly. 1070- A bug corrected in edge betweenness community structure detection, 1071 it failed if called many times from the same program/session. 1072- Bug corrected in 'adjacent edges' edge iterator. 1073- Python interface: edge and vertex attribute deletion bug corrected. 1074- Edge betweeness community structure: handle unconnected graphs properly. 1075- Fixed bug related to fast greedy community detection in unconnected graphs. 1076- Use a different kind of parser (Push) for reading GraphML files. This is almost 1077 invisible for users but fixed a nondeterministic bug when reading in GraphML 1078 files. 1079- R interface: plot now handles properly if called with a vector as the edge.width 1080 argument for directed graphs. 1081- R interface: bug (typo) corrected for walktrap.community and weighted graphs. 1082- Test suite should run correctly on Cygwin now. 1083 1084igraph 0.4.2 1085========= 1086 1087Released June 7, 2007 1088 1089This is another bugfix release, as there was a serious bug in the 1090R package of the previous version: it could not read and write graphs 1091to files in any format under MS Windows. 1092 1093Some other bits added: 1094- circular Reingold-Tilford layout generator for trees 1095- corrected a bug, Pajek files are written properly under MS Windows now. 1096- arrow.size graphical edge parameter added in the R interface. 1097 1098igraph 0.4.1 1099========= 1100 1101Released May 23, 2007 1102 1103This is a minor release, it corrects a number of bugs, mostly in the 1104R package. 1105 1106igraph 0.4 1107========= 1108 1109Released May 21, 2007 1110 1111The major new additions in this release is a bunch of community 1112detection algorithms and support for the GML file format. Here 1113is the complete list of changes: 1114 1115 1116New in the C library 1117-------------------- 1118 1119- internal representation changed 1120- neighbors always returns an ordered list 1121- igraph_is_loop and igraph_is_multiple added 1122 1123- topological sorting 1124- VF2 isomorphism algorithm 1125- support for reading the file format of the Graph Database for isomorphism 1126- igraph_mincut cat calculate the actual minimum cut 1127- girth calculation added, thanks to Keith Briggs 1128- support for reading and writing GML files 1129 1130- Walktrap community detection algorithm added, thanks to Matthieu Latapy 1131 and Pascal Pons 1132- edge betweenness based community detection algorithm added 1133- fast greedy algorithm for community detection by Clauset et al. added 1134 thanks to Aaron Clauset for sharing his code 1135- leading eigenvector community detection algorithm by Mark Newman added 1136- igraph_community_to_membership supporting function added, creates 1137 a membership vector from a community structure merge tree 1138- modularity calculation added 1139 1140New in the R interface 1141---------------------- 1142 1143- as the internal representation changed, graphs stored with 'save' 1144 with an older igraph version cannot be read back with the new 1145 version reliably. 1146- neighbors returns ordered lists 1147 1148- topological sorting 1149- VF2 isomorphism algorithm 1150- support for reading graphs from the Graph Database for isomorphism 1151- girth calculation added, thanks to Keith Briggs 1152- support for reading and writing GML files 1153 1154- Walktrap community detection algorithm added, thanks to Matthieu Latapy 1155 and Pascal Pons 1156- edge betweenness based community detection algorithm added 1157- fast greedy algorithm for community detection by Clauset et al. added 1158 thanks to Aaron Clauset for sharing his code 1159- leading eigenvector community detection algorithm by Mark Newman added 1160- functions for creating denrdograms from the output of the 1161 community detection algorithms added 1162- community.membership supporting function added, creates 1163 a membership vector from a community structure merge tree 1164- modularity calculation added 1165 1166- graphics parameter handling is completely rewritten, uniform handling 1167 of colors and fonts, make sure you read ?igraph.plotting 1168- new plotting parameter for edges: arrow.mode 1169- a bug corrected when playing a nonlinear barabasi.game 1170- better looking plotting in 3d using rglplot: edges are 3d too 1171- rglplot layout is allowed to be two dimensional now 1172- rglplot suspends updates while drawing, this makes it faster 1173- loop edges are correctly plotted by all three plotting functions 1174 1175- better printing of attributes when printing graphs 1176- summary of a graph prints attribute names 1177- is.igraph rewritten to make it possible to inherit from the 'igraph' class 1178- somewhat better looking progress meter for functions which support it 1179 1180Others 1181------ 1182 1183- proper support for Debian packages (re)added 1184- many functions benefit from the new internal representation and are 1185 faster now: transitivity, reciprocity, graph operator functions like 1186 intersection and union, etc. 1187- igraph compiles with Microsoft Visual C++ now 1188- there were some internal changes to make igraph a real graph algorithm 1189 platform in the near future, but these are undocumented now 1190 1191Bugs corrected 1192-------------- 1193 1194- corrected a bug when reading Pajek files: directed graphs were read as undirected 1195 1196Debian package repository available 1197================================== 1198 1199Debian Linux users can now install and update the C interface 1200using the standard package manager. Just add the following two 1201lines to /etc/apt/sources.list and install the libigraph and 1202libigraph-dev packages. Packages for the Python interface are 1203coming soon. 1204 1205deb http://cneurocvs.rmki.kfki.hu /packages/binary/ 1206 1207deb-src http://cneurocvs.rmki.kfki.hu /packages/source/ 1208 1209igraph 0.3.3 1210============ 1211 1212Released February 28, 2007 1213 1214New in the C library 1215-------------------- 1216 1217* igraph_connect_neighborhood, nomen est omen 1218* igraph_watts_strogatz_game and igraph_rewire_edges 1219* K-core decomposition: igraph_coreness 1220* Clique and independent vertex set related functions: 1221 igraph_cliques, igraph_independent_vertex_sets, 1222 igraph_maximal_cliques, igraph_maximal_independent_vertex_sets, 1223 igraph_independence_number, igraph_clique_number, 1224 Some of these function were ported from the very_nauty library 1225 of Keith Briggs, thanks Keith! 1226* The GraphML file format now supports graph attributes 1227* Transitivity calculation speeded up 1228* Correct transitivity calculation for multigraphs (ie. non-simple graphs) 1229 1230New in the R interface 1231---------------------- 1232 1233* connect.neighborhood 1234* watts.strogatz.game and rewire.edges 1235* K-core decomposition: graph.coreness 1236* added the 'innei' and 'outnei' shorthands for vertex sequence indexing 1237 see help(iterators) 1238* Clique and independent vertex set related functions: 1239 cliques, largest.cliques, maximal.cliques, clique.number, 1240 independent.vertex.sets, largest.independent.vertex.sets, 1241 maximal.independent.vertex.sets, independence.number 1242* The GraphML file format now supports graph attributes 1243* edge.lty argument added to plot.igraph and tkplot 1244* Transitivity calculation speeded up 1245* Correct transitivity calculation for multigraphs (ie. non-simple graphs) 1246* alpha.centrality added, calculates Bonacich alpha centrality, see docs. 1247 1248Bugs corrected 1249-------------- 1250 1251* 'make install' installs the library correctly on Cygwin now 1252* Pajek parser corrected to read files with MacOS newline characters correctly 1253* overflow bug in transitivity calculation for large graphs corrected 1254* an internal memcpy/memmove bug causing some segfaults removed 1255* R interface: tkplot bug with graphs containing a 'name' attribute 1256* R interface: attribute handling bug when adding vertices 1257* R interface: color selection bug corrected 1258* R interface: plot.igraph when plotting loops 1259 1260Python interface documentation 1261==================== 1262 1263Jan 8, 2007 1264 1265The documentation of the Python interface is available. 1266See section 'documentation' in the menu on the left. 1267 1268igraph 0.3.2 1269========= 1270 1271Released Dec 19, 2006 1272 1273This is a new major release, it contains many new things: 1274 1275Changes in the C library 1276------------------------ 1277 1278- igraph_maxdegree added, calculates the maximum degree in the graph 1279- igraph_grg_game, geometric random graphs 1280- igraph_density, graph density calculation 1281- push-relabel maximum flow algorithm added, igraph_maxflow_value 1282- minimum cut functions added based on maximum flow: 1283 igraph_st_mincut_value, igraph_mincut_value, the Stoer-Wagner 1284 algorithm is implemented for undirected graphs 1285- vertex connectivity functions, usually based on maximum flow: 1286 igraph_st_vertex_connectivity, igraph_vertex_connectivity 1287- edge connectivity functions, usually based on maximum flow: 1288 igraph_st_edge_connectivity, igraph_edge_connectivity 1289- other functions based on maximum flow: igraph_edge_disjoint_paths, 1290 igraph_vertex_disjoint_paths, igraph_adhesion, igraph_cohesion 1291- dimacs file format added 1292- igraph_to_directed handles attributes 1293- igraph_constraint calculation corrected, it handles weighted graphs 1294- spinglass-based community structure detection, the Joerg Reichardt -- 1295 Stefan Bornholdt algorithm added: igraph_spinglass_community, 1296 igraph_spinglass_my_community 1297- igraph_extended_chordal_rings, it creates extended chordal rings 1298- 'no' argument added to igraph_clusters, it is possible to calculate 1299 the number of clusters without calculating the clusters themselves 1300- minimum spanning tree functions keep attributes now and also the 1301 direction of the edges is kept in directed graphs 1302- there are separate functions to calculate different types of 1303 transitivity now 1304- igraph_delete_vertices rewritten to allocate less memory for the new 1305 graph 1306- neighborhood related functions added: igraph_neighborhood, 1307 igraph_neighborhood_size, igraph_neighborhood_graphs 1308- two new games added based on different node types: 1309 igraph_preference_game and igraph_asymmetric_preference_game 1310- Laplacian of a graph can be calculated by the igraph_laplacian function 1311 1312Changes in the R interface 1313-------------------------- 1314 1315- bonpow function ported from SNA to calculate Bonacich power centrality 1316- get.adjacency supports attributes now, this means that it sets the 1317 colnames and rownames attributes and can return attribute values in 1318 the matrix instead of 0/1 1319- grg.game, geometric random graphs 1320- graph.density, graph density calculation 1321- edge and vertex attributes can be added easily now when added new 1322 edges with add.edges or new vertices with add.vertices 1323- graph.data.frame creates graph from data frames, this can be used to 1324 create graphs with edge attributes easily 1325- plot.igraph and tkplot can plot self-loop edges now 1326- graph.edgelist to create a graph from an edge list, can also handle 1327 edge lists with symbolic names 1328- get.edgelist has now a 'names' argument and can return symbolic 1329 vertex names instead of vertex ids, by default id uses the 'name' 1330 vertex attribute is returned 1331- printing graphs on screen also prints symbolic symbolic names 1332 (the 'name' attribute if present) 1333- maximum flow and minimum cut functions: graph.maxflow, graph.mincut 1334- vertex and edge connectivity: edge.connectivity, vertex.connectivity 1335- edge and vertex disjoint paths: edge.disjoint.paths, 1336 vertex.disjoint.paths 1337- White's cohesion and adhesion measure: graph.adhesion, graph.cohesion 1338- dimacs file format added 1339- as.directed handles attributes now 1340- constraint corrected, it handles weighted graphs as well now 1341- weighted attribute to graph.adjacency 1342- spinglass-based community structure detection, the Joerg Reichardt -- 1343 Stefan Bornholdt algorithm added: spinglass.community 1344- graph.extended.chordal.ring, extended chordal ring generation 1345- no.clusters calculates the number of clusters without calculating 1346 the clusters themselves 1347- minimum spanning tree functions updated to keep attributes 1348- transitivity can calculate local transitivity as well 1349- neighborhood related functions added: neighborhood, 1350 neighborhood.size, graph.neighborhood 1351- new graph generators based on vertex types: preference.game and 1352 asymmetric.preference.game 1353 1354Bugs corrected 1355-------------- 1356 1357- attribute handling bug when deleting edges corrected 1358- GraphML escaping and NaN handling corrected 1359- bug corrected to make it possible compile the R package without the 1360 libxml2 library 1361- a bug in Erdos-Renyi graph generation corrected: it had problems 1362 with generating large directed graphs 1363- bug in constraint calculation corrected, it works well now 1364- fixed memory leaks in igraph_read_graph_graphml 1365- error handling bug corrected in igraph_read_graph_graphml 1366- bug corrected in R version of graph.laplacian when normalized 1367 Laplacian is requested 1368- memory leak corrected in get.all.shortest.paths in the R package 1369 1370igraph 0.2.1 1371========= 1372 1373Released Aug 23, 2006 1374 1375This is a bug-fix release. Bugs fixed: 1376- igraph_reciprocity (reciprocity in R) corrected to avoid segfaults 1377- some docs updates 1378- various R package updated to make it conform to the CRAN rules 1379 1380igraph 0.2 1381========= 1382 1383Released Aug 18, 2006 1384 1385Release time at last! There are many new things in igraph 0.2, the 1386most important ones: 1387- reading writing Pajek and GraphML formats with attributes 1388 (not all Pajek and GraphML files are supported, see documentation 1389 for details) 1390- iterators totally rewritten, it is much faster and cleaner now 1391- the RANDEDU fast motif search algorithm is implemented 1392- many new graph generators, both games and regular graphs 1393- many new structural properties: transitivity, reciprocity, etc. 1394- graph operators: union, intersection, difference, structural holes, etc. 1395- conversion between directed and undirected graphs 1396- new layout algorithms for trees and large graphs, 3D layouts 1397 1398and many more. 1399 1400New things in the R package: 1401- support for CTRL+C 1402- new functions: Graph Laplacian, Burt's constraint, etc. 1403- vertex/edge sequences totally rewritten, smart indexing (see manual) 1404- new R manual and tutorial: 'Network Analysis with igraph', still 1405 under development but useful 1406- very basic 3D plotting using OpenGL 1407 1408Although this release was somewhat tested on Linux, MS Windows, Mac 1409OSX, Solaris 8 and FreeBSD, no heavy testing was done, so it might 1410contain bugs, and we kindly ask you to send bug reports to make igraph 1411better. 1412 1413igraph mailing lists 1414==================== 1415 1416Aug 18, 2006 1417 1418I've set up two igraph mailing lists: igraph-help for 1419general igraph questions and discussion and 1420igraph-anonunce for announcements. See 1421http://lists.nongnu.org/mailman/listinfo/igraph-help and 1422http://lists.nongnu.org/mailman/listinfo/igraph-announce 1423for subscription information, archives, etc. 1424 1425igraph 0.1 1426========= 1427 1428Released Jan 30, 2006 1429 1430After about a year of development this is the first "official" release 1431of the igraph library. This release should be considered as beta 1432software, but it should be useful in general. Please send your 1433questions and comments. 1434