FilippoFantinato / algorithms-on-graphs / #7

Committed 13 Sep 2024 12:26AM UTC coverage: 52.941% (+10.7%) from 42.254%

Build # #7

Build Type

push

Committed by

Commit Message

Added kruskal naive algorithm

Run Details

25 of 40 new or added lines in 3 files covered. (62.5%)

54 of 102 relevant lines covered (52.94%)

549.69 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/src/cli/cli.rs

use clap::Parser;
use std::fs;
use std::ops::{Deref, DerefMut};
use std::path::PathBuf;
use std::rc::Rc;

use crate::algorithms::{cycles, minimum_spanning_tree};
use crate::graph::graph::{Graph, Weight};
use crate::graph::undirected_graph::UndirectedGraph;

#[derive(clap::ValueEnum, Clone, Debug)]
enum Algorithm {
    IsAcyclic,
    KruskalNaive,
}

/// Simple program to greet a person
#[derive(Parser, Debug)]
#[command(version, about, long_about = None)]
pub struct Args {
    #[arg(short, long, value_enum)]
    algorithm: Algorithm,

    #[arg(short, long)]
    file: PathBuf,
}

pub fn run_cli() {
    let args: Args = Args::parse();

    match args.algorithm {
        Algorithm::IsAcyclic => {
            let g = read_graph(args.file);
            let res = cycles::is_acyclic::run(&g);

            println!("Is acylic result: {:}", res);
        }
        Algorithm::KruskalNaive => {
            let g = read_graph(args.file);
            let path = minimum_spanning_tree::kruskal_naive::run(&g);
            let weight: i128 = path.iter().map(|e| (*e).2).sum();

            println!("Kruskal naive path: {:?}", path);
            println!("Kruskal naive weight: {:?}", weight);
        }
    }
}

fn read_graph(path: PathBuf) -> impl Graph {
    let lines = fs::read_to_string(path).unwrap();
    let mut lines = lines.lines();
    let mut header = lines
        .next()
        .unwrap_or_else(|| panic!("Invalid format"))
        .split_whitespace();
    let _n = header
        .next()
        .map(|v| v.parse::<usize>().unwrap())
        .unwrap_or_else(|| panic!("Invalid format"));
    let mut g = UndirectedGraph::new();

    lines.for_each(|v| {
        let mut line = v.split_whitespace();
        let u = line
            .next()
            .map(|v| v.parse::<usize>().unwrap())
            .unwrap_or_else(|| panic!("Invalid format"));
        let v = line
            .next()
            .map(|v| v.parse::<usize>().unwrap())
            .unwrap_or_else(|| panic!("Invalid format"));
        let w = line
            .next()
            .map(|v| v.parse::<i128>().unwrap())
            .unwrap_or_else(|| panic!("Invalid format"));

        g.add_edge(u, v, w);
    });

    return g;
}

1	use clap::Parser;
2	use std::fs;
3	use std::ops::{Deref, DerefMut};
4	use std::path::PathBuf;
5	use std::rc::Rc;
6
7	use crate::algorithms::{cycles, minimum_spanning_tree};
8	use crate::graph::graph::{Graph, Weight};
9	use crate::graph::undirected_graph::UndirectedGraph;
10
11	#[derive(clap::ValueEnum, Clone, Debug)]
12	enum Algorithm {
13	IsAcyclic,
14	KruskalNaive,
15	}
16
17	/// Simple program to greet a person
18	#[derive(Parser, Debug)]
19	#[command(version, about, long_about = None)]
20	pub struct Args {
21	#[arg(short, long, value_enum)]
22	algorithm: Algorithm,
23
24	#[arg(short, long)]
25	file: PathBuf,
26	}
27
28	pub fn run_cli() {	×
29	let args: Args = Args::parse();	×
30
31	match args.algorithm {	×
32	Algorithm::IsAcyclic => {	×
33	let g = read_graph(args.file);	×
NEW 34	let res = cycles::is_acyclic::run(&g);	×
35
36	println!("Is acylic result: {:}", res);	×
37	}
NEW 38	Algorithm::KruskalNaive => {	×
NEW 39	let g = read_graph(args.file);	×
NEW 40	let path = minimum_spanning_tree::kruskal_naive::run(&g);	×
NEW 41	let weight: i128 = path.iter().map(\|e\| (*e).2).sum();	×
42
NEW 43	println!("Kruskal naive path: {:?}", path);	×
NEW 44	println!("Kruskal naive weight: {:?}", weight);	×
45	}
46	}
47	}
48
NEW 49	fn read_graph(path: PathBuf) -> impl Graph {	×
50	let lines = fs::read_to_string(path).unwrap();	×
51	let mut lines = lines.lines();	×
52	let mut header = lines	×
53	.next()
54	.unwrap_or_else(\|\| panic!("Invalid format"))	×
55	.split_whitespace();
NEW 56	let _n = header	×
57	.next()
58	.map(\|v\| v.parse::<usize>().unwrap())	×
59	.unwrap_or_else(\|\| panic!("Invalid format"));	×
NEW 60	let mut g = UndirectedGraph::new();	×
61
62	lines.for_each(\|v\| {	×
63	let mut line = v.split_whitespace();	×
64	let u = line	×
65	.next()	×
NEW 66	.map(\|v\| v.parse::<usize>().unwrap())	×
67	.unwrap_or_else(\|\| panic!("Invalid format"));	×
68	let v = line	×
69	.next()	×
NEW 70	.map(\|v\| v.parse::<usize>().unwrap())	×
71	.unwrap_or_else(\|\| panic!("Invalid format"));	×
72	let w = line	×
73	.next()	×
NEW 74	.map(\|v\| v.parse::<i128>().unwrap())	×
75	.unwrap_or_else(\|\| panic!("Invalid format"));	×
76
77	g.add_edge(u, v, w);	×
78	});
79
80	return g;	×
81	}

FilippoFantinato / algorithms-on-graphs / #7

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous