Summary

JuliaGraphs/LEMONGraphs.jl packages exists and provides a barebones wrapper for the LEMON C++ library.
- JuliaGraphs wants to better support LEMON graphs and networks through funding from the NSF for Quantum Networks.
  - Familiarity with the Graphs.jl API and understanding of the CxxWrap interface package is helpful to interpret requirements

Requirements

fast conversion between Graphs.jl and the C++ structs of LEMON
- slow converters already exist for simple graphs
complete graph API support for the LEMONGraph types
- compatibile use with existing Graph.jl algorithms that do not peek behind the API
GraphsInterfaceChecker.jl in test suite
dispatch from ops defined Graphs/GraphsMatching/GraphsOptim 2 LEMON implementation
- i.e. if theres pre-existing `Graphs.some_{interestingproperty}(::AbstractGraph)`
  - then there should now be a method defined in LEMONGraphs `some_{interestingproperty}(g::AbstractGraph, ::LEMONAlgorithm)`
    - that dispatches to the C++ implementation
      - converting `g` argument to LEMONGraph if necessary
if there is an algorithm in LEMON that does not exist in Graphs.jl
- it should be declared in Graphs.jl, just a func w/ docs but no methods
  - with an error hint if necessary
- given large scope of the library, this should be a PoC setup
  - documenting how to add everything
Idiomatic code, implementation tests, and easy-to-digest documentation

submit with clean git histories and good practices for version control
- well-defined for ease of review

Warmup

study the Graphs.jl API

https://juliagraphs.org/Graphs.jl
- JuliaGraphsTutorials https://github.com/JuliaGraphs/JuliaGraphsTutorials Jupyter Notebooks for learning JuliaGraphs
- Practice Graph Theory
  
  graph generators
  - SBM
  - Barabasi-Albert Model
  - Dorogovtsev-Mendes
  - Erdos-Renyi
  - Generation of Networks with Given Expected Degrees
  - Kronecker graph
  - random-oriented graph, random tournament graph
  - static fitness model
  - scale-free networks
  - Watts-Strogatz small world random graph
  - Barbell graph
  - Binary Tree
  - Circular Ladder graph
  - Clique graph
  - complete mulitpartite/bipartite graph
  - grid
  - lollipop graph
  - roach graph
  - star graph
  - Turan graph
  - wheel graph
  - small graph
  - euclidean graph
  graph pathing and traversal
  - breadth first tree
  - topological sort by depth first search
  - depth first tree
  - maximum adjacency search
  - diffusion
  - random walks
  - graph connectivity
  - bipartite map
  - condensation
  - neighborhood
  - articulation
  - bridges
  - cycle detection
  - minimum spanning trees
  - shortest-path algos
  - path discovery/enumeration
- Reading through docs
- Graph types and creating your own Graph format
- Test graphs
- Contributor Guide
study the LEMON Tutorial http://lemon.cs.elte.hu/pub/tutorial/index.html
Learn CxxWrap to wrap C++ types to Julia https://github.com/JuliaInterop/CxxWrap.jl
- external example: GeographicModels.jl
  - wrapping GeographicLib C++ types for EGMs

Graphs.jl

network and graph analysis in julia
- offering concrete graph implementations
  - SimpleGraph for undirected graphs
  - SimpleDiGraph for directed graphs
    - AbstractGraph abstract type
central package of JuliaGraphs ecosystem
- additional functionality via
  - LightGraphsExtras.jl, MetaGraphs.jl, SimpleWeightedGraphs.jl, GraphIO.jl GraphDataFrameBridge.jl

basic example

using Graphs

g = path_graph(6)
# # of verts
nv(g)
# # of edges
ne(g)
# add edge to make path a loop
add_edge!(g, 1, 6)

Graph Types

In addition to SimpleGraph/SimpleDiGraph
- Graphs serves alternative graph types
  - (un)directed graphs with the ability to specify weights on edges
  - (un)directed graphs that supports UDF properties on graph, verts, and edges
  - supports massive graph structures in a space-time efficient manner
    - but is static, meaning its immutable once instantiated
      
      which to use?
      - prefer the simple implementaitons!
        
        if we need edge weights and does NOT require large numbers of graph manipulations–use weighted graphs
        
        if we need labeling of verts/edges use metadata graphs
        
        if we have graphs with billions to tens of billions of edges and dont need mutability– use static graphs

Concrete Types

SimpleGraph and SimpleDiGraph
- subtypes of AbstractGraphs and system default integer type of Int64

a graph G is described by a set of vertices V and edges E G = {V,E}
- V is an int range `1:n`
- E is represented as forward (or backward for digraph) adjacency lists indexed by vertices
  - edges are also accessed via an iterator
    - that yields `Edge` types containg `(src<:Integer, dst<:Integer)` values
    - both verts and edges may be ints of any type
      - and smallest type that fits the data is recommended in order to save memory
      Graphs are created using SimpleGraph() and SimpleDiGraph() and more
      
      Multiple edges between two given vertices are not allowed
      - an attempt to add an edge that already exists in graph WILL NOT raise an error
        
        this event can be detected using the return val of `add_edge!`
      NOTE: graphs in which the number of vertices equals or approaches the typemax of the underlying graph element
      - may encounter ARITHMETIC OVERFLOW errors in some functions

