سلام عليكم يا جماعة اريد عمل هذا الالجوريزم جافا
من يجد فى نفسه القدرة يقولى يا جماعة
الوقت المتاح له يومان
و سيتم محاسبته بعد التشييك على البروجكت
سلام عليكم
CITS3210 Algorithms Project
Due: 5:00pm Mon 19th Oct, week 13, 2009
Your task is to implement a pattern matching algorithm for labelled graphs in java and analyse
its performance. These sorts of algorithms are used for examining properties of hardware
and software systems, highlighting reaction pathways in complicated biochemical systems, and
forensic analysis of observed faults in systems.
A labelled graph will be a directed (unweighted) graph (V,E) along with a label μ(v) for each
vertex v ∈ V . The labels will just be single letters from a finite alphabet . A pattern is just
a string p = hp1, p2, ..., pmi of letters from . Given , (V,E, μ) and p, the task is to search for
some sequences v1, ..., vm such that each (vi, vi+1) ∈ E and each μ(vi) = pi.
Input will consist of three text files: one to specify the alphabet, one to specify the labelled graph
and one to specify the pattern. This is to allow convenient search for the same pattern in several
different graphs.
To specify an alphabet the text file should just have each different letter on a newline. Eg
a
b
c
d
Note that to allow for large alphabets or convenience for specific applications, some (or all) letters
of the alphabet may be represented by more than one ascii character.
For specifying a labelled graph from the file you should use the following format for the input
data file:
6
0 1 1 1 0 0
1 0 1 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 1 0
b
a
b
a
b
c
where the first line is the total number of vertices. The numbers from the second line onward
are the entries of the n × n adjacency matrix (just 0 or 1 and not necessarily symmetric.) Then
follow the labels of the vertices in order each on a different line.
Finally, a pattern is specified by a text file with letters in order:
1
a
b
b
You may assume that all the vertices have distinct numbers 0, 1, 2, · · · (as well as labels).
The output should be a text file. If the pattern does not appear in the graph then it should
just be a file starting with one line containing -1. If the pattern does appear then the text file
should contain a sequence of numbers of vertices in order (with optional newlines) which have
the pattern as their respective labels. Eg,
2 3 5
Note that there may be other possible answers to any particular instance of the problem. We
just need one correct answer.
This assignment can be done in pairs, although you may work on your own if you prefer.
This assignment is worth 20% of your final grade, and consists of:
• 5% - Commented source files, to be submitted to cssubmit
(https://secure.csse.uwa.edu.au/run/cssubmit)
• 12% - Written report, to be submitted at the front office.
• 3% - Extension and challenge
You’re implementation should consist of a set of java classes that allow labelled graphs to be
searched from the command line. Your program should also satisfy the following requirements:
1. You may make use of code from our Lab class work but acknowledge any use of lines
supplied by the School, (eg Graph.java).
2. You may use classes from java.lang, java.io and java.util. If you wish to use other
classes you may post a message to the discussion list.
3. Your classes should be fully commented, including javadoc.
Your program should be able to be run from the command line, accepting input and output files
as parameters. For example,
java LGSearch alph.txt lg.txt pattern.txt out.txt
may run your program to look for the pattern pattern.txt from the alphabet alph.txt in the
labelled graph lg.txt to produce out.txt. Note that the name of your classes and the way they
are run is up to you. Your program should also be designed to perform efficiently.
2
The deliverable are:
1. A report, which should include the following parts:
(a) A user guide, detailing how to compile and run your program. (1 mark)
(B) A brief overview of the existing graph and pattern matching algorithms you examined
and considered. Explain your choice of algorithm (or combination of algorithms). (2
marks)
© A detailed description of the algorithm used (both in English and pseudo-code). (2
marks)
(d) The software design decisions made and the rationale behind those decisions. (1
marks)
(e) A theoretical analysis of the complexity of the algorithms (time and space). (3 marks)
(f) Experimental analysis of the efficiency of your programs in terms of the time taken.
(3 marks)
Note, your report should also reference all resources used to complete your assignment.
2. The source files which are marked as follows:
(a) Correctness (i.e. all instances located and no others ) (2/5)
(B) Efficiency (time taken) (2/5)
© Clarity (programme design, commenting, etc) (1/5)
3. The extension question is worth 3 marks and the effort required is not proportional to the
marks so this should only be undertaken after you are satisfied with deliverable 1 and 2.
For the extension, you are required to produce
(a) an all paths version of your program which finds all the paths of vertices which match
the pattern;
(B) a labelled graph pattern-matching algorithm, that is able to match a pattern that
may contain a simple regular expression such as a(bc)*a meaning any sequence such
as aa, abca, abcbca, abcbcbca, ... (instead of just fixed strings);
© A short report (2 pages max) (as an appendix to deliverable 1) detailing the algorithm
used and the effectiveness of the algorithm.
Submit the commented source files through cssubmit.
The report should be handed into Room 1.31A, CSSE Building, by the due date/time.
3
