MainPaths.jl

Welcome to MainPaths.jl, a Julia package for computing main paths built on top of the Graphs.jl graph library.

Getting started

The package is currently not registered but can be added directly via the github package URL.

From the julia REPL, type ] to enter the Pkg REPL and run:

pkg> add https://github.com/jfb-h/MainPaths.jl

To get started, you can then run:

>julia using MainPaths

Example

As a showcase of the package's functionality, we compute the forward local main path based on SPC weights for the following simple example graph:

using Graphs, MainPaths

A = [
 0  0  1  0  0  0  0  0  0  0  0
 0  0  1  1  0  0  0  0  0  0  0
 0  0  0  0  1  0  1  0  0  0  0
 0  0  0  0  0  1  0  0  0  1  1
 0  0  0  0  0  0  0  1  1  0  0
 0  0  0  0  0  0  0  0  1  1  0
 0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0
];

julia> g = SimpleDiGraph(A)
{11, 12} directed simple Int64 graph

As a first step, we then specify how to compute traversal weights:

julia> weight = SPCEdge(normalize=:none)
SPCEdge(:none)

We then specify how we want to perform the main path traversal and at which vertices we want to start the traversal:

julia> start = [1,2];

julia> traversal = ForwardLocal(start)
ForwardLocal{Int64}([1, 2])

Now we can compute the main path:

julia> mp = mainpath(g, weight, traversal)
Mainpath with 9 vertices and 8 edges.

The mainpath function returns a MainPathResult, which just wraps a SimpleDiGraph representing the main path network, a vector indicating the indices of the main path vertices in the original graph, and a vector indicating the nodes at which the main path traversal was started:

julia> mp.mainpath
{9, 8} directed simple Int64 graph

julia> mp.vertices
9-element Vector{Int64}:
  1
  2
  3
  4
  5
  6
  8
  9
 10

julia> mp.start
2-element Vector{Int64}:
 1
 2

API

MainPaths.bfs_multi — Method

bfs_multi(g, source, neighborfn)

Traverse graph g via breadth-first search starting at vertices source and choosing neighbors to visit according to neighborfn.

This is a modified breadth-first search traversal where instances of a vertex being visited multiple times by different parents are recorded. This function was modified from the Graphs bfs algorithm.

source

MainPaths.edgeweights — Method

edgeweights(mp, w)

Return the weights of all edges in the mainpath mp from the weights matrix w containing traversal weights for the original graph.

source

MainPaths.mainpath — Method

mainpath(g, weights, traversal)

Compute the main path (or network of main paths) for graph g, utilizing edge/vertex weights as specified by weights and performing main path traversal according to traversal. weights and traversal can be specified as any of the available MainPathWeight and MainPathTraversal types, respectively.

source

MainPaths.BackwardLocal — Type

BackwardLocal(start)

Struct representing a main path traversal following the edge direction of the input DAG, starting at start.

source

MainPaths.ForwardBackwardLocal — Type

ForwardBackwardLocal(start)

Struct representing a main path traversal in both directions of the input DAG, starting at start.

source

MainPaths.ForwardLocal — Type

ForwardLocal(start)

Struct representing a main path traversal against the edge direction of the input DAG, starting at start.

source

MainPaths.GKP — Type

GKP(normalize=:none)(g)

Struct representing Genetic Knowledge Persistence (GKP) vertex weights. This is a modified version of the method proposed in Martinelli & Nomaler (2014) where citations from future patents to patents before the curent layer are not ignored in the persistence computation.