Skip to content

Undirected Graph

1
graph(edges);

example_graph_1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cmath>
#include <matplot/matplot.h>

std::vector<std::pair<size_t, size_t>> get_edges();

int main() {
    using namespace matplot;
    auto edges = get_edges();
    graph(edges);

    show();
    return 0;
}

std::vector<std::pair<size_t, size_t>> get_edges() {
    return {
        {0, 0},   {1, 0},   {5, 0},   {0, 1},   {1, 1},   {2, 1},   {6, 1},
        {1, 2},   {2, 2},   {3, 2},   {7, 2},   {2, 3},   {3, 3},   {4, 3},
        {8, 3},   {3, 4},   {4, 4},   {9, 4},   {0, 5},   {5, 5},   {6, 5},
        {10, 5},  {1, 6},   {5, 6},   {6, 6},   {7, 6},   {11, 6},  {2, 7},
        {6, 7},   {7, 7},   {8, 7},   {12, 7},  {3, 8},   {7, 8},   {8, 8},
        {9, 8},   {13, 8},  {4, 9},   {8, 9},   {9, 9},   {14, 9},  {5, 10},
        {10, 10}, {11, 10}, {15, 10}, {6, 11},  {10, 11}, {11, 11}, {12, 11},
        {16, 11}, {7, 12},  {11, 12}, {12, 12}, {13, 12}, {17, 12}, {8, 13},
        {12, 13}, {13, 13}, {14, 13}, {18, 13}, {9, 14},  {13, 14}, {14, 14},
        {19, 14}, {10, 15}, {15, 15}, {16, 15}, {20, 15}, {11, 16}, {15, 16},
        {16, 16}, {17, 16}, {21, 16}, {12, 17}, {16, 17}, {17, 17}, {18, 17},
        {22, 17}, {13, 18}, {17, 18}, {18, 18}, {19, 18}, {23, 18}, {14, 19},
        {18, 19}, {19, 19}, {24, 19}, {15, 20}, {20, 20}, {21, 20}, {25, 20},
        {16, 21}, {20, 21}, {21, 21}, {22, 21}, {26, 21}, {17, 22}, {21, 22},
        {22, 22}, {23, 22}, {27, 22}, {18, 23}, {22, 23}, {23, 23}, {24, 23},
        {28, 23}, {19, 24}, {23, 24}, {24, 24}, {29, 24}, {20, 25}, {25, 25},
        {26, 25}, {35, 25}, {21, 26}, {25, 26}, {26, 26}, {27, 26}, {36, 26},
        {22, 27}, {26, 27}, {27, 27}, {28, 27}, {37, 27}, {23, 28}, {27, 28},
        {28, 28}, {29, 28}, {38, 28}, {24, 29}, {28, 29}, {29, 29}, {30, 29},
        {39, 29}, {29, 30}, {30, 30}, {31, 30}, {40, 30}, {30, 31}, {31, 31},
        {32, 31}, {41, 31}, {31, 32}, {32, 32}, {33, 32}, {42, 32}, {32, 33},
        {33, 33}, {34, 33}, {43, 33}, {33, 34}, {34, 34}, {44, 34}, {25, 35},
        {35, 35}, {36, 35}, {45, 35}, {26, 36}, {35, 36}, {36, 36}, {37, 36},
        {46, 36}, {27, 37}, {36, 37}, {37, 37}, {38, 37}, {47, 37}, {28, 38},
        {37, 38}, {38, 38}, {39, 38}, {48, 38}, {29, 39}, {38, 39}, {39, 39},
        {40, 39}, {49, 39}, {30, 40}, {39, 40}, {40, 40}, {41, 40}, {50, 40},
        {31, 41}, {40, 41}, {41, 41}, {42, 41}, {51, 41}, {32, 42}, {41, 42},
        {42, 42}, {43, 42}, {52, 42}, {33, 43}, {42, 43}, {43, 43}, {44, 43},
        {53, 43}, {34, 44}, {43, 44}, {44, 44}, {54, 44}, {35, 45}, {45, 45},
        {46, 45}, {55, 45}, {36, 46}, {45, 46}, {46, 46}, {47, 46}, {56, 46},
        {37, 47}, {46, 47}, {47, 47}, {48, 47}, {57, 47}, {38, 48}, {47, 48},
        {48, 48}, {49, 48}, {58, 48}, {39, 49}, {48, 49}, {49, 49}, {50, 49},
        {59, 49}, {40, 50}, {49, 50}, {50, 50}, {51, 50}, {60, 50}, {41, 51},
        {50, 51}, {51, 51}, {52, 51}, {61, 51}, {42, 52}, {51, 52}, {52, 52},
        {53, 52}, {62, 52}, {43, 53}, {52, 53}, {53, 53}, {54, 53}, {63, 53},
        {44, 54}, {53, 54}, {54, 54}, {64, 54}, {45, 55}, {55, 55}, {56, 55},
        {65, 55}, {46, 56}, {55, 56}, {56, 56}, {57, 56}, {66, 56}, {47, 57},
        {56, 57}, {57, 57}, {58, 57}, {67, 57}, {48, 58}, {57, 58}, {58, 58},
        {59, 58}, {68, 58}, {49, 59}, {58, 59}, {59, 59}, {60, 59}, {69, 59},
        {50, 60}, {59, 60}, {60, 60}, {61, 60}, {70, 60}, {51, 61}, {60, 61},
        {61, 61}, {62, 61}, {71, 61}, {52, 62}, {61, 62}, {62, 62}, {63, 62},
        {72, 62}, {53, 63}, {62, 63}, {63, 63}, {64, 63}, {73, 63}, {54, 64},
        {63, 64}, {64, 64}, {74, 64}, {55, 65}, {65, 65}, {66, 65}, {56, 66},
        {65, 66}, {66, 66}, {67, 66}, {57, 67}, {66, 67}, {67, 67}, {68, 67},
        {58, 68}, {67, 68}, {68, 68}, {69, 68}, {59, 69}, {68, 69}, {69, 69},
        {70, 69}, {60, 70}, {69, 70}, {70, 70}, {71, 70}, {61, 71}, {70, 71},
        {71, 71}, {72, 71}, {62, 72}, {71, 72}, {72, 72}, {73, 72}, {63, 73},
        {72, 73}, {73, 73}, {74, 73}, {64, 74}, {73, 74}, {74, 74}};
}

