A graph crate with simplicity in mind

Related tags

Graphics prepona
Overview

A graph crate with simplicity in mind.

Crate API

Prepona aims to be simple to use (for users of the crate) and develop further (for contributors). Nearly every function is documented with specifications and examples for users to quickly figure out how to use a specific functionality. Also nearly every implementation has a useful comment about "why" it is implemented this way, So that contributors can quickly read the code and focus on the improvements they want to make.

General Structure

Prepona uses a layered Architecture for the logical relationship between its different components. Each layer expose functionalities for its upper layer to use. From bottom to top:

  • Storage: This layer contains different structures that can store information about a graph. Each storage must implement GraphStorage trait. This makes swapping out a storage for a different one a trivial task. Also GraphStorage provides default implementation for most of its functions so you can quickly provide an implementation for your custom and incrementally override these default implementation for a custom implementation with higher performance.
  • Graph: This layer adds more logic and sits on top a storage. One good example is the SimpleGraph structure which prevents adding a loop and multiple edges between two vertices. Decoupling this logic from a storage makes it possible to use the storages for any kind of graph.
  • Provide: This layer contains multiple traits, Each one describing a set of functionalities that is exposed by a graph. For example when a graph implements Edges trait, It means graph provides functionalities that enables the user to do computations on the edges of the graph.
  • Algorithm: This layers contains all the algorithms that can get executed on different kinds of graphs. Note that algorithms do not depend on the graph structure. They depend on the traits defined in the provide layer. This makes it possible to write a generic (in the sense that the algorithm does not depend on any structure but the functionalities that the structure provides) algorithm that can get executed on any type of graph that implements the required traits. For example TopologicalSort algorithm requires Vertices and Neighbors traits to do its computation. So any graph, subgraph, augmented graph, etc... that provides these two traits, is a suitable structure for the TopologicalSort algorithm to get executed on.

This architecture is meant to ease both the usage and contributing to this project. Users can try out each storage and graph easily without much change needed in the code base. They can easily replace the defaults with their own storage, graph and algorithm. Contributors can pick an area of interest and improve that area without needing to worry about everything else being compatible with their new enhancements.

For more information about each storage, graph, ... check the documentation of the project.

Basic Usage

First you have to pick a storage to use. For this section we will use AdjMatrix.

use prepona::prelude::*;
use prepona::storage::AdjMatrix;

let adj_matrix = AdjMatrix::<usize, DefaultEdge<usize>, UndirectedEdge>::init(); 

As you can see there are three generic parameters that must be specified. First parameter determines the type of weight is going to be stored in the storage. As you can see we set it to usize because we want our edges to have weights of type usize. Second parameter determines what type of edge is going to be stored. We use DefaultEdge for this example. DefaultEdge has only a weight. But you can define custom edge types. A good example is the FlowEdge which contains weight, capacity and flow. And finally the last parameter determines wether edges are DirectedEdge or UndirectedEdge. We will go with the undirected one for now. This declaration is too long so Prepona provides some aliases to make the process of initializing a storage easier and more readable. For all the aliases exposed by AdjMatrix, visit its documentation page. For now we use the one that is compatible with our defined adj_matrix:

use prepona::storage::Mat;

let adj_matrix = Mat::<usize>::init();

Next we have to find a graph that is suitable for out purpose. For this example we will use SimpleGraph because we don't want loops or multiple edges between two vertices:

use prepona::graph::SimpleGraph;

// Initialize the graph with the storage you have chosen.
let mut graph = SimpleGraph::init(adj_matrix);

Then we can populate our graph with vertices and edges:

//                c    
//                   
//      a     b       d     e
//
let a = graph.add_vertex();
let b = graph.add_vertex();
let c = graph.add_vertex();
let d = graph.add_vertex();
let e = graph.add_vertex();

//            .-- c --.
//            |       |
//      a --- b ----- d --- e
//
let ab = graph.add_edge_unchecked(a, b, 1.into());
let bc = graph.add_edge_unchecked(b, c, 1.into());
let cd = graph.add_edge_unchecked(c, d, 1.into());
let bd = graph.add_edge_unchecked(b, d, 1.into());
let de = graph.add_edge_unchecked(d, e, 1.into());

As you can see we use add_vertex for adding a new vertex to the graph and store the returned id of the vertex in a variable. Then we add the edges (each one with weight equal to 1) using add_edge_unchecked and store the edge ids in their variables. In Prepona each function that has a chance of failure, must provide two versions of itself: A checked version and an unchecked one. In the checked version some lookups will occur before doing the actual computation to make sure the computation is possible. If there is nothing wrong with the state of the graph and passed arguments, checked version of the function will return Ok containing the result of the computation. But if computation could fail, checked version will return an Err with a message explaining what is wrong. But the unchecked version will most likely panic due to some error. Its up to you what version you use. If you are sure about the state of your graph and the arguments you pass to the structure, then use the unchecked version to bypass the lookups and gain more performance. But if you read your values from a source that may produce valid data, use the checked version to prevent panics in your code.

