Labeled Graphs
QXGraphDecompositions uses the SimpleGraph struct from the LightGraphs package to store graph structures. However, some of the algorithms implemented in QXGraphDecompositions repeatedly modify the graphs they work on, either by removing or adding vertices in varying orders, and in turn alter the manner in which vertices of the graph are indexed. This can make it difficult to track where vertices end up in a graph after many modifications are made, which needs to be done if the vertices are used to index different variables in an alternate data structure, such as indices or tensors in a tensor network. To this end, QXGraphDecompositions defines a LabeledGraph struct which pairs a SimpleGraph with and array of julia symbols that can be used to identify vertices in a graph after modifications have been made.
QXGraphDecompositions.LabeledGraph — TypeStruct to represent a labeled graph. Unique symbols are created for each vertex if none are provided and remain unaltered during the lifetime of the graph.
Example
julia> g = LabeledGraph()
LabeledGraph({0, 0} undirected simple Int64 graph, Symbol[])
julia> add_vertex!(g, :a_vertex_label)
1-element Array{Symbol,1}:
:a_vertex_label
julia> g.labels[1]
:a_vertex_labelExample usage
An example of how to use LabeledGraphs is shown below. Note, whenever a modification is made to the graph which re-indexes or re-positions the vertices in the graph, the array of vertex labels in the LabeledGraph is also updated to reflect the reordering. Hence, when a sequence of modifications is made to the graph, we can identify how the vertices of the original graph are now indexed in the new graph by looking at how the corresponding labels are indexed inside the LabeledGraph.
using QXGraphDecompositions
# Create a LabeledGraph with N vertices
N = 10
G = LabeledGraph(N)
# Display the label assigned to the first and last vertices of the graph.
@show G.labels[1]
@show G.labels[end]
# Remove the first vertex of the graph. To remove a vertex, LightGraphs first swaps the
# positions of the vertex being removed with the last vertex and then removes the last vertex.
rem_vertex!(G, 1)
# Display the label which is now assigned to the first vertex in the graph.
@show G.labels[1]LabeledGraph Interface
The interface for the LabeledGraph struct is intended to reflect the interface implemented by the LightGraphs package for the SimpleGraph struct.
QXGraphDecompositions.labels — Functionlabels(G::LabeledGraph)Return the labels contained in a LabeledGraph.
QXGraphDecompositions.get_vertex — Functionget_vertex(G::LabledGraph, v_label)Return the first vertex whose label matches the argument v_label. If an array of labels is provided, an array of the corresponding vertices is return.
QXGraphDecompositions.vertices — Functionvertices(G::LabeledGraph)Return the vertices of a labeled graph.
QXGraphDecompositions.nv — Functionnv(G::LabeledGraph)Return the number of vertices in G.
QXGraphDecompositions.add_vertex! — Functionadd_vertex!(G::LabeledGraph, label::Symbol)Add a new vertex to G and assign the given label to it.
QXGraphDecompositions.rem_vertex! — Functionrem_vertex!(G::LabeledGraph, v)Delete the vertex with index or label v from G.
QXGraphDecompositions.edges — Functionedges(G::LabeledGraph)Return an iterator of the edges of G.
QXGraphDecompositions.ne — Functionne(G::LabeledGraph)Return the number of edges in G.
QXGraphDecompositions.add_edge! — Functionadd_edge!(G::LabeledGraph, u::Int, v::Int)Add an edge to G connecting vertices u and v.
QXGraphDecompositions.has_edge — Functionhas_edge(G::LabeledGraph, u::Int, v::Int)Return true if G has an edge connecting vertices u and v. Return false otherwise.
QXGraphDecompositions.rem_edge! — Functionrem_edge!(G::LabeledGraph, u::Int, v::Int)Remove the edge connecting vertices u and v if it exists.
QXGraphDecompositions.degree — Functiondegree(G::LabeledGraph[, v])Return an array containing the degree of each vertex of G. If v is specified, only return degrees for vertices in v.
QXGraphDecompositions.all_neighbors — Functionall_neighbors(G::LabeledGraph, v::Int)Return an array of all neighbors of v in G.
QXGraphDecompositions.eliminate! — Functioneliminate!(G::LabledGraph, v)Connect all the neighbors of v together before removing v from G.
eliminate!(G::AbstractGraph, v::Integer)Connect all the neighbours of v together before removing v from G.
eliminate!(G::AbstractGraph, v::Integer, c_map::Dict{Int, Int})Connect all the neighbours of v together before removing v from G.
The dictionary c_map mapping vertices of 'G' to their cliqueness is updated inplace accordingly.
QXGraphDecompositions.cliqueness — Functioncliqueness(G::LabeledGraph, v::Symbol)Return the number of edges that need to be added to G in order to make the neighborhood of vertex labeled by the symbol v a clique.
cliqueness(G::LabeledGraph, v::Integer)Return the number of edges that need to be added to G in order to make the neighborhood of vertex v a clique.
LabeledGraph Constructors
QXGraphDecompositions.line_graph — Functionline_graph(G::LabeledGraph)Return a LabeledGraph representing the line graph of the 'G'.
The label for each each vertex of the line graph is created by concatenating the labels of the corresponding vertices in the LabeledGraph 'G'.
line_graph(G::AbstractGraph;
vertex_labels::Array{Symbol, 1}=Symbol[])Return a LabeledGraph representing the line graph of the 'G'.
The label for each each vertex of the line graph is created by concatenating the labels of the corresponding vertices in 'G'.
The symbols in the array vertex_labels are used as labels for the vertices of the returned line graph. If vertex_labels is empty then labels are created by combining the indices of the corresponding vertices in 'G'.
QXGraphDecompositions.tree_from_tree_decompostion — Functiontree_from_tree_decompostion(td::Dict{Symbol, Any})Returns a LabeledGraph representing the tree described by the tree decomposition in td.
QXGraphDecompositions.chordal_graph — Functionchordal_graph(G::LabeledGraph, π̄::Array{Symbol, 1})Return a chordal graph built from 'G' using the elimination order 'π̄'.
The returned graph is created from 'G' by iterating over the vertices of 'G', according to the order 'π̄', and for each vertex, connecting all the neighbors that appear later in the order.
LabeledGraph IO
QXGraphDecompositions.graph_to_gr — Functiongraph_to_gr(G::LabeledGraph, filename::String)Write the provided graph to a file in gr format.
Missing docstring for graph_from_gr. Check Documenter's build log for details.
QXGraphDecompositions.graph_to_cnf — Functiongraph_to_cnf(G::LabeledGraph, filename::String)Write the provided graph to a file in cnf format.
Missing docstring for graph_from_cnf. Check Documenter's build log for details.