代写算法作业，实现一个Graph和Adjacency Matrix之间的转换器。
QUESTION 1
In a di-graph, when each strongly connected component is reduced to a single
node, then the resulting di-graph is a directed acyclic digraph. Explain why
this is the case.
QUESTION 2
Explain why the union of strongly connected components of a digraph G does not
yield G.
QUESTION 3
This question is based on the Algori City assignment created by Ulrich. The
story goes like this.
Algori City’s planners love one-way streets. They say it is safer for
pedestrians to cross them if cars come from one direction only. So they’ve
converted a lot of their streets to one-way streets. But they have a problem:
The drivers of Algori City complain that they cannot get from some parts of
the city to others now. This is something the planners didn’t think of. They
need help from you.
As a budding graph theorist, you know that you can represent a city’s road
network as a digraph. The nodes (vertices) in the digraph are the
intersections, and the arcs are the streets connecting them, such that each
arc points in the direction of the one-way traffic. You also know that such a
graph can be represented as an adjacency matrix or an adjacency list. So you
ask the Algori
City Planning Department to give you a street map of Algori City in the form
of an adjacency matrix.
The format of the matrix is something like the following.
0,1,1,0,0,0,0,…
0,0,1,0,0,0,0,…
0,1,0,0,0,0,1,…
Each row represents the node (intersection) at which the street (arc) starts.
The first row is for intersection 0, the second for 1, etc., so that the nodes
for the n intersections in Algori City are numbered from 0 to n-1. The non-
zero entries in each row represent direct streets (arcs) going to the
respective target intersection, i.e., the j-th entry in row i tells us whether
you can get from intersection i to intersection j by car via a direct street
(arc). So, in the example above, we can see that we can get from intersection
0 to intersection 2 via a one-way street (there is no way back), and that we
can get from 1 to 2 and from 2 to 1 - presumably a two way street. Note: Each
row ends with a 0 or 1 and a single newline character, not with a comma and/or
dots (these are only to indicate that the row may have more entries).
Write a program matrix2list.java or matrix2list.py that reads a text file
matrix.txt with an adjacency matrix in the format above and converts it into
an adjacency list list.txt. You may assume that the file will be in the same
directory as matrix2list.java. Your program must read the file but it must not
ask for the file name (no user input please).
The list should have the following format (for the example above):
1,2,…
2,…
1,6,…
…
such that each row corresponds to the originating node (intersection) and each
entry in each row gives the number of a target intersection. The target
intersections in each row must be listed in increasing order. Note that there
must be no comma (and no “”) after the last entry in each row. The file
list.txt must not contain anything else than the list itself.
Your converter must write to the file list.txt, overwriting any previous
input. Any screen output of your converter will not be marked.
You must put your name and AUID (7 or 9 digit number) in a comment at the top
of the matrix2list.java or matrix2list.py file.
Your application must be delivered such that all the source files are in the
top directory only - our markers will not recreate subdirectory structures for
packages for you. You must not use / copy any other code examples found on the
Internet.
