A graph library entirely written in Julia. Install it with
Erdos defines some types associated to graph mathematical structures and implements a huge number of algorithms to work with them. Moreover edge and vertex properties can be internally stored in some of the graph types (we call them networks) and read/written in most common graph formats. Custom graphs and networks can be defined inheriting from Erdos' abstract types.
Take a look at the companion package ErdosExtras for additional algorithms.
Erdos is released under MIT License. Graphs stored in the datasets directory are released under GPLv3 License.
Huge credit goes to the contributors of LightGraphs.jl, from which this library is derived. Also thanks to Tiago de Paula Peixoto and his Python library graph-tool for inspiration and for the graphs in datasets.
core functions: vertices and edges addition and removal, degree (in/out/all), neighbors (in/out/all)
maps dictionary like types to store properties associated to vertices and edges
networks store vertex/edge/graph properties (maps) inside the graph itself
connectivity: strongly- and weakly-connected components, bipartite checks, condensation, attracting components, neighborhood, k-core
operators: complement, reverse, reverse!, union, join, intersect, difference, symmetric difference, blockdiag, induced subgraphs, products (cartesian/scalar)
shortest paths: Dijkstra, Dijkstra with predecessors, Bellman-Ford, Floyd-Warshall, A*
graph datasets: A collection of real world graphs (e.g. Zachary's karate club)
graph generators: notorious graphs, euclidean graphs and random graphs (Erdős–Rényi, Watts-Strogatz, random regular, arbitrary degree sequence, stochastic block model)
centrality: betweenness, closeness, degree, pagerank, Katz
traversal operations: cycle detection, BFS and DFS DAGs, BFS and DFS traversals with visitors, DFS topological sort, maximum adjacency / minimum cut, multiple random walks
flow operations: maximum flow, minimum s-t cut
matching: minimum weight matching on arbitrary graphs (EE), minimum b-matching (EE)
travelling salesman problem: a TSP solver based on linear programming (EE)
dismantling: collective influencer heuristic
clique enumeration: maximal cliques
linear algebra / spectral graph theory: adjacency matrix, Laplacian matrix, non-backtracking matrix
community: modularity, community detection, core-periphery, clustering coefficients
distance within graphs: eccentricity, diameter, periphery, radius, center
distance between graphs: spectral_distance, edit_distance
3 months ago