Now we can execute algorithms on our graph. In this example we pretend that this graph represents a network and we want to find those vertices(connection nodes) and edges(links) that if removed, cause our network topology to become disconnected:

use prepona::algo::VertexEdgeCut;

let (cut_vertices, cut_edges) = VertexEdgeCut::init(&graph).execute(&graph);

// We find that vertices b and d are weak points in our topology. 
// And if any of them goes down, we will lose connection to part of our network topology.
assert!(
    vec![b, d]
    .iter()
    .all(|vertex_id| cut_vertices.contains(vertex_id))
);

// We find that links a -> b and d -> e are weak links in our topology. 
// And if any of them goes down, we will lose connection to part of our network topology.
assert!(
    vec![ab, de]
    .into_iter()
    .all(|edge_id| cut_edges.iter().find(|(_, _, edge)| edge.get_id() == edge_id).is_some())
);

Then you can use this information to alter the topology in order to remove these weak points/links.

Other graph crates

Also checkout these crates:

If you know any other crate email me. I'll be happy to reference them here.

Contribution

This project uses the same code of conduct as rust project.

Try to document your code using the style that already exists in the project code. For example if you are implementing a new algorithm make sure to explain a bit about what the algorithm does, reference a wikipedia page for more info about the algorithm, list the arguments and explain each one, explain the return value and what it means and at last if algorithm can fail, return a Result and avoid panic as much as possible.

Comments
  • Indexing rather than hashing in DefaultIdMap

    Indexing rather than hashing in DefaultIdMap

    I'm inspecting into VF2 algorithm recently. The IdMap takes lots of execution time as hashing is way too expensive. The algorithm has to visit nodes multiple times, which increases the penalty.

    Index-based lookups seem to solve the problem. I had experimented with the following implementation and main() now takes only half of the time (36s to 18s in debug mode, 2.3s to 1.0s in release mode).

    The drawback is that NodeId must be (usize) in the future, but the tradeoff is worthy. By the same approach, replacing IndexMap with Vec can further speed it up.

    pub struct DefaultIdMap {
        real_to_virt: Vec<Option<usize>>,
        virt_to_real: Vec<NodeId>,
    }
    
    fn main() {
        let complete_graph_size = 8;
        let path_graph_size = 10;
    
        let path_graph: AdjMap<Undirected> = PathGraph::init(path_graph_size).generate();
        let lollipop_graph: AdjMap<Undirected> =
            LollipopGraph::init(complete_graph_size, path_graph_size).generate();
    
        let are_isomorph =
            VF2Isomorphism::init(&lollipop_graph, &path_graph, IsomorphismType::Subgraph).execute();
        assert!(are_isomorph)
    }
    

    Also, I think it is fine to translate between virtual/real ids for memory efficiency. I only feel the trait NodeIdMapProvider is odd because it just relies on NodeProvider. Instead of traits, IdMap::new(graph: impl NodeProvider) seems enough for the usage.

    opened by redbug312 4
  • Support both directed and undirected graphs for views

    Support both directed and undirected graphs for views

    I'm trying to implement UndirectedView. I notice the views focus on the non-trivial case e.g. DirectedView for undirected, ReverseView for directed. This may cause trouble if algorithms contain views like this

    pub struct BiBFS<'a, G, I = DefaultIdMap>
    where
        G: NodeProvider<Dir = Directed>, // ReverseView requires Directed
        I: IdMap,
    {
        forward: &'a G,
        reverse: ReverseView<'a, G>,
        starting_nodes: Vec<NodeId>,
        ending_nodes: Vec<NodeId>,
        state: State<I>,
    }
    

    Here BiBFS can only support directed graphs, and it must define another structure for undirected graphs. I think the views should cover the trivial case to avoid that.

    opened by redbug312 1
  • Generalize IdMap over algorithms

    Generalize IdMap over algorithms

    Close issue #3.

    The trait IdMap ends up with the definition to avoid verbosely generalizing over algorithms.

    pub trait IdMap<VirtId = usize, RealId = NodeId>:
        Index<VirtId, Output = RealId> + Index<RealId, Output = VirtId>
    {
        fn new(graph: &impl NodeProvider) -> Self;
    }
    
    opened by redbug312 1
  • Apply Dijkstra's algorithm on subgraphs

    Apply Dijkstra's algorithm on subgraphs

    I have another question of the algorithms.

    Some algorithms like Dijkstra's cannot be applied on subgraphs, because these algorithms require Graph trait implemented. However, the Graph trait is used only to construct the returned frozen subgraphs, should prepona separate that and provide another trait to construct results?

    I've experimented and found this works, but I'd want to ask for opinions. As this seems relates to the layered architecture.

    pub trait View<W, E: Edge<W>, Dir: EdgeDir> {
        type Base: Graph<W, E, Dir> + Edges<W, E> + Vertices + Neighbors;
        fn base(&self) -> &Self::Base;
    }
    
    opened by redbug312 1
  • Query shortest path from ShortestPathSubgraph

    Query shortest path from ShortestPathSubgraph

    The hidden docs says there's a method to query shortest path from ShortestPathSubgraph, but there's only a method distance_to presented. It seems difficult to obtain the shortest path without information of prev. Is there a way to do this?

    Also, the method distance_to returns Option<Magnitude<W>>. I wonder if Magnitude<W> would be better, with Magnitude::PosInfinite replacing for None?

    opened by redbug312 1
