Graph Types

Graph Types

EvolvingGraphs.AbstractGraph — Type.
AbstractGraph{V,E}

Abstract supertype for all graph types, where V represents node type and E represents edge type.

source
EvolvingGraphs.AbstractEvolvingGraph — Type.
AbstractEvolvingGraph{V,E,T} <: AbstractGraph{V,E}

Abstract supertype for all evolving graph types, where V represents node type, E represents edge type, and T represents timestamp type.

source
EvolvingGraphs.AbstractStaticGraph — Type.
AbstractStaticGraph{V,E} <: AbstractGraph{V,E}

Abstract supertype for all static graph types, where V represents node type and E represents edge etype.

source

Evolving Graphs

EvolvingGraphs.EvolvingGraph — Type.
EvolvingGraph{V,T}(;is_directed=true; is_weighted=true)
EvolvingGraph(;is_directed=true; is_weighted=true)

Construct an evolving graph with node type V and timestamp type T. EvolvingGraph() constructs a simple evolving graph with integer nodes and timestamps.

Example

julia> using EvolvingGraphs

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

julia> add_node!(g, "a")
Node(a)

julia> add_node!(g, "b")
Node(b)

julia> num_nodes(g)
2

julia> add_edge!(g, "a", "b", 2001)
Node(a)->Node(b) at time 2001

julia> add_edge!(g, "a", "c", 2002)
Node(a)->Node(c) at time 2002

julia> timestamps(g)
2-element Array{Int64,1}:
 2001
 2002

julia> active_nodes(g)
4-element Array{EvolvingGraphs.TimeNode{String,Int64},1}:
 TimeNode(a, 2001)
 TimeNode(b, 2001)
 TimeNode(a, 2002)
 TimeNode(c, 2002)

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

julia> add_edge!(g, 1, 2, 1)
Node(1)-1.0->Node(2) at time 1

julia> add_edge!(g, 2, 3, 2)
Node(2)-1.0->Node(3) at time 2

julia> add_edge!(g, 1, 3, 2)
Node(1)-1.0->Node(3) at time 2

julia> nodes(g)
3-element Array{EvolvingGraphs.Node{Int64},1}:
 Node(1)
 Node(2)
 Node(3)
source
EvolvingGraphs.evolving_graph_from_arrays — Function.
evolving_graph_from_arrays(ils, jls, wls, timestamps; is_directed=true)
evolving_graph_from_arrays(ils, jls, timestamps; is_directed=true)

Generate an EvolvingGraph type object from four input arrays: ils, jls, wls and timestamps, such that the ith entry (ils[i], jls[i], wls[i], timestamps[i]) represents a WeightedTimeEdge from ils[i] to jls[i] with edge weight wls[i] at timestamp timestamp[i]. By default, wls is a vector of ones.

Example

julia> using EvolvingGraphs

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

julia> nodes(g)
5-element Array{EvolvingGraphs.Node{Int64},1}:
 Node(1)
 Node(4)
 Node(2)
 Node(5)
 Node(3)

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

julia> g = evolving_graph_from_arrays([1,2], [2, 3], [2.5, 3.8], [1998,2001])
Directed EvolvingGraph 3 nodes, 2 static edges, 2 timestamps

julia> edges(g)
2-element Array{EvolvingGraphs.WeightedTimeEdge{EvolvingGraphs.Node{Int64},Int64,Float64},1}:
 Node(1)-2.5->Node(2) at time 1998
 Node(2)-3.8->Node(3) at time 2001
source
EvolvingGraphs.adjacency_matrix — Function.
adjacency_matrix(g, t)

Return an adjacency matrix representation of an evolving graph g at timestamp t.

Example

julia> using EvolvingGraphs

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

julia> adjacency_matrix(g, 1)
5×5 Array{Float64,2}:
 0.0  1.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0
 0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0
source
EvolvingGraphs.sparse_adjacency_matrix — Function.
sparse_adjacency_matrix(g, t)

Return a sparse adjacency matrix representation of an evolving graph g at timestamp t.

Example

julia> using EvolvingGraphs

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

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

julia> sparse_adjacency_matrix(g, 1)
4×4 SparseMatrixCSC{Float64,Int64} with 1 stored entry:
  [1, 2]  =  1.0

julia> sparse_adjacency_matrix(g, 3)
4×4 SparseMatrixCSC{Float64,Int64} with 2 stored entries:
  [2, 4]  =  1.0
  [3, 4]  =  1.0

julia> sparse_adjacency_matrix(g, 2)
4×4 SparseMatrixCSC{Float64,Int64} with 1 stored entry:
  [1, 3]  =  1.0
source
EvolvingGraphs.add_graph! — Function.
add_graph!(eg, g, t)

Add a static graph g at timestamp t to an evolving graph eg.

Examples

julia> using EvolvingGraphs

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

julia> sg = DiGraph()
DiGraph 0 nodes, 0 edges

julia> add_edge!(sg, 1, 2)
Node(1)->Node(2)

