Graphics algorithm (adjacency matrix)

preface

Recently, some friends in writing form linkage relationship is very complex, do not know where to start. In most cases, a nested structure will be required for the backend, but this structure has a fatal drawback: no upward linkage and a large amount of redundant data. Recommended the adjacencies matrix found a lot of students do not understand, write a simple popular science article to explain.

What is an adjacency matrix

Don’t ask inertia at the beginning of no why

An adjacency matrix is a data structure used to describe the relationship between vertices and edges. Its essence is a two-dimensional array, suitable for dealing with the relationship between the smallest data units. There are two modes of adjacencies: undirected and directed. The main characteristic of undirected graph is that it does not indicate that directional points can flow bidirectionally, while directed graph contains both unidirectional and bidirectional points. They are mainly used in graphic scenarios such as mazes, simple maps, cascading forms, etc

Undirected graph

describe

Undirected graph: Refers to the point to the point of the associated edges have no direction restrictions. We can go back and forth between two points

Here’s an example:

The figure above is a simple relation between edges and points:

The top line where V0 is connected is v2, v3

The top line where V1 meets V1 is v3, v4

The top line that V2 is connected to is v0, v3, v4

The top line where V3 is connected is v0, v1, v2

The top line V4 is going to be v1, v2

What format does the above graph look like after being datalized by the adjacencies matrix?

const arr = [
// v0  v1  v2  v3  v4
   0,  0,  1,  1,  0, // v0
   0,  0,  0,  1,  1, // v1
   1,  0,  0,  1,  1, // v2
   1,  1,  1,  0,  0, // v3
   0,  1,  1,  0,  0, // v4
]Copy the code

The characteristics of

Several characteristics of undirected graphs:

• The length of the matrix must be lengt^2 squared of the number of vertices
• The hypotenuse of the matrix must have no value
• The matrix is symmetric by the hypotenuse

Simple implementation

After a brief introduction, we simply implement an adjacencies matrix undirected graph through JS

class Adjoin {
  constructor(vertex) {
    this.vertex = vertex;
    this.quantity = vertex.length;
    this.init();
  }

  init() {
    this.adjoinArray = Array.from({ length: this.quantity * this.quantity });
  }

  getVertexRow(id) {
    const index = this.vertex.indexOf(id);
    const col = [];
    this.vertex.forEach((item, pIndex) => {
      col.push(this.adjoinArray[index + this.quantity * pIndex]);
    });
    return col;
  }

  getAdjoinVertexs(id) {
    return this.getVertexRow(id).map((item, index) => (item ? this.vertex[index] : ' ')).filter(Boolean);
  }

  setAdjoinVertexs(id, sides) { const pIndex = this.vertex.indexOf(id); sides.forEach((item) => { const index = this.vertex.indexOf(item); this.adjoinArray[pIndex * this.quantity + index] = 1; }); } // Create matrix const demo = new Adjoin(['v0'.'v1'.'v2'.'v3'.'v4']) // Register the adjacent.demo.setadJoinVerTexs ('v0'['v2'.'v3']);
demo.setAdjoinVertexs('v1'['v3'.'v4']);
demo.setAdjoinVertexs('v2'['v0'.'v3'.'v4']);
demo.setAdjoinVertexs('v3'['v0'.'v1'.'v2']);
demo.setAdjoinVertexs('v4'['v1'.'v2']); / / print the console. The log (demo. GetAdjoinVertexs ('v0')); / / /'v2'.'v3']Copy the code

Application scenario: Linkage forms

After this brief introduction we should have a basic concept of the adjacencies matrix undirected graph. So how do we apply this to a real project. Below is a familiar Tmall order specification selection page, the sales page of the order page contains color, package type, storage capacity and other three key factors. And there is a correlation between the three key factors.

Analysis of the interaction

• When the user selects the color specification, all black-related options are illuminated
• The same specification option is also on
• When the user selects the package type, some of the specifications are illuminated under the public effect of the color and package

If you let the back end deliver a recursive tree structure 1: there is a lot of data hoarding. 2: The magnitude of transmitted data becomes larger. 3: Computing on the server increases the cost of the server.

Conventional data

