function parity with igraph C core

[iosonofabio]

We should aim, as a continuous self-improvement kind of goal, to close the gap in function availability between the igraph C core and the Python interface. To help with that, let's try and keep track of what functions:

• are missing from the Python interface
• would be useful to have there
• are already implemented in the C core

Other igraph folks: please feel free to edit the list adding functions you find or deleting them if they got implemented or if you think they aren't necessary in the Python interface:

• [ ] maximal_cliques_count
• [ ] maximal_cliques_subset
• [ ] clique_size_hist and other histogram functions (useful for large graphs, where a list of all items would be too large)
• [ ] weighted cliques functions (?)
• [ ] vertex_coloring_greedy
• [ ] trussness
• [ ] eigen_laplacian
• [ ] laplacian_spectral_embedding
• [ ] SIR simulations (do we want it?)
• [ ] is_eulerian and related functions
• [ ] is_bigraphical
• [ ] graphlet functions (SKIP)
• [ ] is_matching and is_maximal_matching (they seem to be there partially, perhaps a quick fix?)
• [ ] maximum_bipartite_matching (it's there but buggy)
• [ ] random_edge_walk (i.e. get random_walk result in terms of edges)
• [ ] from_prufer
• [ ] maximum_cardinality_search and is_chordal
• [ ] local scan statistics (?)
• [ ] random_spanning_tree
• [ ] "microscopic update rules" (do we want it? it's not in any high-level interface now)
• [ ] shortest path functions should return either vertices or edges
• [ ] pseudo_diameter and pseudo_diameter_dijkstra
• [ ] layout_gem
• [ ] new methods of to_directed
• [ ] transitive_closure
• [ ] rewire_directed_edges
• [ ] Bliss isomorphism: return generators of the automorphism group; return number of automorphisms
• [x] is_chordal (#437)
• [ ] global and local efficiency
• [ ] igraph_list_triangles
• [ ] automorphism_group and autmorphisms (which counts them)
• [ ] voronoi
• [ ] widest path functions
• [ ] shortest path functions with cutoff
• [ ] symmetric_tree
• [ ] regular_tree
• [ ] wheel
• [ ] triangular and hexagonal lattice generators
• [ ] Floyd-Warshall shortest path
• [ ] spanner
• [ ] is_forest
• [ ] graph_count (for use with motif functions)
• [ ] has_loop
• [ ] has_mutual
• [ ] is_perfect
• [ ] generalized_petersen
• [ ] full_multipartite and turan
• [ ] graph_center
• [ ] ecc
• [ ] callaway_traits_game
• [ ] cited_type_game
• [ ] citing_cited_type_game

[szhorvat]

I am not completely comfortable with the "graphlet" functions. I looked into the paper, and could never quite make sense of what igraph's function returns. Finally I decided it's not worth spending the time on as it is very niche functionality. This use of the word "graphlet" is also an outlier. Most commonly, "graphlet" is used as an alternative name for motifs (what igraph calls "motifs"). This use is entirely different.

Given that I am not 100% convinced that the results are even correct, I am considering removing graphlets from IGraph/M. (But I'd be happy if someone could help me make sense of the results.)

https://igraph.discourse.group/t/on-the-naming-of-igraphs-graphlet-functions/65/

[szhorvat]

I added a few that came to mind, but without much organization. Feel free to remove/reorganize/rewrite as needed. In many cases, some functions are already exposed, but not with their full feature set.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 14 days if no further activity occurs. Thank you for your contributions.

[cptwunderlich]

FYI, from a user perspective, I just wanted to check if a graph is chordal and typed it in, just to realize that is_chordal is not part of python-igraph. I think this would be a very useful function, not often found in other libraries.

[szhorvat]

@cptwunderlich IMO if you need a specific feature, it's worth opening a separate issue for it. This helps us prioritize it, as well as schedule it for a specific release. (@ntamas are you okay with this, or do you think it will overload the issue tracker?)

[iosonofabio]

I directly opened a PR against develop, should not be a big deal and we can include in the next release. Thanks for requesting @cptwunderlich

[cptwunderlich]

@szhorvat OK, will do in future! @iosonofabio thank you very much!

[ntamas]

(@ntamas are you okay with this, or do you think it will overload the issue tracker?)

I am in favour; I like "actionable" issues where it is clear when the issue can be closed. This particular issue is not really "actionable" because we will probably never reach function parity, or even if we do, adding a new function to the C core would necessitate the re-opening of this issue :) But I'll keep this one open as well until we get reasonably close (which will probably be at the time when I start using generated code based on functions.def in the C core to generate the Python wrappers).

[ntamas]

PR #437 now contains an interface to igraph_is_chordal() (actually, two, is_chordal() and chordal_completion())

[szhorvat]

to_prufer is exposed, but it is not very useful without also having from_prufer, which is not exposed.

[szhorvat]

I updated this list, it may still not be complete though.