More examples

example_graph_2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cmath>
#include <matplot/matplot.h>

std::vector<std::pair<size_t, size_t>> get_edges();

int main() {
    using namespace matplot;
    auto edges = get_edges();
    graph(edges, "-.dr")->show_labels(false);

    show();
    return 0;
}

std::vector<std::pair<size_t, size_t>> get_edges() {
    return {
        {0, 1},   {0, 4},   {0, 5},   {1, 2},   {1, 10},  {2, 3},   {2, 15},
        {3, 4},   {3, 20},  {4, 25},  {5, 6},   {5, 9},   {6, 7},   {6, 29},
        {7, 8},   {7, 41},  {8, 9},   {8, 37},  {9, 11},  {10, 11}, {10, 14},
        {11, 12}, {12, 13}, {12, 36}, {13, 14}, {13, 32}, {14, 16}, {15, 16},
        {15, 19}, {16, 17}, {17, 18}, {17, 31}, {18, 19}, {18, 52}, {19, 21},
        {20, 21}, {20, 24}, {21, 22}, {22, 23}, {22, 51}, {23, 24}, {23, 47},
        {24, 26}, {25, 26}, {25, 29}, {26, 27}, {27, 28}, {27, 46}, {28, 29},
        {28, 42}, {30, 31}, {30, 34}, {30, 53}, {31, 32}, {32, 33}, {33, 34},
        {33, 35}, {34, 55}, {35, 36}, {35, 39}, {36, 37}, {37, 38}, {38, 39},
        {38, 40}, {39, 56}, {40, 41}, {40, 44}, {41, 42}, {42, 43}, {43, 44},
        {43, 45}, {44, 57}, {45, 46}, {45, 49}, {46, 47}, {47, 48}, {48, 49},
        {48, 50}, {49, 58}, {50, 51}, {50, 54}, {51, 52}, {52, 53}, {53, 54},
        {54, 59}, {55, 56}, {55, 59}, {56, 57}, {57, 58}, {58, 59}};
}

example_graph_3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cmath>
#include <matplot/matplot.h>