ensure your graph is sized with some spare capacity

AbstractGraph Type

Graphs.jl is structured around a few abstract types
- developers can base their types on
  
  Graphs.AbstractEdge Graphs.AbstractEdgeIter Graphs.AbstractGraph

All types that are a subset of AbstractGraph must implement the following functions: Base.reverse Base.zero Graphs.dst Graphs.edges Graphs.edgetype Graphs.has_edge Graphs.inneighbors Graphs.is_directed Graphs.ne Graphs.nv Graphs.outneighbors Graphs.src Graphs.vertices

using Graphs

g = SimpleDiGraph(2)
add_edge!(g, 1, 2)
reverse(first(edges(g)))
# Edge 2 => 1
dst(first(edges(g)))
# 2

g = path_graph(3)
collect(edges(g))
#2-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
# Edge 1 => 2
# Edge 2 => 3
edgetype(g)
# SimpleEdge
has_edge(g, 1, 2)
# true
has_edge(g, 2, 1)
# false
has_vertex(SimpleGraph(2), 1)
# true
g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);
inneighbors(g, 4)
#2-element Array{Int64,1}:
# 3
# 5
is_directed(SimpleGraph(2))
# false
g = path_graph(3)
ne(g)
# 2
nv(SimpleGraph(3))
# 3
g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);
outneighbors(g, 4)
#1-element Array{Int64,1}:
# 5
g = SimpleGraph(2)
add_edge!(g, 1, 2)
src(first(edges(g)))
# 1
collect(vertices(SimpleGraph(4)))
#4-element Array{Int64,1}:
# 1
# 2
# 3
# 4

g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);
zero(typeof(g))
# {0, 0} directed simple Int64 graph
zero(g)
# {0, 0} directed simple Int64 graph

Source Code for simple undirected graphs

simple edge

import Base: Pair, Tuple, show, ==, hash
import Graphs: AbstractEdge, src, dst, reverse

abstract type AbstractSimpleEdge{T<:Integer} <: AbstractEdge{T} end

struct SimpleEdge{T<:Integer} <: AbstractSimpleEdge{T}
    src::T
    dst::T
end

SimpleEdge(t::Tuple) = SimpleEdge(t[1], t[2])
SimpleEdge(p::Pair) = SimpleEdge(p.first, p.second)
SimpleEdge{T}(p::Pair) where T<:Integer = SimpleEdge(T(p.first), T(p.second))
SimpleEdge{T}(t::Tuple) where T<:Integer = SimpleEdge(T(t[1]), T(t[2]))

eltype(::Type{<:ET}) where ET<:AbstractSimpleEdge{T} where T = T

# Accessors
src(e::AbstractSimpleEdge) = e.src
dst(e::AbstractSimpleEdge) = e.dst

# I/O
show(io::IO, e::AbstractSimpleEdge) = print(io, "Edge $(e.src) => $(e.dst)")

# Conversions
Pair(e::AbstractSimpleEdge) = Pair(src(e), dst(e))
Tuple(e::AbstractSimpleEdge) = (src(e), dst(e))

SimpleEdge{T}(e::AbstractSimpleEdge) where T <: Integer = SimpleEdge{T}(T(e.src), T(e.dst))

# Convenience functions
reverse(e::T) where T<:AbstractSimpleEdge = T(dst(e), src(e))
==(e1::AbstractSimpleEdge, e2::AbstractSimpleEdge) = (src(e1) == src(e2) && dst(e1) == dst(e2))
hash(e::AbstractSimpleEdge, h::UInt) = hash(src(e), hash(dst(e), h))

type for undirected graph

mutable struct SimpleGraph{T <: Integer} <: AbstractSimpleGraph{T}
    ne::Int
    fadjlist::Vector{Vector{T}} # [src]: (dst, dst, dst)

    function SimpleGraph{T}(ne::Int, fadjlist::Vector{Vector{T}}) where T
        throw_if_invalid_eltype(T)
        new{T}(ne, fadjlist)
    end
end

function SimpleGraph(
    ne,
    fadjlist::Vector{Vector{T}}
) where T

    SimpleGraph{T}(ne, fadjlist)
end

eltype(x::SimpleGraph{T}) where T = T

Making and Modifying Graphs

Graphs.jl provides a number of methods for creating a graph object
- tools for building and manipulating graph objects
  - a wide array of graph generator functions
    - and the ability to read and write graphs from files
      - using GraphIO.jl

Modifying Graphs

SimpleGraph{T}
SimpleGraphFromIterator(iter)
eltype(iter) <: SimpleEdge
SimpleDiGraph{T}
SimpleDiGraphFromIterator(iter)
Edge
add_edge!
rem_edge!
add_vertex!
add_vertices!
rem_vertex!
Base.zero(g)
# Return a zero-vertex, zero-edge version of the graph type G

