Algorithms

# Algorithms

## Search

``````depth_first_impl(g, i, j, verbose = true)
depth_first_impl(g, i_key, i_t, j_key, j_t, verbose = true)``````

Find the shortest temporal path between TimeNode `i` and `j` on an evolving graph `g` using DFS. Alternatively, we could inpute the node keys `i_key`, `j_key` and node timestamps `i_t`, `j_t` respectively.

Example

``````julia> using EvolvingGraphs

julia> g = EvolvingGraph{Node{String}, Int}()
Directed EvolvingGraph 0 nodes, 0 static edges, 0 timestamps

julia> add_bunch_of_edges!(g, [("A", "B", 1), ("B", "F", 1), ("B", "G", 1), ("C", "E", 2), ("E", "G", 2), ("A", "B", 2), ("A", "B", 3), ("C", "F", 3), ("E","G", 3)])
Directed EvolvingGraph 6 nodes, 9 static edges, 3 timestamps

julia> depth_first_impl(g, "A", 1, "F", 3)
Current path: TimeNode(A, 1)
Current path: TimeNode(A, 1)->TimeNode(B, 1)
Current path: TimeNode(A, 1)->TimeNode(B, 1)->TimeNode(F, 1)
Current path: TimeNode(A, 1)->TimeNode(B, 1)->TimeNode(F, 1)->TimeNode(F, 3)
Current path: TimeNode(A, 1)->TimeNode(B, 1)->TimeNode(G, 1)
Current path: TimeNode(A, 1)->TimeNode(B, 1)->TimeNode(G, 1)->TimeNode(G, 2)
Current path: TimeNode(A, 1)->TimeNode(B, 1)->TimeNode(G, 1)->TimeNode(G, 3)
Current path: TimeNode(A, 1)->TimeNode(B, 1)->TimeNode(B, 2)
Current path: TimeNode(A, 1)->TimeNode(B, 1)->TimeNode(B, 2)->TimeNode(B, 3)
Current path: TimeNode(A, 1)->TimeNode(B, 1)->TimeNode(B, 3)
Current path: TimeNode(A, 1)->TimeNode(A, 2)
Current path: TimeNode(A, 1)->TimeNode(A, 2)->TimeNode(B, 2)
Current path: TimeNode(A, 1)->TimeNode(A, 2)->TimeNode(B, 2)->TimeNode(B, 3)
Current path: TimeNode(A, 1)->TimeNode(A, 2)->TimeNode(A, 3)
Current path: TimeNode(A, 1)->TimeNode(A, 2)->TimeNode(A, 3)->TimeNode(B, 3)
Current path: TimeNode(A, 1)->TimeNode(A, 3)
Current path: TimeNode(A, 1)->TimeNode(A, 3)->TimeNode(B, 3)
TimeNode(A, 1)->TimeNode(B, 1)->TimeNode(F, 1)->TimeNode(F, 3)``````
source
``breadth_first_impl(g,i)``

Find all the reachable node from TimeNode `i` using BFS.

Example

``````julia> using EvolvingGraphs

julia> g = EvolvingGraph{Node{String}, Int}()
Directed EvolvingGraph 0 nodes, 0 static edges, 0 timestamps

julia> add_bunch_of_edges!(g, [("A", "B", 1), ("B", "F", 1), ("B", "G", 1), ("C", "E", 2), ("E", "G", 2), ("A", "B", 2), ("A", "B", 3), ("C", "F", 3), ("E","G", 3)])
Directed EvolvingGraph 6 nodes, 9 static edges, 3 timestamps

Dict{EvolvingGraphs.TimeNode{String,Int64},Int64} with 14 entries:
TimeNode(B, 3) => 2
TimeNode(B, 3) => 2
TimeNode(A, 2) => 1
TimeNode(F, 1) => 2
TimeNode(G, 3) => 3
TimeNode(A, 3) => 1
TimeNode(A, 1) => 0
TimeNode(F, 3) => 3
TimeNode(B, 3) => 3
TimeNode(G, 1) => 2
TimeNode(B, 2) => 2
TimeNode(B, 2) => 2
TimeNode(G, 2) => 3
TimeNode(B, 1) => 1``````
source

## Random Graphs

``random_graph(n,p=0.5, has_self_loops=false)``

generate a random directed graph `g` with `n` nodes and the probability to include edge is `p`. If `has_self_loops`, `g` will include self loops.

source
``random_evolving_graph(nv, nt, p=0.5, is_directed=true, has_self_loops=false)``

Generate a random evolving graph `g` with `nv` nodes, `nt` timestamps. The probability to include each edge is equal to `p`. If `has_self_loops`, we allow `g` to have self loops.

source

## Sort and Slice

``issorted(g)``

Return `true` if the timestamps of an evolving graph `g` is sorted and `false` otherwise.

source
``sort_timestamps!(g)``

Sort an evolving graph `g` according to the order of its timestamps.

``````julia> using EvolvingGraphs

julia> g = EvolvingGraph()
Directed EvolvingGraph 0 nodes, 0 static edges, 0 timestamps

Directed EvolvingGraph 6 nodes, 4 static edges, 4 timestamps

julia> edges(g)
4-element Array{EvolvingGraphs.WeightedTimeEdge{EvolvingGraphs.Node{Int64},Int64,Float64},1}:
Node(1)-1.0->Node(2) at time 2001
Node(3)-1.0->Node(4) at time 2008
Node(5)-1.0->Node(6) at time 2007
Node(2)-1.0->Node(1) at time 2003

julia> sort_timestamps!(g)
Directed EvolvingGraph 6 nodes, 4 static edges, 4 timestamps

julia> edges(g)
4-element Array{EvolvingGraphs.WeightedTimeEdge{EvolvingGraphs.Node{Int64},Int64,Float64},1}:
Node(1)-1.0->Node(2) at time 2001
Node(2)-1.0->Node(1) at time 2003
Node(5)-1.0->Node(6) at time 2007
Node(3)-1.0->Node(4) at time 2008``````
source
``sort_timestamps(g)``

Sort evolving graph `g` according to timestamps, return a new sorted evolving graph.

source
``slice_timestamps!(g, t_min, t_max)``

Slice an (sorted) evolving graph `g` between timestamp `t_min` and `t_max.`

source
``slice_timestamps(g, t_min, t_max)``

Slice an (sorted) evolving graph `g` between timestamp `t_min` and `t_max.`, return a new evolving graph.

``````julia> using EvolvingGraphs

julia> g = EvolvingGraph()
Directed EvolvingGraph 0 nodes, 0 static edges, 0 timestamps

julia> add_bunch_of_edges!(g, [(1,2,1), (2,3,1), (1,4,2), (2,3,3), (3,4,5)])
Directed EvolvingGraph 4 nodes, 5 static edges, 4 timestamps

julia> g2 = slice_timestamps(g, 2,3)
Directed EvolvingGraph 4 nodes, 2 static edges, 2 timestamps

julia> edges(g)
5-element Array{EvolvingGraphs.WeightedTimeEdge{EvolvingGraphs.Node{Int64},Int64,Float64},1}:
Node(1)-1.0->Node(2) at time 1
Node(2)-1.0->Node(3) at time 1
Node(1)-1.0->Node(4) at time 2
Node(2)-1.0->Node(3) at time 3
Node(3)-1.0->Node(4) at time 5

julia> edges(g2)
2-element Array{EvolvingGraphs.WeightedTimeEdge{EvolvingGraphs.Node{Int64},Int64,Float64},1}:
Node(1)-1.0->Node(4) at time 2
Node(2)-1.0->Node(3) at time 3``````
source