Graph Algorithms

This toolbox makes use of a number of the graph algorithms provided in the Graphs.jl package. In addition, we have implemented a number of graph algorithms that you may find useful when developing analytics around curriculum graphs. The functions implementing these algorithms are described next.

CurricularAnalytics.dfs — Function

dfs(g)

Perform a depth-first traversal of input graph g.

Arguments

Required:

  • g::AbstractGraph : input graph.

This function returns the classification of each edge in graph g, as well as the order in which vertices are first discovered during a depth-first search traversal, and when the processing from that vertex is completed during the depth-first traverlsa. According to the vertex discovery and finish times, each edge in g will be classified as one of:

  • tree edge : Any collection of edges in g that form a forest. Every vertex is either a single-vertex tree

with respect to such a collection, or is part of some larger tree through its connection to another vertex via a tree edge. This collection is not unique defined on g.

  • back edge : Given a collection of tree edges, back edges are those edges that connect some descendent vertex

in a tree to an ancestor vertex in the same tree.

  • forward edge : Given a collection of tree edges, forward edges are those that are incident from an ancestor

in a tree, and incident to an descendent in the same tree.

  • cross edge : Given a collection of tree edges, cross edges are those that are adjacent between vertices in

two different trees, or between vertices in two different subtrees in the same tree.

julia> edges, discover, finish = dfs(g)
CurricularAnalytics.gad — Function
gad(g)

Returns the transpose of directed acyclic graph (DAG) g, i.e., a DAG identical to g, except the direction of all edges is reversed. If g is not a DAG, and error is thrown.

Arguments

Required:

  • g::SimpleDiGraph : input graph.
CurricularAnalytics.all_paths — Function
all_paths(g)

Enumerate all of the unique paths in acyclic graph g, where a path in this case must include a source vertex (a vertex with in-degree zero) and a different sink vertex (a vertex with out-degree zero). I.e., a path is this case must contain at least two vertices. This function returns an array of these paths, where each path consists of an array of vertex IDs.

Arguments

Required:

  • g::AbstractGraph : acylic graph. 
julia> paths = all_paths(g)
CurricularAnalytics.longest_path — Function
longest_path(g, s)

The longest path from vertx s to any other vertex in a acyclic graph g. The longest path is not necessarily unique, i.e., there can be more than one longest path between two vertices.

Arguments

Required:

  • g::AbstractGraph : acylic graph.
  • s::Int : index of the source vertex in g. 
julia> path = longest_paths(g, s)
CurricularAnalytics.reachable_from — Function
reachable_from(g, s)

Returns the the set of all vertices in g that are reachable from vertex s.

Arguments

Required:

  • g::AbstractGraph : acylic input graph.
  • s::Int : index of the source vertex in g.
CurricularAnalytics.reachable_from_subgraph — Function
reachable_from_subgraph(g, s)

Returns the subgraph induced by s in g (i.e., a graph object consisting of vertex s and all vertices reachable from vertex s ing), as well as a vector mapping the vertex IDs in the subgraph to their IDs in the orginal graph g.

julia-rep sg, vmap = reachable_from_subgraph(g, s)`

CurricularAnalytics.reachable_to — Function
reachable_to(g, t)

Returns the set of all vertices in g that can reach target vertex t through any path.

Arguments

Required:

  • g::AbstractGraph : acylic input graph.
  • t::Int : index of the target vertex in g.
CurricularAnalytics.reachable_to_subgraph — Function
reachable_to_subgraph(g, t)

Returns a subgraph in g consisting of vertex t and all vertices that can reach vertex t ing, as well as a vector mapping the vertex IDs in the subgraph to their IDs in the orginal graph g.

Arguments

Required:

  • g::AbstractGraph : acylic graph.
  • t::Int : index of the target vertex in g.

julia-rep sg, vmap = reachable_to(g, t)`

CurricularAnalytics.reach — Function
reach(g, v)

Returns the reach of vertex v in g, ie., the set of all vertices in g that can reach vertex v and can be reached from v.

Arguments

Required:

  • g::AbstractGraph : acylic graph.
  • v::Int : index of a vertex in g.
CurricularAnalytics.reach_subgraph — Function
reach_subgraph(g, v)

Returns a subgraph in g consisting of vertex v and all vertices that can reach v, as well as all vertices that v can reach. In addition, a vector is returned that maps the vertex IDs in the subgraph to their IDs in the orginal graph g.

Arguments

Required:

  • g::AbstractGraph : acylic graph.
  • v::Int : index of a vertex in g.

julia-rep sg, vmap = reachable_to(g, v)`

CurricularAnalytics.topological_sort — Function
topological_sort(g; <keyword arguments>)

Perform a topoloical sort on graph g, returning the weakly connected components of the graph, each in topological sort order. If the sort keyword agrument is supplied, the components will be sorted according to their size, in either ascending or descending order. If two or more components have the same size, the one with the smallest vertex ID in the first position of the topological sort will appear first.

Arguments

Required:

  • g::AbstractGraph : input graph.

Keyword:

  • sort::String : sort weakly connected components according to their size, allowable

strings: ascending, descending.