const data = [
  { id: '1', specs: [ 'purple'.'Set meal one'.'64G' ] },
  { id: '2', specs: [ 'purple'.'Set meal one'.'128G' ] },
  { id: '3', specs: [ 'purple'.'Set Meal two'.'128G' ] },
  { id: '4', specs: [ 'black'.'Set meal three'.'256G']]}, const commoditySpecs = [ { title:The 'color', list: [ 'red'.'purple'.'white'.'black' ] },
  { title: 'package', list: [ 'Set meal one'.'Set Meal two'.'Set meal three'.'Set four' ]},
  { title: 'memory', list: [ '64G'.'128G'.'256G']}];Copy the code

CommoditySpecs are lazy, regular operation should be the concept of having goods in stock. The full delivery front end picks up all specifications on its own

I’m going to apply the undirected graph

It can be seen from the above data that all product data is a single product ID associated with different specifications. Then these specifications can be used as individual vertices. The combination of various specifications of a single product can be regarded as the association of various specifications. One thing to notice here is that in different scenarios

Ignore the sibling option

At the same level of the optional

Let’s try to explain the above interaction with an undirected graph

• Unselected state, all reachable vertices are clickable. (figure 1)
• After a vertex is selected, all options for the current vertex are found (Figure 2)
• When multiple vertices are selected, the alternative is the union of the adjacent points of each vertex (Figure 3).

Graph one:

Figure 2:

Figure 3:

Reachable >= number of vertices

Code implementation

class Adjoin {
  ********
  ****
  **
  getRowToatl(params) {
    params = params.map(id= > this.getVertexRow(id));
    const adjoinNames = [];
    this.vertex.forEach((item, index) = > {
      const rowtotal = params.map(value= > value[index]).reduce((total, current) = > {
        total += current || 0;
        return total;
      }, 0);
      adjoinNames.push(rowtotal);
    });
    return adjoinNames;
  }

  / / intersection
  getUnions(params) {
    const row = this.getRowToatl(params);
    return row.map((item, index) = > item >= params.length && this.vertex[index]).filter(Boolean);
  }

  / / and set
  getCollection(params) {
    params = this.getRowToatl(params);
    return params.map((item, index) = > item && this.vertex[index]).filter(Boolean); }}class ShopAdjoin extends Adjoin {
  constructor(commoditySpecs, data) {
    super(commoditySpecs.reduce((total, current) = > [
      ...total,
      ...current.list,
    ], []));
    this.commoditySpecs = commoditySpecs;
    this.data = data;
    // Create a single spec matrix
    this.initCommodity();
    // Create similar vertices
    this.initSimilar();
  }

  initCommodity() {
    this.data.forEach((item) = > {
      this.applyCommodity(item.specs);
    });
  }

  initSimilar() {
    // Get all options
    const specsOption = this.getCollection(this.vertex);
    this.commoditySpecs.forEach((item) = > {
      const params = [];
      item.list.forEach((value) = > {
        if (specsOption.indexOf(value) > - 1) params.push(value);
      });
      // Create at the same level
      this.applyCommodity(params);
    });
  }

  querySpecsOptions(params) {
    // Check whether an option exists
    if (params.some(Boolean)) {
      // Filter the options
      params = this.getUnions(params.filter(Boolean));
    } else {
      // Choose the bottom pocket
      params = this.getCollection(this.vertex);
    }
    return params;
  }

  applyCommodity(params) {
    params.forEach((param) = > {
      this.setAdjoinVertexs(param, params); }); }}export default function App({ data, commoditySpecs }) {
  const [specsS, setSpecsS] = useState(Array.from({ length: commoditySpecs.length }));
  // Create a shopping matrix
  const shopAdjoin = useMemo((a)= > new ShopAdjoin(commoditySpecs, data), [
    commoditySpecs,
    data,
  ]);
  // Get the option table
  const optionSpecs = shopAdjoin.querySpecsOptions(specsS);

  const handleClick = function (bool, text, index) {
    if(specsS[index] ! == text && ! bool)return;
    specsS[index] = specsS[index] === text ? ' ' : text;
    setSpecsS(specsS.slice());
  };

  return (
    <div className="container">
      {
        commoditySpecs.map(({ title, list }, index) => (
          <div key={index}>
            <h1>{title}</h1>
            <Flex wrap="wrap">
              {
                list.map((value, i) => (
                  <span
                    key={i}
                    className={classnames({
                      option: optionSpecs.indexOf(value) > -1,
                      active: specsS.indexOf(value) > -1,
                    })}
                    onClick={() => handleClick(optionSpecs.indexOf(value) > -1, value, index)}
                  >{value}
                  </span>))}</Flex>
          </div>))}</div>
  );
}Copy the code

Directed graph

describe