Graph Generators

Graphs.jl implements many graph generators

Graphs.Edge Graphs.add_vertices!

Datasets
- graphs and integration withe the MatrixDepot.jl pkg are available in Datasets submodule of LightGraphsExtra.jl
- selected graphs from Stanford Large Network Dataset Collection may found in SNAPDatasets.jl

ALL GENERATORS

SimpleDiGraph{T}(nv, ne; seed=-1)
SimpleGraph{T}(nv, ne, edgestream::Channel)
SimpleGraph{T}(nv, ne, smb::StochasticBlockModel)
SimpleGraph{T}(nv, ne; seed=-1)
StochasticBlockModel{T,P}
barabasi_albert!(g::AbstractGraph, n::Integer, k::Integer)
barabasi_albert(n::Integer, n0::Integer, k::Integer)
barabasi_albert(n, k)
blockcounts(sbm, A)
dorogovtsev_mendes(n)
erdos_renyi(n, ne)
erdos_renyi(n, p)
expected_degree_graph(ω)
kronecker(SCALE, edgefactor, A=0.57, B=0.19, C=0.19; seed=-1)
make_edgestream(sbm)
random_configuration_model(n, ks)
random_orientation_dag(g)
random_regular_digraph(n, k)
random_regular_graph(n, k)
random_tournament_digraph(n)
static_fitness_model(m, fitness)
static_fitness_model(m, fitness_out, fitness_in)
static_scale_free(n, m, α_out, α_in)
stochastic_block_model(c, n)
# just to name a few theres a bunch...

Reading/Writing Graphs

Graphs may be written to I/O streams and files using savegraph and read with the loadgraph

the default graph format is compressed Graphs.jl gormat LG


g = erdos_renyi(5, 0.2)

savegraph("mygraph.lgz", g)
reloaded_g = loadgraph("mygraph.lgz")

# dictionaries of graphs can also be saved
# and subsequently re-loaded one by one
graph_dict = {"g1" => erdos_renyi(5, 0.1),
              "g2" => erdos_renyi(10, 0.2),
              "g3" => erdos_renyi(2, 0.9)}

savegraph("mygraph_dict.lg", graph_dict)

# Re-load only graph g1
reloaded_g1 = loadgraph("mygraph_dict.lg", "g1")

Source code for loadgraph and savegraph

function loadgraph(fn::AbstractString, gname::AbstractString, format::AbstractGraphFormat)
    open(fn, "r") do io
        loadgraph(auto_decompress(io), gname, format)
    end
end
loadgraph(fn::AbstractString) = loadgraph(fn, "graph", LGFormat())
loadgraph(fn::AbstractString, gname::AbstractString) = loadgraph(fn, gname, LGFormat())
loadgraph(fn::AbstractString, format::AbstractGraphFormat) = loadgraph(fn, "graph", format)


function savegraph(fn::AbstractString, g::AbstractGraph, gname::AbstractString,
        format::AbstractGraphFormat; compress=nothing
    )
    if compress !== nothing
        if !compress
            @info("Note: the `compress` keyword is no longer supported in Graphs. Saving uncompressed.")
        else
            Base.depwarn("Saving compressed graphs is no longer supported in Graphs. Use `LGCompressedFormat()` from the `GraphIO.jl` package instead. Saving uncompressed.", :savegraph)
        end
    end
    io = open(fn, "w")
    try
        return savegraph(io, g, gname, format)
    catch
        rethrow()
    finally
        close(io)
    end
end

# without graph name
savegraph(fn::AbstractString, g::AbstractGraph, format::AbstractGraphFormat; compress=nothing) =
    savegraph(fn, g, "graph", format, compress=compress)

# without format - default to LGFormat()
savegraph(fn::AbstractString, g::AbstractSimpleGraph; compress=nothing) = savegraph(fn, g, "graph", LGFormat(), compress=compress)

Operators

Graphs.jl implements the following graph operators. In general, functions with two graph arguments will require them to be of the same type (either both SimpleGraph or both SimpleDiGraph).

Base.intersect Base.join Base.reverse Base.reverse! Base.union Graphs.cartesian_product Graphs.complement Graphs.crosspath Graphs.difference Graphs.egonet Graphs.induced_subgraph Graphs.merge_vertices Graphs.merge_vertices! Graphs.symmetric_difference Graphs.tensor_product SparseArrays.blockdiag

Core functions

Graphs.jl includes the following core functions:

Graphs.add_vertices! Graphs.all_neighbors Graphs.common_neighbors Graphs.degree Graphs.degree_histogram Graphs.density Graphs.has_selfloops Graphs.indegree Graphs.is_ordered Graphs.neighbors Graphs.num_selfloops Graphs.outdegree Graphs.squash Graphs.weights Graphs.Δ Graphs.Δin Graphs.Δout Graphs.δ Graphs.δin Graphs.δout

Plotting Graphs

Integrates with GraphPlot.jl, GraphRecipes.jl, GraphMakie.jl, and more

Path and Traversal

