Convert 2D Matrix to Graph
I am facing a problem while converting a given 2D matrix containing both invalid and valid points to a graph with valid nodes. The problem is this. I have a 2D matrix like
# # # # #
# . C C #
# S # # #
# . . E #
# # # # #
I want to find the shortest distance from S to E, meaning that I have to cover all "C" and "#" acts like a wall and ".". acts like a free path. Now I want to convert this matrix to a graph containing only valid nodes. Please help me.
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
for i=1 to n:
for j=1 to n:
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest
source to share
A 2d symbol matrix is an ideal representation for this task.
Each matrix element (i, j) is a node. Assuming you can only go east, west, north, south, there are 0-4 undirected edges from this node to its neighbors (i + or -1, j + or- 1), as determined by simply testing the character at each location ...
You can also check for i, j values out of range (negative or too large), but if there is always a "wall" on the border, as you have shown, this is not necessary. The wall serves as a sentinel .
Creating a general purpose structure to represent a graph embedded in a grid is a waste of time and memory.
source to share
To make a graph, you need to create a node for each non-stationary space. Step through the 2D matrix (let's assume it's just a char array) and create nodes and add edges:
nodes = new Node[matrix.length][matrix[0].length]; //instance variable
for ( int row = 0; row < matrix.length; row++ )
{
for ( int col = 0; col < matrix[row].length; col++ )
{
char type = matrix[row][col];
if ( type != '#' )
{
Node n = new Node();
nodes[row][col] = n; //constructor to determine type of node
if ( type == 'S' )
startNode = n;
else if ( type == 'E' )
endNode = n;
findNeighbors(row, col); //assuming nodes and matrix variables are instance variables
}
else
nodes[row][col] = null;
}
}
With a 2D array of nodes, you can walk through and add neighbors using findNeighbors:
public void findNeighbors(int row, int col)
{
for ( int r = -1; r <= 1; r++ )
{
for ( int c = -1; c <= 1; c++ )
{
try {
if ( matrix[row+r][col+c] != '#' )
nodes[row][col].addEdge(nodes[row+r][col+c]);
} catch (ArrayIndexOutOfBoundsException e) {}
}
}
}
Now, after all this code, you have a 2D array of node objects representing the graph. You can store the Start node in an instance variable to keep a handy reference to it and easily access your neighbors.
With the code I wrote, the node class would need a method addEdge(Node)
that adds the node argument to the list of nodes.
source to share
This sounds like homework, but for the sake of conversation (time / space complexity) I would do something different. First, I would create a graph that only contains valid edges between nodes, which can be paths (not walls, for example). This will minimize the space required. I won't use a matrix because it uses too much space in real graphics (sparse) and the time complexity is ROW * COL (V ^ 2 for a square matrix).
class Graph {
Map<Integer, Set<Integer>> edgeTo;
Graph() {
this.edgeTo = new HashMap<Integer, Set<Integer>>();
}
public int size() {
return edgeTo.size();
}
public void addEdge(int v1, int v2) {
add(v1, v2);
add(v2, v1);
}
private void add(int from, int to) {
if (!edgeTo.containsKey(from)) {
Set<Integer> s = new HashSet<Integer>();
s.add(to);
edgeTo.put(from, s);
} else {
edgeTo.get(from).add(to);
}
}
public Set<Integer> adj(int v) {
return edgeTo.get(v);
}
}
With this in place, the creation of the schedule follows the idea of the previous post,
private Graph createGrap(char[][] matrix) {
Graph g = new Graph();
for (int r = 0; r < matrix.length; r++) {
for (int c = 0; c < matrix[0].length; c++) {
// skip this cells
if (!isFreeCell(matrix[r][c])) {
continue;
}
int id = createUniqueId(r, c);
if (matrix[r][c] == 'S') {
startVertex = id;
} else if (matrix[r][c] == 'E') {
endVertex = id;
}
createNeighbor(r, c, matrix, g);
}
}
return g;
}
private void createNeighbor(final int r, final int c, final char[][] matrix2, final Graph g) {
for (int row = -1; row <= 1; row++) {
for (int col = -1; col <= 1; col++) {
// avoid the center cell
if (row ==0 && col == 0){
continue;
}
// outside matrix
if ((0 > c + col) || (c + col >= matrix2[0].length) || (0 > r + row) || (r + row >= matrix2.length)) {
continue;
}
char value = matrix2[r+row][c+col];
if (!isFreeCell(value)){
continue;
}
int from = createUniqueId(r, c);
int to = createUniqueId(row+r, col+c);
g.add(from, to);
}
}
}
private boolean isFreeCell(char value) {
return (value != '#' && value !='C');
}
private int createUniqueId(int r, int c) {
return r * MAX_COL + c;
}
Now all that remains is to find the shortest path ... using the BFS of this undirected graph without negative weighted edges ...
private void findSP(Graph g) {
if (g == null || g.size() == 0) {
throw new IllegalArgumentException("empty or null graph");
}
if (g.size() == 1) {
throw new IllegalArgumentException(
"graph size must be greater than 1");
}
if (startVertex == -1) {
throw new IllegalArgumentException("Start vertex not found");
}
if (endVertex == -1) {
throw new IllegalArgumentException("End vertex not found");
}
Map<Integer, Integer> sonToParent = bfs(g, startVertex, endVertex);
Stack<Integer> path = new Stack<Integer>();
for (int son = endVertex; son!= startVertex; son = sonToParent.get(son)){
path.push(son);
}
path.push(startVertex);
while (!path.isEmpty()){
System.out.print(path.pop() + ", ");
}
}
private Map<Integer, Integer> bfs(Graph g, int startVertex2, int endVertex2) {
Queue<Integer> q = new LinkedList<Integer>();
Set<Integer> marked = new HashSet<Integer>();
Map<Integer, Integer> sonToParent = new HashMap<Integer, Integer>();
q.add(startVertex2);
while (!q.isEmpty()) {
int v = q.poll();
for (Integer s : g.adj(v)) {
if (!marked.contains(s)) {
marked.add(s);
sonToParent.put(s, v);
if (s == endVertex2) {
return sonToParent;
}
q.add(s);
}
}
}
return null;
}
source to share
I would either create a node structure or a node class. For example:
struct Node {
node type; //Indicate in some way if the node is a 'S', '.' or 'E'
std::vector<Node> adjacentNodes;
}
As for populating this data structure, I would start with the "S" block. And do a recursive look like:
Set alreadyVisited;
FillGraph(i,j,Node){
// for all adjacent nodes, add them to Node adjacentNodes.
// add Node to alreadyVisited Set
// for each of the adjacentNodes (i.e. any neighbor that isn't a wall.
// if(adjacentNode is not in alreadyVisited)
// FillGraph(adjaent-i, adjacent-j, adjacentNode);
}
source to share