22
\$\begingroup\$

A simple graph is toroidal if it can be drawn on the surface of a torus without any edges intersecting. Your task is to take a simple undirected graph via any reasonable method (adjacency matrix, edge vertex sets, etc.) and decide whether or not it is a toroidal graph. You should output one of two distinct values for each of the two decisions. You may choose what these values are.

This is so answers will be scored in bytes with less bytes being better.

Test Cases

Here Kn is the complete graph with n vertices and Kn,m is the complete bipartite graph.

Toroidal

Not Toroidal

  • K8
\$\endgroup\$
  • 12
    \$\begingroup\$ Actual test cases would be helpful, for instance a few adjacency matrices. People are probably able to convert it to another appropriate format if they have to. \$\endgroup\$ – Stewie Griffin Aug 25 '17 at 18:44
  • 2
    \$\begingroup\$ web.math.ucsb.edu/~padraic/ucsb_2013_14/math137b_s2014/… the theorem at the end states: "If G is toroidal, then the Euler characteristic of G is 0" \$\endgroup\$ – Giuseppe Aug 25 '17 at 19:03
  • 6
    \$\begingroup\$ What are K₃, K₇, K₃,₃ and K₈? \$\endgroup\$ – Erik the Outgolfer Aug 25 '17 at 19:16
  • 3
    \$\begingroup\$ Looks like the general purpose algorithm for this is quite extensive and probably beyond the scope of PPCG. See the Yu (2011) paper mentioned at: mathoverflow.net/questions/119493/toroidality-testing. If "maybe" is a suitable answer I've got a short 1-liner :) \$\endgroup\$ – Kelly Lowder Aug 25 '17 at 19:48
  • 7
    \$\begingroup\$ @KellyLowder This is not meant to be an easy question. I don't really think there is a scope of difficulty on PPCG, after all we have the implement tetris in GoL question. \$\endgroup\$ – Wheat Wizard Aug 25 '17 at 19:50
10
+200
\$\begingroup\$

Rust, 1210 1200 bytes

use std::collections::HashMap as H;type I=i64;type E=Vec<(I,I)>;fn d(g:&E)->bool{let mut s:Vec<(E,Vec<I>)>=vec![];for e in g{let(v,w)=e;let f=(*v,*w);let z=|x|s.iter().position(|p|p.1.contains(x));match(z(v),z(w)){(Some(i),Some(j))=>{if i!=j{let mut p=s.remove(i);let q=s.remove(j-(i<j)as usize);p.0.extend(q.0);p.1.extend(q.1);s.push(p)}else{s[i].0.push(f)}}(Some(i),_)=>{s[i].0.push(f);s[i].1.push(*w)}(_,Some(j))=>{s[j].0.push(f);s[j].1.push(*v)}_=>{s.push((vec![f], vec![*v, *w]))}}}s.iter().map(|h|{let mut p=H::new();let mut r=H::new();let mut i=0;for e in&h.0{let(v,w)=e;i+=2;p.insert(i-1,i);p.insert(i,i-1);r.entry(v).or_insert(vec![]).push(i-1);r.entry(w).or_insert(vec![]).push(i)}let mut r:Vec<Vec<I>>=r.values().cloned().collect();r.sort();let mut x=0;let m=r.iter().flat_map(|v|1..v.len()).fold(1,|p,n|p*n);for mut w in 0..m{let mut t=H::new();for u in&r{let mut v=u.clone();let s=v.pop().unwrap();let mut f=s;while v.len()>0{let o=v.remove(w%v.len());w/=v.len()+1;t.insert(f,o);f=o}t.insert(f,s);}let mut f=vec![];let mut n=0;for s in p.keys(){if!f.contains(s){n+=1;let mut c=s;loop{f.push(*c);c=&t[&p[c]];if c==s{break}}}}x=x.max(n)}1-(r.len()as I-g.len()as I+x as I)/2}).sum::<I>()<2}

A toroidal example: Try it online!

That's this toroidal graph: enter image description here

A non-toroidal example: Try it online!

That's this non-toroidal graph: enter image description here

The original code I wrote, before golfing, was the following. It has printouts so you can see what's happening:

use std::collections::HashMap;

#[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)]
struct Vertex(u64);
type Edge = (Vertex, Vertex);
type Graph = Vec<Edge>;

