10

I am trying to learn graph structures and algorithms. Conceptually I understand DFS, BFS, and I can implement them provided a graph, but how are graphs traditionally composed?

Typically I see them as list of nodes with edges as pointers, a list of edges with the nodes they connect, or a 2d matrix where the intersection of both arr[node_a][node_b] is the weight of the edge.

When it comes to actually building it out of input, I don't know where to start.

As an example, how you would you build a graph when provided a 2d grid like (an online pacman problem) where P is the source node and -'s are nodes in the tree.

%%%%%%%%%%%%%%%%%%%%
%--------------%---%
%-%%-%%-%%-%%-%%-%-%
%--------P-------%-%
%%%%%%%%%%%%%%%%%%-%
%.-----------------%
%%%%%%%%%%%%%%%%%%%%

Or, how would you build it when provided with an adjacency list?

I understand this is probably a big question, as the subject is rather complicated. Links to documentation are appreciated! I've been having trouble finding any from an introductory level.

Dakota West
  • 441
  • 1
  • 4
  • 13
  • Actually if you get that grid, why make a graph? You can use the grid as implicit graph, right? – harold Nov 20 '13 at 20:45
  • 3
    @harold How could I do that? – Dakota West Nov 20 '13 at 21:19
  • I know it might be too late lol but what you ask is that actually a matrix. Then (assuming that Pacman is regular) it can go up,down,right,left (without any restrictions that says you can go to % but not - or smth). Therefore, you have your vertices as matrix[x][y] and DFS/BFS only cares about vertices. You know the edges since neighbours (or you can call the vertices that you have edge from your current vertex) are matrix[x/x+1/x-1][y/y+1/y-1]. – ihatec May 19 '22 at 14:29
  • By the way, next time speciliaze your language to get more help – ihatec May 19 '22 at 14:30

2 Answers2

3

for this purpose I wrote this javascript, it converts a matrix (array of array) in a unweight graph. It starts to navigate in the 4 directions (up/down/right/left) without walking where it already goes.

Then, it will use DFS to find the shortest path.

const wall = 0
const flat = 1
const target = 9

// no diagonals
const possibleMoves = [
  [-1, 0], // nord
  [0, +1],
  [+1, 0], // sud
  [0, -1],
]

function pathFinder(map) {
  const gridW = map[0].length
  const gridH = map.length
  const start = buildNode([0, 0], map)
  const tree = buildTreeMap(start, map, [start])
  const path = navigateTree(tree)
  console.log(path.map(_ => _.point));
  return path.length


  // Depth-first search (DFS)
  function navigateTree(node) {
    const dfp = (acc, _) => {
      if (_.value === target) {
        acc.push(_)
        return acc
      }
      const targetInMyChildren = _.children.reduce(dfp, [])
      if (targetInMyChildren.length > 0) {
        targetInMyChildren.unshift(_)
        return targetInMyChildren
      }
      return acc
    }

    return node.children.reduce(dfp, [])
  }

  function buildTreeMap(node, map2d, visited) {
    const [x, y] = node.point
    node.children = possibleMoves
      .map((([incx, incy]) => [x + incx, y + incy]))
      .filter(([nx, ny]) => {
    /**
     * REMOVE
     * + out of grid
     * + walls
     * + already visited points
     */
        if (nx < 0 || nx >= gridW
          || ny < 0 || ny >= gridH
          || map2d[ny][nx] === wall) {
          return false
        }

        return visited.findIndex(vis => vis.point[0] === nx && vis.point[1] === ny) === -1
      })
      .map(_ => {
        const newNode = buildNode(_, map2d)
        visited.push(newNode)
        return newNode
      })
    node.children.forEach(_ => buildTreeMap(_, map2d, visited))
    return node
  }

}

function buildNode(point, map) {
  const value = map[point[1]][point[0]]
  return {
    point,
    value,
    children: []
  }
}



const stepsCount = pathFinder([
  [1, 1, 1, 1],
  [0, 1, 1, 0],
  [0, 1, 1, 0],
  [0, 1, 0, 0],
  [0, 1, 1, 1],
  [0, 1, 1, 1],
  [9, 0, 1, 1],
  [1, 1, 1, 1],
  [1, 0, 1, 0],
  [1, 1, 1, 1]
])
console.log(stepsCount);
Manuel Spigolon
  • 11,003
  • 5
  • 50
  • 73
2

Graphs are typically stored using one of two data structures:

  1. Adjacency List (http://en.wikipedia.org/wiki/Adjacency_list)

  2. Adjacency Matrix (http://en.wikipedia.org/wiki/Adjacency_matrix)

Each has its own space and time advantages.

You would have to convert whatever input you want to represent as a graph (e.g., parse it), into one of the above data structures.

mattnedrich
  • 7,577
  • 9
  • 39
  • 45
  • This is what I said above. I'm looking for the parsing part. – Dakota West Nov 20 '13 at 21:19
  • Create a Node and Edge class. Edge can have two Nodes (one for each endpoint). Node can have a collection of Edges (one for each Node it's connected to). Parse your 2D input array one character at a time. Create a hashset of Node objects. When you encounter a "-" check to see if it's in the Hashset (e.g., you already created a Node for it), if not, create a new Node object. Then check the four locations around the "-" (top, bottom, left, right), and create new node objects if you see any "-"'s and connect them. – mattnedrich Nov 20 '13 at 22:36