Graphs.jl interface

using Graphs
using MetaGraphsNext

MetaGraphs inherit many methods from Graphs.jl. In general, inherited methods refer to vertices by codes, not labels, for compatibility with the AbstractGraph interface.

Note that vertex codes get reassigned after rem_vertex! operations to remain contiguous, so we recommend systematically converting to and from labels.

Undirected graphs

We can make MetaGraphs based on (undirected) Graphs.

cities = MetaGraph(
    Graph();
    label_type=Symbol,
    vertex_data_type=String,
    edge_data_type=Int,
    graph_data=nothing,
    weight_function=identity,
);

Let us add some cities and the distance between them:

cities[:Paris] = "France";
cities[:London] = "UK";
cities[:Berlin] = "Germany";
cities[:Paris, :London] = 344;
cities[:Paris, :Berlin] = 878;

The general properties of the graph are as expected:

is_directed(cities)

false

eltype(cities)

Int64

edgetype(cities)

Graphs.SimpleGraphs.SimpleEdge{Int64}

We can check the set of vertices:

nv(cities)

3

collect(vertices(cities))

3-element Vector{Int64}:
 1
 2
 3

has_vertex(cities, 2)

true

has_vertex(cities, 4)

false

Note that we can't add the same city (i.e. vertex label) twice:

add_vertex!(cities, :London, "Italy")

false

nv(cities)

3

cities[:London]

"UK"

We then check the set of edges:

ne(cities)

2

collect(edges(cities))

2-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 1 => 3

has_edge(cities, 1, 2)

true

has_edge(cities, 2, 3)

false

From this initial graph, we can create some others:

copy(cities)

Meta graph based on a SimpleGraph{Int64} with vertex labels of type Symbol, vertex metadata of type String, edge metadata of type Int64, graph metadata given by nothing, and default weight 1.0

zero(cities)

Meta graph based on a SimpleGraph{Int64} with vertex labels of type Symbol, vertex metadata of type String, edge metadata of type Int64, graph metadata given by nothing, and default weight 1.0

Since cities is a weighted graph, we can leverage the whole Graphs.jl machinery of graph analysis and traversal:

diameter(cities)

1222.0

ds = dijkstra_shortest_paths(cities, 2)

Graphs.DijkstraState{Float64, Int64}([2, 0, 1], [344.0, 0.0, 1222.0], [Int64[], Int64[], Int64[]], [1.0, 1.0, 1.0], Int64[])

Finally, let us remove some edges and vertices

rem_edge!(cities, 1, 3);
rem_vertex!(cities, 3);
has_vertex(cities, 1) && !has_vertex(cities, 3)

true

Directed graphs

We can make MetaGraphs based on DiGraphs as well.

rock_paper_scissors = MetaGraph(DiGraph(); label_type=Symbol, edge_data_type=String);

for label in [:rock, :paper, :scissors]
    rock_paper_scissors[label] = nothing
end

rock_paper_scissors[:rock, :scissors] = "rock beats scissors"
rock_paper_scissors[:scissors, :paper] = "scissors beat paper"
rock_paper_scissors[:paper, :rock] = "paper beats rock";

We see that the underlying graph has changed:

is_directed(rock_paper_scissors)

true

Directed graphs can be reversed:

haskey(rock_paper_scissors, :scissors, :rock)

false

haskey(reverse(rock_paper_scissors), :scissors, :rock)

true

Let us take a subgraph induced by a subset of vertices:

rock_paper, _ = induced_subgraph(rock_paper_scissors, [1, 2])

(Meta graph based on a SimpleDiGraph{Int64} with vertex labels of type Symbol, vertex metadata of type Nothing, edge metadata of type String, graph metadata given by nothing, and default weight 1.0, [1, 2])

issubset(rock_paper, rock_paper_scissors)

true

haskey(rock_paper, :paper, :rock)

true

haskey(rock_paper, :rock, :scissors)

false

Subgraphs can also be induced by a subset of edges.

subtree_edges = collect(edges(rock_paper_scissors))[2:3]
rock_paper_scissors_subtree, _ = induced_subgraph(rock_paper_scissors, subtree_edges)
issubset(rock_paper_scissors_subtree, rock_paper_scissors)
ne(rock_paper_scissors_subtree)

2

nv(rock_paper_scissors_subtree)

3

[rock_paper_scissors_subtree[e...] for e in edge_labels(rock_paper_scissors_subtree)]

2-element Vector{String}:
 "paper beats rock"
 "scissors beat paper"

Checking that a graph is a subset of another is not supported yet. For example, an induced subgraph may appear as not a subset of the original graph, if vertex codes were modified.

issubset(rock_paper_scissors_subtree, rock_paper_scissors)

false

rock_scissors, _ = induced_subgraph(rock_paper_scissors, [1, 3])
issubset(rock_scissors, rock_paper_scissors)

false

This page was generated using Literate.jl.