Graphs.jl provides several traversal and shortest-path algos w/ various utilty functions
- where appropriate, edge distances may be passed in as a matrix of real-number values
edge distances for most traversals may be passed in as a sparse or dense matrix of values index by [src,dst] vertices
- that is distmx[2,4] = 2.5 assigns the distance 2.5 to (directed) edge connecting vertex 2 and vertex 4
  
  default edge distances are passed in via
  
  DefaultDistance

Traversal

traversal refers to a process that traverses vertices of a graph
- following a certain order
  
  BreadthFirst
provides a breadth first traversal of the graph `g`starting with source vertex `s`,
- and return a DAG of vertices in the order they were discoverd
perform a BFS of graph `g` starting from vertex `s`
- return a vector of parent vertices indexed by vertex this implementation is designed to perform well on large graphs

bfs(g, s[; dir=:out])
bfs_parents(g, s[; dir=:out])

DepthFirst

return a topo sort of a directed graph `g` as a vector of vertices
- in topological order
return an ordered vector of vertices representing a DAG
- based on DFS of graph `g` starting with source vertex `s`
```
topological_sort_by_dfs(g)
dfs_tree(g, s)
```
MaximumAdjacency
return vertices in `g` traversed by maximum adjacency search
- starting from `s` optionally
- optional `distmx` matrix
- if `log` is `true`
  - visitor events will be printed to `io` `STDOUT`
```
maximum_adjacency_visit(g[, distmx][, log][, io][, s])
maximum_adjacency_visit(g[, s])
```

Diffusion

run diffusion simulation for `g` and `n` steps with spread probability based on `p`
- return a vector with the set of new vertices reached at each step of the simul.
given results of `diffusion` or params to the `diffusion` itself
- return the rate of diffusion as a vector resprestnting the cum num of vertices
  - infected at each simulation step
```
diffusion(g, p, n)
diffusion_rate(g, p, n; ...)
```

Random Walks

perform a random walk on graph `g` starting at `s`
- continuing for a maximum of `niter` steps
  - return a vector of vertices vistited in order

randomwalk(g, s, niter; seed=-1)
non_backtracking_randomwalk(g, s, niter; seed=-1)
self_avoiding_walk(g, s, niter; seed=-1)

Connectivity/Bipartiteness

connectivity funcs are defined on both undirected and directed graphs

is_connected(g)
is_strongly_connected(g)
is_weakly_connected(g)
connected_components(g)
strongly_connected_components(g)
strongly_connected_components_kosaraju(g)
weakly_connected_components(g)
has_self_loops(g)
attracting_components(g)
is_bipartite(g)
bipartite_map(g) -> Vector{UInt8}
biconnected_components(g) -> Vector{Vector{Edge{eltype(g)}}}
condensation(g[, scc])
neighborhood(g, v, d, distmx=weights(g))
neighborhood_dists(g, v, d, distmx=weights(g))
articulation(g)
bridges(g)
period(g)
isgraphical(degs)

Cycle Detection

is_cyclic(g)
cycle_basis(g, root=nothing)
maxsimplecycles(dg::::IsDirected, byscc::Bool = true)
simplecycles(dg::::IsDirected)
simplecycles_iter(dg::DiGraph, ceiling = 10^6)
simplecycles_hawick_james(g)
simplecyclescount(dg::DiGraph, ceiling = 10^6)
simplecycleslength(dg::DiGraph, ceiling = 10^6)
simplecycles_limited_length(g, n, ceiling=10^6)
karp_minimum_cycle_mean(g[, distmx])

Minimum Spanning Trees

kruskal_mst(g, distmx=weights(g); minimize=true)
prim_mst(g, distmx=weights(g))

Shortest-Path

a_star(g, s, t[, distmx][, heuristic])
dijkstra_shortest_paths(g, srcs, distmx=weights(g));
desopo_pape_shortest_paths(g, src, distmx=weights(g))
bellman_ford_shortest_paths(g, s, distmx=weights(g))
bellman_ford_shortest_paths(g, ss, distmx=weights(g))
floyd_warshall_shortest_paths(g, distmx=weights(g))
yen_k_shortest_paths(g, source, target, distmx=weights(g), K=1; maxdist=Inf);
spfa_shortest_paths(g, s, distmx=weights(g))

Path discovery/enumeration

gdistances(g, source; sort_alg=QuickSort)
gdistances!(g, source, dists; sort_alg=QuickSort)
enumerate_paths(state[, vs])
AbstractPathState
struct DijkstraState{T, U}
struct DEposoPapeState{T, U}
BellmanFordState{T, U}
struct FloydWarshallState{T, U}
struct YenState{T, U}

Distance Measurement

BoundedMinkowskiCost(μ₁, μ₂)
MinkowskiCost(μ₁, μ₂; p::Real=1)
center(eccentricities)
center(g, distmx=weights(g))
diameter(eccentricities)
diameter(g, distmx=weights(g))
eccentricity(g[, v][, distmx])
eccentricity(g[, vs][, distmx])
edit_distance(G₁::AbstractGraph, G₂::AbstractGraph)
edit_distance(G₁, G₂, subst_cost=MinkowskiCost(μ₁, μ₂))
periphery(eccentricities)
periphery(g, distmx=weights(g))
radius(eccentricities)
radius(g, distmx=weights(g))
transitiveclosure(g, selflooped=false)
transitiveclosure(g, selflooped=false)