int main() {
    using namespace matplot;
    std::vector<std::pair<size_t, size_t>> edges = {
        {0, 1}, {0, 2},  {0, 3}, {0, 4}, {0, 6},  {0, 9}, {1, 5},
        {1, 6}, {2, 5},  {2, 9}, {3, 7}, {3, 9},  {4, 6}, {4, 7},
        {5, 8}, {5, 10}, {6, 8}, {7, 8}, {7, 10}, {9, 10}};
    std::vector<double> weights = {1, 1, 1, 1, 3, 3, 2,  4,  1,  6,
                                   2, 8, 8, 9, 3, 2, 10, 12, 15, 16};
    auto g = graph(edges);

    g->x_data({0, 0.5, -0.5, -0.5, 0.5, 0, 1.5, 0, 2, -1.5, -2});
    g->y_data({0, 0.5, 0.5, -0.5, -0.5, 2, 0, -2, 0, 0, 0});
    g->z_data({5, 3, 3, 3, 3, 0, 1, 0, 0, 1, 0});

    g->edge_labels(weights);
    view(2);

    show();
    return 0;
}

example_graph_4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <cmath>
#include <matplot/matplot.h>

int main() {
    using namespace matplot;
    std::vector<std::pair<size_t, size_t>> edges = {
        {0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 5},
        {2, 5}, {3, 4}, {3, 6}, {4, 6}, {5, 6}};
    std::vector<double> weights = {50, 10, 20, 80, 90, 90, 30, 20, 100, 40, 60};
    auto g = graph(edges);
    g->edge_labels(weights);

    double m_weight = max(weights);
    std::vector<double> line_widths =
        transform(weights, [&](double w) { return 5. * w / m_weight; });
    g->line_widths(line_widths);

    show();
    return 0;
}

example_graph_5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <matplot/matplot.h>
#include <thread>

std::vector<std::pair<size_t, size_t>> get_edges();

int main() {
    using namespace matplot;
    auto edges = get_edges();
    auto g = graph(edges);
    g->layout_algorithm(network::layout::force);

    for (int i = 0; i < 300; ++i) {
        g->layout_iterations(i);
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }

    show();
    return 0;
}

