graph_solver

Struct Graph

Source 
pub struct Graph {
    pub nodes: Vec<Node>,
    pub edges: Vec<Vec<Color>>,
    pub pairs: Vec<(usize, usize)>,
    pub no_triangles: bool,
    pub meet_quad: bool,
    pub connected: bool,
    pub commute_quad: Option<bool>,
    /* private fields */
}
Expand description

Stores information about graph.

An edge value 0 means no edge.

Fields§

§nodes: Vec<Node>

Nodes.

§edges: Vec<Vec<Color>>

Edges.

§pairs: Vec<(usize, usize)>

Pair constraints, using indices.

§no_triangles: bool

Whether triangle cycles are allowed.

§meet_quad: bool

Whether any shortest cycle for any vertex must be 4 or less.

§connected: bool

Whether any node can be reached from any other node.

§commute_quad: Option<bool>

Whether commutativity/anticommutativity is enabled for quads.

When a quad commutes, the edges along one dimension have same colors. When a quad anticommutes, the edges along one dimension have same colors, but with an odd number of positive and negative signs (1+3 or 3+1).

It is assumed that even and odd colors for edges above 2 anticommutes, e.g. 2 and 3 anticommutes.

  • When set to Some(true), every quad commutes.
  • When set to Some(false), every quad anticommutes.
  • When set to None

Implementations§

Source§

impl Graph

Source

pub fn new() -> Graph

Creates a new graph.

Initialized with these default settings:

  • no-triangles: false
  • meet-quad: false
  • connected: false
Examples found in repository?
examples/adinkra1.rs (line 7)
6fn main() {
7    let mut g = Graph::new();
8    let a = Node {
9        color: 0,
10        self_connected: false,
11        edges: vec![Constraint {edge: RED, node: 1}]
12    };
13    let b = Node {
14        color: 1,
15        self_connected: false,
16        edges: vec![Constraint {edge: RED, node: 0}]
17    };
18    g.push(a);
19    g.push(b);
20
21    let solve_settings = SolveSettings::new();
22    if let Some(solution) = g.solve(solve_settings) {
23        solution.puzzle.print();
24    }
25}
More examples
Hide additional examples
examples/triangle.rs (line 7)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![Constraint {edge: EDGE, node: 0}; 2]
14    };
15
16    for _ in 0..3 {g.push(a.clone())}
17
18    let solve_settings = SolveSettings::new();
19    if let Some(solution) = g.solve(solve_settings) {
20        // solution.puzzle.print();
21        println!("{}", solution.puzzle.graphviz(
22            "sfdp",
23            &["black"],
24            &["black"]
25        ));
26    }
27}
examples/pentagon.rs (line 7)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![
14            Constraint {edge: EDGE, node: 0},
15            Constraint {edge: EDGE, node: 0},
16        ]
17    };
18
19    for _ in 0..5 {g.push(a.clone())}
20
21    let solve_settings = SolveSettings::new();
22    if let Some(solution) = g.solve(solve_settings) {
23        // solution.puzzle.print();
24        println!("{}", solution.puzzle.graphviz(
25            "sfdp",
26            &["black"],
27            &["black"]
28        ));
29    }
30}
examples/cube.rs (line 17)
16fn main() {
17    let mut g = Graph::new();
18
19    // Create a node pattern with 3 edges.
20    let a = Node {
21        color: 0,
22        self_connected: false,
23        edges: vec![Constraint {edge: EDGE, node: 0}; 3]
24    };
25
26    // Add 8 vertices.
27    for _ in 0..8 {g.push(a.clone())}
28    g.no_triangles = true;
29
30    let solve_settings = SolveSettings::new();
31    if let Some(solution) = g.solve(solve_settings) {
32        println!("{}", solution.puzzle.graphviz(
33            "sfdp",
34            &["black"],
35            &["black"]
36        ));
37    } else {
38        eprintln!("<no solution>");
39    }
40}
examples/square2.rs (line 7)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![Constraint {edge: SOLID, node: 0}; 2]
14    };
15
16    // Add 4 nodes.
17    for _ in 0..4 {g.push(a.clone())}
18
19    let solve_settings = SolveSettings::new()
20        .debug(true).sleep_ms(2000);
21    if let Some(solution) = g.solve(solve_settings) {
22        // Prints:
23        // 0 0 0 0
24        // ========================================
25        // 0 2 1 0
26        // 2 0 0 1
27        // 1 0 0 2
28        // 0 1 2 0
29        solution.puzzle.print();
30    }
31}
examples/hexagon.rs (line 7)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![
14            Constraint {edge: EDGE, node: 0},
15            Constraint {edge: EDGE, node: 0},
16        ]
17    };
18
19    for _ in 0..6 {g.push(a.clone())}
20    g.push_pair((2, 3));
21
22    let solve_settings = SolveSettings::new();
23    if let Some(solution) = g.solve(solve_settings) {
24        // solution.puzzle.print();
25        println!("{}", solution.puzzle.graphviz(
26            "sfdp",
27            &["black,fontcolor=white"],
28            &["black"]
29        ));
30    }
31}
Additional examples can be found in:
Source

