forked from igraph/igraph
-
Notifications
You must be signed in to change notification settings - Fork 1
/
ONEWS
1433 lines (1274 loc) · 61.3 KB
/
ONEWS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
igraph 0.6.5
============
Released February 24, 2013
The version number is not a mistake, we jump to 0.6.5 from 0.6,
for technical reasons.
R: new features and bug fixes
-----------------------------
- Added a vertex shape API for defining new vertex shapes, and also
a couple of new vertex shapes.
- Added the get.data.frame() function, opposite of graph.data.frame().
- Added bipartite support to the Pajek reader and writer, closes bug
\#1042298.
- `degree.sequence.game()` has a new method now: "simple_no_multiple".
- Added the is.degree.sequence() and is.graphical.degree.sequence()
functions.
- rewire() has a new method: "loops", that can create loop edges.
- Walktrap community detection now handles isolates.
- layout.mds() returns a layout matrix now.
- layout.mds() uses LAPACK instead of ARPACK.
- Handle the '~' character in write.graph and read.graph. Bug
\#1066986.
- Added k.regular.game().
- Use vertex names to plot if no labels are specified in the function
call or as vetex attributes. Fixes issue \#1085431.
- power.law.fit() can now use a C implementation.
- Fixed a bug in barabasi.game() when out.seq was an empty vector.
- Fixed a bug that made functions with a progress bar fail if called
from another package.
- Fixed a bug when creating graphs from a weighted integer adjacency
matrix via graph.adjacency(). Bug \#1019624.
- Fixed overflow issues in centralization calculations.
- Fixed a minimal.st.separators() bug, some vertex sets were incorrectly
reported as separators. Bug \#1033045.
- Fixed a bug that mishandled vertex colors in VF2 isomorphism
functions. Bug \#1032819.
- Pajek exporter now always quotes strings, thanks to Elena Tea Russo.
- Fixed a bug with handling small edge weights in shortest paths
calculation in shortest.paths() (Dijkstra's algorithm.) Thanks to
Martin J Reed.
- Weighted transitivity uses V(graph) as 'vids' if it is NULL.
- Fixed a bug when 'pie' vertices were drawn together with other
vertex shapes.
- Speed up printing graphs.
- Speed up attribute queries and other basic operations, by avoiding
copying of the graph. Bug \#1043616.
- Fixed a bug in the NCV setting for ARPACK functions. It cannot be
bigger than the matrix size.
- layout.merge()'s DLA mode has better defaults now.
- Fixed a bug in layout.mds() that resulted vertices on top of each
other.
- Fixed a bug in layout.spring(), it was not working properly.
- Fixed layout.svd(), which was completely defunct.
- Fixed a bug in layout.graphopt() that caused warnings and on
some platforms crashes.
- Fixed community.to.membership(). Bug \#1022850.
- Fixed a graph.incidence() crash if it was called with a non-matrix
argument.
- Fixed a get.shortest.paths bug, when output was set to "both".
- Motif finding functions return NA for isomorphism classes that are
not motifs (i.e. not connected). Fixes bug \#1050859.
- Fixed get.adjacency() when attr is given, and the attribute has some
complex type. Bug \#1025799.
- Fixed attribute name in graph.adjacency() for dense matrices. Bug
\#1066952.
- Fixed erratic behavior of alpha.centrality().
- Fixed igraph indexing, when attr is given. Bug \#1073705.
- Fixed a bug when calculating the largest cliques of a directed
graph. Bug \#1073800.
- Fixed a bug in the maximal clique search, closes \#1074402.
- Warn for negative weights when calculating PageRank.
- Fixed dense, unweighted graph.adjacency when diag=FALSE. Closes
issue \#1077425.
- Fixed a bug in eccentricity() and radius(), the results were often
simply wrong.
- Fixed a bug in get.all.shortest.paths() when some edges had zero weight.
- graph.data.frame() is more careful when vertex names are numbers, to
avoid their scientific notation. Fixes issue \#1082221.
- Better check for NAs in vertex names. Fixes issue \#1087215
- Fixed some potential crashes in the DrL layout generator.
- Fixed a bug in the Reingold-Tilford layout when the graph is
directed and mode != ALL.
- Eliminate gap between vertex and edge when plotting an edge without an arrow.
Fixes \#1118448.
- Fixed a bug in has.multiple() that resulted in false negatives for
some undirected graphs.
- Fixed a crash in weighted betweenness calculation.
- R plotting: fixed a bug that caused misplaced arrows at rectangle
vertex shapes.
Python news and fixes
---------------------
- Added bipartite support to the Pajek reader and writer, closes bug
\#1042298.
- Graph.Degree_Sequence() has a new method now: "no_multiple".
- Added the is_degree_sequence() and is_graphical_degree_sequence()
functions.
- rewire() has a new mode: "loops", that can create loop edges.
- Walktrap community detection now handles isolates.
- Added Graph.K_Regular().
- power_law_fit() now uses a C implementation.
- Added support for setting the frame (stroke) width of vertices using the
frame_width attribute or the vertex_frame_width keyword argument in plot()
- Improved Inkscape-friendly SVG output from Graph.write_svg(), thanks to drlog
- Better handling of named vertices in Graph.delete_vertices()
- Added experimental Gephi graph streaming support; see igraph.remote.gephi and
igraph.drawing.graph.GephiGraphStreamingDrawer
- Nicer __repr__ output for Flow and Cut instances
- Arrows are now placed correctly around diamond-shaped nodes on plots
- Added Graph.TupleList, a function that allows one to create graphs with
edge attributes quickly from a list of tuples.
- plot() now also supports .eps as an extension, not only .ps
- Fixed overflow issues in centralization calculations.
- Fixed a bug that mishandled vertex colors in VF2 isomorphism
functions. Bug \#1032819.
- Pajek exporter now always quotes strings, thanks to Elena Tea Russo.
- Fixed a bug with handling small edge weights in shortest paths
calculation in Graph.shortest_paths() (Dijkstra's algorithm.) Thanks to
Martin J Reed.
- Fixed a bug in the NCV setting for ARPACK functions. It cannot be
bigger than the matrix size.
- Fixed a bug in Graph.layout_mds() that resulted vertices on top of each
other.
- Motif finding functions return nan for isomorphism classes that are
not motifs (i.e. not connected). Fixes bug \#1050859.
- Fixed a bug when calculating the largest cliques of a directed
graph. Bug \#1073800.
- Warn for negative weights when calculating PageRank.
- Fixed a bug in Graph.eccentricity() and Graph.radius(), the results were often
simply wrong.
- Fixed a bug in Graph.get.all.shortest.paths() when some edges had zero weight.
- Fixed some potential crashes in the DrL layout generator.
- Fixed a bug in the Reingold-Tilford layout when the graph is
directed and mode != ALL.
- Fixed a bug in Graph.layout_sugiyama() when the graph had no edges.
- Fixed a bug in Graph.community_label_propagation() when initial labels
contained -1 entries. Issue \#1105460.
- Repaired the DescartesCoordinateSystem class (which is not used too frequently
anyway)
- Fixed a bug that caused segfaults when an igraph Graph was used in a thread
forked from the main Python interpreter thread
- Fixed a bug that affected file handles created from Python strings in the
C layer
- Fixed a bug in has_multiple() that resulted in false negatives
for some undirected graphs.
- Fixed a crash in weighted betweenness calculation.
C library news and changes
--------------------------
- Added bipartite support to the Pajek reader and writer, closes bug
\#1042298.
- igraph_layout_mds() uses LAPACK instead of ARPACK.
- igraph_degree_sequence_game has a new method:
IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE.
- Added the igraph_is_degree_sequence() and
igraph_is_graphical_degree_sequence() functions.
- igraph_rewire() has a new method: IGRAPH_REWIRING_SIMPLE_LOOPS,
that can create loops.
- Walktrap community detection now handles isolates.
- Added igraph_k_regular_game().
- Added igraph_power_law_fit.
- Fixed a bug in igraph_barabasi_game when outseq was an empty vector.
- Fixed overflow issues in centralization calculations.
- Fixed an invalid return value of igraph_vector_ptr_pop_back.
- Fixed a igraph_all_minimal_st_separators() bug, some vertex sets
were incorrectly reported as separators. Bug \#1033045.
- Pajek exporter now always quotes strings, thanks to Elena Tea Russo.
- Fixed a bug with handling small edge weights in
igraph_shortest_paths_dijkstra(), thanks to Martin J Reed.
- Fixed a bug in the NCV setting for ARPACK functions. It cannot be
bigger than the matrix size.
- igraph_layout_merge_dla uses better default parameter values now.
- Fixed a bug in igraph_layout_mds() that resulted vertices on top of
each other.
- Attribute handler table is not thread-local any more.
- Motif finding functions return IGRAPH_NAN for isomorphism classes
that are not motifs (i.e. not connected). Fixes bug \#1050859.
- Fixed a bug when calculating the largest cliques of a directed
graph. Bug \#1073800.
- Fix a bug in degree_sequence_game(), in_seq can be an empty vector as
well instead of NULL, for an undirected graph.
- Fixed a bug in the maximal clique search, closes \#1074402.
- Warn for negative weights when calculating PageRank.
- Fixed a bug in igraph_eccentricity() (and also igraph_radius()),
the results were often simply wrong.
- Fixed a bug in igraph_get_all_shortest_paths_dijkstra() when edges
had zero weight.
- Fixed some potential crashes in the DrL layout generator.
- Fixed a bug in the Reingold-Tilford layout when the graph is
directed and mode != ALL.
- Fixed a bug in igraph_has_multiple() that resulted in false negatives
for some undirected graphs.
- Fixed a crash in weighted betweenness calculation.
igraph 0.6
==========
Released June 11, 2012
See also the release notes at
http://igraph.sf.net/relnotes-0.6.html
R: Major new features
---------------------
- Vertices and edges are numbered from 1 instead of 0.
Note that this makes most of the old R igraph code incompatible
with igraph 0.6. If you want to use your old code, please use
the igraph0 package. See more at http://igraph.sf.net/relnotes-0.6.html.
- The '\[' and '\[\[' operators can now be used on igraph graphs,
for '\[' the graph behaves as an adjacency matrix, for '[[' is
is treated as an adjacency list. It is also much simpler to
manipulate the graph structure, i.e. add/remove edges and vertices,
with some new operators. See more at ?graph.structure.
- In all functions that take a vector or list of vertices or edges,
vertex/edge names can be given instead of the numeric ids.
- New package 'igraphdata', contains a number of data sets that can
be used directly in igraph.
- Igraph now supports loading graphs from the Nexus online data
repository, see nexus.get(), nexus.info(), nexus.list() and
nexus.search().
- All the community structure finding algorithm return a 'communities'
object now, which has a bunch of useful operations, see
?communities for details.
- Vertex and edge attributes are handled much better now. They
are kept whenever possible, and can be combined via a flexible API.
See ?attribute.combination.
- R now prints igraph graphs to the screen in a more structured and
informative way. The output of summary() was also updated
accordingly.
R: Other new features
---------------------
- It is possible to mark vertex groups on plots, via
shading. Communities and cohesive blocks are plotted using this by
default.
- Some igraph demos are now available, see a list via
'demo(package="igraph")'.
- igraph now tries to select the optimal layout algorithm, when
plotting a graph.
- Added a simple console, using Tcl/Tk. It contains a text area
for status messages and also a status bar. See igraph.console().
- Reimplemented igraph options support, see igraph.options() and
getIgraphOpt().
- Igraph functions can now print status messages.
R: New or updated functions
---------------------------
Community detection
-------------------
- The multi-level modularity optimization community structure detection
algorithm by Blondel et al. was added, see multilevel.community().
- Distance between two community structures: compare.communities().
- Community structure via exact modularity optimization,
optimal.community().
- Hierarchical random graphs and community finding, porting the code
from Aaron Clauset. See hrg.game(), hrg.fit(), etc.
- Added the InfoMAP community finding method, thanks to Emmanuel
Navarro for the code. See infomap.community().
Shortest paths
--------------
- Eccentricity (eccentricity()), and radius (radius()) calculations.
- Shortest path calculations with get.shortest.paths() can now
return the edges along the shortest paths.
- get.all.shortest.paths() now supports edge weights.
Centrality
----------
- Centralization scores for degree, closeness, betweenness and
eigenvector centrality. See centralization.scores().
- Personalized Page-Rank scores, see page.rank().
- Subgraph centrality, subgraph.centrality().
- Authority (authority.score()) and hub (hub.score()) scores support
edge weights now.
- Support edge weights in betweenness and closeness calculations.
- bonpow(), Bonacich's power centrality and alpha.centrality(),
Alpha centrality calculations now use sparse matrices by default.
- Eigenvector centrality calculation, evcent() now works for
directed graphs.
- Betweenness calculation can now use arbitrarily large integers,
this is required for some lattice-like graphs to avoid overflow.
Input/output and file formats
-----------------------------
- Support the DL file format in graph.read(). See
http://www.analytictech.com/networks/dataentry.htm.
- Support writing the LEDA file format in write.graph().
Plotting and layouts
--------------------
- Star layout: layout.star().
- Layout based on multidimensional scaling, layout.mds().
- New layouts layout.grid() and layout.grid.3d().
- Sugiyama layout algorithm for layered directed acyclic graphs,
layout.sugiyama().
Graph generators
----------------
- New graph generators: static.fitness.game(), static.power.law.game().
- barabasi.game() was rewritten and it supports three algorithms now,
the default algorithm does not generate multiple or loop edges.
The graph generation process can now start from a supplied graph.
- The Watts-Strogatz graph generator, igraph_watts_strogatz() can
now create graphs without loop edges.
Others
------
- Added the Spectral Coarse Graining algorithm, see scg().
- The cohesive.blocks() function was rewritten in C, it is much faster
now. It has a nicer API, too. See demo("cohesive").
- Added generic breadth-first and depth-first search implementations
with many callbacks, graph.bfs() and graph_dfs().
- Support vertex and edge coloring in the VF2 (sub)graph isomorphism
functions (graph.isomorphic.vf2(), graph.count.isomorphisms.vf2(),
graph.get.isomorphisms.vf2(), graph.subisomorphic.vf2(),
graph.count.subisomorphisms.vf2(), graph.get.subisomorphisms.vf2()).
- Assortativity coefficient, assortativity(), assortativity.nominal()
and assortativity.degree().
- Vertex operators that work by vertex names:
graph.intersection.by.name(), graph.union.by.name(),
graph.difference.by.name(). Thanks to Magnus Torfason for
contributing his code!
- Function to calculate a non-induced subraph: subgraph.edges().
- More comprehensive maximum flow and minimum cut calculation,
see functions graph.maxflow(), graph.mincut(), stCuts(), stMincuts().
- Check whether a directed graph is a DAG, is.dag().
- has.multiple() to decide whether a graph has multiple edges.
- Added a function to calculate a diversity score for the vertices,
graph.diversity().
- Graph Laplacian calculation (graph.laplacian()) supports edge
weights now.
- Biconnected component calculation, biconnected.components()
now returns the components themselves.
- bipartite.projection() calculates multiplicity of edges.
- Maximum cardinality search: maximum.cardinality.search() and
chordality test: is.chordal()
- Convex hull computation, convex.hull().
- Contract vertices, contract.vertices().
New in the Python interface
---------------------------
TODO
Major changes in the Python interface
-------------------------------------
TODO
New in the C layer
------------------
- Maximum cardinality search: igraph_maximum_cardinality_search() and
chordality test: igraph_is_chordal().
- Support the DL file format, igraph_read_graph_dl(). See
http://www.analytictech.com/networks/dataentry.htm.
- Added generic breadth-first and depth-first search implementations
with many callbacks (igraph_bfs(), igraph_dfs()).
- Centralization scores for degree, closeness, betweenness and
eigenvector centrality, see igraph_centralization().
- Added igraph_sparsemat_t, a type that implements sparse
matrices based on the CXSparse library by Tim Davis.
See http://www.cise.ufl.edu/research/sparse/CXSparse/.
- Personalized Page-Rank scores, igraph_personalized_pagerank() and
igraph_personalized_pagerank_vs().
- Assortativity coefficient, igraph_assortativity(),
igraph_assortativity_nominal(), and igraph_assortativity_degree().
- The multi-level modularity optimization community structure detection
algorithm by Blondel et al. was added, see igraph_community_multilevel().
- Added the igraph_version() function.
- Star layout: igraph_layout_star().
- Function to calculate a non-induced subraph: igraph_subgraph_edges().
- Distance between two community structures: igraph_compare_communities().
- Community structure via exact modularity optimization,
igraph_community_optimal_community().
- More comprehensive maximum flow and minimum cut calculation,
see functions igraph_maxflow(), igraph_mincut(),
igraph_all_st_cuts(), igraph_all_st_mincuts().
- Layout based on multidimensional scaling, igraph_layout_mds().
- It is now possible to access the random number generator(s) via an
API. Multiple RNGs can be used, from external sources as well.
The default RNG is MT19937.
- Added igraph_get_all_shortest_paths_dijkstra, for calculating all
non-negatively weighted shortest paths.
- Check whether a directed graph is a DAG, igraph_is_dag().
- Cohesive blocking, a'la Moody & White, igraph_cohesive_blocks().
- Igraph functions can now print status messages, see igraph_status()
and related functions.
- Support writing the LEDA file format, igraph_write_graph_leda().
- Contract vertices, igraph_contract_vertices().
- The C reference manual has now a lot of example programs.
- Hierarchical random graphs and community finding, porting the code
from Aaron Clauset. See igraph_hrg_game(), igraph_hrg_fit(), etc.
- igraph_has_multiple() to decide whether a graph has multiple edges.
- New layouts igraph_layout_grid() and igraph_layout_grid_3d().
- igraph_integer_t is really an integer now, it used to be a double.
- igraph_minimum_spanning_tree(), calls either the weighted or
the unweighted implementation.
- Eccentricity (igraph_eccentricity()), and radius (igraph_radius())
calculations.
- Several game theory update rules, written by Minh Van Nguyen. See
igraph_deterministic_optimal_imitation(),
igraph_stochastic_imitation(), igraph_roulette_wheel_imitation(),
igraph_moran_process(),
- Sugiyama layout algorithm for layered directed acyclic graphs,
igraph_layout_sugiyama().
- New graph generators: igraph_static_fitness_game(),
igraph_static_power_law_game().
- Added the InfoMAP community finding method, thanks to Emmanuel
Navarro for the code. See igraph_community_infomap().
- Added the Spectral Coarse Graining algorithm, see igraph_scg().
- Added a function to calculate a diversity score for the vertices,
igraph_diversity().
Major changes in the C layer
----------------------------
- Authority (igraph_authority_score()) and hub (igraph_hub_score()) scores
support edge weights now.
- Graph Laplacian calculation (igraph_laplacian()) supports edge
weights now.
- Support edge weights in betweenness (igraph_betweenness()) and closeness
(igraph_closeness()) calculations.
- Support vertex and edge coloring in the VF2 graph isomorphism
algorithm (igraph_isomorphic_vf2(), igraph_count_isomorphisms_vf2(),
igraph_get_isomorphisms_vf2(), igraph_subisomorphic_vf2(),
igraph_count_subisomorphisms_vf2(), igraph_get_subisomorphisms_vf2()).
- Added print operations for the igraph_vector*_t, igraph_matrix*_t and
igraph_strvector_t types.
- Biconnected component calculation (igraph_biconnected_components())
can now return the components themselves.
- Eigenvector centrality calculation, igraph_eigenvector_centrality()
now works for directed graphs.
- Shortest path calculations with get_shortest_paths() and
get_shortest_paths_dijkstra() can now return the edges along the paths.
- Betweenness calculation can now use arbitrarily large integers,
this is required for some lattice-like graphs to avoid overflow.
- igraph_bipartite_projection() calculates multiplicity of edges.
- igraph_barabasi_game() was rewritten and it supports three
algorithms now, the default algorithm does not generate multiple or
loop edges.
- The Watts-Strogatz graph generator, igraph_watts_strogatz() can
now create graphs without loop edges.
- igraph should be now thread-safe, on architectures that support
thread-local storage (Linux and Windows: yes, Mac OSX: no).
We also fixed numerous bugs, too many to include them here, sorry.
You may look at our bug tracker at https://bugs.launchpad.net/igraph
to check whether a bug was fixed or not. Thanks for all the people
reporting bugs. Special thanks to Minh Van Nguyen for a lot of bug
reports, documentation fixes and contributed code!
igraph 0.5.3
============
Released November 22, 2009
Bugs corrected in the R interface
---------------------------------
- Some small changes to make 'R CMD check' clean
- Fixed a bug in graph.incidence, the 'directed' and 'mode' arguments
were not handled correctly
- Betweenness and edge betweenness functions work for graphs with
many shortest paths now (up to the limit of long long int)
- When compiling the package, the configure script fails if there is
no C compiler available
- igraph.from.graphNEL creates the right number of loop edges now
- Fixed a bug in bipartite.projection() that caused occasional crashes
on some systems
New in the Python interface
---------------------------
- Added support for weighted diameter
- get_eid() considers edge directions by default from now on
- Fixed a memory leak in the attribute handler
- 'NaN' and 'inf' are treated correctly now
Bugs corrected in the C layer
-----------------------------
- Betweenness and edge betweenness functions work for graphs with
many shortest paths now (up to the limit of long long int)
- The configure script fails if there is no C compiler available
- Fixed a bug in igraph_community_spinglass, when csize was a NULL
pointer, but membership was not
- Fixed a bug in igraph_bipartite_projection that caused occasional
crashes on some systems
igraph 0.5.2
============
Released April 10, 2009
See also the release notes at
http://igraph.sf.net/relnotes-0.5.2.html
New in the R interface
----------------------
- Added progress bar support to beweenness() and
betweenness.estimate(), layout.drl()
- Speeded up betweenness estimation
- Speeded up are.connected()
- Johnson's shortest paths algorithm added
- shortest.paths() has now an 'algorithm' argument to choose from the
various implementations manually
- Always quote symbolic vertex names when printing graphs or edges
- Average nearest neighbor degree calculation, graph.knn()
- Weighted degree (also called strength) calculation, graph.strength()
- Some new functions to support bipartite graphs: graph.bipartite(),
is.bipartite(), get.indicence(), graph.incidence(),
bipartite.projection(), bipartite.projection.size()
- Support for plotting curved edges with plot.igraph() and tkplot()
- Added support for weighted graphs in alpha.centrality()
- Added the label propagation community detection algorithm by
Raghavan et al., label.propagation.community()
- cohesive.blocks() now has a 'cutsetHeuristic' argument to choose
between two cutset algorithms
- Added a function to "unfold" a tree, unfold.tree()
- New tkplot() arguments to change the drawing area
- Added a minimal GUI, invoke it with tkigraph()
- The DrL layout generator, layout.drl() has a three dimensional mode
now.
Bugs corrected in the R interface
---------------------------------
- Fixed a bug in VF2 graph isomorphism functions
- Fixed a bug when a sparse adjacency matrix was requested in
get.adjacency() and the graph was named
- VL graph generator in degree.sequence.game() checks now that
the sum of the degrees is even
- Many fixes for supporting various compilers, e.g. GCC 4.4 and Sun's
C compiler
- Fixed memory leaks in graph.automorphisms(), Bellman-Ford
shortest.paths(), independent.vertex.sets()
- Fix a bug when a graph was imported from LGL and exported to NCOL
format (\#289596)
- cohesive.blocks() creates its temporary file in the session
temporary directory
- write.graph() and read.graph() now give error messages when unknown
arguments are given
- The GraphML reader checks the name of the attributes to avoid adding
a duplicate 'id' attribute
- It is possible to change the 'ncv' ARPACK parameter for
leading.eigenvector.community()
- Fixed a bug in path.length.hist(), 'unconnected' was wrong
for unconnected and undirected graphs
- Better handling of attribute assingment via iterators, this is now
also clarified in the manual
- Better error messages for unknown vertex shapes
- Make R package unload cleanly if unloadNamespace() is used
- Fixed a bug in plotting square shaped vertices (\#325244)
- Fixed a bug in graph.adjacency() when the matrix is a sparse matrix
of class "dgTMatrix"
New in the Python interface
---------------------------
- Speeded up betweenness estimation
- Johnson's shortest paths algorithm added (selected automatically
by Graph.shortest_paths() if needed)
- Weighted degree (also called strength) calculation, Graph.strength()
- Some new methods to support bipartite graphs: Graph.Bipartite(),
Graph.is_bipartite(), Graph.get_indicence(), Graph.Incidence(),
Graph.bipartite_projection(), Graph.bipartite_projection_size()
- Added the label propagation community detection algorithm by
Raghavan et al., Graph.community_label_propagation()
- Added a function to "unfold" a tree, Graph.unfold_tree()
- setup.py script improvements
- Graph plotting now supports edge_arrow_size and edge_arrow_width
- Added Graph.Formula to create small graphs from a simple notation
- VertexSeq and EdgeSeq objects can now be indexed by slices
New in the C layer
------------------
- Added progress bar support to igraph_betweenness() and
igraph_betweenness_estimate(), igraph_layout_drl()
- Speeded up igraph_betweenness_estimate(), igraph_get_eid(),
igraph_are_connected(), igraph_get_eids()
- Added igraph_get_eid2()
- Johnson's shortest path algorithm added:
igraph_shortest_paths_johnson()
- Average nearest neighbor degree calculation,
igraph_avg_nearest_neighbor_degree()
- Weighted degree (also called strength) calculation,
igraph_strength()
- Some functions to support bipartite graphs: igraph_full_bipartite(),
igraph_bipartite_projection(), igraph_create_bipartite(),
igraph_incidence(), igraph_get_incidence(),
igraph_bipartite_projection_size(), igraph_is_bipartite()
- Added the label propagation community detection algorithm by
Raghavan et al., igraph_community_label_propagation()
- Added an example that shows how to set the random number generator's
seed from C (examples/simple/random_seed.c)
- Added a function to "unfold" a tree, igraph_unfold_tree()
- C attribute handler updates: added functions to query many
vertices/edges at once
- Three dimensional DrL layout, igraph_layout_drl_3d()
Bugs corrected in the C layer
-----------------------------
- Fixed a bug in igraph_isomorphic_function_vf2(), affecting all VF2
graph isomorphism functions
- VL graph generator in igraph_degree_sequence_game() checks now that
the sum of the degrees is even
- Many small corrections to make igraph compile with Microsoft Visual
Studio 2003, 2005 and 2008
- Many fixes for supporting various compilers, e.g. GCC 4.4 and Sun's
C compiler
- Fix a bug when a graph was imported from LGL and exported to NCOL
format (\#289596)
- Fixed memory leaks in igraph_automorphisms(),
igraph_shortest_paths_bellman_ford(),
igraph_independent_vertex_sets()
- The GraphML reader checks the name of the attributes to avoid adding
a duplicate 'id' attribute
- It is possible to change the 'ncv' ARPACK parameter for
igraph_community_leading_eigenvector()
- Fixed a bug in igraph_path_length_hist(), 'unconnected' was wrong
for unconnected and undirected graphs.
igraph 0.5.1
============
Released July 14, 2008
See also the release notes at
http://igraph.sf.net/relnotes-0.5.1.html
New in the R interface
----------------------
- A new layout generator called DrL.
- Uniform sampling of random connected undirected graphs with a
given degree sequence.
- Edge labels are plotted at 1/3 of the edge, this is better if
the graph has mutual edges.
- Initial and experimental vertex shape support in 'plot'.
- New function, 'graph.adjlist' creates igraph graphs from
adjacency lists.
- Conversion to/from graphNEL graphs, from the 'graph' R package.
- Fastgreedy community detection can utilize edge weights now, this
was missing from the R interface.
- The 'arrow.width' graphical parameter was added.
- graph.data.frame has a new argument 'vertices'.
- graph.adjacency and get.adjacency support sparse matrices,
the 'Matrix' package is required to use this functionality.
- graph.adjacency adds column/row names as 'name' attribute.
- Weighted shortest paths using Dijkstra's or the Belmann-Ford
algorithm.
- Shortest path functions return 'Inf' for unreachable vertices.
- New function 'is.mutual' to find mutual edges in a directed graph.
- Added inverse log-weighted similarity measure (a.k.a. Adamic/Adar
similarity).
- preference.game and asymmetric.preference.game were
rewritten, they are O(|V|+|E|) now, instead of O(|V|^2).
- Edge weight support in function 'get.shortest.paths', it uses
Dijkstra's algorithm.
Bugs corrected in the R interface
---------------------------------
- A bug was corrected in write.pajek.bgraph.
- Several bugs were corrected in graph.adjacency.
- Pajek reader bug corrected, used to segfault if '\*Vertices'
was missing.
- Directedness is handled correctly when writing GML files.
(But note that 'correct' conflicts the standard here.)
- Corrected a bug when calculating weighted, directed PageRank on an
undirected graph. (Which does not make sense anyway.)
- Several bugs were fixed in the Reingold-Tilford layout to avoid
edge crossings.
- A bug was fixed in the GraphML reader, when the value of a graph
attribute was not specified.
- Fixed a bug in the graph isomorphism routine for small (3-4 vertices)
graphs.
- Corrected the random sampling implementation (igraph_random_sample),
now it always generates unique numbers. This affects the
Gnm Erdos-Renyi generator, it always generates simple graphs now.
- The basic igraph constructor (igraph_empty_attrs, all functions
are expected to call this internally) now checks whether the number
of vertices is finite.
- The LGL, NCOL and Pajek graph readers handle errors properly now.
- The non-symmetric ARPACK solver returns results in a consistent form
now.
- The fast greedy community detection routine now checks that the graph
is simple.
- The LGL and NCOL parsers were corrected to work with all
kinds of end-of-line encodings.
- Hub & authority score calculations initialize ARPACK parameters now.
- Fixed a bug in the Walktrap community detection routine, when applied
to unconnected graphs.
- Several small memory leaks were removed, and a big one from the Spinglass
community structure detection function
New in the Python interface
---------------------------
- A new layout generator called DrL.
- Uniform sampling of random connected undirected graphs with a
given degree sequence.
- Methods parameters accepting igraph.IN, igraph.OUT and igraph.ALL
constants now also accept these as strings ("in", "out" and "all").
Prefix matches also allowed as long as the prefix match is unique.
- Graph.shortest_paths() now supports edge weights (Dijkstra's and
Bellman-Ford algorithm implemented)
- Graph.get_shortest_paths() also supports edge weights
(only Dijkstra's algorithm yet)
- Added Graph.is_mutual() to find mutual edges in a directed graph.
- Added inverse log-weighted similarity measure (a.k.a. Adamic/Adar
similarity).
- preference.game and asymmetric.preference.game were
rewritten, they are O(|V|+|E|) now, instead of O(|V|^2).
- ARPACK options can now be modified from the Python interface
(thanks to Kurt Jacobson)
- Layout.to_radial() added -- now you can create a top-down tree
layout by the Reingold-Tilford algorithm and then turn it to a
radial tree layout
- Added Graph.write_pajek() to save graphs in Pajek format
- Some vertex and edge related methods can now also be accessed via
the methods of VertexSeq and EdgeSeq, restricted to the current
vertex/edge sequence of course
- Visualisations now support triangle shaped vertices
- Added Graph.mincut()
- Added Graph.Weighted_Adjacency() to create graphs from weighted
adjacency matrices
- Kamada-Kawai and Fruchterman-Reingold layouts now accept initial
vertex positions
- Graph.Preference() and Graph.Asymmetric_Preference() were
rewritten, they are O(|V|+|E|) now, instead of O(|V|^2).
Bugs corrected in the Python interface
--------------------------------------
- Graph.constraint() now properly returns floats instead of integers
(thanks to Eytan Bakshy)
- Graphs given by adjacency matrices are now finally loaded and saved
properly
- Graph.Preference() now accepts floats in type distributions
- A small bug in Graph.community_edge_betweenness() corrected
- Some bugs in numeric attribute handling resolved
- VertexSeq and EdgeSeq objects can now be subsetted by lists and
tuples as well
- Fixed a bug when dealing with extremely small layout sizes
- Eigenvector centality now always return positive values
- Graph.authority_score() now really returns the authority scores
instead of the hub scores (blame copypasting)
- Pajek reader bug corrected, used to segfault if '\*Vertices'
was missing.
- Directedness is handled correctly when writing GML files.
(But note that 'correct' conflicts the standard here.)
- Corrected a bug when calculating weighted, directed PageRank on an
undirected graph. (Which does not make sense anyway.)
- Several bugs were fixed in the Reingold-Tilford layout to avoid
edge crossings.
- A bug was fixed in the GraphML reader, when the value of a graph
attribute was not specified.
- Fixed a bug in the graph isomorphism routine for small (3-4 vertices)
graphs.
- Corrected the random sampling implementation (igraph_random_sample),
now it always generates unique numbers. This affects the
Gnm Erdos-Renyi generator, it always generates simple graphs now.
- The LGL, NCOL and Pajek graph readers handle errors properly now.
- The non-symmetric ARPACK solver returns results in a consistent form
now.
- The fast greedy community detection routine now checks that the graph
is simple.
- The LGL and NCOL parsers were corrected to work with all
kinds of end-of-line encodings.
- Hub & authority score calculations initialize ARPACK parameters now.
- Fixed a bug in the Walktrap community detection routine, when applied
to unconnected graphs.
- Several small memory leaks were removed, and a big one from the Spinglass
community structure detection function
New in the C layer
------------------
- A new layout generator called DrL.
- Uniform sampling of random connected undirected graphs with a
given degree sequence.
- Some stochastic test results are ignored (for spinglass community
detection, some Erdos-Renyi generator tests)
- Weighted shortest paths, Dijkstra's algorithm.
- The unweighted shortest path routine returns 'Inf' for unreachable
vertices.
- New function, igraph_adjlist can create igraph graphs from
adjacency lists.
- New function, igraph_weighted_adjacency can create weighted graphs
from weight matrices.
- New function, igraph_is_mutual to search for mutual edges.
- Added inverse log-weighted similarity measure (a.k.a. Adamic/Adar
similarity).
- igraph_preference_game and igraph_asymmetric_preference_game were
rewritten, they are O(|V|+|E|) now, instead of O(|V|^2).
- The Bellman-Ford shortest path algorithm was added.
- Added weighted variant of igraph_get_shortest_paths, based on
Dijkstra's algorithm.
- Several small memory leaks were removed, and a big one from the Spinglass
community structure detection function
Bugs corrected in the C layer
-----------------------------
- Several bugs were corrected in the (still experimental) C attribute
handler.
- Pajek reader bug corrected, used to segfault if '\*Vertices'
was missing.
- Directedness is handled correctly when writing GML files.
(But note that 'correct' conflicts the standard here.)
- Corrected a bug when calculating weighted, directed PageRank on an
undirected graph. (Which does not make sense anyway.)
- Some code polish to make igraph compile with GCC 4.3
- Several bugs were fixed in the Reingold-Tilford layout to avoid
edge crossings.
- A bug was fixed in the GraphML reader, when the value of a graph
attribute was not specified.
- Fixed a bug in the graph isomorphism routine for small (3-4 vertices)
graphs.
- Corrected the random sampling implementation (igraph_random_sample),
now it always generates unique numbers. This affects the
Gnm Erdos-Renyi generator, it always generates simple graphs now.
- The basic igraph constructor (igraph_empty_attrs, all functions
are expected to call this internally) now checks whether the number
of vertices is finite.
- The LGL, NCOL and Pajek graph readers handle errors properly now.
- The non-symmetric ARPACK solver returns results in a consistent form
now.
- The fast greedy community detection routine now checks that the graph
is simple.
- The LGL and NCOL parsers were corrected to work with all
kinds of end-of-line encodings.
- Hub & authority score calculations initialize ARPACK parameters now.x
- Fixed a bug in the Walktrap community detection routine, when applied
to unconnected graphs.
igraph 0.5
=========
Released February 14, 2008
See also the release notes at http://igraph.sf.net/relnotes-0.5.html
New in the R interface
----------------------
- The 'rescale', 'asp' and 'frame' graphical parameters were added
- Create graphs from a formula notation (graph.formula)
- Handle graph attributes properly
- Calculate the actual minimum cut for undirected graphs
- Adjacency lists, get.adjlist and get.adjedgelist added
- Eigenvector centrality computation is much faster now
- Proper R warnings, instead of writing the warning to the terminal
- R checks graphical parameters now, the unknown ones are not just
ignored, but an error message is given
- plot.igraph has an 'add' argument now to compose plots with multiple
graphs
- plot.igraph supports the 'main' and 'sub' arguments
- layout.norm is public now, it can normalize a layout
- It is possible to supply startup positions to layout generators
- Always free memory when CTRL+C/ESC is pressed, in all operating
systems
- plot.igraph can plot square vertices now, see the 'shape' parameter
- graph.adjacency rewritten when creating weighted graphs
- We use match.arg whenever possible. This means that character scalar
options can be abbreviated and they are always case insensitive
- VF2 graph isomorphism routines can check subgraph isomorphism now,
and they are able to return matching(s)
- The BLISS graph isomorphism algorithm is included in igraph now. See
canonical.permutation, graph.isomorphic.bliss
- We use ARPACK for eigenvalue/eigenvector calculation. This means that the
following functions were rewritten: page.rank,
leading.eigenvector.community.\*, evcent. New functions based on
ARPACK: hub.score, authority.score, arpack.
- Edge weights for Fruchterman-Reingold layout (layout.fruchterman.reingold).
- Line graph calculation (line.graph)
- Kautz and de Bruijn graph generators (graph.kautz, graph.de.bruijn)
- Support for writing graphs in DOT format
- Jaccard and Dice similarity coefficients added (similarity.jaccard,
similarity.dice)
- Counting the multiplicity of edges (count.multiple)
- The graphopt layout algorithm was added, layout.graphopt
- Generation of "famous" graphs (graph.famous).
- Create graphs from LCF notation (graph.cf).
- Dyad census and triad cencus functions (dyad.census, triad.census)
- Cheking for simple graphs (is.simple)
- Create full citation networks (graph.full.citation)
- Create a histogram of path lengths (path.length.hist)
- Forest fire model added (forest.fire.game)
- DIMACS reader can handle different file types now
- Biconnected components and articulation points (biconnected.components,
articulation.points)
- Kleinberg's hub and authority scores (hub.score, authority.score)
- as.undirected handles attributes now
- Geometric random graph generator (grg.game) can return the
coordinates of the vertices
- Function added to convert leading eigenvector community structure result to
a membership vector (community.le.to.membership)
- Weighted fast greedy community detection
- Weighted page rank calculation
- Functions for estimating closeness, betweenness, edge betweenness by
introducing a cutoff for path lengths (closeness.estimate,
betweenness.estimate, edge.betweenness.estimate)
- Weighted modularity calculation
- Function for permuting vertices (permute.vertices)
- Betweenness and closeness calculations are speeded up
- read.graph can handle all possible line terminators now (\r, \n, \r\n, \n\r)
- Error handling was rewritten for walktrap community detection,
the calculation can be interrupted now
- The maxflow/mincut functions allow to supply NULL pointer for edge
capacities, implying unit capacities for all edges
Bugs corrected in the R interface
---------------------------------
- Fixed a bug in cohesive.blocks, cohesive blocks were sometimes not
calculated correctly
New in the Python interface
---------------------------
- Added shell interface: igraph can now be invoked by calling the script called
igraph from the command line. The script launches the Python interpreter and
automatically imports igraph functions into the main namespace
- Pickling (serialization) support for Graph objects
- Plotting functionality based on the Cairo graphics library (so you need to
install python-cairo if you want to use it). Currently the following
objects can be plotted: graphs, adjacency matrices and dendrograms. Some
crude support for plotting histograms is also implemented. Plots can be
saved in PNG, SVG and PDF formats.
- Unified Graph.layout method for accessing layout algorithms
- Added interfaces to walktrap community detection and the BLISS isomorphism
algorithm
- Added dyad and triad census functionality and motif counting
- VertexSeq and EdgeSeq objects can now be restricted to subsets of the
whole network (e.g., you can select vertices/edges based on attributes,
degree, centrality and so on)
New in the C library
--------------------
- Many types (stack, matrix, dqueue, etc.) are templates now
They were also rewritten to provide a better organized interface
- VF2 graph isomorphism routines can check subgraph isomorphism now,
and they are able to return matching(s)
- The BLISS graph isomorphism algorithm is included in igraph now. See
igraph_canonical_permutation, igraph_isomorphic_bliss
- We use ARPACK for eigenvalue/eigenvector calculation. This means that the
following functions were rewritten: igraph_pagerank,
igraph_community_leading_eigenvector_\*. New functions based on
ARPACK: igraph_eigenvector_centrality, igraph_hub_score,
igraph_authority_score, igraph_arpack_rssolve, igraph_arpack_rnsolve
- Experimental C attribute interface added. I.e. it is possible to use
graph/vertex/edge attributes from C code now.
- Edge weights for Fruchterman-Reingold layout.
- Line graph calculation.
- Kautz and de Bruijn graph generators
- Support for writing graphs in DOT format
- Jaccard and Dice similarity coefficients added
- igraph_count_multiple added
- igraph_is_loop and igraph_is_multiple "return" boolean vectors
- The graphopt layout algorithm was added, igraph_layout_graphopt
- Generation of "famous" graphs, igraph_famous
- Create graphs from LCF notation, igraph_lcf, igraph_lcf_vector
- igraph_add_edge adds a single edge to the graph
- Dyad census and triad cencus functions added
- igraph_is_simple added
- progress handlers are allowed to stop calculation
- igraph_full_citation to create full citation networks
- igraph_path_length_hist, create a histogram of path lengths
- forest fire model added
- DIMACS reader can handle different file types now
- Adjacency list types made public now (igraph_adjlist_t, igraph_adjedgelist_t)
- Biconnected components and articulation points can be computed
- Eigenvector centrality computation
- Kleinberg's hub and authority scores
- igraph_to_undirected handles attributes now
- Geometric random graph generator can return the coordinates of the vertices
- Function added to convert leading eigenvector community structure result to
a membership vector (igraph_le_community_to_membership)
- Weighted fast greedy community detection
- Weighted page rank calculation
- Functions for estimating closeness, betweenness, edge betweenness by
introducing a cutoff for path lengths