Module editgraph

Graph data structure with various editing operations.

This is a versatile graph data structure that allows various modifications. It uses hash maps to store adjacency lists internally, therefore it is not very memory- or cash-efficient.

Graphs can either be loaded from file (see graphbench::io) or constructed by manually adding vertices and edges. The struct offers a few constructors for named graphs:

use graphbench::graph::*;
use graphbench::iterators::*;
use graphbench::editgraph::EditGraph;
 
fn main() {
    let graph = EditGraph::path(5);
    let edges:EdgeSet = vec![(0,1),(1,2),(2,3),(3,4)].into_iter().collect();
    assert_eq!(graph.edges().collect::<EdgeSet>(), edges);
 
    let graph = EditGraph::cycle(5);
    let edges:EdgeSet = vec![(0,1),(1,2),(2,3),(3,4),(0,4)].into_iter().collect();
    assert_eq!(graph.edges().collect::<EdgeSet>(), edges);
 
    let graph = EditGraph::matching(4);
    let edges:EdgeSet = vec![(0,4),(1,5),(2,6),(3,7)].into_iter().collect();
    assert_eq!(graph.edges().collect::<EdgeSet>(), edges);
 
    let graph = EditGraph::clique(4);
    let edges:EdgeSet = vec![(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)].into_iter().collect();
    assert_eq!(graph.edges().collect::<EdgeSet>(), edges);
 
    let graph = EditGraph::biclique(2,3);
    let edges:EdgeSet = vec![(0,2),(0,3),(0,4),(1,2),(1,3),(1,4)].into_iter().collect();
    assert_eq!(graph.edges().collect::<EdgeSet>(), edges);
 
    let graph = EditGraph::complete_kpartite(vec![1,2,2].iter());
    let edges:EdgeSet = vec![(0,1),(0,2),(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)].into_iter().collect();
    assert_eq!(graph.edges().collect::<EdgeSet>(), edges);
}

Editing operations

Vertices and edges can be added an removed from the graph in $O(1)$ time (see basic example on the graphbench page). These operations can also be applied in bulk:

use graphbench::graph::*;
use graphbench::editgraph::EditGraph;
 
fn main() {
    let mut graph = EditGraph::new();
    graph.add_vertices(vec![0,1,2,3].into_iter());   
    graph.add_edges(vec![(0,1),(1,2),(2,3)].into_iter());
 
    println!("Graph has {} vertices and {} edges", graph.num_vertices(), graph.num_edges());
}
 

The data structure further supports the contraction or identification of vertices. This operation takes a set of vertices $X$ and turns it into a single vertex whose neighbourhood are the neighbours of $X$. In graph-theoretic terms, the difference between a contraction and identification is that for a contraction we demand that $G[X]$ is connected. The methods offered here will not check connectivity.

use graphbench::graph::*;
use graphbench::iterators::*;
use graphbench::editgraph::EditGraph;
 
fn main() {
    let mut graph = EditGraph::path(4);
    graph.contract_pair(&1, &2);
    assert!(graph.contains(&1));
    assert!(!graph.contains(&2));
    assert_eq!(graph.neighbours(&1).collect::<VertexSetRef>(),
                [0,3].iter().collect());
 
    // Identify vertices on left side of a matching
    let mut graph = EditGraph::matching(3);
    graph.contract_into(&0, vec![1,2].iter());
    assert!(graph.contains(&0));
    assert!(!graph.contains(&1));
    assert!(!graph.contains(&2));
    assert_eq!(graph.neighbours(&0).collect::<VertexSetRef>(),
                [3,4,5].iter().collect());
 
    // The following is equivalent
    let mut graph_other = EditGraph::matching(3);
    graph_other.contract(vec![0,1,2].iter());
    assert_eq!(graph, graph_other);
}

Structs

EditGraph

An implementation of the MutableGraph trait with additional convenient editing and generating functions.