pub fn graphviz( &self, layout: &str, node_colors: &[&str], edge_colors: &[&str], ) -> String

Generates a GraphViz dot format.

Examples found in repository?
examples/triangle.rs (lines 21-25)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![Constraint {edge: EDGE, node: 0}; 2]
14    };
15
16    for _ in 0..3 {g.push(a.clone())}
17
18    let solve_settings = SolveSettings::new();
19    if let Some(solution) = g.solve(solve_settings) {
20        // solution.puzzle.print();
21        println!("{}", solution.puzzle.graphviz(
22            "sfdp",
23            &["black"],
24            &["black"]
25        ));
26    }
27}
More examples
Hide additional examples
examples/pentagon.rs (lines 24-28)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![
14            Constraint {edge: EDGE, node: 0},
15            Constraint {edge: EDGE, node: 0},
16        ]
17    };
18
19    for _ in 0..5 {g.push(a.clone())}
20
21    let solve_settings = SolveSettings::new();
22    if let Some(solution) = g.solve(solve_settings) {
23        // solution.puzzle.print();
24        println!("{}", solution.puzzle.graphviz(
25            "sfdp",
26            &["black"],
27            &["black"]
28        ));
29    }
30}
examples/cube.rs (lines 32-36)
16fn main() {
17    let mut g = Graph::new();
18
19    // Create a node pattern with 3 edges.
20    let a = Node {
21        color: 0,
22        self_connected: false,
23        edges: vec![Constraint {edge: EDGE, node: 0}; 3]
24    };
25
26    // Add 8 vertices.
27    for _ in 0..8 {g.push(a.clone())}
28    g.no_triangles = true;
29
30    let solve_settings = SolveSettings::new();
31    if let Some(solution) = g.solve(solve_settings) {
32        println!("{}", solution.puzzle.graphviz(
33            "sfdp",
34            &["black"],
35            &["black"]
36        ));
37    } else {
38        eprintln!("<no solution>");
39    }
40}
examples/hexagon.rs (lines 25-29)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![
14            Constraint {edge: EDGE, node: 0},
15            Constraint {edge: EDGE, node: 0},
16        ]
17    };
18
19    for _ in 0..6 {g.push(a.clone())}
20    g.push_pair((2, 3));
21
22    let solve_settings = SolveSettings::new();
23    if let Some(solution) = g.solve(solve_settings) {
24        // solution.puzzle.print();
25        println!("{}", solution.puzzle.graphviz(
26            "sfdp",
27            &["black,fontcolor=white"],
28            &["black"]
29        ));
30    }
31}
examples/4cube.rs (lines 23-27)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![Constraint {edge: EDGE, node: 0}; 4]
14    };
15
16    for _ in 0..16 {g.push(a.clone())}
17    g.no_triangles = true;
18    g.connected = true;
19
20    let solve_settings = SolveSettings::new(); // .debug(true).sleep_ms(10);
21    if let Some(solution) = g.solve(solve_settings) {
22        // solution.puzzle.print();
23        println!("{}", solution.puzzle.graphviz(
24            "sfdp",
25            &["black,fontcolor=white"],
26            &["black"]
27        ));
28    } else {
29        eprintln!("<no solution>");
30    }
31}
examples/grid.rs (lines 40-44)
6fn main() {
7    let mut g = Graph::new();
8
9    let edge = Constraint {edge: EDGE, node: 0};
10
11    // Create a node pattern.
12    let a = Node {
13        color: 0,
14        self_connected: false,
15        edges: vec![edge; 2],
16    };
17    let b = Node {
18        color: 0,
19        self_connected: false,
20        edges: vec![edge; 3]
21    };
22    let c = Node {
23        color: 0,
24        self_connected: false,
25        edges: vec![edge; 4]
26    };
27
28    for _ in 0..4 {g.push(a.clone())}
29    for _ in 0..4 {g.push(b.clone())}
30    g.push(c);
31    g.no_triangles = true;
32    g.meet_quad = true;
33
34    for i in 0..4 {g.set((i, 8), 1)}
35    g.set((1, 5), 1);
36
37    let solve_settings = SolveSettings::new();
38    if let Some(solution) = g.solve(solve_settings) {
39        // solution.puzzle.print();
40        println!("{}", solution.puzzle.graphviz(
41            "sfdp",
42            &["black,fontcolor=white"],
43            &["black"]
44        ));
45    } else {
46        eprintln!("<no solution>");
47    }
48}
Additional examples can be found in:
Source