Directed graph: the connection between two points has a direction. It gives the concept of direction on the basis of undirected graphs. Its main application is maps

Here’s an example:

The figure above shows a simple edge-point relationship

The vertex that V0 goes to is v2

The vertex that V1 goes to is v4

The vertex that V2 goes to is v3

The vertex that V3 goes to is v0, v1

The vertex V4 goes to is v2, v3

What format does the above graph look like after being datalized by the adjacencies matrix?

const arr = [
// v0 v1 v2 v3 v4
   0.0.1.0.0.// v0
   0.0.0.0.1.// v1
   0.0.0.1.0.// v2
   1.1.0.0.0.// v3
   0.0.1.1.0.// v4
]Copy the code

The characteristics of

The degree of the ith vertex is the sum of the number of non-zero elements in row I and column I

• The length of the matrix must be lengt^2 squared of the number of vertices
• The hypotenuse of the matrix must have no value
• The number of non-zero elements in row I is the exit degree of the ith vertex
• The number of non-zero elements in column I is the input degree of the ith vertex

Link matrix algorithm

It is useful to show an application of undirected graphs above, but there is no example of a map application of directed graphs. Let’s start by looking at two key algorithms for the link matrix.

Depth-first algorithm

The depth-first algorithm starts from a point to traverse the whole graph, accesses its nearest node first and continues to access the last unvisited node along a unilateral path, and then returns to the original path and explores the next path (first in, then out).

Specific steps:

• You start at some vertex V in the graph, and you start accessing it.
• Find the first unvisited adjacent point of its vertex and access that vertex.
• Take this vertex as the new vertex and repeat this step until the current vertex has no adjacencies that are not accessed.
• Returns a previously visited vertex that has an unvisited adjacent. finds the next unvisited adjacent. accesses the vertex.
• Repeat steps 2, 3, and 4 until all vertices in the graph have been accessed.

For the matrix we created earlier, look at the following access path: starting from V0

Let’s implement the above function. Also add a function, you can contract the cutoff node

* * * * * *// Depth-first traversal
  dfs(startId, endID) {
    const nodes = [];

    if(startId ! =null) {
      const stack = [];
      stack.push([startId]);
      while(stack.length ! = =0) {
        const sides = stack.pop();
        const side = sides[0];

        if (nodes.every(item= > item[0] !== side)) {
          // Register the node
          nodes.push(sides);
          // Exit at the end point
          if (side === endID) break;
          const children = this.getAdjoinVertexs(side);
          children.slice().reverse().forEach((item) = >{ stack.push([item, side]); }); }}}return nodes;
  }
  // Search for links
  lookupLink(params) {
    return params.reduceRight((total, current) = > {
      if (total[total.length - 1] === current[0] && current[1]) {
        total.push(current[1]);
      }
      return total;
    }, params[params.length - 1]).reverse(); } * * * * * * *console.log(demo.lookupLink(demo.dfs('v0'.'v4')));
 console.log(demo.lookupLink(demo.dfs('v3'.'v4')));

// ["v0", "v2", "v3", "v1", "v4"]
// ["v3", "v0", "v2", "v4"]Copy the code

This is a way to quickly find a path between two points. But it’s not guaranteed to be optimal

Breadth-first algorithm

Breadth-first algorithm starts from a point, starts to traverse the whole graph, and first traverses all its adjacent nodes to spread out. Similar to the way ripples spread in water

Specific steps:

• You start at some vertex V in the graph, and you start accessing it.
• Find all unaccessed adjacencies of the current vertex and access all nodes.
• Step 2 continues with the accessible nodes until all vertices in the graph have been accessed.

For the matrix we created earlier, look at the following access path: starting from V0

Let’s implement the above functions and add one more function. Cutoff nodes can be agreed upon

// BFS (startId, endID) {const nodes = [];if(startId ! = null) { const stack = []; stack.unshift([startId]);while(stack.length ! == 0) { const sides = stack.shift(); const side = sides[0];if(nodes.every(item => item[0] ! == side)) { nodes.push(sides); // Exit at the end pointif (side === endID) break; const children = this.getAdjoinVertexs(side); children.forEach((item) => { stack.push([item, side]); }); }}}return nodes;
  }

console.log(demo.lookupLink(demo.dfs('v0'.'v3')));
console.log(demo.lookupLink(demo.bfs('v0'.'v3'))); / / /"v0"."v2"."v3"] / ["v0"."v3"]Copy the code

This method can quickly find the path of the optimal solution between two points.

Application of maps

A simple map

