CODEWITHSUNDEEP
c++algorithmparsinggraph
Chiffa
Chiffa

Reputation: 1506

Read in a matrix and build a graph

I have a rectangular room; its' floor is coverd with floor boards, some of them are broken. The dimensions of the room are N and M: 1 <=N,M<=300. I read N and M from stdin, and then I read N strings of length M, which look like this:

..**.***....*.**...**.***
.**......**...***..***...

and so on, where . is a good floor board and * is a broken one. I intend to replace the broken floor boards with new one, and I only have two types of those: two-by-ones and one-by-ones. I can't cut the two-by-ones into two one-by-ones. To find a way to do this, I paint the floor like a checkerboard, so that the halves of a broken two-by-one are of different color. Then I mean to build a bipartite graph (consisting of a white and a black part) from the resulting matrix, and I'd like to build and analyse it with this code.

What's the best way to do that? I think that I shouldn't keep all the matrix in memory (since it can be rather large). Ideally I should be able to read in strings and update the graph on the run.

EDIT: My code should like this:

int main()
{
int N, M;
std::cin >> N;
assert (( N >=1) && (N <=300));
std::cin >> M;
assert (( M >=1) && (M <=300));
for (int i = 0; i < N; ++i)
    std::cin >> // that's where I have to read the string
                //...and the next string
                // use these 2 strings to update a graph
                // with prGraph.AddEdge()
return 0;
}

Upvotes: 0

Views: 96

Answers (2)

kraskevich
kraskevich

Reputation: 18556

If it is really so important not to store the entire matrix in memory, you can read it line by line and store only the current and the previous line because it is sufficient to construct a graph properly.

Upvotes: 2

Larry
Larry

Reputation: 4559

A naive graph construction using an adjacency matrix would take 300x300 ^2, which is tough to fit in memory.

You can take advantage of the fact that each vertex can have at most 4 edges - you would only need space on order of 300 x 300 x 4 using adjacency lists for your maxflow instead, as long as you change the graph traversal accordingly.

Upvotes: 1

Related Questions