pub fn fst_empty(&self) -> Option<(usize, usize)>

Finds the first empty edge.

Source

pub fn min_colors(&self) -> Option<(usize, usize)>

Finds the edge with the least possible colors.

Source

pub fn solve(self, solve_settings: SolveSettings) -> Option<Solution<Graph>>

Solves the graph puzzle using default strategy.

The default strategy is Graph::min_colors, Graph::colors.

Examples found in repository?
examples/adinkra1.rs (line 22)
6fn main() {
7    let mut g = Graph::new();
8    let a = Node {
9        color: 0,
10        self_connected: false,
11        edges: vec![Constraint {edge: RED, node: 1}]
12    };
13    let b = Node {
14        color: 1,
15        self_connected: false,
16        edges: vec![Constraint {edge: RED, node: 0}]
17    };
18    g.push(a);
19    g.push(b);
20
21    let solve_settings = SolveSettings::new();
22    if let Some(solution) = g.solve(solve_settings) {
23        solution.puzzle.print();
24    }
25}
More examples
Hide additional examples
examples/triangle.rs (line 19)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![Constraint {edge: EDGE, node: 0}; 2]
14    };
15
16    for _ in 0..3 {g.push(a.clone())}
17
18    let solve_settings = SolveSettings::new();
19    if let Some(solution) = g.solve(solve_settings) {
20        // solution.puzzle.print();
21        println!("{}", solution.puzzle.graphviz(
22            "sfdp",
23            &["black"],
24            &["black"]
25        ));
26    }
27}
examples/pentagon.rs (line 22)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![
14            Constraint {edge: EDGE, node: 0},
15            Constraint {edge: EDGE, node: 0},
16        ]
17    };
18
19    for _ in 0..5 {g.push(a.clone())}
20
21    let solve_settings = SolveSettings::new();
22    if let Some(solution) = g.solve(solve_settings) {
23        // solution.puzzle.print();
24        println!("{}", solution.puzzle.graphviz(
25            "sfdp",
26            &["black"],
27            &["black"]
28        ));
29    }
30}
examples/cube.rs (line 31)
16fn main() {
17    let mut g = Graph::new();
18
19    // Create a node pattern with 3 edges.
20    let a = Node {
21        color: 0,
22        self_connected: false,
23        edges: vec![Constraint {edge: EDGE, node: 0}; 3]
24    };
25
26    // Add 8 vertices.
27    for _ in 0..8 {g.push(a.clone())}
28    g.no_triangles = true;
29
30    let solve_settings = SolveSettings::new();
31    if let Some(solution) = g.solve(solve_settings) {
32        println!("{}", solution.puzzle.graphviz(
33            "sfdp",
34            &["black"],
35            &["black"]
36        ));
37    } else {
38        eprintln!("<no solution>");
39    }
40}
examples/square2.rs (line 21)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![Constraint {edge: SOLID, node: 0}; 2]
14    };
15
16    // Add 4 nodes.
17    for _ in 0..4 {g.push(a.clone())}
18
19    let solve_settings = SolveSettings::new()
20        .debug(true).sleep_ms(2000);
21    if let Some(solution) = g.solve(solve_settings) {
22        // Prints:
23        // 0 0 0 0
24        // ========================================
25        // 0 2 1 0
26        // 2 0 0 1
27        // 1 0 0 2
28        // 0 1 2 0
29        solution.puzzle.print();
30    }
31}
examples/hexagon.rs (line 23)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![
14            Constraint {edge: EDGE, node: 0},
15            Constraint {edge: EDGE, node: 0},
16        ]
17    };
18
19    for _ in 0..6 {g.push(a.clone())}
20    g.push_pair((2, 3));
21
22    let solve_settings = SolveSettings::new();
23    if let Some(solution) = g.solve(solve_settings) {
24        // solution.puzzle.print();
25        println!("{}", solution.puzzle.graphviz(
26            "sfdp",
27            &["black,fontcolor=white"],
28            &["black"]
29        ));
30    }
31}
Additional examples can be found in:
Source