fn full_genus(graph: &Graph) -> usize {
    componets(graph).iter().map(|g| genus(g)).sum()
}
fn genus(graph: &Graph) -> usize {
    #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug, PartialOrd, Ord)]
    struct HalfEdge(usize);
    let mut edge_pairing: HashMap<HalfEdge, HalfEdge> = HashMap::new();
    let mut vertex_groups: HashMap<&Vertex, Vec<HalfEdge>> = HashMap::new();
    let mut i = 0;
    for edge in graph {
        let (vert1, vert2) = edge;
        let half1 = HalfEdge(i);
        i += 1;
        let half2 = HalfEdge(i);
        i += 1;
        edge_pairing.insert(half1, half2);
        edge_pairing.insert(half2, half1);
        vertex_groups.entry(vert1).or_insert(vec![]).push(half1);
        vertex_groups.entry(vert2).or_insert(vec![]).push(half2);
    }
    let mut vertex_groups: Vec<Vec<HalfEdge>> = vertex_groups.values().cloned().collect();
    vertex_groups.sort();
    println!("{:?}", edge_pairing);
    println!("{:?}", vertex_groups);

    let mut max_faces = 0;
    let num_rotations = vertex_groups
        .iter()
        .map(|v| v.len() - 1)
        .map(|n| {
            let mut prod = 1;
            for i in 0..n {
                prod *= i + 1;
            }
            prod
        })
        .fold(1, |p, n| p * n);
    println!("\nNum rotations: {}\n", num_rotations);
    for rotation_index in 0..num_rotations {
        let mut working_index = rotation_index;
        let mut rotation: HashMap<HalfEdge, HalfEdge> = HashMap::new();
        let mut pretty_rotation: Vec<Vec<HalfEdge>> = vec![];
        for group in &vertex_groups {
            let mut removal_group = group.clone();
            let start = removal_group.pop().unwrap();
            let mut from = start;
            let mut pretty_group = vec![from];
            while !removal_group.is_empty() {
                let index = working_index % removal_group.len();
                working_index /= removal_group.len();
                let to = removal_group.swap_remove(index);
                rotation.insert(from, to);
                pretty_group.push(to);
                from = to;
            }
            rotation.insert(from, start);
            pretty_rotation.push(pretty_group);
        }
        let mut seen_on_face: Vec<HalfEdge> = Vec::new();
        let mut num_faces = 0;
        for start_halfedge in edge_pairing.keys() {
            if !seen_on_face.contains(start_halfedge) {
                num_faces += 1;
                let mut current_halfedge = start_halfedge;
                loop {
                    seen_on_face.push(*current_halfedge);
                    let pair_halfedge = &edge_pairing[current_halfedge];
                    current_halfedge = &rotation[pair_halfedge];
                    if current_halfedge == start_halfedge {
                        break;
                    }
                }
            }
        }
        if num_faces > max_faces {
            max_faces = num_faces;
            let euler_characteristic: isize =
                vertex_groups.len() as isize - graph.len() as isize + max_faces as isize;
            let genus_num: isize = 1 - euler_characteristic / 2;
            println!(
                "Faces: {}, Genus <= {} on rotation {}",
                max_faces, genus_num, rotation_index
            );
            println!("{:?}\n", pretty_rotation);
        }
        if rotation_index % 1e7 as usize == 0 {
            println!("Faces: {} <= {} on rotation {}", num_faces, max_faces, rotation_index);
        }
    }
    let euler_characteristic: isize =
        vertex_groups.len() as isize - graph.len() as isize + max_faces as isize;
    let genus_num: isize = 1 - euler_characteristic / 2;
    assert!(genus_num >= 0);
    genus_num as usize
}

fn componets(graph: &Graph) -> Vec<Graph> {
    let mut graphs: Vec<(Graph, Vec<Vertex>)> = vec![];
    for edge in graph {
        let (vert1, vert2) = edge;
        let g_index1 = graphs.iter().position(|(_g, h)| h.contains(&vert1));
        let g_index2 = graphs.iter().position(|(_g, h)| h.contains(&vert2));
        match (g_index1, g_index2) {
            (Some(i1), Some(i2)) => {
                if i1 != i2 {
                    let (mut graph1, mut vs1) = graphs.remove(i1);
                    let new_i2 = if i1 < i2 { i2 - 1 } else { i2 };
                    let (graph2, vs2) = graphs.remove(new_i2);
                    graph1.extend(graph2);
                    vs1.extend(vs2);
                    graphs.push((graph1, vs1));
                } else {
                    graphs[i1].0.push(edge.clone());
                }
            }
            (Some(i1), None) => {
                graphs[i1].0.push(edge.clone());
                graphs[i1].1.push(vert2.clone());
            }
            (None, Some(i2)) => {
                graphs[i2].0.push(edge.clone());
                graphs[i2].1.push(vert1.clone());
            }
            (None, None) => {
                let edges = vec![edge.clone()];
                let vs = vec!(vert1.clone(), vert2.clone());
                graphs.push((edges, vs));
            }
        }
    }
    graphs.into_iter().map(|(g, _h)| g).collect()
}

fn main() {
    let graph = vec![
        (Vertex(0), Vertex(1)),
        (Vertex(0), Vertex(2)),
        (Vertex(0), Vertex(3)),
        (Vertex(0), Vertex(4)),
        (Vertex(0), Vertex(5)),
        (Vertex(1), Vertex(2)),
        (Vertex(1), Vertex(3)),
        (Vertex(1), Vertex(4)),
        (Vertex(1), Vertex(5)),
        (Vertex(2), Vertex(3)),
        (Vertex(2), Vertex(4)),
        (Vertex(2), Vertex(5)),
        (Vertex(3), Vertex(4)), 
        (Vertex(3), Vertex(5)),
    ];  
    let result = full_genus(&graph);
    println!("Result: {}", result);
}

This program finds the minimum genus surface that the given graph can be embedded in. A graph is toroidal if that genus is at most 1, the genus of the torus.

The code works by separating the graph into its connected components, finding their genii separately, and adding up the results.

To find the genus of a connected graph, I brute force search over all possible rotation systems of the graph, and figure out which one has the most faces. A rotation system is simply an ordering on the edges emerging from each vertex, saying what order those edges are in going around the vertex. Each rotation system has a straightforward minimum genus it can be embedded in, and having more faces directly corresponds to having lower genus. Since every possible embedding corresponds to some rotation system, if there is a toroidal embedding, my program will find the corresponding rotation system and declare that the graph is toroidal, and vice versa.

This program is very slow, because it searches through a number of rotation systems equal to the product over all degrees d of the vertices of (d-1)!. However, it can search through a little over 10 million such rotation systems per minute, so it can verify the toroidality or non-toroidality of simple graphs like the ones shown above.

\$\endgroup\$
  • 1
    \$\begingroup\$ You do know that your main function is still called is_toroidal right? Changing that to say t saves 10 bytes \$\endgroup\$ – caird coinheringaahing Nov 17 at 20:50
  • \$\begingroup\$ @cairdcoinheringaahing Thanks, I feel silly for missing that \$\endgroup\$ – isaacg Nov 17 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.