adjacency_graphs.cpp

Go to the documentation of this file.

// generated by scripts/build_keyboard_adjacency_graphs.py
#include <zxcvbn/adjacency_graphs.hpp>
 
#include <zxcvbn/optional.hpp>
 
#include <array>
#include <initializer_list>
#include <utility>
 
namespace zxcvbn {
 
static
optional::optional<std::string> M(const char *s) {
  return optional::make_optional(std::string(s));
}
 
const auto no = optional::nullopt;
 
const Graphs _graphs = {
  {GraphTag::QWERTY, {
    {"!", {M("`~"), no, no, M("2@"), M("qQ"), no}},
    {"\"", {M(";:"), M("[{"), M("]}"), no, no, M("/?")}},
    {"#", {M("2@"), no, no, M("4$"), M("eE"), M("wW")}},
    {"$", {M("3#"), no, no, M("5%"), M("rR"), M("eE")}},
    {"%", {M("4$"), no, no, M("6^"), M("tT"), M("rR")}},
    {"&", {M("6^"), no, no, M("8*"), M("uU"), M("yY")}},
    {"'", {M(";:"), M("[{"), M("]}"), no, no, M("/?")}},
    {"(", {M("8*"), no, no, M("0)"), M("oO"), M("iI")}},
    {")", {M("9("), no, no, M("-_"), M("pP"), M("oO")}},
    {"*", {M("7&"), no, no, M("9("), M("iI"), M("uU")}},
    {"+", {M("-_"), no, no, no, M("]}"), M("[{")}},
    {",", {M("mM"), M("kK"), M("lL"), M(".>"), no, no}},
    {"-", {M("0)"), no, no, M("=+"), M("[{"), M("pP")}},
    {".", {M(",<"), M("lL"), M(";:"), M("/?"), no, no}},
    {"/", {M(".>"), M(";:"), M("'\""), no, no, no}},
    {"0", {M("9("), no, no, M("-_"), M("pP"), M("oO")}},
    {"1", {M("`~"), no, no, M("2@"), M("qQ"), no}},
    {"2", {M("1!"), no, no, M("3#"), M("wW"), M("qQ")}},
    {"3", {M("2@"), no, no, M("4$"), M("eE"), M("wW")}},
    {"4", {M("3#"), no, no, M("5%"), M("rR"), M("eE")}},
    {"5", {M("4$"), no, no, M("6^"), M("tT"), M("rR")}},
    {"6", {M("5%"), no, no, M("7&"), M("yY"), M("tT")}},
    {"7", {M("6^"), no, no, M("8*"), M("uU"), M("yY")}},
    {"8", {M("7&"), no, no, M("9("), M("iI"), M("uU")}},
    {"9", {M("8*"), no, no, M("0)"), M("oO"), M("iI")}},
    {":", {M("lL"), M("pP"), M("[{"), M("'\""), M("/?"), M(".>")}},
    {";", {M("lL"), M("pP"), M("[{"), M("'\""), M("/?"), M(".>")}},
    {"<", {M("mM"), M("kK"), M("lL"), M(".>"), no, no}},
    {"=", {M("-_"), no, no, no, M("]}"), M("[{")}},
    {">", {M(",<"), M("lL"), M(";:"), M("/?"), no, no}},
    {"?", {M(".>"), M(";:"), M("'\""), no, no, no}},
    {"@", {M("1!"), no, no, M("3#"), M("wW"), M("qQ")}},
    {"A", {no, M("qQ"), M("wW"), M("sS"), M("zZ"), no}},
    {"B", {M("vV"), M("gG"), M("hH"), M("nN"), no, no}},
    {"C", {M("xX"), M("dD"), M("fF"), M("vV"), no, no}},
    {"D", {M("sS"), M("eE"), M("rR"), M("fF"), M("cC"), M("xX")}},
    {"E", {M("wW"), M("3#"), M("4$"), M("rR"), M("dD"), M("sS")}},
    {"F", {M("dD"), M("rR"), M("tT"), M("gG"), M("vV"), M("cC")}},
    {"G", {M("fF"), M("tT"), M("yY"), M("hH"), M("bB"), M("vV")}},
    {"H", {M("gG"), M("yY"), M("uU"), M("jJ"), M("nN"), M("bB")}},
    {"I", {M("uU"), M("8*"), M("9("), M("oO"), M("kK"), M("jJ")}},
    {"J", {M("hH"), M("uU"), M("iI"), M("kK"), M("mM"), M("nN")}},
    {"K", {M("jJ"), M("iI"), M("oO"), M("lL"), M(",<"), M("mM")}},
    {"L", {M("kK"), M("oO"), M("pP"), M(";:"), M(".>"), M(",<")}},
    {"M", {M("nN"), M("jJ"), M("kK"), M(",<"), no, no}},
    {"N", {M("bB"), M("hH"), M("jJ"), M("mM"), no, no}},
    {"O", {M("iI"), M("9("), M("0)"), M("pP"), M("lL"), M("kK")}},
    {"P", {M("oO"), M("0)"), M("-_"), M("[{"), M(";:"), M("lL")}},
    {"Q", {no, M("1!"), M("2@"), M("wW"), M("aA"), no}},
    {"R", {M("eE"), M("4$"), M("5%"), M("tT"), M("fF"), M("dD")}},
    {"S", {M("aA"), M("wW"), M("eE"), M("dD"), M("xX"), M("zZ")}},
    {"T", {M("rR"), M("5%"), M("6^"), M("yY"), M("gG"), M("fF")}},
    {"U", {M("yY"), M("7&"), M("8*"), M("iI"), M("jJ"), M("hH")}},
    {"V", {M("cC"), M("fF"), M("gG"), M("bB"), no, no}},
    {"W", {M("qQ"), M("2@"), M("3#"), M("eE"), M("sS"), M("aA")}},
    {"X", {M("zZ"), M("sS"), M("dD"), M("cC"), no, no}},
    {"Y", {M("tT"), M("6^"), M("7&"), M("uU"), M("hH"), M("gG")}},
    {"Z", {no, M("aA"), M("sS"), M("xX"), no, no}},
    {"[", {M("pP"), M("-_"), M("=+"), M("]}"), M("'\""), M(";:")}},
    {"\\", {M("]}"), no, no, no, no, no}},
    {"]", {M("[{"), M("=+"), no, M("\\|"), no, M("'\"")}},
    {"^", {M("5%"), no, no, M("7&"), M("yY"), M("tT")}},
    {"_", {M("0)"), no, no, M("=+"), M("[{"), M("pP")}},
    {"`", {no, no, no, M("1!"), no, no}},
    {"a", {no, M("qQ"), M("wW"), M("sS"), M("zZ"), no}},
    {"b", {M("vV"), M("gG"), M("hH"), M("nN"), no, no}},
    {"c", {M("xX"), M("dD"), M("fF"), M("vV"), no, no}},
    {"d", {M("sS"), M("eE"), M("rR"), M("fF"), M("cC"), M("xX")}},
    {"e", {M("wW"), M("3#"), M("4$"), M("rR"), M("dD"), M("sS")}},
    {"f", {M("dD"), M("rR"), M("tT"), M("gG"), M("vV"), M("cC")}},
    {"g", {M("fF"), M("tT"), M("yY"), M("hH"), M("bB"), M("vV")}},
    {"h", {M("gG"), M("yY"), M("uU"), M("jJ"), M("nN"), M("bB")}},
    {"i", {M("uU"), M("8*"), M("9("), M("oO"), M("kK"), M("jJ")}},
    {"j", {M("hH"), M("uU"), M("iI"), M("kK"), M("mM"), M("nN")}},
    {"k", {M("jJ"), M("iI"), M("oO"), M("lL"), M(",<"), M("mM")}},
    {"l", {M("kK"), M("oO"), M("pP"), M(";:"), M(".>"), M(",<")}},
    {"m", {M("nN"), M("jJ"), M("kK"), M(",<"), no, no}},
    {"n", {M("bB"), M("hH"), M("jJ"), M("mM"), no, no}},
    {"o", {M("iI"), M("9("), M("0)"), M("pP"), M("lL"), M("kK")}},
    {"p", {M("oO"), M("0)"), M("-_"), M("[{"), M(";:"), M("lL")}},
    {"q", {no, M("1!"), M("2@"), M("wW"), M("aA"), no}},
    {"r", {M("eE"), M("4$"), M("5%"), M("tT"), M("fF"), M("dD")}},
    {"s", {M("aA"), M("wW"), M("eE"), M("dD"), M("xX"), M("zZ")}},
    {"t", {M("rR"), M("5%"), M("6^"), M("yY"), M("gG"), M("fF")}},
    {"u", {M("yY"), M("7&"), M("8*"), M("iI"), M("jJ"), M("hH")}},
    {"v", {M("cC"), M("fF"), M("gG"), M("bB"), no, no}},
    {"w", {M("qQ"), M("2@"), M("3#"), M("eE"), M("sS"), M("aA")}},
    {"x", {M("zZ"), M("sS"), M("dD"), M("cC"), no, no}},
    {"y", {M("tT"), M("6^"), M("7&"), M("uU"), M("hH"), M("gG")}},
    {"z", {no, M("aA"), M("sS"), M("xX"), no, no}},
    {"{", {M("pP"), M("-_"), M("=+"), M("]}"), M("'\""), M(";:")}},
    {"|", {M("]}"), no, no, no, no, no}},
    {"}", {M("[{"), M("=+"), no, M("\\|"), no, M("'\"")}},
    {"~", {no, no, no, M("1!"), no, no}},
  }},
  {GraphTag::DVORAK, {
    {"!", {M("`~"), no, no, M("2@"), M("'\""), no}},
    {"\"", {no, M("1!"), M("2@"), M(",<"), M("aA"), no}},
    {"#", {M("2@"), no, no, M("4$"), M(".>"), M(",<")}},
    {"$", {M("3#"), no, no, M("5%"), M("pP"), M(".>")}},
    {"%", {M("4$"), no, no, M("6^"), M("yY"), M("pP")}},
    {"&", {M("6^"), no, no, M("8*"), M("gG"), M("fF")}},
    {"'", {no, M("1!"), M("2@"), M(",<"), M("aA"), no}},
    {"(", {M("8*"), no, no, M("0)"), M("rR"), M("cC")}},
    {")", {M("9("), no, no, M("[{"), M("lL"), M("rR")}},
    {"*", {M("7&"), no, no, M("9("), M("cC"), M("gG")}},
    {"+", {M("/?"), M("]}"), no, M("\\|"), no, M("-_")}},
    {",", {M("'\""), M("2@"), M("3#"), M(".>"), M("oO"), M("aA")}},
    {"-", {M("sS"), M("/?"), M("=+"), no, no, M("zZ")}},
    {".", {M(",<"), M("3#"), M("4$"), M("pP"), M("eE"), M("oO")}},
    {"/", {M("lL"), M("[{"), M("]}"), M("=+"), M("-_"), M("sS")}},
    {"0", {M("9("), no, no, M("[{"), M("lL"), M("rR")}},
    {"1", {M("`~"), no, no, M("2@"), M("'\""), no}},
    {"2", {M("1!"), no, no, M("3#"), M(",<"), M("'\"")}},
    {"3", {M("2@"), no, no, M("4$"), M(".>"), M(",<")}},
    {"4", {M("3#"), no, no, M("5%"), M("pP"), M(".>")}},
    {"5", {M("4$"), no, no, M("6^"), M("yY"), M("pP")}},
    {"6", {M("5%"), no, no, M("7&"), M("fF"), M("yY")}},
    {"7", {M("6^"), no, no, M("8*"), M("gG"), M("fF")}},
    {"8", {M("7&"), no, no, M("9("), M("cC"), M("gG")}},
    {"9", {M("8*"), no, no, M("0)"), M("rR"), M("cC")}},
    {":", {no, M("aA"), M("oO"), M("qQ"), no, no}},
    {";", {no, M("aA"), M("oO"), M("qQ"), no, no}},
    {"<", {M("'\""), M("2@"), M("3#"), M(".>"), M("oO"), M("aA")}},
    {"=", {M("/?"), M("]}"), no, M("\\|"), no, M("-_")}},
    {">", {M(",<"), M("3#"), M("4$"), M("pP"), M("eE"), M("oO")}},
    {"?", {M("lL"), M("[{"), M("]}"), M("=+"), M("-_"), M("sS")}},
    {"@", {M("1!"), no, no, M("3#"), M(",<"), M("'\"")}},
    {"A", {no, M("'\""), M(",<"), M("oO"), M(";:"), no}},
    {"B", {M("xX"), M("dD"), M("hH"), M("mM"), no, no}},
    {"C", {M("gG"), M("8*"), M("9("), M("rR"), M("tT"), M("hH")}},
    {"D", {M("iI"), M("fF"), M("gG"), M("hH"), M("bB"), M("xX")}},
    {"E", {M("oO"), M(".>"), M("pP"), M("uU"), M("jJ"), M("qQ")}},
    {"F", {M("yY"), M("6^"), M("7&"), M("gG"), M("dD"), M("iI")}},
    {"G", {M("fF"), M("7&"), M("8*"), M("cC"), M("hH"), M("dD")}},
    {"H", {M("dD"), M("gG"), M("cC"), M("tT"), M("mM"), M("bB")}},
    {"I", {M("uU"), M("yY"), M("fF"), M("dD"), M("xX"), M("kK")}},
    {"J", {M("qQ"), M("eE"), M("uU"), M("kK"), no, no}},
    {"K", {M("jJ"), M("uU"), M("iI"), M("xX"), no, no}},
    {"L", {M("rR"), M("0)"), M("[{"), M("/?"), M("sS"), M("nN")}},
    {"M", {M("bB"), M("hH"), M("tT"), M("wW"), no, no}},
    {"N", {M("tT"), M("rR"), M("lL"), M("sS"), M("vV"), M("wW")}},
    {"O", {M("aA"), M(",<"), M(".>"), M("eE"), M("qQ"), M(";:")}},
    {"P", {M(".>"), M("4$"), M("5%"), M("yY"), M("uU"), M("eE")}},
    {"Q", {M(";:"), M("oO"), M("eE"), M("jJ"), no, no}},
    {"R", {M("cC"), M("9("), M("0)"), M("lL"), M("nN"), M("tT")}},
    {"S", {M("nN"), M("lL"), M("/?"), M("-_"), M("zZ"), M("vV")}},
    {"T", {M("hH"), M("cC"), M("rR"), M("nN"), M("wW"), M("mM")}},
    {"U", {M("eE"), M("pP"), M("yY"), M("iI"), M("kK"), M("jJ")}},
    {"V", {M("wW"), M("nN"), M("sS"), M("zZ"), no, no}},
    {"W", {M("mM"), M("tT"), M("nN"), M("vV"), no, no}},
    {"X", {M("kK"), M("iI"), M("dD"), M("bB"), no, no}},
    {"Y", {M("pP"), M("5%"), M("6^"), M("fF"), M("iI"), M("uU")}},
    {"Z", {M("vV"), M("sS"), M("-_"), no, no, no}},
    {"[", {M("0)"), no, no, M("]}"), M("/?"), M("lL")}},
    {"\\", {M("=+"), no, no, no, no, no}},
    {"]", {M("[{"), no, no, no, M("=+"), M("/?")}},
    {"^", {M("5%"), no, no, M("7&"), M("fF"), M("yY")}},
    {"_", {M("sS"), M("/?"), M("=+"), no, no, M("zZ")}},
    {"`", {no, no, no, M("1!"), no, no}},
    {"a", {no, M("'\""), M(",<"), M("oO"), M(";:"), no}},
    {"b", {M("xX"), M("dD"), M("hH"), M("mM"), no, no}},
    {"c", {M("gG"), M("8*"), M("9("), M("rR"), M("tT"), M("hH")}},
    {"d", {M("iI"), M("fF"), M("gG"), M("hH"), M("bB"), M("xX")}},
    {"e", {M("oO"), M(".>"), M("pP"), M("uU"), M("jJ"), M("qQ")}},
    {"f", {M("yY"), M("6^"), M("7&"), M("gG"), M("dD"), M("iI")}},
    {"g", {M("fF"), M("7&"), M("8*"), M("cC"), M("hH"), M("dD")}},
    {"h", {M("dD"), M("gG"), M("cC"), M("tT"), M("mM"), M("bB")}},
    {"i", {M("uU"), M("yY"), M("fF"), M("dD"), M("xX"), M("kK")}},
    {"j", {M("qQ"), M("eE"), M("uU"), M("kK"), no, no}},
    {"k", {M("jJ"), M("uU"), M("iI"), M("xX"), no, no}},
    {"l", {M("rR"), M("0)"), M("[{"), M("/?"), M("sS"), M("nN")}},
    {"m", {M("bB"), M("hH"), M("tT"), M("wW"), no, no}},
    {"n", {M("tT"), M("rR"), M("lL"), M("sS"), M("vV"), M("wW")}},
    {"o", {M("aA"), M(",<"), M(".>"), M("eE"), M("qQ"), M(";:")}},
    {"p", {M(".>"), M("4$"), M("5%"), M("yY"), M("uU"), M("eE")}},
    {"q", {M(";:"), M("oO"), M("eE"), M("jJ"), no, no}},
    {"r", {M("cC"), M("9("), M("0)"), M("lL"), M("nN"), M("tT")}},
    {"s", {M("nN"), M("lL"), M("/?"), M("-_"), M("zZ"), M("vV")}},
    {"t", {M("hH"), M("cC"), M("rR"), M("nN"), M("wW"), M("mM")}},
    {"u", {M("eE"), M("pP"), M("yY"), M("iI"), M("kK"), M("jJ")}},
    {"v", {M("wW"), M("nN"), M("sS"), M("zZ"), no, no}},
    {"w", {M("mM"), M("tT"), M("nN"), M("vV"), no, no}},
    {"x", {M("kK"), M("iI"), M("dD"), M("bB"), no, no}},
    {"y", {M("pP"), M("5%"), M("6^"), M("fF"), M("iI"), M("uU")}},
    {"z", {M("vV"), M("sS"), M("-_"), no, no, no}},
    {"{", {M("0)"), no, no, M("]}"), M("/?"), M("lL")}},
    {"|", {M("=+"), no, no, no, no, no}},
    {"}", {M("[{"), no, no, no, M("=+"), M("/?")}},
    {"~", {no, no, no, M("1!"), no, no}},
  }},
  {GraphTag::KEYPAD, {
    {"*", {M("/"), no, no, no, M("-"), M("+"), M("9"), M("8")}},
    {"+", {M("9"), M("*"), M("-"), no, no, no, no, M("6")}},
    {"-", {M("*"), no, no, no, no, no, M("+"), M("9")}},
    {".", {M("0"), M("2"), M("3"), no, no, no, no, no}},
    {"/", {no, no, no, no, M("*"), M("9"), M("8"), M("7")}},
    {"0", {no, M("1"), M("2"), M("3"), M("."), no, no, no}},
    {"1", {no, no, M("4"), M("5"), M("2"), M("0"), no, no}},
    {"2", {M("1"), M("4"), M("5"), M("6"), M("3"), M("."), M("0"), no}},
    {"3", {M("2"), M("5"), M("6"), no, no, no, M("."), M("0")}},
    {"4", {no, no, M("7"), M("8"), M("5"), M("2"), M("1"), no}},
    {"5", {M("4"), M("7"), M("8"), M("9"), M("6"), M("3"), M("2"), M("1")}},
    {"6", {M("5"), M("8"), M("9"), M("+"), no, no, M("3"), M("2")}},
    {"7", {no, no, no, M("/"), M("8"), M("5"), M("4"), no}},
    {"8", {M("7"), no, M("/"), M("*"), M("9"), M("6"), M("5"), M("4")}},
    {"9", {M("8"), M("/"), M("*"), M("-"), M("+"), no, M("6"), M("5")}},
  }},
  {GraphTag::MAC_KEYPAD, {
    {"*", {M("/"), no, no, no, no, no, M("-"), M("9")}},
    {"+", {M("6"), M("9"), M("-"), no, no, no, no, M("3")}},
    {"-", {M("9"), M("/"), M("*"), no, no, no, M("+"), M("6")}},
    {".", {M("0"), M("2"), M("3"), no, no, no, no, no}},
    {"/", {M("="), no, no, no, M("*"), M("-"), M("9"), M("8")}},
    {"0", {no, M("1"), M("2"), M("3"), M("."), no, no, no}},
    {"1", {no, no, M("4"), M("5"), M("2"), M("0"), no, no}},
    {"2", {M("1"), M("4"), M("5"), M("6"), M("3"), M("."), M("0"), no}},
    {"3", {M("2"), M("5"), M("6"), M("+"), no, no, M("."), M("0")}},
    {"4", {no, no, M("7"), M("8"), M("5"), M("2"), M("1"), no}},
    {"5", {M("4"), M("7"), M("8"), M("9"), M("6"), M("3"), M("2"), M("1")}},
    {"6", {M("5"), M("8"), M("9"), M("-"), M("+"), no, M("3"), M("2")}},
    {"7", {no, no, no, M("="), M("8"), M("5"), M("4"), no}},
    {"8", {M("7"), no, M("="), M("/"), M("9"), M("6"), M("5"), M("4")}},
    {"9", {M("8"), M("="), M("/"), M("*"), M("-"), M("+"), M("6"), M("5")}},
    {"=", {no, no, no, no, M("/"), M("9"), M("8"), M("7")}},
  }},
};
 
// on qwerty, 'g' has degree 6, being adjacent to 'ftyhbv'. '' has degree 1.
// this calculates the average over all keys.
static
degree_t calc_average_degree(const Graph & graph)  {
  degree_t average = 0;
  for (const auto & item : graph) {
    for (const auto & neighbor : item.second) {
        average += neighbor ? 1 : 0;
    }
  }
  average /= graph.size();
  return average;
}
 
extern const degree_t KEYBOARD_AVERAGE_DEGREE = calc_average_degree(_graphs.at(GraphTag::QWERTY));
// slightly different for keypad/mac keypad, but close enough
extern const degree_t KEYPAD_AVERAGE_DEGREE = calc_average_degree(_graphs.at(GraphTag::KEYPAD));
 
extern const std::size_t KEYBOARD_STARTING_POSITIONS = _graphs.at(GraphTag::QWERTY).size();
extern const std::size_t KEYPAD_STARTING_POSITIONS = _graphs.at(GraphTag::KEYPAD).size();
 
const Graphs & graphs() {
  return _graphs;
}
 
}