Centrality Measures

betweenness_centrality(g[, vs])
betweenness_centrality(g, k)
closeness_centrality(g, distmx=weights(g); normalize=true)
degree_centrality(g)
indegree_centrality(g)
outdegree_centrality(g)
eigenvector_centrality(g)
katz_centrality(g, α=0.3)
pagerank(g, α=0.85, n=100, ϵ=1.0e-6)
stress_centrality(g[, vs])
stress_centrality(g, k)
radiality_centrality(g)

Linear Algebra

Developing Alternate Graph Types

All graph functions rely on the Graphs.jl API
- As long as your graph structure is a subtype of AbstractGraph
  - and implements the following API functions given return values
    
    edges Base.eltype edgetype has_edge has_vertex inneighbors ne nv outneighbors vertices is_directed zero
if the graph is designed to represent weights on edges, the weights function should also be defined

Inheriting from AbstractSimpleGraph

every subtype of AbstractSimpleGraph must have vertices forming a UnitRange
- starting from 1 and return neighbors in ascending order

LinAlg is the pkg for using the type system to check types of graph matrices

the core Adjacency matrix type
- subtypes represent the different normalizations of the adj matrix
  
  AveragingAdjacency AveragingLaplacian CombinatorialAdjacency GraphMatrix NormalizedAdjacency NormalizedLaplacian StochasticAdjacency StochasticLaplacian
Noop represents no action
degrees(adjmat)
- returns the degrees of a graph represnted by CombinatorialAdjacency `adjmat`
degrees(graphmx)
- returns the degrees of a graph represented by graph matrix `graphmx`
symmetrize(A::SparseMatrix, which=:or)
- return a symmetric version of graph as a sparse matrix
  - which may be one of :triu, :tril, :sum, or :or. Use :sum for weighted graphs
symmetrize(adjmat, which=:or)
- return a symmetric version of graph (represented by CombinatorialAdjacency adjmat) as a CombinatorialAdjacency
adjacency_matrix(g[, T=Int; dir:=out])
- Return a sparse adjacency matrix for a graph, indexed by [u, v] vertices
adjacency_spectrum(g[, T=Int; dir=:unspec])
- Return the eigenvalues of the adjacency matrix for a graph g, indexed by vertex
incidence_matrix(g[, T=Int; oriented=false])
- Return a sparse node-arc incidence matrix for a graph, indexed by [v, i], where i is in 1:ne(g), indexing an edge e
laplacian_matrix(g[, T=Int; dir=:unspec])
- Return a sparse Laplacian matrix for a graph g, indexed by [u, v] vertices
laplacian_spectrum(g[, T=Int; dir=:unspec])
- Return the eigenvalues of the Laplacian matrix for a graph g, indexed by vertex
spectral_distance(G₁, G₂ [, k])
- Compute the spectral distance between undirected n-vertex graphs G₁ and G₂ using the top k greatest eigenvalues

LEMON

LEMON stands for Lib for Efficient Modeling and Optimization

cpp template library for providing efficient implementations of data structs and algos
- focus on combinatorial optimization tasks connected
  - connected mainly with graphs and networks
    - for telecommunication, computer networks, logistics, scheduling, and other areas

Installation Instructions

building and installing LEMON from source on Linux

cd lemon-x.y.z
mkdir build && cd build
cmake ..
make
make check
make html
make install

Compile your First Code

a directed graph is created with 2 nodes and an arc is added to it

#include <iostream>
#include <lemon/list_graph.h>

using namespace lemon;
using namespace std;

int main()
  {
    ListDigraph g;
    ListDigraph::Node u = g.addNode();
    ListDigraph::Node v = g.addNode();
    ListDigraph::Arc a = g.addArc(u, v);

    cout << "hello world! this is LEMON" << end1;
    cout << "we have a directed graph with " << countNodes(g) << " nodes"
         << " and " << countArcs(g) << " arc" << end1;
    return 0;
  }

compile this code

# system-wide LEMON install
g++ -o hello_lemon hello_lemon.cc -lemon

# executable
./hello_lemon

# user-local LEMON install
g++ -o hello_lemon -I ~/lemon/include hello_lemon.cc -L ~/lemon/lib -lemon

Basic Concepts

we work the with `lemon` namespace

please assume that below directive is added to all code snippets `using namespace lemon;`

Directed Graphs

most versatile digraph structure `ListDiGraph`
- there are more digraph types
include the header file
default constructor of the class creates empty graph
nodes and arcs are identified by two data types
- Node and Arc
  - you can add items to the graph using member functions
  - parallel and loop arcs are supported
you can also remove nodes/arcs with erase()
- there are several more options to remove but not every graph item supports deletion
source() and target() give back the two nodes of an arc