Owner
Mohamad Amin Rayej
Mohamad Amin Rayej
Graph data structure library for Rust.

petgraph Graph data structure library. Supports Rust 1.41 and later. Please read the API documentation here Crate feature flags: graphmap (default) en

null 2k Jan 9, 2023
A graph library for Rust.

Gamma A graph library for Rust. Gamma provides primitives and traversals for working with graphs. It is based on ideas presented in A Minimal Graph AP

Metamolecular, LLC 122 Dec 29, 2022
Simple but powerful graph library for Rust

Graphlib Graphlib is a simple and powerful Rust graph library. This library attempts to provide a generic api for building, mutating and iterating ove

Purple Protocol 177 Nov 22, 2022
πŸ¦€ Rust Graph Routing runtime for Apollo Federation πŸš€

Apollo Router The Apollo Router is a configurable, high-performance graph router for a federated graph. Getting started Follow the quickstart tutorial

Apollo GraphQL 502 Jan 8, 2023
A simple and elegant, pipewire graph editor

pw-viz A simple and elegant, pipewire graph editor This is still a WIP, node layouting is kinda jank at the moment. Installation A compiled binary is

null 180 Dec 27, 2022
Graph API client writen in Rust

graph-rs Now available on stable Rust at crates.io graph-rs-sdk = "0.1.0" 0.1.0 and above use stable Rust. Anything before 0.1.0 uses nightly Rust. M

Sean Reeise 56 Jan 3, 2023
Rust library for of graph ensembles

Rust library for random graph ensembles Minimal Rust version: 1.55.0 Implements simple sampling and monte carlo (or rather markov-) steps, that can be

Yannick Feld 2 Dec 14, 2022
A Graph implemented using nothing but `Vec`s in rust

VecGraph A Graph implemented using nothing but Vecs in rust. Details The graph is implemented using two Vecs: nodes and edges. nodes stores "nodes". w

null 1 Jan 27, 2022
Simple, performant graph generator for Feynman diagrams* βš›οΈ

Feynman diagram generator βš›οΈ A simple generator of "Feynman diagram" permutations (as defined by problem 781). Incrementally builds isomorphically uni

eugene huang 3 Jan 1, 2023
Theorem relational dependencies automatic extraction and visualization as a graph for Lean4.

Lean Graph Interactive visualization of dependencies for any theorem/definitions in your Lean project. How to use In your browser: lean-graph.com Or r

Patrik Číhal 8 Jan 3, 2024
Jotsy is a self-hosted, free and open-source note taking app with a goal of simplicity in mind

Jotsy: Just your notes Jotsy is a self-hosted, free and open-source note taking app with a goal of simplicity in mind. It is powered by Skytable. Read

Sayan 433 Dec 30, 2022
Egui node graph is a featureful, customizable library to create node graph applications using egui

Egui node graph is a featureful, customizable library to create node graph applications using egui. The library takes care of presenting a node graph to your users, and allows customizing many aspects of the interaction, creating the semantics you want for your specific application.

null 367 Jan 8, 2023
Valheim Docker powered by Odin. The Valheim dedicated gameserver manager which is designed with resiliency in mind by providing automatic updates, world backup support, and a user friendly cli interface.

Valheim Docker If you are looking for a guide on how to get started click here Mod Support! It is supported to launch the server with BepInEx but!!!!!

Michael 657 Dec 30, 2022
A rust web framework with safety and speed in mind.

darpi A web api framework with speed and safety in mind. One of the big goals is to catch all errors at compile time, if possible. The framework uses

null 32 Apr 11, 2022
πŸ”΅πŸŸ  Portal Explorer β€” web visualization of mind-blowing portals using ray-tracing.

In Portal Explorer you can view how interesting portals are constructed, and visually explore their properties by moving and rotating them. This program doesn't work well on mobile, better opened from PC.

ilya sheprut 99 Dec 7, 2022
Doku is a framework for building documentation with code-as-data methodology in mind.

Doku is a framework for building documentation with code-as-data methodology in mind. Say goodbye to stale, hand-written documentation - with D

ANIXE 73 Nov 28, 2022
Minimal and persistent key-value store designed with security in mind

microkv Minimal and persistent key-value store designed with security in mind. Introduction microkv is a persistent key-value store implemented in Rus

Alan 17 Jan 2, 2023
πŸ“‘ Rust mDNS library designed with user interfaces in mind

?? Searchlight Searchlight is an mDNS server & client library designed to be simple, lightweight and easy to use, even if you just have basic knowledg

William 5 Jan 8, 2023
A WIP svelte parser written in rust. Designed with error recovery and reporting in mind

Svelte(rs) A WIP parser for svelte files that is designed with error recovery and reporting in mind. This is mostly a toy project for now, with some v

James Birtles 3 Apr 19, 2023