CODEWITHSUNDEEP
graphadjacency-list
andrescr94
andrescr94

Reputation: 57

How to code adjacency lists in a dodecahedron graph?

It has:

20 vertices 30 edges G{20,30}

How can you generate the adjacency lists for each vertex 1,2,...20? V1 is linked with 2 and 3 v2 is linked with 1 and 4 v3 is linked with 1 and 5 ??

Is there like a formula? This is for a game project, don't know if I missed a math class or something? What should I study to understand the solution?

Upvotes: 1

Views: 420

Answers (2)

andrescr94
andrescr94

Reputation: 57

Manually constructed:

int adjs[] = { 1, 4, 7, 0, 2, 9, 1, 3, 11, 2, 4, 13, 0, 3, 5, 4, 6, 14, 5, 7, 16, 0, 6, 8, 7, 9, 17, 1, 8, 10, 9, 11, 18, 2, 10, 12, 11, 13, 19, 3, 12, 14, 5, 13, 15, 14, 16, 19, 6, 15, 17, 8, 16, 18, 10, 17, 19, 12, 15, 18 };

for (int i = 0, int j = 0; i < 20; i++, j = i * 3) {
    caves[i] = Cave(i);
    for (int c = j; c < j + 3; c++) {
        caves[i].adjsListy.addAdj(adjs[c]);
    }

I found help in the solution here: https://rosettacode.org/wiki/Hunt_The_Wumpus/C%2B%2B

Upvotes: 1

visibleman
visibleman

Reputation: 3315

I think the link list is usually manually constructed. However you can take a look at the special case of a 2:1 pyritohedron in https://en.wikipedia.org/wiki/Dodecahedron to get an understanding of how to go from a cube to a dodecahedron. (Also take a look at the animated gif in the section "Cartesian Coordinates")

What this tells us is that a dodecahedron can be constructed by inserting new vertices bisecting each of the cubes 12 edges. Then insert new edges connecting these new vertices such that they bisect each face of the 6 faces of the cube in alternating directions.

I think this understanding can be helpful, either for constructing an algorithm, or just to help you construct a manual link list.

This of-course only takes care of the vertex-links, to find the coordinates of each vertex, see e.g. How to generate/calculate vertices of dodecahedron?

Upvotes: 0

Related Questions