pub fn push(&mut self, node: Node)

Adds a node description.

Examples found in repository?
examples/adinkra1.rs (line 18)
6fn main() {
7    let mut g = Graph::new();
8    let a = Node {
9        color: 0,
10        self_connected: false,
11        edges: vec![Constraint {edge: RED, node: 1}]
12    };
13    let b = Node {
14        color: 1,
15        self_connected: false,
16        edges: vec![Constraint {edge: RED, node: 0}]
17    };
18    g.push(a);
19    g.push(b);
20
21    let solve_settings = SolveSettings::new();
22    if let Some(solution) = g.solve(solve_settings) {
23        solution.puzzle.print();
24    }
25}
More examples
Hide additional examples
examples/triangle.rs (line 16)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![Constraint {edge: EDGE, node: 0}; 2]
14    };
15
16    for _ in 0..3 {g.push(a.clone())}
17
18    let solve_settings = SolveSettings::new();
19    if let Some(solution) = g.solve(solve_settings) {
20        // solution.puzzle.print();
21        println!("{}", solution.puzzle.graphviz(
22            "sfdp",
23            &["black"],
24            &["black"]
25        ));
26    }
27}
examples/pentagon.rs (line 19)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![
14            Constraint {edge: EDGE, node: 0},
15            Constraint {edge: EDGE, node: 0},
16        ]
17    };
18
19    for _ in 0..5 {g.push(a.clone())}
20
21    let solve_settings = SolveSettings::new();
22    if let Some(solution) = g.solve(solve_settings) {
23        // solution.puzzle.print();
24        println!("{}", solution.puzzle.graphviz(
25            "sfdp",
26            &["black"],
27            &["black"]
28        ));
29    }
30}
examples/cube.rs (line 27)
16fn main() {
17    let mut g = Graph::new();
18
19    // Create a node pattern with 3 edges.
20    let a = Node {
21        color: 0,
22        self_connected: false,
23        edges: vec![Constraint {edge: EDGE, node: 0}; 3]
24    };
25
26    // Add 8 vertices.
27    for _ in 0..8 {g.push(a.clone())}
28    g.no_triangles = true;
29
30    let solve_settings = SolveSettings::new();
31    if let Some(solution) = g.solve(solve_settings) {
32        println!("{}", solution.puzzle.graphviz(
33            "sfdp",
34            &["black"],
35            &["black"]
36        ));
37    } else {
38        eprintln!("<no solution>");
39    }
40}
examples/square2.rs (line 17)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![Constraint {edge: SOLID, node: 0}; 2]
14    };
15
16    // Add 4 nodes.
17    for _ in 0..4 {g.push(a.clone())}
18
19    let solve_settings = SolveSettings::new()
20        .debug(true).sleep_ms(2000);
21    if let Some(solution) = g.solve(solve_settings) {
22        // Prints:
23        // 0 0 0 0
24        // ========================================
25        // 0 2 1 0
26        // 2 0 0 1
27        // 1 0 0 2
28        // 0 1 2 0
29        solution.puzzle.print();
30    }
31}
examples/hexagon.rs (line 19)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![
14            Constraint {edge: EDGE, node: 0},
15            Constraint {edge: EDGE, node: 0},
16        ]
17    };
18
19    for _ in 0..6 {g.push(a.clone())}
20    g.push_pair((2, 3));
21
22    let solve_settings = SolveSettings::new();
23    if let Some(solution) = g.solve(solve_settings) {
24        // solution.puzzle.print();
25        println!("{}", solution.puzzle.graphviz(
26            "sfdp",
27            &["black,fontcolor=white"],
28            &["black"]
29        ));
30    }
31}
Additional examples can be found in:
Source

