Algorithms

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)

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

julia> breadth_first_impl(g, "A", 1)
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

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.

random_evolving_graph(nn, nt, p=0.5, is_directed=true, has_self_loops=false)
random_evolving_graph(g, nn, nt, p=0.5, is_directed=true, has_self_loops=false)

Generate a random evolving graph g with nn nodes, nt timestamps. The random evolving graph has integer nodes and timestamps. The probability to include each edge is equal to p. If has_self_loops, we allow g to have self loops. If g is not given, we generate a random IntAdjacencyList evolving graph.

Example

julia> using EvolvingGraphs

julia> random_evolving_graph(10, 4, 0.1)
Directed IntAdjacencyList (10 nodes, 37 static edges, 4 timestamps)

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

julia> random_evolving_graph(g, 20, 3, 0.5)
Directed EvolvingGraph 20 nodes, 558 static edges, 3 timestamps

issorted(g)

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

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

julia> add_bunch_of_edges!(g, [(1,2,2001),(3,4,2008),(5,6,2007),(2,1,2003)])
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

sort_timestamps(g)

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

slice_timestamps!(g, t_min, t_max)

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

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