A shorter blog entry this time if it can be helped, having found a method of checking if graphs are connected or not and keeping the efficiency of said algorithm to a minimum O(|V|) at best, the next step included some testing to check if it works, and so, some assumptions have to be made in order for success.
1. The file input should be in the "Chaco" format (NB to self and advise to readers: find original source for this file type, might be useful)
2. The file input is read in the correct order, so the first vertex read in is vertex 1, 2nd is 2 and so on. Disruption of this order may cause some undesired or unexpected issues (as far as can be told, if the rule above holds, this should not be an issue as chaco files tend to be in the correct order)
3. The vertices are in order, so for part of a disjoint graph Ga = Va; Va { v1, v2, v3 } and Gb = Vb; Vb { v4, v5, v6}, the vertices are in some kind of order, whereas if Va { v1, v4, v2} and Vb {v3, v5, v6}, this may cause some unexpected issues.
More on these assumptions and rules after some more research and testing. The algorithm I'm using is actually a variant of the breadth-first search algorithm. I am also aware of Menger's theorem.
NB: Yesterday (Monday 27th was my first Tutorial, 2hours with group 6, and 2hours with group 10), not of interest to you readers but its always good to have somewhere to look up things in case something goes missing.
No comments:
Post a Comment