Crates.io | graaf |
lib.rs | graaf |
version | 0.67.0 |
source | src |
created_at | 2024-03-30 15:06:09.080279 |
updated_at | 2024-07-15 19:29:39.119129 |
description | Work with directed graphs. |
homepage | |
repository | https://github.com/bsdrks/graaf |
max_upload_size | |
id | 1191151 |
size | 657,392 |
Work with directed graphs in Rust.
Add the following to your Cargo.toml
:
[dependencies]
graaf = "0.70.3"
Graaf provides three representations of directed graphs.
adjacency_list
represents unweighted sparse digraphs.adjacency_matrix
represents unweighted dense digraphs.adjacency_list_weighted
represents arc-weighted sparse digraphs.These types eagerly implement digraph operations and digraph algorithms.
The gen
module provides six digraph generators.
Biclique
generates a complete bipartite digraph.Complete
generates a complete digraph.Cycle
generates a digraph with a cycle of a given length.Empty
generates a digraph with no arcs.RandomTournament
generates a random tournament.Star
generates a star digraph.The op
module provides digraph operation traits. The digraph types implement these traits. One can implement these traits for custom digraph types. Operations form the foundation for algorithms.
Individual digraph types implement the basic operations.
AddArcWeighted
adds an arc to an arc-weighted digraph.AddArc
adds an arc to an unweighted digraph.ArcWeight
returns the weight of an arc.ArcsWeighted
returns the arcs and their weights in a digraph.Arcs
returns the arcs in a digraph.Converse
returns the converse of a digraph.HasArc
checks if an arc exists in a digraph.Indegree
returns the indegree of a vertex.IsSimple
checks if a digraph contains no loops or parallel arcs.Order
returns the number of vertices.OutNeighborsWeighted
returns the weighted out-neighbors of a vertex.OutNeighbors
returns the out-neighbors of a vertex.Outdegree
returns the outdegree of a vertex.RemoveArc
removes an arc from a digraph.Size
returns the number of arcs in a digraph.Vertices
returns the vertices in a digraph.The extended traits derive their implementation from the basic operations.
Complement
returns the complement of a digraph.Degree
returns the degree of a vertex.DegreeSequence
returns the degree sequence of a digraph.HasEdge
checks if an edge exists in a digraph.InNeighbors
returns the in-neighbors of a vertex.IsBalanced
checks if a digraph is balanced.IsComplete
checks if a digraph is complete.IsIsolated
checks if a vertex is isolated.IsOriented
checks if a digraph is oriented.IsPendant
checks if a vertex is a pendant.IsRegular
checks if a digraph is regular.IsSemicomplete
checks if a digraph is semicomplete.IsSubdigraph
checks if a digraph is a subdigraph.IsSuperdigraph
checks if a digraph is a superdigraph.IsSymmetric
checks if a digraph is symmetric.IsTournament
checks if a digraph is a tournament.IsWalk
checks if a sequence of vertices is a walk in a digraph.The algo
module provides digraph algorithms.
The Bellman-Ford-Moore algorithm finds the shortest paths in an arc-weighted digraph with negative weights.
single_source_distances
finds the shortest distances.A breadth-first search explores the vertices of an unweighted digraph in order of their distance from a source.
These functions start from one or more source vertices and allow a custom step function, target predicate, distance array, breadth-first tree, and queue, where applicable.
distances
finds the shortest distances.predecessors
finds the predecessors.shortest_path
finds the shortest path.These functions start from one source vertex.
single_source_distances
finds the shortest distances.single_source_predecessors
finds the predecessors.single_pair_shortest_path
finds the shortest path.A depth-first search explores the vertices of an unweighted digraph in order of their depth from a source.
dfsa
traverses the digraph.dfsa_predecessors
finds the predecessors.acyclic_ordering
generates an acyclic ordering.Dijkstra's algorithm finds the shortest paths in an arc-weighted digraph.
These functions start from one or more source vertices and allow a custom step function, target predicate, distance array, and heap, where applicable.
distances
finds the shortest distances.predecessors
finds the predecessors.shortest_path
finds the shortest path.These functions start from one source vertex.
single_source_distances
finds the shortest distances.single_source_predecessors
finds the predecessors.single_pair_shortest_path
finds the shortest path.The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in an arc-weighted digraph.
distances
finds the shortest distances.A breadth-first tree is the result of a breadth-first search.
These functions produce a breadth-first tree.
bfs::single_source_predecessors
bfs::predecessors
dijkstra::single_source_predecessors
dijkstra::predecessors
A distance matrix contains the shortest distances between all pairs of vertices in a digraph.
center
finds the center of the digraph.diameter
finds the diameter of the digraph.eccentricities
returns the eccentricities of the vertices.is_connected
checks if the digraph is connected.periphery
finds the periphery of the digraph.s
denotes a source vertex.t
denotes a target vertex.u
denotes a tail vertex or the first vertex in scope.v
denotes a head vertex or the second vertex in scope.w
denotes the weight of an arc.x
denotes a tail vertex or the third vertex in scope.y
denotes a head vertex or the fourth vertex in scope.See CHANGELOG.md for a list of changes.
Licensed under Apache License, Version 2.0 or MIT license at your option.