julia> add_edge!(sg, 2, 3)
Node(2)->Node(3)

julia> add_graph!(g, sg, 1)
Directed EvolvingGraph 3 nodes, 2 static edges, 1 timestamps

julia> edges(g)
2-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
source

Matrix List

EvolvingGraphs.MatrixList — Type.
MatrixList

Data type of storing a list of sparse matrices in CSC format.

source
EvolvingGraphs.evolving_graph_to_matrices — Function.
evolving_graph_to_matrices(g)

Convert an evolving graph g to a matrix list.

Example

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,4,1), (2,3,1), (3,4,2), (1,3,3)])
Directed EvolvingGraph 4 nodes, 5 static edges, 3 timestamps

julia> ml = evolving_graph_to_matrices(g)
MatrixList (3 matrices)

julia> sparse_adjacency_matrix(ml, 1)
4×4 SparseMatrixCSC{Float64,Int64} with 3 stored entries:
  [1, 2]  =  1.0
  [2, 3]  =  1.0
  [2, 4]  =  1.0

julia> sparse_adjacency_matrix(ml,2)
4×4 SparseMatrixCSC{Float64,Int64} with 1 stored entry:
  [4, 3]  =  1.0
source
EvolvingGraphs.matrices — Function.
matrices(ml)

Return a list of matrices in MatrixList ml.

source
EvolvingGraphs.num_matrices — Function.
num_matrices(ml)

Return the number of matrices in MatrixList ml.

source

Adjacency List

EvolvingGraphs.IntAdjacencyList — Type.
IntAdjacencyList(nv, nt)

Construct a graph represented by an adjacency list with nv nodes and nt timestamps, where both nodes and timestamps are represented by integers.

Example

julia> using EvolvingGraphs

julia> g = IntAdjacencyList(4,3)
Directed IntAdjacencyList (4 nodes, 0 static edges, 3 timestamps)

julia> add_edge!(g, 1, 2, 1)
Directed IntAdjacencyList (4 nodes, 1 static edges, 3 timestamps)

julia> add_edge!(g, 2, 3, 2)
Directed IntAdjacencyList (4 nodes, 2 static edges, 3 timestamps)

julia> num_edges(g)
2
source
EvolvingGraphs.evolving_graph_to_adj — Function.
evolving_graph_to_adj(g)

Convert an evolving graph g to an adjacency list.

Example

julia> using EvolvingGraphs

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

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

julia> evolving_graph_to_adj(g)
Directed IntAdjacencyList (4 nodes, 4 static edges, 3 timestamps)
source

Static Graphs

EvolvingGraphs.DiGraph — Type.
DiGraph{V,E}()
DiGraph{V}()
DiGraph()

Construct a static directed graph with node type V and edge type E. DiGraph() constructs a static directed graph with integer nodes and edges.

Example

julia> using EvolvingGraphs

julia> g = DiGraph()
DiGraph 0 nodes, 0 edges

julia> add_edge!(g, 1, 2)
Node(1)->Node(2)

julia> add_edge!(g, 2, 3)
Node(2)->Node(3)

julia> adjacency_matrix(g)
3×3 Array{Float64,2}:
 0.0  1.0  0.0
 0.0  0.0  1.0
 0.0  0.0  0.0

julia> add_node!(g, 4)
Node(4)

julia> nodes(g)
4-element Array{EvolvingGraphs.Node{Int64},1}:
 Node(1)
 Node(2)
 Node(3)
 Node(4)
source
EvolvingGraphs.out_edges — Function.
out_edges(g, v)

Return the outward edges of node v in a static graph g, where v can be a node or a node key.

Example

julia> using EvolvingGraphs

julia> g = DiGraph()
DiGraph 0 nodes, 0 edges

julia> add_bunch_of_edges!(g, [(1,2), (2,3), (3,4)])
DiGraph 4 nodes, 3 edges

julia> out_edges(g, 1)
1-element Array{EvolvingGraphs.Edge{EvolvingGraphs.Node{Int64}},1}:
 Node(1)->Node(2)
source
EvolvingGraphs.out_degree — Function.
out_degree(g, v)

Return the number of outward edges of node v in static graph g, where v can be a node of a node key.

source
EvolvingGraphs.in_edges — Function.
in_edges(g, v)

Return the inward edges of node v in static graph g.

Example

julia> using EvolvingGraphs

julia> g = DiGraph()
DiGraph 0 nodes, 0 edges

julia> add_bunch_of_edges!(g, [(2,1), (3,1), (4,1)])
DiGraph 4 nodes, 3 edges

julia> in_edges(g,1)
3-element Array{EvolvingGraphs.Edge{EvolvingGraphs.Node{Int64}},1}:
 Node(2)->Node(1)
 Node(3)->Node(1)
 Node(4)->Node(1)

julia> in_degree(g,1)
3
source
EvolvingGraphs.in_degree — Function.
in_degree(g, v)

Return the number of inward edges of node v in static graph g.

