In the past week, I got it so the edge weight is shown on each edge and so it is possible to have an edge weight of zero and negative edge weights. This resulted in me changing what integer represented no edge in the adjacency matrix. I originally used zero then changed it to the max integer since that was the closest to infinity I could get. I also messed a little bit with the animation. As it goes forward in an algorithm, it is truly animating. Unfortunately, it is not truly animating going backward. As is goes forward, a list is created. When it goes backwards, it goes backwards through that list. I also added a fourth algorithm, Shortest Path. Since I added negative edge weights, Dijkstra's algorithm would not work. So I went with the Bellman-Ford-Moore algorithm which is in the picture below. My immediate plans are to continue trying to get bugs out and to work on my presentation which is on Thursday.
Before I left for break, I wanted all types of edges working. Before last Thursday, I had the tree edges and back edges working just fine but it could not tell the difference between forward edges and cross edges. After messing around with when each vertex was visited, I got the forward and cross edges working correctly. I then decided to add Minimum Spanning Tree as another algorithm. On Monday, I finally got it working. I have been drawing a lot of graphs by hand during the course of this project. Currently, I have been focusing on the weights. I changed it so the weight is shown by the edge instead of by the thickness of the edge so there are more options in edge weight. There are still some problems with the way I am doing it. Finding a color that does not blend into any of the various edge colors is hard. I am also checking for edges by checking if the weight is greater than 0 so that will have to change if I want to allow weights that are zero or negative which does happen. I have been slowly finding some of the bugs and eliminating them but more always seem to appear. Since a graph cannot be changed in the middle of running an algorithm, I disabled anything that could change the graph while the algorithm was running. Below are examples of a graph in the middle of having BFS, DFS, and MST (respectively) ran on it. Update on laptop: So during break, I got the new adapter sent to me from Dell. Naturally, even with the new adopter, my laptop still would not charge. So I called Dell again. They finally agreed with me that it was the laptop itself having problems and had me ship in my laptop. I might get is back around finals' week.
I currently have BFS and DFS animation mostly working through what Dr. McVey called a "smoke and mirrors" method. There are still some bugs. I did recently fix the one where if you consecutively opened files, parts of the previous graph would still be there which resulted in even more bugs. I now make sure the graph is cleared when a new file is opened which seemed to fix the problem. I still need to make the visuals a bit more user friendly and include things like back edges and forward edges.
When I was at home grabbing my old laptop (since my new one is practically dead and not charging), I somehow ended up getting a mini-lecture about yield return, IEnumerable<> and why I should consider using them for the algorithms from my brother.This is apparently what happens when I talk about my computer science projects at home. The following two pictures are snapshots of a graph that had BFS ran and DFS ran. Vertices turn red when visited and green when done. The tree edges of the algorithms are blue. So, a few weeks ago I mentioned in a post the my laptop crashed twice since I got it back in January. I did take it to ITS on campus and they found nothing wrong with it besides it would randomly crash and display a message that the hard drive (that I have been using) was not installed. Today, more issues appeared. My laptop was running low on power so I plugged it in when I noticed that it would not charge. When I restarted my laptop, it gave me a message similar to the one about my hard drive except it was about my power adapter. So, I currently have to leave my laptop plugged in because if I unplug it (or the power goes out) the battery will drain (even when off - I tested that) and I will not be able to recharge it. Also, every few hours of use while plugged in causes it to lose a percent of battery power. It most likely has a hardware issue with it, probably involving the circuits. I plan on using my warranty and handing it over to Dell soon.
On a slightly brighter note, I still have my old laptop which I am getting from home tomorrow. Although, the reason I stopped using that one was that ONE of its problems was that it would randomly black out at times because the graphics driver was failing. It got so bad that the only way I could recover from it was by pressing the power button. I previously used a key combination that would restart my laptop safely (i.e. stop all running processes before shutting down). Saving often has been much more important this semester than previous semesters. I have also come to the conclusion that I have really bad luck when it comes to laptops. Since last time I posted, I got a few bugs out of my program. I was home at one point so I handed my project to my brother and asked him to find as many ways as he could to break it. He found a few that I fixed. After seeing the weird way I was drawing the edges (see last post's picture for an example), he pointed out that in C# there exists Math.(whatever trigonometric you need). So after that helpful hint, the edges look like they should. I now have all the requirements for the graph creation done. Although, I still do not have an undo.
More recently, I have been working on implementing the algorithms. I currently only have breadth-first search and depth-first search. My immediate goal is to figure out how to actually animate the algorithms instead of just running them and showing the results with color and text on the side (see picture). The biggest improvement I made since last week was fixing my adjacency matrix so that anything involving the adjacency matrix did not give run-time errors. When I had showed my project to the class last Thursday, I had all of that code commented out so it only handled the vertices. The edges now do what they are supposed to for moving and deleting vertices. Although, when I first tried to delete vertices, some of the edges were doing some strange things. Any edge that was connected to a vertex with a lower number than the one you were trying to delete and the last vertex was still showing up. However, instead of connecting to the last vertex, they connected to the upper left hand corner. I spent some time drawing graphs and adjacency matrices to figure out exactly what was happening and how to fix it. The weight is shown through the thickness of the edge and in the menu there is a check mark next to the current weight selected. It also shows the edge as you draw it. Although, there is a lot of flashing during that because it is redrawing on a mouse move. For directed verses non-directed and going between the two there are still a few bugs. While I did solve the problem of the edges going all the way to the center of the vertices, they still have slightly weird angles. I also still need a way to delete edges. Suggestions that were made to me last Thursday that were not part of the requirements included having a way to clear without creating a new file and having an undo option. With the way that the structures are set up, clearing should not be a problem since it is already part of what happens when creating a new file. Creating an undo is going to be a bit tricky considering I would needed both the type of action and what it involved.
Looking back, it's been a while since I last posted anything. I had to actually count the weeks to figure out which week it is. Anyway, a lot has happened since then. That includes a few technological problems like my project being corrupted and my laptop crashing twice. A few weeks ago when my project was corrupted, I started a new project in Visual Studios. Since then, I can draw the vertices again, edges can be drawn, and parts of some of the graph features are working. Lab 6 from CSCI 350 where we used a mouse click to draw points with a line connecting it to the previous point was very helpful to look at. Looking at the graph there is one obvious problem of the edges covering up the vertex numbers. I will probably need to use some trigonometry to fix that unless I find an easier way. I would also like the line to be arrows, particularly if the graph is directed. First, though, I want to get the rest of the graph features working completely.
After last Thursday's class, my plans for how I am proceeding with my project slightly changed. I was informed that it was actually best to start out with the graph being able to be weighted and directed. I plan on having the weight for edges in a non-weighted graph to be zero. If the graph is non-directed, I plan on having it act like there is an edge pointing to both vertices.
I have decided to use C# and have planned a form that I have been working on making. It has check boxes and radio buttons on it currently. My main focus right now is trying to get it so the user can create a graph by clicking on the form. I know how to have mouse clicks form shapes on the form. Currently, when the form is clicked, a circle with an indexed number appears. However, it is the being able to interact with those shapes (circles that are vertices) that I am currently trying to figure out. Below is an image of what the executable currently looks like. There are quite a few things I what to still add to it. The circles with numbers inside of them were form from mouse clicks. I received my project this week and have started to plan how I want to approach it. I am planning on starting simple and adding slowly to it. I believe that it would be best to start with the part that creates the graph since that part is needed to see whether or not the algorithms are working. The graph creation part is going to be limited to non-weighted and non-directed edges to keep it simpler. When I get to testing the algorithms, I am planning on starting with breadth first search and depth first search. Those are algorithms that are simpler than many other algorithms and they are also used in other algorithms. Once that is working, I plan on slowly making it more complicated.
This week I have also been working on this website. I have come to regret that whenever I was in group projects that involved making a website, I would let someone else be in change of the actual making of the website. While using a website builder is not hard to figure out how to do, having experience would have made making this website go faster and smoother. There are still several things I plan on adding to this website in the next few days. |
Archives
April 2017
Categories |