- I use the Thoughbot convention of avoiding begin blocks in specs; that way, the conditions are clearly obvious at each example, even though it's not so DRY. Depending on a site's particular coding guidelines, these might need to be refactored with begin blocks and additional context definitions.
- 'Path' = character sequence showing nodes visited; e.g., 'ABC'
- 'Route' = a Route object containing a path and its cumulative distance; e.g., <'ABC', 7>. Occasionally, a degenerate route of the form <'A',0> is used to initiate processing.
- Decided to use an adjacency list as opposed to adjacency matrix: Approach works well for smaller digraphs Adjacency matrix would work best with separate matrix library and for larger, dense graphs. The adjacency lists are used only in Dignode; when passing data to an external user, Dignode creates a route list of the form: [<'AB', 3>, <'AC',4>,...]
- When creating an edge, any required vertices are created as needed.
- Access to Dignode is always through Digraph; no 'external' use so that Dignode is effectively 'hidden' from eeryone by Digraph
- Code was entirely developed using RSpec/TDD.
- Spec'ing this out led me to a solution that didn't include the classic DFS or BFS implementation. Instead, I wound up implementing an algorithm to directly handle the case of routes with n stops (get_routes_by_stops) and that naturally led to a similar approach for the distance problem (get_routes_by_distance). Were I to consider further work, I might well refactor this to use the more common approach.
- The Dijkstra algorithm to find all shortest paths between two nodes was implemented based on material in the book "The Algorithm Design Manual" using the standard approach. That method has not been refactored, but has been left in the canonical form.
E.g.,
trains sample.dat
will run the sample data set and print out the results
- Digraph.new()
- Initialize the Directed Graph
- #add_vertex(vertex_name)
- Add a vertex to the Digraph
- #add_edge(from, to, distance)
- Add an edge to the Digraph; Vertices are automatically added as needed
- #node_list()
- Return the list of all vertices in the Digraph
- #distance(from, to)
- Return the distance from -> to where to is adjacent to from
- #[index]
- Return the node at position 'index'; 'index' may be a number position in the internal array or a vertex name
- #find_vertex(name)
- Return the node with the name 'name' or false if not found
- #read_graph(infile)
- Initialize the Digraph from the given file
- #path_distance(path)
- Return the total path distance
- #get_route_list(name)
- Return a routelist for the named node's adjacencies
- #get_routes_by_stops(start, depth)
- Return a list of routes, starting at node 'start' and proceeding 'depth' levels
- #get_routes_by_distance(from, to, distance)
- Return a list of routes, starting at 'from' and going to 'to' which have a total distance >= distance. Cycles are automatically supported.
- #shortest_path(from, to)
- Return the distance of the shortest path from -> to. Cycles are automatically supported.
- DigraphReader.new()
- Initialize the Directed Graph Reader
- #read_graph_input()
- Read the graph file
- #checked_file_for_input(file_name)
- Ensure fie requested file is available to read