/
README2
executable file
·105 lines (78 loc) · 4.13 KB
/
README2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/-------------------------------------------------------------------------
/ Starter Code and GUI Application for Course 3 in the
/ Java Programming: Object Oriented Design of
/ Data Structures Specialization:
/
/ Advanced Data Structures in Java
/ https://www.coursera.org/learn/advanced-data-structures
/
/ Authored by UCSD MOOC Team:
/ Mia Minnes, Christine Alvarado, Leo Porter, Alec Brickner
/ and Adam Setters
/
/ Date: 12/16/2015
/-------------------------------------------------------------------------
---------------------------------------------------------[ DESCRIPTION ]--
The files provided are skeleton code, as well as grading previews and
testing files to be used in completing the course programming
assignments. Additionally, you are provided a runnable JavaFX program
which will help to test and demonstrate your implementations.
-------------------------------------------------------[ FILES BY WEEK ]--
Below are the files introduced in each week and used in each week
of the course. See file for description...
Week 1 : Introduction to the course and graphs
==============================================
basicgraph.Graph.java
basicgraph.GraphAdjList.java
basicgraph.GraphAdjMatrix.java
Week 2 : Class design and simple graph search
==================================================
roadgraph.MapGraph.java
week2example.Maze.java
week2example.MazeLoader.java
week2example.MazeNode.java
**Method Implementations**
1. **Degree Sequence** which is an ordered list containing the degrees of each of the vertices in a graph, in non-increasing sorted order (with repetitions). The degree sequence of a graph is an invariant of the graph and can be used to distinguish between two graphs and to analyze graph properties.
2. **getDistance2** (get Distance 2) finds all vertices reachable by two hops from vertex.
- **GraphAdjList** getDistance2 - get vertex's neighbors and loop through them adding to the new array.
- **GraphAdjMatrix** getDistance2 - in this case can be obtained by squaring the matrix representation of the graph. Then creating a nested loop where you loop through the column of the inner squared matrix adding all values that are greater than 0 to the new array.
Week 3: Class design and implementation.
================================================
**Class: MapGraph**
A class which represents a graph of geographic locations.
Nodes in the graph are intersections between roads (Edges) in the map.
This class contains methods that return the number of vertices (nodes), and edges.
Also allows to add a vertex and edge.
It performs searches in different ways:
* Breadth First Search (bfs)
* Dijkstra Search (to be implemented in week 4)
* A Star Search (to be implemented in week 4)
Modifications: BFS method was too long, and it was broke into two small private methods:
* doBFSSearch
* constructPath
**Class: MapNode**
A class which represents a node (vertex) in a graph of geographic locations.
Nodes in the graph are intersections between roads (edges).
This class contains methods that allows to add and edge, and return a list of edges, and a list of nodes around a specific edge.
**Class: MapEdge**
A class which represents an edge in a graph of a Geographic Location.
The edge in this case, is a road.
It contains a list of getter methods:
* getStart() (return GeographicPoint object)
* getGoal() (return GeographicPoint object)
* getRoadName() (return String object)
* getRoadType() (return String object)
* getLength() (return Double object)
Utility files
=============
geography.GeographicPoint.java
geography.RoadSegment.java
util.GraphLoader.java
---------------------------------------------------------------[ SETUP ]--
Importing Project into eclipse:
1. Create a new Java Project in your workspace
2. Import the starter files:
File -> Import -> Select "File System" -> Next -> Browse and set
root directory to folder contents of zip were extracted to -> Finish
Feel free to use another IDE or manually compile and run your programs.
If you need help, google is your friend.