std::vector<std::pair<size_t, size_t>> get_edges() {
    return {
        {0, 0},   {1, 0},   {5, 0},   {0, 1},   {1, 1},   {2, 1},   {6, 1},
        {1, 2},   {2, 2},   {3, 2},   {7, 2},   {2, 3},   {3, 3},   {4, 3},
        {8, 3},   {3, 4},   {4, 4},   {9, 4},   {0, 5},   {5, 5},   {6, 5},
        {10, 5},  {1, 6},   {5, 6},   {6, 6},   {7, 6},   {11, 6},  {2, 7},
        {6, 7},   {7, 7},   {8, 7},   {12, 7},  {3, 8},   {7, 8},   {8, 8},
        {9, 8},   {13, 8},  {4, 9},   {8, 9},   {9, 9},   {14, 9},  {5, 10},
        {10, 10}, {11, 10}, {15, 10}, {6, 11},  {10, 11}, {11, 11}, {12, 11},
        {16, 11}, {7, 12},  {11, 12}, {12, 12}, {13, 12}, {17, 12}, {8, 13},
        {12, 13}, {13, 13}, {14, 13}, {18, 13}, {9, 14},  {13, 14}, {14, 14},
        {19, 14}, {10, 15}, {15, 15}, {16, 15}, {20, 15}, {11, 16}, {15, 16},
        {16, 16}, {17, 16}, {21, 16}, {12, 17}, {16, 17}, {17, 17}, {18, 17},
        {22, 17}, {13, 18}, {17, 18}, {18, 18}, {19, 18}, {23, 18}, {14, 19},
        {18, 19}, {19, 19}, {24, 19}, {15, 20}, {20, 20}, {21, 20}, {25, 20},
        {16, 21}, {20, 21}, {21, 21}, {22, 21}, {26, 21}, {17, 22}, {21, 22},
        {22, 22}, {23, 22}, {27, 22}, {18, 23}, {22, 23}, {23, 23}, {24, 23},
        {28, 23}, {19, 24}, {23, 24}, {24, 24}, {29, 24}, {20, 25}, {25, 25},
        {26, 25}, {35, 25}, {21, 26}, {25, 26}, {26, 26}, {27, 26}, {36, 26},
        {22, 27}, {26, 27}, {27, 27}, {28, 27}, {37, 27}, {23, 28}, {27, 28},
        {28, 28}, {29, 28}, {38, 28}, {24, 29}, {28, 29}, {29, 29}, {30, 29},
        {39, 29}, {29, 30}, {30, 30}, {31, 30}, {40, 30}, {30, 31}, {31, 31},
        {32, 31}, {41, 31}, {31, 32}, {32, 32}, {33, 32}, {42, 32}, {32, 33},
        {33, 33}, {34, 33}, {43, 33}, {33, 34}, {34, 34}, {44, 34}, {25, 35},
        {35, 35}, {36, 35}, {45, 35}, {26, 36}, {35, 36}, {36, 36}, {37, 36},
        {46, 36}, {27, 37}, {36, 37}, {37, 37}, {38, 37}, {47, 37}, {28, 38},
        {37, 38}, {38, 38}, {39, 38}, {48, 38}, {29, 39}, {38, 39}, {39, 39},
        {40, 39}, {49, 39}, {30, 40}, {39, 40}, {40, 40}, {41, 40}, {50, 40},
        {31, 41}, {40, 41}, {41, 41}, {42, 41}, {51, 41}, {32, 42}, {41, 42},
        {42, 42}, {43, 42}, {52, 42}, {33, 43}, {42, 43}, {43, 43}, {44, 43},
        {53, 43}, {34, 44}, {43, 44}, {44, 44}, {54, 44}, {35, 45}, {45, 45},
        {46, 45}, {55, 45}, {36, 46}, {45, 46}, {46, 46}, {47, 46}, {56, 46},
        {37, 47}, {46, 47}, {47, 47}, {48, 47}, {57, 47}, {38, 48}, {47, 48},
        {48, 48}, {49, 48}, {58, 48}, {39, 49}, {48, 49}, {49, 49}, {50, 49},
        {59, 49}, {40, 50}, {49, 50}, {50, 50}, {51, 50}, {60, 50}, {41, 51},
        {50, 51}, {51, 51}, {52, 51}, {61, 51}, {42, 52}, {51, 52}, {52, 52},
        {53, 52}, {62, 52}, {43, 53}, {52, 53}, {53, 53}, {54, 53}, {63, 53},
        {44, 54}, {53, 54}, {54, 54}, {64, 54}, {45, 55}, {55, 55}, {56, 55},
        {65, 55}, {46, 56}, {55, 56}, {56, 56}, {57, 56}, {66, 56}, {47, 57},
        {56, 57}, {57, 57}, {58, 57}, {67, 57}, {48, 58}, {57, 58}, {58, 58},
        {59, 58}, {68, 58}, {49, 59}, {58, 59}, {59, 59}, {60, 59}, {69, 59},
        {50, 60}, {59, 60}, {60, 60}, {61, 60}, {70, 60}, {51, 61}, {60, 61},
        {61, 61}, {62, 61}, {71, 61}, {52, 62}, {61, 62}, {62, 62}, {63, 62},
        {72, 62}, {53, 63}, {62, 63}, {63, 63}, {64, 63}, {73, 63}, {54, 64},
        {63, 64}, {64, 64}, {74, 64}, {55, 65}, {65, 65}, {66, 65}, {56, 66},
        {65, 66}, {66, 66}, {67, 66}, {57, 67}, {66, 67}, {67, 67}, {68, 67},
        {58, 68}, {67, 68}, {68, 68}, {69, 68}, {59, 69}, {68, 69}, {69, 69},
        {70, 69}, {60, 70}, {69, 70}, {70, 70}, {71, 70}, {61, 71}, {70, 71},
        {71, 71}, {72, 71}, {62, 72}, {71, 72}, {72, 72}, {73, 72}, {63, 73},
        {72, 73}, {73, 73}, {74, 73}, {64, 74}, {73, 74}, {74, 74}};
}

All these subcategories depend on the network class. Graphs are abstract structures that represent objects and relationships between these objects. The objects are represented as vertices and the relationships are depicted as edges.

In an abstract graph, the vertices have no specific position in space. Mathematically, a graph does not depend on its layout. However, the graph layout has a large impact on its understandability. The network class can calculate appropriate positions for graph vertices with several algorithms: Kamada Kawai algorithm, Fruchterman-Reingold algorithm, circle layout, random layout, and automatic layout.

The implementation of the Kamada Kawai and Fruchterman-Reingold algorithms depend on the NodeSoup library. The automatic layout uses the Kamada Kawai algorithm for small graphs and the Fruchterman-Reingold algorithm for larger graphs.