[dependencies]
graphman = { git = "https://github.com/lkzppm/GraphMan" }

use graphman::{AdjacencyList, Build, EdgeList, Graph, algo};

// The sample graph: five vertices, six edges.
let edges = EdgeList::parse(b"5\n1 2\n1 3\n2 3\n2 4\n3 5\n4 5\n")?;
let graph = AdjacencyList::build(&edges)?;
let n = graph.vertex_count(); // 5

let tree = algo::bfs(&graph, 1);
let parent = tree.parent(4); // Some(2)
let level = tree.level(4); // Some(2)

let diameter = algo::diameter(&graph, algo::DiameterMethod::IFub);
let value = diameter.value; // 2

use graphman::EdgeList;

// The parser normalises once: self-loops go, every edge is kept once as
// [min, max], the list is sorted. Every representation is built from this.
let text = b"5\n2 1\n1 2\n3 3\n1 3\n2 3\n2 4\n3 5\n4 5\n";
let edges = EdgeList::parse(text).unwrap();
let kept = edges.edge_count(); // 6
let first = edges.edges()[0]; // [1, 2]
let loops = edges.self_loops_dropped(); // 1
let duplicates = edges.duplicates_dropped(); // 1

// From a file, or from memory.
// let edges = EdgeList::from_path("graphs/grafo_1.txt")?;
let pairs = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)];
let same = EdgeList::from_edges(5, pairs).unwrap(); // == edges

use graphman::{AdjacencyList, AdjacencyMatrix, Build, Csr, EdgeList, Graph, algo};

let edges = EdgeList::parse(b"5\n1 2\n1 3\n2 3\n2 4\n3 5\n4 5\n").unwrap();
let list = AdjacencyList::build(&edges).unwrap();
let matrix = AdjacencyMatrix::build(&edges).unwrap();
let csr = Csr::build(&edges).unwrap();

// One graph, three layouts in memory, the same answers: neighbours come
// out ascending from all three, so the search trees are identical.
let around_2: Vec<_> = list.neighbors(2).collect(); // [1, 3, 4]
let adjacent = matrix.has_edge(1, 3); // true
let same_tree = algo::bfs(&list, 1) == algo::bfs(&csr, 1); // true

use graphman::{BuildError, EdgeList, MemoryBudget, Representation, algo, dispatch};

// Chosen at runtime (the CLI's --repr flag): AnyGraph holds any of the
// three, and dispatch! runs a generic expression on whichever it is.
let edges = EdgeList::parse(b"5\n1 2\n1 3\n2 3\n2 4\n3 5\n4 5\n").unwrap();
let chosen: Representation = "csr".parse().unwrap();
let any = chosen.build(&edges).unwrap();
let depth = dispatch!(&any, g => algo::bfs(g, 1).depth()); // 2

// What each one costs is known before anything is allocated, and every
// builder checks it against a MemoryBudget (the machine's memory by
// default): over it is a typed error, not a process dying in swap.
let bytes = Representation::Csr.required_bytes(5, 6, false); // 76
let matrix = Representation::AdjacencyMatrix.required_bytes(375_000, 0, false); // 17_580_000_000
let refused = chosen.build_within(&edges, MemoryBudget::Bytes(64)); // Err(OverBudget { .. })

use graphman::{Build, Csr, EdgeList, algo};

let edges = EdgeList::parse(b"5\n1 2\n1 3\n2 3\n2 4\n3 5\n4 5\n").unwrap();
let graph = Csr::build(&edges).unwrap();

// A search tree: parent and level of every reached vertex, in discovery order.
let bfs = algo::bfs(&graph, 1);
let order = bfs.order(); // [1, 2, 3, 4, 5]
let parent_of_4 = bfs.parent(4); // Some(2)
let depth = bfs.depth(); // 2

// DFS takes neighbours in ascending order, iteratively, in O(depth) memory,
// and produces exactly the tree the recursive version would.
let dfs = algo::dfs(&graph, 1);
let dfs_order = dfs.order(); // [1, 2, 3, 5, 4]
let dfs_parent_of_4 = dfs.parent(4); // Some(5)
let dfs_depth = dfs.depth(); // 4

use graphman::{Build, Control, Csr, EdgeList, Graph, SearchTree, Vertex, Visitor, algo};

let edges = EdgeList::parse(b"5\n1 2\n1 3\n2 3\n2 4\n3 5\n4 5\n").unwrap();
let graph = Csr::build(&edges).unwrap();

// A visitor watches a traversal and may stop it. Distance is just this.
struct Until(Vertex, Option<u32>);
impl Visitor for Until {
    fn discover(&mut self, v: Vertex, _parent: Vertex, level: u32) -> Control {
        if v != self.0 {
            return Control::Continue;
        }
        self.1 = Some(level);
        Control::Break
    }
}
let mut until = Until(4, None);
algo::bfs_with(&graph, 1, &mut until);
let found_at = until.1; // Some(2), after discovering 1, 2, 3 and 4

// A tree is reusable: each search resets only what the previous one
// reached, so thousands of them cost no allocation and no O(n) clear.
let mut tree = SearchTree::new(graph.vertex_count());
for root in graph.vertices() {
    algo::bfs_into(&graph, root, &mut tree, &mut ());
}

use graphman::{Build, Components, Csr, EdgeList, algo};

// The sample plus a second component, {6, 7}.
let edges = EdgeList::parse(b"7\n1 2\n1 3\n2 3\n2 4\n3 5\n4 5\n6 7\n").unwrap();
let graph = Csr::build(&edges).unwrap();

