Algorithms

Search

EvolvingGraphs.depth_first_impl — Function.

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

EvolvingGraphs.breadth_first_impl — Function.

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

source

Random Graphs

EvolvingGraphs.random_graph — Function.

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

EvolvingGraphs.random_evolving_graph — Function.

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

Base.issorted — Function.

issorted(g)

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

source

EvolvingGraphs.sort_timestamps! — Function.

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

source

EvolvingGraphs.sort_timestamps — Function.

sort_timestamps(g)

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

source

EvolvingGraphs.slice_timestamps! — Function.

slice_timestamps!(g, t_min, t_max)

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

source

EvolvingGraphs.slice_timestamps — Function.

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