each graph item has a non-negative int identifier using the id()

identifiers are unique w.r.t. a certain itemtype in a graph

a node and an arc may have the same ID

#include <lemon/list_graph.h>
ListDigraph g;
ListDigraph::Node x = g.addNode();
ListDigraph::Node y = g.addNode();
ListDigraph::Node z = g.addNode();
g.addArc(x,y);
g.addArc(y,z);
g.addArc(z,x);

ListDigraph::Arc parallel = g.addArc(x,y);
ListDigraph::Arc loop = g.addArc(x,x);

if (g.source(loop) == g.target(loop))
  std::cout << "This is a loop arc" << std::endl;

std::cout << "Arc " << g.id(arc) << " goes from node "
  << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;

Iterators

graph strucutres provide several iterators
- using NodeIt lists nodes
  - name of iter type starts with a name that refers to the iterated objects
  - INVALID is a constant in lemon namespace

CONTRARY TO THE ITERATORS IN C++ STL, LEMON ITERATORS ARE CONVERTIBLE TO ITEM TYPES without having to use operator*()

graph items are ordered by `less than` operator (w.r.t. to int identifiers)

using ArcIt lists arcs
- you can list arcs starting from/arriving at a certain node
  - OutArcIt InArcIt

LEMON provides counting functions

countNodes(), countArcs(), countInArcs(), countOutArcs() Using them is not just simpler than the above loops, but they could be much faster, since several graph types support constant time item counting

 int cnt = 0;
 for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
     cnt++;
 std::cout << "number of nodes:" << cnt << std::endl;

 // add full graph to existing nodes
 for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
   for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
     if (u != v) g.addArc(u, v);

// only add one of the opposite arcs
for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
  for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
    if (u < v) g.addArc(u, v);

int cnt = 0;
for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
  cnt++;
std::cout << "Number of arcs: " << cnt << std::endl;

int cnt = 0;
for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a)
  cnt++;
std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl;

Maps

maps allows assigning values of any type to the node or arcs of a graph maps enable FAST read/write, DYNAMIC alloc/dealloc, AUTOMATIC storage construction/destruction

graph classes represent pure graph structure, data that is assigned to the items of the graph MUST be stored separately using maps
to assign int values to each node
- you alloc a NodeMap<int>
any data typed w/ a default constructor can be assigned to graph items

when a map is created

you can give an initial values of the elements as a second parameter

ListDigraph::NodeMap<int> map(g);
map[x] = 2;
map[y] = 3;
map[z] = map[x] + map[y];
ListDigraph::NodeMap<std::string> name(g);
name[x] = "Node A";
name[y] = "Node B";

// create a map that assigns char labels to the nodes
ListDigraph::NodeMap<char> label(g);
char ch = 'A';
for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
  label[n] = ch++;

// puts the number of outgoing arcs for each node in map
ListDigraph::NodeMap<int> out_deg(g, 0);
for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
  out_deg[g.source(a)]++;

Graph Structures

implementation of combinatorial algorithms heavily rely on efficient graph structures
diverse applications require the usage of different physical graph structures

`ListDigraph`, `ListGraph`
- LEMON also provides several other classes for handling directed/undirected graphs

in order to save time or memory usage, some structures may fail to support some graph features like node or arc/egde deletion

Graph concepts

all LEMON graph types conform to the corresponding graph concept

classses - DiGraph, Graph
files - digraph.h, graph.h, graph_components.h

a generic graph algorithm should only exploit the features of the corresponding graph concept

so that it could be applied to any graph structure

Directed Graph structures

ListDigraph class is most versatile directed graph struct
- based on linked lists
  - therefore iterating through its nodes and arcs is fast
    - and flexible!
- provides operations for
  - adding/removing nodes/arcs
  - changing the source/target node of an arc
  - contracting/splitting nodes or arcs
SmartDigraph is another general digraph impl
- significantly more efficient in terms of space and time
  - but less functionality
    - nodes and arcs cannot be removed from it
StaticGraph structure is even more optimized for efficiency
- requires less space in memory
- provides fastest iteration
  - especially using OutArcIt iterators
    - since it arcs are stored in an appropriate order however you can't add or delete arcs or nodes
      - the graph has to be built at once w/ no modifications afterwards
FullDigraph is an efficient implementation of a directed full graph
- also completely static and it needs constant space in memory

Undirected Graph structure

ListGraph and SmartGraph have similar implementations as their directed variants

FullGraph

simple, fast implementation of undirected full/complete graphs
- contains an edge between every distinct pair of nodes
  - therefore the number of edges is \(n(n-1)/2\)
this class is completely static and needs constant memory space
- you can't add/delete nodes or edges

however the structure can be resized using `resize()` provides constant time counting for nodes, edges, and arcs

GridGraph

the nodes of the graph can be indexed by two integer values \((i,j)\)
- where \(i\) is in the range \([0,...,width()-1]\)
  - and \(j\) is in the range \([0,...,height()-1]\)