source
EvolvingGraphs.aggregate_graph — Function.
aggregate_graph(g)

Convert an evolving graph g to a static graph by aggregate the edges to the same timestamp.

Example

julia> using EvolvingGraphs

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

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

julia> aggregate_graph(eg)
DiGraph 3 nodes, 2 edges
source

General Functions

EvolvingGraphs.nodes — Function.
nodes(g)

Return the nodes of a graph g.

source
EvolvingGraphs.num_nodes — Function.
num_nodes(g)
source
EvolvingGraphs.active_nodes — Function.
active_nodes(g)

Return the active nodes of an evolving graph g. An active node is a node at a specific time stamp.

julia> using EvolvingGraphs

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

julia> add_edge!(g, 1, 2, 2001)
Node(1)-1.0->Node(2) at time 2001

julia> add_edge!(g, 1, 2, 2002)
Node(1)-1.0->Node(2) at time 2002

julia> nodes(g)
2-element Array{EvolvingGraphs.Node{Int64},1}:
 Node(1)
 Node(2)

julia> active_nodes(g)
4-element Array{EvolvingGraphs.TimeNode{Int64,Int64},1}:
 TimeNode(1, 2001)
 TimeNode(2, 2001)
 TimeNode(1, 2002)
 TimeNode(2, 2002)
source
EvolvingGraphs.num_active_nodes — Function.
num_active_nodes(g)

Return the number of active nodes of evolving graph g.

source
EvolvingGraphs.add_node! — Function.
add_node!(g, v)

Add a node to graph g, where v can be either a node type object or a node key.

source
EvolvingGraphs.find_node — Function.
find_node(g, v)

Return node v if v is a node of graph g, otherwise return false. If v is a node key, return corresponding node.

source
EvolvingGraphs.edges — Function.
edges(g)
edges(g, t)

Return all the edges of graph g. If timestamp t is given, returns all the edges at timestamp t.

source
EvolvingGraphs.num_edges — Function.
num_edges(g)

Return the number of edges of graph g.

source
EvolvingGraphs.add_edge! — Function.
add_edge!(g, v1, v2, t; weight = 1.0)

Add an edge from v1 to v2 at timestamp t to evolving graph g. By default edge weight weight is equal to 1.0.

source
EvolvingGraphs.add_bunch_of_edges! — Function.
add_bunch_of_edges!(g, ebunch)

Add a bunch of edges to graph g where ebunch is an array of edges. Each edge in ebunch is of form (source, target, timestamp) or (source, target, timestamp, weight).

Example

julia> using EvolvingGraphs

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

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

julia> timestamps(g)
4-element Array{Int64,1}:
 2001
 2001
 2002
 2004
source
EvolvingGraphs.is_directed — Function.
is_directed(g)

Determine if a graph g is a directed graph.

source
EvolvingGraphs.timestamps — Function.
timestamps(g)

Return the timestamps of graph g.

source
EvolvingGraphs.unique_timestamps — Function.
unique_timestamps(g)

Return the unique timestamps of graph g.

source
EvolvingGraphs.num_timestamps — Function.
num_timestamps(g)

Return the number of timestamps of graph g.

source
EvolvingGraphs.forward_neighbors — Function.
forward_neighbors(g, v)

Find the forward neighbors of a node v in graph g. If g is an evolving graph, we define the forward neighbors of a TimeNode v to be a collection of forward neighbors at time stamp node_timestamp(v) and the same node key at later time stamps.

Example

julia> using EvolvingGraphs

julia> g = evolving_graph_from_arrays([1,1,2],[2,3,3], [1,2,3])
Directed EvolvingGraph 3 nodes, 3 static edges, 3 timestamps

julia> n = active_nodes(g)[1]
TimeNode(1, 1)

julia> forward_neighbors(g,n)
2-element Array{EvolvingGraphs.TimeNode{Int64,Int64},1}:
 TimeNode(2, 1)
 TimeNode(1, 2)

References:

  1. Jiahao Chen and Weijian Zhang, The Right Way to Search Evolving Graphs, Proceedings of IPDPS 2016.

source
EvolvingGraphs.backward_neighbors — Function.
backward_neighbors(g, v)

Find the backward neighbors of a node v in graph g. If g is an evolving graph, we define the backward neighbors of a TimeNode v to be a collection of backward neighbors at time stamp node_timestamp(v) and the same node key at earlier time stamps.

julia> using EvolvingGraphs

julia> g = evolving_graph_from_arrays([1,1,2],[2,3,3], [1,2,3])
Directed EvolvingGraph 3 nodes, 3 static edges, 3 timestamps

julia> n = active_nodes(g)[2]
TimeNode(2, 1)

julia> backward_neighbors(g,n)
1-element Array{EvolvingGraphs.TimeNode{Int64,Int64},1}:
 TimeNode(1, 1)

References:

  1. Jiahao Chen and Weijian Zhang, The Right Way to Search Evolving Graphs, Proceedings of IPDPS 2016.

source