VertexFinder.jl

Package author: Jukka Aho (@ahojukka5)

The need to determine pseudoperipheral vertices arises from several graph-theoretical approaches for ordering sparse matrix equations. This package implements George-Liu algorithm for finding a pseudoperipheral vertex in a graph aiming at returning a vertex having a large eccentricity.

Usage

Let's consider the following graph:

It is easy to see that peripheral vertices for this graph are 9 and 6. The requirement for the description of the graph is the following: graph must implement getindex and each adjacency list must be iterable. For example, list of lists or dictionary of lists meets the requirements.

G = Dict(
    1 => (3, 8, 9),
    2 => (3, 8, 7),
    3 => (1, 2),
    4 => (8, 9),
    5 => (7, 8),
    6 => (2, 7),
    7 => (5, 2, 6),
    8 => (1, 2, 4, 5),
    9 => (1, 4))

Starting from node 1:

w0 = 1
w1 = find(G, w0)
w2 = find(G, w1)
w3 = find(G, w2)
println(w1)
println(w2)
println(w3)

# output

6
9
6

Contributing to project

Any contributions are highly appreciated! If you have some good ideas how to make this package better, feel free to open an issue or send me an email.