// A BFS that stops at the target; None across components.
let near = algo::distance(&graph, 4, 3); // Some(2)
let apart = algo::distance(&graph, 1, 7); // None
// The farthest vertex from 1, and how far.
let farthest = algo::eccentricity(&graph, 1); // (2, 5)

// Components, numbered from the largest, each listed ascending.
let components = Components::compute(&graph);
let count = components.count(); // 2
let largest = components.members(1); // [1, 2, 3, 4, 5]
let of_7 = components.component_of(7); // 2

use graphman::{Build, Control, Csr, DiameterMethod, EdgeList, algo};

let edges = EdgeList::parse(b"5\n1 2\n1 3\n2 3\n2 4\n3 5\n4 5\n").unwrap();
let graph = Csr::build(&edges).unwrap();

// Four methods, one driver: brute force, iFUB, Takes-Kosters bounds and
// the 4-sweep lower bound. All but the sweep certify their answer.
let exact = algo::diameter(&graph, DiameterMethod::IFub);
let (value, certified) = (exact.value, exact.is_exact); // (2, true)
let endpoints = exact.endpoints; // (1, 5): a longest shortest path, 1-3-5
let sweep = algo::diameter(&graph, DiameterMethod::Sweep);
let lower_bound = (sweep.value, sweep.is_exact); // (2, false)

// Every method takes a budget: the callback sees the BFS count after each
// search and may stop the run, which then reports its best lower bound.
let stop_after_two = |bfs_count: usize| match bfs_count < 2 {
    true => Control::Continue,
    false => Control::Break,
};
let bounded = algo::diameter_with_progress(&graph, DiameterMethod::Exact, &stop_after_two);
let gave_up = bounded.cancelled; // true

use graphman::{Build, Csr, EdgeList, Weighted};

// A third column makes a weighted graph: the sample, each edge weighed.
let text = b"5\n1 2 0.5\n1 3 2\n2 3 1\n2 4 2.5\n3 5 1\n4 5 0.75\n";
let edges = EdgeList::parse(text)?;
let graph = Csr::build(&edges)?;
let weighted = graph.is_weighted(); // true
let around_2: Vec<_> = graph.weighted_neighbors(2).collect(); // [(1, 0.5), (3, 1.0), (4, 2.5)]
let w = graph.weight(4, 5); // Some(0.75)

// The weights are a column beside the adjacency: BFS never reads it, and
// a graph without one weighs 1 per edge, so hops are the unit-weight case.
let plain = Csr::build(&EdgeList::parse(b"5\n1 2\n1 3\n2 3\n2 4\n3 5\n4 5\n")?)?;
let unit = plain.weight(4, 5); // Some(1.0)

// A repeated edge keeps its smallest weight, the only one a path would use.
let repeated = EdgeList::parse(b"2\n1 2 4\n2 1 0.5\n")?;
let kept = repeated.weights(); // Some([0.5])

use graphman::{Build, Csr, EdgeList, FrontierKind, algo};

let text = b"5\n1 2 0.5\n1 3 2\n2 3 1\n2 4 2.5\n3 5 1\n4 5 0.75\n";
let graph = Csr::build(&EdgeList::parse(text)?)?;

// One Dijkstra; the frontier (how estimates are kept) is the strategy.
let tree = algo::dijkstra(&graph, 1, FrontierKind::Heap)?;
let to_5 = tree.distance(5); // Some(2.5)
let path = tree.path_to(5); // Some([1, 2, 3, 5]): three edges, lighter than 1-3-5
let order = tree.order(); // [1, 2, 3, 5, 4], by distance

// The vector scan (O(n²)) and the heap (O((n + m) log n)) agree exactly:
// ties go to the smaller vertex in both, so even the tree is the same.
let vector = algo::dijkstra(&graph, 1, FrontierKind::Vector)?;
let same = vector == tree; // true

// A negative weight is refused, not answered wrongly.
let negative = Csr::build(&EdgeList::parse(b"3\n1 2 1\n2 3 -1\n")?)?;
let refused = algo::dijkstra(&negative, 1, FrontierKind::Heap); // Err(NegativeWeight { .. })

use graphman::algo::{self, Frontier, HeapFrontier, ShortestPathTree};
use graphman::{Build, Csr, EdgeList, Graph};

let text = b"5\n1 2 0.5\n1 3 2\n2 3 1\n2 4 2.5\n3 5 1\n4 5 0.75\n";
let graph = Csr::build(&EdgeList::parse(text)?)?;

// A pair query stops as soon as the target is settled.
let path = algo::shortest_path(&graph, 1, 4)?.unwrap();
let (distance, via) = (path.distance, path.vertices); // (3.0, [1, 2, 4])

// k sources (the case study): one frontier and one tree for every run,
// each run resetting only what the previous one touched.
let mut frontier = HeapFrontier::default();
let mut tree = ShortestPathTree::new(graph.vertex_count());
let mut farthest = Vec::new();
for root in graph.vertices() {
    algo::dijkstra_into(&graph, root, &mut frontier, &mut tree, &mut ())?;
    farthest.push(tree.last_settled()); // (vertex, distance) farthest from root
}
let kind = frontier.kind(); // FrontierKind::Heap

use graphman::VertexNames;

// Names live beside the graph, in their own file (`index,name` per line).
let names =
    VertexNames::parse("1,Edsger W. Dijkstra\n2,Alan M. Turing\n3,Éva Tardos\n".as_bytes())?;
let dijkstra = names.vertex("Edsger W. Dijkstra"); // Some(1), exact spelling
let third = names.name(3); // Some("Éva Tardos")
let near_miss = names.search("eva tardos", 5); // [3]: ignoring case and accents
// let names = VertexNames::from_path("graphs/rede_colaboracao_vertices.txt")?;