Simple maps calculate only the number of steps, not the size.

This describes the depth-first and breadth-first algorithms, and allows us to specify termination nodes. Now let’s test the graph

demo.setAdjoinVertexs('v0'['v2']);
demo.setAdjoinVertexs('v1'['v4']);
demo.setAdjoinVertexs('v2'['v3']);
demo.setAdjoinVertexs('v3'['v0'.'v1']);
demo.setAdjoinVertexs('v4'['v2'.'v3']);

console.log(demo.lookupLink(demo.dfs('v4'.'v3')));
console.log(demo.lookupLink(demo.bfs('v4'.'v3'))); / / /"v4"."v2"."v3"] / ["v4"."v3"]Copy the code

The running results in the figure above also demonstrate that the path of the breadth-first algorithm is closer to the starting point, and it is more tried in the map scene.

Weighted digraph

There’s the ultimate challenge

describe

In the previous demo we solved the simple map problem by using the directed graph link matrix, which corresponds to the minimum transfer in The Gaudon map. But there are other ways to navigate a path on Amap: shortest distance, shortest time. In fact, this kind of navigation mode assigns the concept of step size (time, distance, etc.) to the directed graph connection matrix, which is collectively called the weighted directed graph connection matrix. Here is an example:

The figure above adds the concept of distance to the directed graph introduced earlier. Let’s create a two-dimensional matrix. Because of the concept of adding weights we can no longer use 0 for unreachable paths. Unreachable paths are represented as ∞

Const arr = [/ / where v0 v1 v2 v3 v4 0, up to 1, up, up, / / where v0 up to 0, up, up to 4, / / v1 up, up, 0, 3, up, / / v2 5, 3, up, 0, up, / / v3 up, ∞, 1, 6, 0, // v4]Copy the code

As the current node is associated with its own, the weight is 0

How do we solve the shortest side problem for weighted shapes? So let’s look at the algorithm

Dekoscher’s algorithm

Dijkstra algorithm adopts the breadth-first algorithm realization idea, and extends from the center point to the shortest edge from the starting vertex to the outer layer.

Specific steps:

• You start at some vertex V in the graph, and you start accessing it.
• Find all the unaccessed adjacencies of the current vertex and sort them according to the weighted order to form array A.
• Access the shortest edge, and access all adjacencies that are not accessed.
• Current vertex weighting + adjacent vertex weighting < starting vertex weighting to adjacent nodes. Then the shortest path is synchronized to A
• Repeat steps 2-4 until all vertices are accessed

For example: what is the shortest path from V0 to each vertex?

1: Construct weighted tie matrix

FIG. 1

2: take v0 to all vertex link array, and sort according to vertex weighting

3: vertex V0 enters the column, weights to 0, and enters the next vertex

Figure 2

4: reorder unvisited vertices

5: vertex V2 is listed, and all connected vertices that are not accessed are accessed

6: v0V2 weighted + V2V3 weighted < V0V3 weighted. Adjust the original queue, reorder.

FIG. 3

FIG. 4

Figure 5

Figure 6

// Dikosche shortest path
dijkstra(startId, endID) {
    const stack = this.getVertexRow(startId).map((item, index) = > [
      item,
      this.vertex[index],
      startId,
    ]).sort((a, b) = > b[0] - a[0]);
    const nodes = [];

    while (stack.length) {
      // Delete the last node
      const node = stack.pop();
      const [weights, side] = node;

      nodes.push(node);
      if (side === endID) break;

      if (weights) {
        const children = this.getVertexRow(side).map((item, index) = > [item, this.vertex[index]]);
        children.forEach((item) = > {
          let single = [];
          stack.some((value) = > {
            if (value[1] === item[1]) {
              single = value;
              return true;
            }
            return false;
          });

          const [nodeWeights, id] = single;
          // const index
          if (id && weights + item[0] < nodeWeights) {
            single[0] = weights + item[0];
            single[2] = side; }}); } stack.sort((a, b) = > b[0] - a[0]);
    }

    return nodes;
  }

const router = demo2.dijkstra('v4'.'v3');
console.log(` distance:${router[router.length - 1] [0]}Route:${demo.lookupLink(router.map(item => [item[1], item[2]])}`);
// Distance: 4, route: V4, V2,v3Copy the code

conclusion

In this paper, there are many algorithms to solve this kind of graphical network association, such as Floyd, Johnson, SPFA, A*, B* and so on. If you are interested, you can further study it.

The following is the key: 👇👇👇👇👇