two nodes are connected in the graph if the indices differ extactly on one position and the difference is aso exactly one
the nodes of the graph can be obtained by position using the \(operator()()\) function
- and the indices of the nodes can be obtained using \(pos(),col(),row()\) members
the outgoing arcs can be retrieved with the \(right(),up(),left(),down()\) functions
- where the bottom-left corner is the origin

class is completely static and needs constant memory space

cannnot add/delete nodes or edges but \(resize()\) can be used

#include <lemon/grid_graph.h>

GridGraph g(rows,cols);
GridGraph::NodeMap<int> val(g);
for (int i = 0; i < g.width(); ++i) {
    for (int j = 0; j < g.height(); ++j) {
        val[g(i, j)] = i + j;
     }
}

HypercubeGraph

the nodes of the graph are indexed with integers having at most `dim` binary digits
- two nodes are connected in the graph if and only if their indices differ only on one position in the binary form

completely static graph and needs constant memory space

thus cannot add/delete nodes or edges only use resize()

provides constant time counting for nodes/edges/arcs

NOTE: the type of the indices is chosen to `int` for efficiency reasons

the maximum dimension of the implemenation is 26 assuming size of int is 32 bit

Undirected Graphs

each undirectde edge of a graph can also be regarded as two oppositely directed arcs

As a result all directed graphs algos automatically run on undirected graphs

provides an `Edge` type for the undirected edges
- and `Arc` type for the directed arcs
  - the `Arc` type is convertible to `Edge`
    - thus the corresponding edge can always be obtained from an arc
only nodes and edges can be added or removed from an undirected graph
- and the corresponding arcs are added or removed automatically
  - there are twice as many arcs as edges
each edge has inherent orientation
- this can be defined whether an arc is forward or backward oriented
  - in a undirected graph with respect to this default orientation of the represented edge
the direction of an arc can be obtained and set using the functions
- `direction()` and `direct()` respectively

ListGraph::Arc a1 = g.direct(e, true);    // a1 is the forward arc
ListGraph::Arc a2 = g.direct(e, false);   // a2 is the backward arc
if (a2 == g.oppositeArc(a1))
  std::cout << "a2 is the opposite of a1" << std::endl;

the end nodes of an edge can obtained using the functions `u()` and `v()`

while the `source()` and `target()` can be used for arcs

std::cout << "Edge " << g.id(e) << " connects node "
  << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
std::cout << "Arc " << g.id(a2) << " goes from node "
  << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl;

also provides iterators `NodeIt` `ArcIt` `OutArcIt` `InArcIt`
- there is also iterator classes for edges
  - `EdgeIt` traverses all edges in the graph and `IncEdgeIt` lists the incidence edges of a certain node

print out the degree of each node

for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
  int cnt = 0;
  for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
    cnt++;
  }
  std::cout << "deg(" << g.id(n) << ") = " << cnt << std::endl;
}

in an undirected graph, both `OutArcIt` and `InArcIt` iterates on the same edges but w/ opposite direction
- they are convertible to both `Arc` and `Edge` types
`IncEdgeIt` also iterates on these edges
- but not convertible to `Arc`, only to `Edge`

using the member class for constructing edge maps

ListGraph::EdgeMap cost(g);
cost[e] = 10;
std::cout << cost[e] << std::endl;
std::cout << cost[a1] << ", " << cost[a2] << std::endl;
ListGraph::ArcMap arc_cost(g);
arc_cost[a1] = cost[a1];
arc_cost[a2] = 2 * cost[a2];
// std::cout << arc_cost[e] << std::endl;   // this is not valid
std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;

Practice

we would like to design an electric network minimizing the total length of wires
- then you might be looking for a MST in an undirected graph
  - you can use the `Kruskal` algo
Let us suppose that the network is stored in a ListGraph object `g` with a cost map `cost`
- we create a `bool` valued edge map `tree_map` or a vector `tree_vector`
  - for storing the tree that is found by the algorithm
    - after that we call the `kruskal()` function
      - it gives backt he weight of the MST and `tree_map` or `tree_vector` will contain the found spanning tree

if you want to store arcs in a bool valued edge map

// Kruskal algorithm with edge map
ListGraph::EdgeMap<bool> tree_map(g);
std::cout << "The weight of the minimum spanning tree is "
          << kruskal(g, cost_map, tree_map) << std::endl;
// Print the results
std::cout << "Edges of the tree: " << std::endl;
for (ListGraph::EdgeIt e(g); e != INVALID; ++e) {
  if (!tree_map[e]) continue;
  std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";
}

if you would like to store the edges in a standard container

// Kruskal algorithm with edge vector
std::vector<ListGraph::Edge> tree_vector;
std::cout << "The weight of the minimum spanning tree is "
          << kruskal(g, cost_map, std::back_inserter(tree_vector))
          << std::endl;
// Print the results
std::cout << "Edges of the tree: " << std::endl;
for (unsigned i = 0; i != tree_vector.size(); ++i) {
  Edge e = tree_vector[i];
  std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";
}

Algorithms

LEMON provides well-known fundamental algorithms for discovering graph properties