pub fn push_pair(&mut self, (i, j): (usize, usize))

Adds a pair constraint.

Examples found in repository?
examples/hexagon.rs (line 20)
6fn main() {
7    let mut g = Graph::new();
8
9    // Create a node pattern.
10    let a = Node {
11        color: 0,
12        self_connected: false,
13        edges: vec![
14            Constraint {edge: EDGE, node: 0},
15            Constraint {edge: EDGE, node: 0},
16        ]
17    };
18
19    for _ in 0..6 {g.push(a.clone())}
20    g.push_pair((2, 3));
21
22    let solve_settings = SolveSettings::new();
23    if let Some(solution) = g.solve(solve_settings) {
24        // solution.puzzle.print();
25        println!("{}", solution.puzzle.graphviz(
26            "sfdp",
27            &["black,fontcolor=white"],
28            &["black"]
29        ));
30    }
31}
Source

pub fn node_satisfied(&self, i: usize) -> Vec<Constraint>

Returns a list of edge constraints that makes a node unsatisfied.

If the returned list is empty, then the node is satisfied.

Source

pub fn all_satisfied(&self) -> bool

Returns true if all nodes are satisfied.

Source

pub fn pairs_satisfied(&self) -> bool

Returns true if all pair constraints are satisfied.

Source

pub fn has_triangles(&self) -> bool

Returns whether the graph contains triangles.

Source

pub fn meet_quad_satisfied(&self) -> bool

Returns true when for any node, the greatest shortest cycle is either 3 or 4.

Source

pub fn commute_quad_satisfied(&self, commute: bool) -> bool

Returns true when for any quad, the commute property is satisfied.

For more information, see Graph::commute.

Source

pub fn is_connected(&self) -> bool

Returns true if all nodes can be reached from any node.

Source

pub fn is_upper_right_disconnected(&self) -> bool

Returns true if no-edges covers the upper right rectangle of the matrix form.

This means that the graph will be disconnected.

Source

pub fn colors(&self, (i, j): (usize, usize)) -> Vec<Color> ⓘ

Returns a list of possible actions for a node.

Trait Implementations§

Source§

impl Clone for Graph

Source§

fn clone(&self) -> Graph

Returns a copy of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for Graph

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl Default for Graph

Source§

fn default() -> Graph

Returns the “default value” for a type. Read more
Source§

impl Puzzle for Graph

Source§

type Pos = (usize, usize)

The type of position.
Source§

type Val = u64

The type of values stored in the puzzle.
Source§

fn set(&mut self, (i, j): (usize, usize), val: Color)

Sets a value at position.
Source§

fn get(&self, (i, j): (usize, usize)) -> Color

Gets value at position.
Source§

fn print(&self)

Print puzzle out to standard output.
Source§

fn solve_simple<F: FnMut(&mut Self, Self::Pos, Self::Val)>(&mut self, f: F)

Solve simple stuff faster. This will reduce the number of steps in solution. If you do not know how to solve this, leave it empty. Read more
Source§

fn is_solved(&self) -> bool

Whether puzzle is solved.
Source§

fn remove(&mut self, other: &Graph)

Removes values from other puzzle to show changes.

Auto Trait Implementations§

§

impl !Freeze for Graph

§

impl !RefUnwindSafe for Graph

§

impl Send for Graph

§

impl !Sync for Graph

§

impl Unpin for Graph

§

impl UnwindSafe for Graph

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.