and even complex optimisation algorithms

Graph Search

commonly we have BFS, DFS implemented as classes `Bfs` and `Dfs`
- algos are placed in separated files named after the algo

*All algorithms are implemented in template classes *

typically template params specify the used graph type and required map types
you can execute the algo by calling run()

by default distances and path info are stored in internal maps

access with distMap() and predMap() or dist(),path(),predNode(),predArc()
call init() to initialize internal data structures
- instead of run() have more control executing algo step-by-step
- add one or more source nodes to the queue
  - and they'll be processed just like the run()
- start path computation with the start()
  - or write your own loop to process nodes one-by-one


#include <lemon/bfs.h>
ListDigraph g;
Bfs<ListDigraph> bfs(g);
// find shortest path from s to all other nodes
bfs.run(s);
// find shortest path from s to target node t
bfs.run(s,t);

// print the shortest path of those nodes that are at most in a certain distnace `max_dist`
for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
  if (bfs.reached(n) && bfs.dist(n) <= max_dist) {
    std::cout << gr.id(n);
    Node prev = bfs.prevNode(n);
    while (prev != INVALID) {
      std::cout << "<-" << gr.id(prev);
      prev = bfs.prevNode(n);
    }
    std::cout << std::endl;
  }
}

bfs.init();
bfs.addSource(s1);
bfs.addSource(s2);
bfs.start(t);

// execution reaches all nodes in the digraph
// ... algo is started for each node that is not visited before
bfs.init();
for (NodeIt n(g); n != INVALID; ++n) {
  if (!bfs.reached(n)) {
    bfs.addSource(n);
    bfs.start();
  }
}

// bfs.start() is only a shortcut of following code
while (!bfs.emptyQueue()) {
  bfs.processNextNode();
}

Shortest Paths

the LEMON Dijkstra class

dijkstra(g, length).distMap(dist).run(s,t);
// or use class inteface like below
// execution is controlled to a higher extent
Dijkstra<ListDigraph> dijkstra(g, length);
dijkstra.distMap(dist);
dijsktra.init();
dijkstra.addSource(s);
dijkstra.start();

// instaed of using .start()
while (!dijkstra.emptyQueue()) {
  ListDigraph::Node n = dijkstra.processNextNode();
  cout << g.id(n) << ' ' << dijkstra.dist(g) << endl;
}

LEMON provides other algos for finding shortest paths

Maximum Flows

SUBSECTION IS ON TODO TO BE WRITTEN

Preflow<GR,CAP,TR> class template reference

GR = type of digraph the algo runs on
CAP = the type of capacity map
- default map type is `GR::ArcMap<int>`
TR = the traits class that define various types used by the algo
provides implementation of Goldberg-Tarjan's preflow push-relabel algorithm
- producing a flow of maximum value in a digraph

preflow algorithms are the fastest known max flow algos

current impl uses a mix of `highest label` and `bound decrease` heuristics

worse case time complexity of the algorithm is \(O(n^{2}\sqrt{e})\) …

algo consists of 2 phases
- max flow value and minimum cut is obtained
- constructs a feasible maximum flow on each arc

cannot handle infinite or very large capacities

max value of `CAP::Value`
```
#include <lemon/preflow.h>
```

Style Guide

Naming Conventions

in LEMON the name of a source file is written in lowercase and words are separated with underscores
- all header files are located in the lemon subdir
  
  `#include <lemon/header_file.h>`
the name of the a class or any type look like `AllWordsCapitalizedWithoutUnderscores`
the name of a function looks like `firstWorldLowercaseRestCapitalizedWithoutUnderscores`
the names of constants and macros look like `ALL_{UPPERCASEWITHUNDERSCORES}`

LEMON Graph Format (LGF)

LGF is a column-oriented file format for storing graphs and associated data like node and edges maps
each line with `#` first non-whitespace char is considered a comment line
- otherwise the file consists of sections starting with a header line
the header line starts with `@` char
- followed by the section type `@nodes, @arcs, @edges, @attributes`
  - each header line may have an optional name to distinguish sections
the standard sections are column-oriented
- consisting of tokens separated by whitespaces
  - a token can be plain or quoted
    - plain token is a sequence of non-whitespace chars
    - quoted token is a char sequence surrounded by """"
      - can contain whitespaces and escape sequences
        
        @nodes describes a set of nodes and associated maps @arcs describes the names of the maps but label is not obligatory
        
        if no map in @arcs then a sole `-` exists in the first line
        
        @edges is just a synonym of @arcs,
        
        @arcs section can store the edgeset of an undirected graph
        
        @attributes sections contains KV pairs
        
        consisting of two tokens on each line
        
        an attribute name and an attribute value
        
        @nodes label coordinates size title 1 (10,20) 10 "First node" 2 (80,80) 8 "Second node" 3 (40,10) 10 "Third node" ... @arcs capacity 1 2 16 1 3 12 2 3 18 ... @arcs - 1 2 1 3 2 3 ... @attributes source 1 target 3 caption "LEMON test digraph"

Lemon Graphs