Salam
Online editor

Standard library · Machine learning

graph

Graph theory: traversal, shortest paths, spanning trees, flow, coloring, communities and centrality.

import graph
On this page
  1. Types
  2. Constants and variables
  3. Functions

This package has more than two hundred graph algorithms. Make a graph with NewUndirected or NewDirected, add edges with add_edge and add_weighted, then call build; or read the whole thing from text in one go with FromEdgeList. Nodes are numbered from zero to n minus one.

Everything from traversal and components to shortest paths, spanning trees, flow and cuts, matching, coloring, communities and centrality is ready to use. You can export the result with ToDot or ToMermaid to draw it. The algorithms that solve hard problems, such as maximum clique and Hamiltonian cycle, are meant for small graphs.

Types

FlowNet

struct FlowNet
A flow network with capacities and costs.
NameTypeDescription
nint = 0The number of nodes.
headVectorWhere each node's arcs start.
toVectorThe target of each arc.
capVectorThe remaining capacity.
costVectorThe cost.
origVectorThe original capacity.
nxtVectorThe next arc.
graph-Flow.salam
import graph

func list(text: str): Vector<int>:
    mut out := Vector {} as Vector<int>
    each num in text.split(" "):
        out.push(num.to_int())
    end
    ret out
end


func ints(v: Vector<int>): str:
    mut text := "["
    repeat v.len() in i:
        if i > 0:
            text += " "
        end
        text += "" + v.get(i)
    end
    ret text + "]"
end


func main:
    mut net := graph.NewFlowNet(4)
    e := net.add_arc(0, 1, 3.0)
    _ := net.add_arc(0, 2, 2.0)
    _ := net.add_arc(1, 3, 2.0)
    _ := net.add_arc(2, 3, 3.0)
    _ := net.add_edge(1, 2, 1.0)
    println net.arc_count(), graph.MaxFlow(net, 0, 3), net.flow_on(e)
    net.reset()
    println graph.MaxFlowEdmondsKarp(net, 0, 3)
    net.reset()
    mut side := Vector {} as Vector<bool>
    println graph.MinCut(net, 0, 3, side), side.get(0), side.get(3)
    mut costly := graph.NewFlowNet(3)
    _ := costly.add_cost_arc(0, 1, 2.0, 1.0)
    _ := costly.add_cost_arc(0, 2, 2.0, 5.0)
    _ := costly.add_cost_arc(1, 2, 1.0, 1.0)
    mut sent := 0.0
    println graph.MinCostFlow(costly, 0, 2, 2.0, sent), sent
    net.free()
    mut roads := graph.FromEdgeList("0 1 3\n0 2 2\n1 3 2\n2 3 3\n1 2 1", 4, true)
    mut cut := Vector {} as Vector<int>
    println graph.MaxFlowValue(roads, 0, 3), graph.MinCutEdges(roads, 0, 3, cut), ints(cut), graph.FlowFromGraph(roads).n
    mut ring := graph.CycleGraph(5)
    println graph.GlobalMinCut(ring), graph.EdgeConnectivity(ring), graph.VertexConnectivity(graph.CompleteGraph(4))

    mut bip := graph.FromEdgeList("0 3\n0 4\n1 3\n2 5", 6, false)
    mut mate := Vector {} as Vector<int>
    println graph.BipartiteMatching(bip, mate), ints(mate), graph.MaximalMatching(ring, mate)
    mut cover := Vector {} as Vector<bool>
    println graph.MinimumVertexCover(bip, cover), graph.MaximumIndependentSetBipartite(bip, cover), graph.GreedyVertexCover(ring, cover)
    println ints(graph.MaxClique(graph.CompleteGraph(4))), graph.CliqueNumber(ring), ints(graph.MaximumIndependentSet(ring)), graph.IndependenceNumber(ring), graph.VertexCoverNumber(ring)

    color := graph.GreedyColoringNatural(ring)
    println ints(color), graph.ColorCount(color), graph.IsProperColoring(ring, color), graph.ChromaticNumber(ring), graph.ChromaticNumber(graph.PetersenGraph())
    println ints(graph.GreedyColoring(ring, list("4 3 2 1 0"))), ints(graph.WelshPowell(ring)), ints(graph.DSatur(ring))
    println ints(graph.EdgeColoringGreedy(graph.StarGraph(4))), graph.CountColorings(graph.PathGraph(3), 3)

    mut social := graph.FromEdgeList("0 1\n1 2\n2 0\n3 4\n4 5\n5 3\n2 3", 6, false)
    mut alive := Vector {} as Vector<bool>
    println graph.KCore(social, 2, alive), ints(graph.CoreNumbers(social)), graph.Degeneracy(social)
    mut group := Vector {} as Vector<int>
    println graph.Louvain(social, group), ints(group)
    println (graph.Modularity(social, group) * 100.0 + 0.5) as int
    println graph.LabelPropagation(social, group) >= 1, graph.GirvanNewman(social, 2, group), ints(group)
end
Output10 5 3 5 5 true false 7 2 5 5 [0 1] 4 2 2 3 3 [4 3 5 1 0 2] 2 3 3 4 [0 1 2 3] 2 [0 2] 2 3 [0 1 0 1 2] 3 true 3 3 [2 1 0 1 0] [0 2 1 0 1] [0 1 0 1 2] [0 1 2] 12 6 [2 2 2 2 2 2] 2 2 [0 0 0 1 1 1] 36 true 2 [0 0 0 1 1 1]

arc_count

func arc_count(): int
The number of arcs, counting the reverse arcs.

The example for this item is shown with the ones above: graph-Flow.salam

add_arc

func add_arc(u: int, v: int, c: f64): int
Adds a directed arc with a capacity.

The example for this item is shown with the ones above: graph-Flow.salam

add_cost_arc

func add_cost_arc(u: int, v: int, c: f64, k: f64): int
Adds an arc with a capacity and a unit cost.

The example for this item is shown with the ones above: graph-Flow.salam

add_edge

func add_edge(u: int, v: int, c: f64): int
Adds an undirected edge with a capacity.

The example for this item is shown with the ones above: graph-Flow.salam

flow_on

func flow_on(e: int): f64
The flow on an arc.

The example for this item is shown with the ones above: graph-Flow.salam

reset

func reset()
Sets every flow back to zero.

The example for this item is shown with the ones above: graph-Flow.salam

free

func free()
Frees the network.

The example for this item is shown with the ones above: graph-Flow.salam

Matrix

struct Matrix
The simple float matrix of this package.
NameTypeDescription
rowsint = 0The rows.
colsint = 0The columns.
aVectorThe entries.
graph-Build.salam
import graph

func list(text: str): Vector<int>:
    mut out := Vector {} as Vector<int>
    each num in text.split(" "):
        out.push(num.to_int())
    end
    ret out
end


func ints(v: Vector<int>): str:
    mut text := "["
    repeat v.len() in i:
        if i > 0:
            text += " "
        end
        text += "" + v.get(i)
    end
    ret text + "]"
end


func main:
    mut g := graph.NewUndirected(4)
    _ := g.add_edge(0, 1)
    _ := g.add_weighted(1, 2, 2.5)
    e := g.add_edge(2, 3)
    r := g.add_node()
    g.add_nodes(1)
    _ := g.add_edge(3, r)
    g.set_weight(e, 4.0)
    g.set_name(0, "Tehran")
    g.build()
    println g.order(), g.size(), g.name(0), g.directed, g.built
    println g.edge_from(e), g.edge_to(e), g.edge_weight(e), g.weight_between(1, 2), g.has_edge(2, 1), g.find_edge(0, 3)
    println g.degree(2), g.out_degree(2), g.in_degree(2), ints(g.neighbors(2))
    repeat g.adj_start(1) to g.adj_stop(1) in k:
        println g.adj_node(k), g.adj_edge(k), g.adj_weight(k)
    end

    mut d := graph.NewDirected(3)
    _ := d.add_edge(0, 1)
    _ := d.add_edge(1, 2)
    _ := d.add_edge(2, 2)
    _ := d.add_edge(0, 1)
    d.build()
    repeat d.in_start(1) to d.in_stop(1) in k:
        println "in", d.in_node(k), d.in_edge(k)
    end
    println graph.SelfLoopCount(d), graph.HasSelfLoop(d), graph.ParallelEdgeCount(d), graph.IsSimple(d)
    mut simple := graph.Simplify(d)
    mut noloops := graph.RemoveSelfLoops(d)
    println simple.size(), noloops.size(), graph.TotalWeight(g)
    println graph.Transpose(d).has_edge(1, 0), graph.Reverse(d).has_edge(2, 1), graph.ToUndirected(d).directed, graph.ToDirected(g).size()
    general := graph.New(2, true)
    println general.directed, graph.Clone(g).size()
    mut keep := Vector {} as Vector<bool>
    graph.FillBool(keep, g.order(), true)
    keep.set(0, false)
    mut mapping := Vector {} as Vector<int>
    println graph.Subgraph(g, keep).order(), graph.SubgraphMap(g, keep, mapping).size(), ints(mapping)
    mut edges := Vector {} as Vector<bool>
    graph.FillBool(edges, g.size(), false)
    edges.set(0, true)
    println graph.EdgeSubgraph(g, edges).size(), graph.Complement(graph.PathGraph(4)).size()
    mut a := graph.PathGraph(3)
    mut b := graph.CycleGraph(3)
    println graph.Union(a, b).size(), graph.DisjointUnion(a, b).order(), graph.Intersection(a, b).size(), graph.LineGraph(b).size()

    sources := list("0 1 2")
    targets := list("1 2 0")
    mut fromedges := graph.FromEdges(3, sources, targets, true)
    println fromedges.size()
    mut text := graph.FromEdgeList("0 1 2.5\n1 2", 3, false)
    println text.weight_between(0, 1)
    println graph.ToEdgeList(text)
    println graph.ToAdjacencyList(text)
    println graph.ToMatrixText(text)
    println graph.ToDot(text)
    println graph.ToMermaid(text)
    println graph.ToJSON(text)
    println graph.Describe(text)
    println graph.IsClose(0.1 + 0.2, 0.3), graph.GRAPH_INF > 1000.0, graph.GRAPH_NONE

    println graph.EmptyGraph(3).size(), graph.CompleteGraph(4).size(), graph.CompleteBipartite(2, 3).size(), graph.StarGraph(4).size(), graph.WheelGraph(5).size()
    println graph.GridGraph(2, 3).size(), graph.HypercubeGraph(3).size(), graph.PetersenGraph().size(), graph.CirculantGraph(6, list("1 2")).size(), graph.BalancedTree(2, 2).order()
    println graph.ErdosRenyi(10, 0.5).order(), graph.RandomGraph(10, 15).size(), graph.RandomTree(8).size(), graph.BarabasiAlbert(20, 2).order(), graph.WattsStrogatz(20, 4, 0.1).order()
    g.free()
end
Output6 4 Tehran false true 2 3 4 2.5 true -1 2 2 2 [1 3] 0 0 1 2 1 2.5 1 1 2.5 in 0 0 in 0 3 in 1 1 1 true 1 false 2 3 8.5 true true false 8 true 4 5 3 [-1 0 1 2 3 4] 1 3 5 6 2 3 3 2.5 0 1 2.5 1 2 1 0: 1 1: 0 2 2: 1 0 1 0 1 0 1 0 1 0 graph G { "0"; "1"; "2"; "0" -- "1" [label="2.5"]; "1" -- "2"; } graph LR 0 --- 1 1 --- 2 {"directed":false,"nodes":[{"id":0,"name":"0"},{"id":1,"name":"1"},{"id":2,"name":"2"}],"links":[{"source":0,"target":1,"weight":2.5},{"source":1,"target":2,"weight":1}]} n=3 m=2 undirected components=1 simple bipartite tree true true -1 0 6 6 3 8 7 12 15 12 7 10 15 7 20 20

at

func at(i: int, j: int): f64
An entry.

The example for this item is shown with the ones above: graph-Build.salam

set

func set(i: int, j: int, v: f64)
Sets an entry.

The example for this item is shown with the ones above: graph-Build.salam

add_at

func add_at(i: int, j: int, v: f64)
Adds to an entry.

The example for this item is shown with the ones above: graph-Build.salam

trace

func trace(): f64
The trace.

The example for this item is shown with the ones above: graph-Build.salam

row_sum

func row_sum(i: int): f64
The sum of a row.

The example for this item is shown with the ones above: graph-Build.salam

free

func free()
Frees the matrix.

The example for this item is shown with the ones above: graph-Build.salam

IntMatrix

struct IntMatrix
An integer matrix.
NameTypeDescription
rowsint = 0The rows.
colsint = 0The columns.
aVectorThe entries.
graph-Paths.salam
import graph

func list(text: str): Vector<int>:
    mut out := Vector {} as Vector<int>
    each num in text.split(" "):
        out.push(num.to_int())
    end
    ret out
end


func ints(v: Vector<int>): str:
    mut text := "["
    repeat v.len() in i:
        if i > 0:
            text += " "
        end
        text += "" + v.get(i)
    end
    ret text + "]"
end


func floats(v: Vector<f64>): str:
    mut text := "["
    repeat v.len() in i:
        if i > 0:
            text += " "
        end
        text += "" + ((v.get(i) * 100.0 + 100000.5) as int - 100000)
    end
    ret text + "]/100"
end

func main:
    mut cities := graph.FromEdgeList("0 1 4\n0 2 1\n2 1 2\n1 3 1\n2 3 5", 4, false)
    mut dist := Vector {} as Vector<f64>
    mut parent := Vector {} as Vector<int>
    println graph.Dijkstra(cities, 0, dist, parent), floats(dist), ints(parent)
    println floats(graph.DijkstraDist(cities, 0)), ints(graph.ShortestPath(cities, 0, 3)), graph.ShortestPathLength(cities, 0, 3)
    mut guess := Vector {} as Vector<f64>
    graph.FillFloat(guess, 4, 0.0)
    println ints(graph.AStar(cities, 0, 3, guess)), floats(graph.KShortestLengths(cities, 0, 3, 3))
    floyd := graph.FloydWarshall(cities)
    mut next := graph.NewIntMatrix(0, 0, 0)
    floyd2 := graph.FloydWarshallPaths(cities, next)
    println floyd.at(0, 3), floyd2.at(3, 0), ints(graph.FloydPath(next, 0, 3)), graph.Johnson(cities).at(0, 1)
    mut zeroone := graph.FromEdgeList("0 1 0\n1 2 1\n0 2 1", 3, true)
    println graph.ZeroOneBFS(zeroone, 0, dist, parent), floats(dist)

    mut negative := graph.FromEdgeList("0 1 1\n1 2 -2\n2 0 0.5", 3, true)
    println graph.BellmanFord(negative, 0, dist, parent), graph.HasNegativeCycle(negative), ints(graph.FindNegativeCycle(negative))

    mut project := graph.FromEdgeList("0 1 3\n0 2 2\n1 3 4\n2 3 1", 4, true)
    println graph.DAGShortestPath(project, 0, dist, parent), floats(dist)
    println graph.DAGLongestPath(project, 0, dist, parent), floats(dist), ints(graph.CriticalPath(project))
    println graph.CountPaths(project, 0, 3), floats(graph.PathCounts(project, 0))
    closure := graph.TransitiveClosure(project)
    println closure.at(0, 3), closure.at(3, 0), graph.TransitiveReduction(graph.FromEdgeList("0 1\n1 2\n0 2", 3, true)).size()
    mut layer := Vector {} as Vector<int>
    println graph.TopologicalLayers(project, layer), ints(layer), graph.IsTotalOrder(graph.FromEdgeList("0 1\n1 2", 3, true))
    println graph.WalkCount(graph.CycleGraph(4), 2, 0, 0)

    mut ring := graph.CycleGraph(4)
    println graph.HasEulerianCircuit(ring), ints(graph.EulerianCircuit(ring)), graph.HasEulerianPath(graph.PathGraph(3)), ints(graph.EulerianPath(graph.PathGraph(3)))
    println graph.HasHamiltonianCycle(ring), ints(graph.HamiltonianCycle(ring)), ints(graph.HamiltonianPath(graph.PathGraph(3)))
    mut full := graph.NewUndirected(4)
    each edge in ["0 1 1", "0 2 4", "0 3 3", "1 2 2", "1 3 5", "2 3 1"]:
        mut parts := list(edge)
        _ := full.add_weighted(parts.get(0), parts.get(1), parts.get(2) as f64)
    end
    full.build()
    mut tour := graph.TSPNearestNeighbor(full, 0)
    println ints(tour), graph.TourLength(full, tour), graph.TSPTwoOpt(full, tour), graph.TourLength(full, graph.TSPHeuristic(full, 0))
end
Outputtrue [0 300 100 400]/100 [-1 2 0 1] [0 300 100 400]/100 [0 2 1 3] 4 [0 2 1 3] [400 500 600]/100 4 4 [0 2 1 3] 3 true [0 0 100]/100 false true [1 2 0] true [0 300 200 300]/100 true [0 300 200 700]/100 [0 1 3] 2 [100 100 100 200]/100 1 0 2 3 [0 1 1 2] true 2 true [0 1 2 3 0] true [0 1 2] true [0 1 2 3] [0 1 2] [0 1 2 3] 7 7 7

at

func at(i: int, j: int): int
An entry.

The example for this item is shown with the ones above: graph-Paths.salam

set

func set(i: int, j: int, v: int)
Sets an entry.

The example for this item is shown with the ones above: graph-Paths.salam

free

func free()
Frees the matrix.

The example for this item is shown with the ones above: graph-Paths.salam

Graph

struct Graph
A graph: nodes numbered 0 to n minus one and edges, directed or undirected, with optional weights. Call build after adding the edges.
NameTypeDescription
directedbool = falseWhether the graph is directed.
nint = 0The number of nodes.
euVectorThe start node of each edge.
evVectorThe end node of each edge.
ewVectorThe edge weights.
namesVectorThe node names.
offVectorWhere each node's adjacency list starts.
nbrVectorThe adjacent nodes.
eixVectorThe adjacent edges.
roffVectorWhere each node's incoming list starts.
rnbrVectorThe incoming nodes.
reixVectorThe incoming edges.
builtbool = falseWhether the adjacency lists have been built.

The example for this item is shown with the ones above: graph-Build.salam

add_node

func add_node(): int
Adds a new node and returns its number.

The example for this item is shown with the ones above: graph-Build.salam

add_nodes

func add_nodes(k: int)
Adds k new nodes.

The example for this item is shown with the ones above: graph-Build.salam

add_edge

func add_edge(u: int, v: int): int
Adds an edge with weight one and returns the edge number.

The example for this item is shown with the ones above: graph-Build.salam

add_weighted

func add_weighted(u: int, v: int, w: f64): int
Adds a weighted edge.

The example for this item is shown with the ones above: graph-Build.salam

order

func order(): int
The number of nodes.

The example for this item is shown with the ones above: graph-Build.salam

size

func size(): int
The number of edges.

The example for this item is shown with the ones above: graph-Build.salam

edge_from

func edge_from(e: int): int
The start node of an edge.

The example for this item is shown with the ones above: graph-Build.salam

edge_to

func edge_to(e: int): int
The end node of an edge.

The example for this item is shown with the ones above: graph-Build.salam

edge_weight

func edge_weight(e: int): f64
The weight of an edge.

The example for this item is shown with the ones above: graph-Build.salam

set_weight

func set_weight(e: int, w: f64)
Sets the weight of an edge.

The example for this item is shown with the ones above: graph-Build.salam

set_name

func set_name(u: int, s: str)
Sets the name of a node.

The example for this item is shown with the ones above: graph-Build.salam

name

func name(u: int): str
The name of a node; its number when it has none.

The example for this item is shown with the ones above: graph-Build.salam

build

func build()
Builds the adjacency lists; call it after adding the edges.

The example for this item is shown with the ones above: graph-Build.salam

adj_start

func adj_start(u: int): int
Where the node's outgoing neighbors start in the adjacency list.

The example for this item is shown with the ones above: graph-Build.salam

adj_stop

func adj_stop(u: int): int
Where the outgoing neighbors stop.

The example for this item is shown with the ones above: graph-Build.salam

adj_node

func adj_node(k: int): int
The neighbor node at position k.

The example for this item is shown with the ones above: graph-Build.salam

adj_edge

func adj_edge(k: int): int
The edge at position k.

The example for this item is shown with the ones above: graph-Build.salam

adj_weight

func adj_weight(k: int): f64
The weight at position k.

The example for this item is shown with the ones above: graph-Build.salam

in_start

func in_start(u: int): int
Where the incoming neighbors start.

The example for this item is shown with the ones above: graph-Build.salam

in_stop

func in_stop(u: int): int
Where the incoming neighbors stop.

The example for this item is shown with the ones above: graph-Build.salam

in_node

func in_node(k: int): int
The incoming node at position k.

The example for this item is shown with the ones above: graph-Build.salam

in_edge

func in_edge(k: int): int
The incoming edge at position k.

The example for this item is shown with the ones above: graph-Build.salam

out_degree

func out_degree(u: int): int
The out-degree.

The example for this item is shown with the ones above: graph-Build.salam

in_degree

func in_degree(u: int): int
The in-degree.

The example for this item is shown with the ones above: graph-Build.salam

degree

func degree(u: int): int
The degree.

The example for this item is shown with the ones above: graph-Build.salam

has_edge

func has_edge(u: int, v: int): bool
True when there is an edge from u to v.

The example for this item is shown with the ones above: graph-Build.salam

find_edge

func find_edge(u: int, v: int): int
The number of the edge from u to v; -1 when there is none.

The example for this item is shown with the ones above: graph-Build.salam

weight_between

func weight_between(u: int, v: int): f64
The weight of the edge from u to v.

The example for this item is shown with the ones above: graph-Build.salam

neighbors

func neighbors(u: int): Vector<int>
The neighbors of a node.

The example for this item is shown with the ones above: graph-Build.salam

free

func free()
Frees the graph.

The example for this item is shown with the ones above: graph-Build.salam

LCAIndex

struct LCAIndex
A common ancestor index.
NameTypeDescription
nint = 0The number of nodes.
levelsint = 0The number of lifting levels.
depthVectorThe depth of each node.
upVectorThe ancestor table.
graph-Trees.salam
import graph

func ints(v: Vector<int>): str:
    mut text := "["
    repeat v.len() in i:
        if i > 0:
            text += " "
        end
        text += "" + v.get(i)
    end
    ret text + "]"
end


func main:
    mut net := graph.FromEdgeList("0 1 4\n0 2 1\n1 2 2\n1 3 5\n2 3 8\n3 4 3", 5, false)
    mut chosen := Vector {} as Vector<int>
    println graph.Kruskal(net, chosen), ints(chosen)
    println graph.MaximumSpanningTree(net, chosen), ints(chosen)
    mut parent := Vector {} as Vector<int>
    println graph.Prim(net, 0, parent), ints(parent), graph.Boruvka(net, chosen), graph.MSTWeight(net)
    mut tree := graph.MinimumSpanningTree(net)
    println tree.size(), graph.IsTree(tree), graph.IsForest(tree), graph.IsTree(net), graph.SpanningAgreement(net), graph.SpanningTreeCount(graph.CompleteGraph(4))

    mut order := Vector {} as Vector<int>
    graph.RootTree(tree, 0, parent, order)
    println ints(parent), ints(order), ints(graph.SubtreeSizes(tree, 0))
    mut ends := Vector {} as Vector<int>
    println graph.TreeDiameter(tree, ends), ints(ends), ints(graph.TreeCenter(tree)), ints(graph.TreeCentroid(tree))
    mut lca := graph.BuildLCA(tree, 0)
    println graph.LCA(lca, 3, 4), graph.LCA(lca, 4, 2), graph.TreeDistance(lca, 4, 2), lca.ancestor(0, 4), lca.n, lca.levels > 0
    lca.free()

    code := graph.PruferEncode(tree)
    println ints(code), graph.PruferDecode(code).size(), graph.LabeledTreeCount(5)
    println graph.TreeIsomorphic(graph.PathGraph(4), graph.StarGraph(4)), graph.TreeIsomorphic(tree, graph.PruferDecode(code))
    println graph.TreeCanonicalForm(graph.StarGraph(3)), graph.TreeToString(tree, 0)
end
Output11 [1 2 5 3] 20 [4 3 0 5] 11 [-1 2 0 1 3] 11 11 4 true true false true 16 [-1 2 0 1 3] [0 2 1 3 4] [5 3 4 2 1] 4 [4 0] [1] [1] 3 2 3 3 5 true [2 1 3] 4 125 false true (()()) 0(2(1(3(4))))

ancestor

func ancestor(k: int, v: int): int
The level k ancestor of a node.

The example for this item is shown with the ones above: graph-Trees.salam

free

func free()
Frees the index.

The example for this item is shown with the ones above: graph-Trees.salam

MinHeap

struct MinHeap
A min-heap with float keys and integer values.
NameTypeDescription
keyVectorThe keys.
valVectorThe values.
graph-Analysis.salam
import graph

func list(text: str): Vector<int>:
    mut out := Vector {} as Vector<int>
    each num in text.split(" "):
        out.push(num.to_int())
    end
    ret out
end


func ints(v: Vector<int>): str:
    mut text := "["
    repeat v.len() in i:
        if i > 0:
            text += " "
        end
        text += "" + v.get(i)
    end
    ret text + "]"
end


func floats(v: Vector<f64>): str:
    mut text := "["
    repeat v.len() in i:
        if i > 0:
            text += " "
        end
        text += "" + ((v.get(i) * 100.0 + 100000.5) as int - 100000)
    end
    ret text + "]/100"
end

func round(x: f64): int:
    ret (x * 100.0 + 100000.5) as int - 100000
end

func main:
    mut g := graph.FromEdgeList("0 1\n0 2\n1 2\n2 3\n3 4", 5, false)
    println round(graph.Density(g)), round(graph.AverageDegree(g)), graph.MaxDegree(g), graph.MinDegree(g), ints(graph.DegreeSequence(g)), ints(graph.DegreeHistogram(g))
    println graph.IsRegular(graph.CycleGraph(5)), graph.IsComplete(graph.CompleteGraph(3)), graph.Eccentricity(g, 4), ints(graph.EccentricityAll(g))
    println graph.Diameter(g), graph.Radius(g), ints(graph.Center(g)), ints(graph.Periphery(g)), round(graph.AveragePathLength(g)), graph.WienerIndex(g), graph.Girth(g)
    println round(graph.LocalClustering(g, 2)), round(graph.AverageClustering(g)), round(graph.Transitivity(g)), graph.TriangleCount(g), round(graph.Assortativity(g)), graph.CircuitRank(g), graph.WeightedDiameter(g)

    println floats(graph.DegreeCentrality(g))
    println floats(graph.ClosenessCentrality(g))
    println floats(graph.HarmonicCentrality(g))
    println floats(graph.BetweennessCentrality(g))
    println floats(graph.EdgeBetweenness(g))
    println floats(graph.EigenvectorCentrality(g, 200, 0.000001))
    println floats(graph.KatzCentrality(g, 0.1, 1.0, 200, 0.000001))
    mut web := graph.FromEdgeList("0 1\n1 2\n2 0\n3 2", 4, true)
    rank := graph.PageRank(web, 0.85, 100, 0.000001)
    println floats(rank), graph.TopNode(rank)
    println floats(graph.InDegreeCentrality(web)), floats(graph.OutDegreeCentrality(web))
    mut hubs := Vector {} as Vector<f64>
    mut auth := Vector {} as Vector<f64>
    graph.HITS(web, 100, 0.000001, hubs, auth)
    println graph.TopNode(auth)
    mut score := Vector {} as Vector<f64>
    graph.FillFloat(score, 4, 2.0)
    graph.ScaleToSum(score)
    println floats(score)

    mut path := graph.PathGraph(3)
    adj := graph.AdjacencyMatrix(path)
    println adj.rows, adj.at(0, 1), adj.trace(), adj.row_sum(1)
    println graph.WeightMatrix(path).at(1, 2), graph.DegreeMatrix(path).at(1, 1), graph.LaplacianMatrix(path).at(1, 1), round(graph.NormalizedLaplacian(path).at(0, 1)), graph.IncidenceMatrix(path).cols
    mut m := graph.NewMatrix(2, 2)
    m.set(0, 0, 2.0)
    m.add_at(1, 1, 3.0)
    println graph.Determinant(m), graph.MatrixMultiply(m, graph.MatrixIdentity(2)).at(1, 1), graph.MatrixPower(m, 2).at(0, 0)
    println floats(graph.SymmetricEigenvalues(m)), floats(graph.AdjacencySpectrum(path)), floats(graph.LaplacianSpectrum(path))
    println round(graph.SpectralRadius(path)), round(graph.AlgebraicConnectivity(path))
    mut im := graph.NewIntMatrix(2, 2, 7)
    im.set(0, 1, 3)
    println im.at(0, 1), im.at(1, 1), im.rows
    m.free()
    im.free()

    mut a := graph.CycleGraph(5)
    mut b := graph.PetersenGraph()
    mut mapping := Vector {} as Vector<int>
    println graph.Isomorphic(a, graph.CycleGraph(5)), graph.IsomorphismMap(a, graph.CycleGraph(5), mapping), graph.AutomorphismCount(a), graph.SameDegreeSequence(a, b)
    println graph.IsGraphical(list("2 2 2")), graph.IsGraphical(list("3 1")), graph.HavelHakimi(list("2 2 2")).size()

    mut heap := graph.MinHeap {}
    heap.push(3.0, 30)
    heap.push(1.0, 10)
    heap.push(2.0, 20)
    println heap.size(), heap.top_key(), heap.top_value(), heap.pop(), heap.pop(), heap.is_empty()
    heap.clear()
    println heap.is_empty()
    heap.free()
    mut sets := graph.NewDisjointSet(5)
    println sets.union(0, 1), sets.union(1, 2), sets.union(0, 2), sets.connected(0, 2), sets.set_size(0), sets.count(), sets.find(2) == sets.find(0)
    sets.reset(3)
    println sets.count()
    sets.free()
    mut nums := Vector {} as Vector<int>
    graph.Iota(nums, 4)
    graph.ReverseInt(nums)
    println ints(nums), graph.MaxInt(nums), graph.SumInt(nums)
    graph.FillInt(nums, 3, 7)
    mut fl := Vector {} as Vector<f64>
    graph.FillFloat(fl, 2, 1.5)
    println ints(nums), graph.SumFloat(fl)
end
Output50 200 3 1 [3 2 2 2 1] [0 1 3 1] true true 3 [3 3 2 2 3] 3 2 [2 3] [0 1 4] 170 17 3 33 47 50 1 -11 1 3 [50 50 75 50 25]/100 [57 57 80 67 44]/100 [71 71 88 75 54]/100 [0 0 400 300 0]/100 [100 300 300 600 400]/100 [50 50 60 34 15]/100 [126 126 138 125 113]/100 [32 31 33 4]/100 2 [33 33 67 0]/100 [33 33 33 33]/100 2 [25 25 25 25]/100 3 1 0 2 1 2 2 -71 2 6 3 4 [200 300]/100 [-141 0 141]/100 [0 100 300]/100 141 100 3 7 2 true true 10 false true false 3 3 1 10 10 20 false true true true false true 3 3 true 3 [3 2 1 0] 3 6 [7 7 7] 3

push

func push(k: f64, v: int)
Adds an entry.

The example for this item is shown with the ones above: graph-Analysis.salam

size

func size(): int
The size.

The example for this item is shown with the ones above: graph-Analysis.salam

is_empty

func is_empty(): bool
True when the heap is empty.

The example for this item is shown with the ones above: graph-Analysis.salam

top_key

func top_key(): f64
The smallest key.

The example for this item is shown with the ones above: graph-Analysis.salam

top_value

func top_value(): int
The value of the smallest key.

The example for this item is shown with the ones above: graph-Analysis.salam

pop

func pop(): int
Removes the smallest entry and returns its value.

The example for this item is shown with the ones above: graph-Analysis.salam

clear

func clear()
Empties the heap.

The example for this item is shown with the ones above: graph-Analysis.salam

free

func free()
Frees the heap.

The example for this item is shown with the ones above: graph-Analysis.salam

DisjointSet

struct DisjointSet
Disjoint sets, that is union-find.
NameTypeDescription
parentVectorThe parents.
szVectorThe sizes.
groupsint = 0The number of sets.

The example for this item is shown with the ones above: graph-Analysis.salam

reset

func reset(n: int)
Starts over with n single-member sets.

The example for this item is shown with the ones above: graph-Analysis.salam

find

func find(x: int): int
The representative of a set.

The example for this item is shown with the ones above: graph-Analysis.salam

union

func union(a: int, b: int): bool
Merges two sets; false when they were already one.

The example for this item is shown with the ones above: graph-Analysis.salam

connected

func connected(a: int, b: int): bool
True when both are in the same set.

The example for this item is shown with the ones above: graph-Analysis.salam

set_size

func set_size(a: int): int
The size of a set.

The example for this item is shown with the ones above: graph-Analysis.salam

count

func count(): int
The number of sets.

The example for this item is shown with the ones above: graph-Analysis.salam

free

func free()
Frees the sets.

The example for this item is shown with the ones above: graph-Analysis.salam

Constants and variables

GRAPH_INF

const GRAPH_INF: f64 = 1e+300
Infinity, for a distance that cannot be reached.

The example for this item is shown with the ones above: graph-Build.salam

GRAPH_NONE

const GRAPH_NONE: i32 = -1
No node or edge, that is -1.

The example for this item is shown with the ones above: graph-Build.salam

Functions

KCore

func KCore(g &: Graph, k: int, alive &: Vector<bool>): int
The k-core and its size.

The example for this item is shown with the ones above: graph-Flow.salam

CoreNumbers

func CoreNumbers(g &: Graph): Vector<int>
The core number of each node.

The example for this item is shown with the ones above: graph-Flow.salam

Degeneracy

func Degeneracy(g &: Graph): int
The degeneracy.

The example for this item is shown with the ones above: graph-Flow.salam

Modularity

func Modularity(g &: Graph, comm: Vector<int>): f64
The modularity of a partition.

The example for this item is shown with the ones above: graph-Flow.salam

LabelPropagation

func LabelPropagation(g &: Graph, comm &: Vector<int>): int
Communities by label propagation.

The example for this item is shown with the ones above: graph-Flow.salam

Louvain

func Louvain(g &: Graph, comm &: Vector<int>): int
Communities with Louvain.

The example for this item is shown with the ones above: graph-Flow.salam

GirvanNewman

func GirvanNewman(g &: Graph, want: int, comm &: Vector<int>): int
Communities by removing the edges with the highest betweenness.

The example for this item is shown with the ones above: graph-Flow.salam

NewMatrix

func NewMatrix(rows: int, cols: int): Matrix
A zero matrix.

The example for this item is shown with the ones above: graph-Analysis.salam

NewIntMatrix

func NewIntMatrix(rows: int, cols: int, fill: int): IntMatrix
An integer matrix filled with one value.

The example for this item is shown with the ones above: graph-Paths.salam

AdjacencyMatrix

func AdjacencyMatrix(g &: Graph): Matrix
The adjacency matrix.

The example for this item is shown with the ones above: graph-Analysis.salam

WeightMatrix

func WeightMatrix(g &: Graph): Matrix
The weight matrix.

The example for this item is shown with the ones above: graph-Analysis.salam

DegreeMatrix

func DegreeMatrix(g &: Graph): Matrix
The degree matrix.

The example for this item is shown with the ones above: graph-Analysis.salam

LaplacianMatrix

func LaplacianMatrix(g &: Graph): Matrix
The Laplacian matrix.

The example for this item is shown with the ones above: graph-Analysis.salam

NormalizedLaplacian

func NormalizedLaplacian(g &: Graph): Matrix
The normalized Laplacian.

The example for this item is shown with the ones above: graph-Analysis.salam

IncidenceMatrix

func IncidenceMatrix(g &: Graph): Matrix
The node-edge incidence matrix.

The example for this item is shown with the ones above: graph-Analysis.salam

MatrixMultiply

func MatrixMultiply(x &: Matrix, y &: Matrix): Matrix
Matrix multiplication.

The example for this item is shown with the ones above: graph-Analysis.salam

MatrixIdentity

func MatrixIdentity(n: int): Matrix
The identity matrix.

The example for this item is shown with the ones above: graph-Analysis.salam

MatrixPower

func MatrixPower(x &: Matrix, k: int): Matrix
A matrix power.

The example for this item is shown with the ones above: graph-Analysis.salam

WalkCount

func WalkCount(g &: Graph, k: int, u: int, v: int): f64
The number of walks of length k.

The example for this item is shown with the ones above: graph-Paths.salam

BFSFrom

func BFSFrom(g &: Graph, src: int, dist &: Vector<int>, parent &: Vector<int>)
Breadth-first search with distances and parents.
graph-Search.salam
import graph

func ints(v: Vector<int>): str:
    mut text := "["
    repeat v.len() in i:
        if i > 0:
            text += " "
        end
        text += "" + v.get(i)
    end
    ret text + "]"
end


func main:
    mut g := graph.FromEdgeList("0 1\n1 2\n2 0\n2 3\n4 5", 6, false)
    println ints(graph.BFS(g, 0)), ints(graph.BFSOrder(g, 0)), ints(graph.DFSOrder(g, 0)), ints(graph.DFSPostOrder(g, 0))
    mut dist := Vector {} as Vector<int>
    mut parent := Vector {} as Vector<int>
    graph.BFSFrom(g, 0, dist, parent)
    println ints(dist), ints(graph.PathFromParents(parent, 0, 3)), ints(graph.DFSForest(g))
    println graph.ReachableCount(g, 0), graph.Reachable(g, 4).get(5), graph.HopDistance(g, 0, 3), graph.HopDistance(g, 0, 4), ints(graph.HopPath(g, 1, 3))
    mut comp := Vector {} as Vector<int>
    println graph.Components(g, comp), ints(comp), graph.ComponentCount(g), ints(graph.ComponentSizes(g)), graph.IsConnected(g)
    mut color := Vector {} as Vector<int>
    println graph.IsBipartite(graph.CycleGraph(4), color), ints(color), graph.Bipartite(g)
    println ints(graph.FindCycle(g)), graph.HasCycle(g)
    println ints(graph.Bridges(g)), ints(graph.ArticulationPoints(g))
    mut bicomp := Vector {} as Vector<int>
    println graph.BiconnectedComponents(g, bicomp), ints(bicomp), graph.IsBiconnected(graph.CycleGraph(5)), graph.IsTwoEdgeConnected(graph.CycleGraph(5))
    mut twoedge := Vector {} as Vector<int>
    println graph.TwoEdgeComponents(g, twoedge), ints(twoedge)
    hops := graph.AllPairsHops(graph.PathGraph(3))
    println hops.at(0, 2), hops.rows

    mut tasks := graph.FromEdgeList("0 1\n0 2\n1 3\n2 3\n3 4", 5, true)
    mut order := Vector {} as Vector<int>
    println graph.TopologicalSort(tasks, order), ints(order)
    println graph.TopologicalSortLex(tasks, order), ints(order), graph.IsDAG(tasks)
    mut cyclic := graph.FromEdgeList("0 1\n1 2\n2 0\n2 3\n3 4\n4 3", 5, true)
    mut strong := Vector {} as Vector<int>
    println graph.StronglyConnected(cyclic, strong), ints(strong), graph.SCCCount(cyclic), graph.IsStronglyConnected(cyclic)
    mut kosa := Vector {} as Vector<int>
    println graph.Kosaraju(cyclic, kosa)
    dag := graph.Condensation(cyclic, strong)
    println dag.order(), dag.size()
end
Output[0 1 1 2 -1 -1] [0 1 2 3] [0 1 2 3] [3 2 1 0] [0 1 1 2 -1 -1] [0 2 3] [0 1 2 3 4 5] 4 true 2 -1 [1 2 3] 2 [0 0 0 0 1 1] 2 [4 2] false true [0 1 0 1] false [0 1 2] true [3 4] [2] 3 [1 1 1 0 2] true true 4 [0 0 0 1 2 3] 2 3 true [0 1 2 3 4] true [0 1 2 3 4] true 2 [1 1 1 0 0] 2 false 2 2 1

BFS

func BFS(g &: Graph, src: int): Vector<int>
The hop distance of every node from the source; -1 means unreachable.

The example for this item is shown with the ones above: graph-Search.salam

BFSOrder

func BFSOrder(g &: Graph, src: int): Vector<int>
The order in which breadth-first search visits the nodes.

The example for this item is shown with the ones above: graph-Search.salam

DFSOrder

func DFSOrder(g &: Graph, src: int): Vector<int>
The depth-first order.

The example for this item is shown with the ones above: graph-Search.salam

DFSPostOrder

func DFSPostOrder(g &: Graph, src: int): Vector<int>
The depth-first post-order.

The example for this item is shown with the ones above: graph-Search.salam

DFSForest

func DFSForest(g &: Graph): Vector<int>
The depth-first order of the whole graph.

The example for this item is shown with the ones above: graph-Search.salam

Reachable

func Reachable(g &: Graph, src: int): Vector<bool>
Whether each node is reachable.

The example for this item is shown with the ones above: graph-Search.salam

ReachableCount

func ReachableCount(g &: Graph, src: int): int
The number of reachable nodes.

The example for this item is shown with the ones above: graph-Search.salam

HopDistance

func HopDistance(g &: Graph, s: int, t: int): int
The fewest number of hops.

The example for this item is shown with the ones above: graph-Search.salam

PathFromParents

func PathFromParents(parent: Vector<int>, s: int, t: int): Vector<int>
A path from the parent list.

The example for this item is shown with the ones above: graph-Search.salam

HopPath

func HopPath(g &: Graph, s: int, t: int): Vector<int>
The path with the fewest hops.

The example for this item is shown with the ones above: graph-Search.salam

CountColorings

func CountColorings(g &: Graph, k: int): f64
The number of colorings with k colors.

The example for this item is shown with the ones above: graph-Flow.salam

DegreeCentrality

func DegreeCentrality(g &: Graph): Vector<f64>
The degree centrality.

The example for this item is shown with the ones above: graph-Analysis.salam

InDegreeCentrality

func InDegreeCentrality(g &: Graph): Vector<f64>
The in-degree centrality.

The example for this item is shown with the ones above: graph-Analysis.salam

OutDegreeCentrality

func OutDegreeCentrality(g &: Graph): Vector<f64>
The out-degree centrality.

The example for this item is shown with the ones above: graph-Analysis.salam

ClosenessCentrality

func ClosenessCentrality(g &: Graph): Vector<f64>
The closeness centrality.

The example for this item is shown with the ones above: graph-Analysis.salam

HarmonicCentrality

func HarmonicCentrality(g &: Graph): Vector<f64>
The harmonic centrality.

The example for this item is shown with the ones above: graph-Analysis.salam

BetweennessCentrality

func BetweennessCentrality(g &: Graph): Vector<f64>
The betweenness centrality, with Brandes.

The example for this item is shown with the ones above: graph-Analysis.salam

EdgeBetweenness

func EdgeBetweenness(g &: Graph): Vector<f64>
The betweenness of the edges.

The example for this item is shown with the ones above: graph-Analysis.salam

EigenvectorCentrality

func EigenvectorCentrality(g &: Graph, iters: int, tol: f64): Vector<f64>
The eigenvector centrality.

The example for this item is shown with the ones above: graph-Analysis.salam

KatzCentrality

func KatzCentrality(g &: Graph, alpha: f64, beta: f64, iters: int, tol: f64): Vector<f64>
The Katz centrality.

The example for this item is shown with the ones above: graph-Analysis.salam

PageRank

func PageRank(g &: Graph, damping: f64, iters: int, tol: f64): Vector<f64>
Page ranking, as Google does it.

The example for this item is shown with the ones above: graph-Analysis.salam

HITS

func HITS(g &: Graph, iters: int, tol: f64, hubs &: Vector<f64>, auth &: Vector<f64>)
The hub and authority scores.

The example for this item is shown with the ones above: graph-Analysis.salam

TopNode

func TopNode(score: Vector<f64>): int
The node with the highest score.

The example for this item is shown with the ones above: graph-Analysis.salam

ScaleToSum

func ScaleToSum(v &: Vector<f64>)
Normalizes the scores so they sum to one.

The example for this item is shown with the ones above: graph-Analysis.salam

GreedyColoring

func GreedyColoring(g &: Graph, order: Vector<int>): Vector<int>
A greedy coloring in the given order.

The example for this item is shown with the ones above: graph-Flow.salam

GreedyColoringNatural

func GreedyColoringNatural(g &: Graph): Vector<int>
A greedy coloring in number order.

The example for this item is shown with the ones above: graph-Flow.salam

WelshPowell

func WelshPowell(g &: Graph): Vector<int>
The Welsh-Powell coloring.

The example for this item is shown with the ones above: graph-Flow.salam

DSatur

func DSatur(g &: Graph): Vector<int>
The DSatur coloring.

The example for this item is shown with the ones above: graph-Flow.salam

ColorCount

func ColorCount(color: Vector<int>): int
The number of colors.

The example for this item is shown with the ones above: graph-Flow.salam

IsProperColoring

func IsProperColoring(g &: Graph, color: Vector<int>): bool
True when no two neighbors share a color.

The example for this item is shown with the ones above: graph-Flow.salam

ChromaticNumber

func ChromaticNumber(g &: Graph): int
The fewest colors needed; for small graphs.

The example for this item is shown with the ones above: graph-Flow.salam

EdgeColoringGreedy

func EdgeColoringGreedy(g &: Graph): Vector<int>
A greedy edge coloring.

The example for this item is shown with the ones above: graph-Flow.salam

Clone

func Clone(g &: Graph): Graph
A copy.

The example for this item is shown with the ones above: graph-Build.salam

Transpose

func Transpose(g &: Graph): Graph
Reverses the direction of every edge.

The example for this item is shown with the ones above: graph-Build.salam

Reverse

func Reverse(g &: Graph): Graph
The same as the transpose.

The example for this item is shown with the ones above: graph-Build.salam

ToUndirected

func ToUndirected(g &: Graph): Graph
An undirected version.

The example for this item is shown with the ones above: graph-Build.salam

ToDirected

func ToDirected(g &: Graph): Graph
A directed version with an edge in both directions.

The example for this item is shown with the ones above: graph-Build.salam

SubgraphMap

func SubgraphMap(g &: Graph, keep: Vector<bool>, map &: Vector<int>): Graph
The subgraph of the kept nodes, with a map from old numbers to new ones.

The example for this item is shown with the ones above: graph-Build.salam

Subgraph

func Subgraph(g &: Graph, keep: Vector<bool>): Graph
The subgraph of the kept nodes.

The example for this item is shown with the ones above: graph-Build.salam

EdgeSubgraph

func EdgeSubgraph(g &: Graph, keep: Vector<bool>): Graph
The subgraph of the kept edges.

The example for this item is shown with the ones above: graph-Build.salam

Complement

func Complement(g &: Graph): Graph
The complement.

The example for this item is shown with the ones above: graph-Build.salam

Union

func Union(a &: Graph, b &: Graph): Graph
The union of the edges over the same nodes.

The example for this item is shown with the ones above: graph-Build.salam

DisjointUnion

func DisjointUnion(a &: Graph, b &: Graph): Graph
Two graphs side by side, with no shared edge.

The example for this item is shown with the ones above: graph-Build.salam

Intersection

func Intersection(a &: Graph, b &: Graph): Graph
The shared edges.

The example for this item is shown with the ones above: graph-Build.salam

LineGraph

func LineGraph(g &: Graph): Graph
The line graph: each edge becomes a node.

The example for this item is shown with the ones above: graph-Build.salam

Simplify

func Simplify(g &: Graph): Graph
Without self-loops and parallel edges.

The example for this item is shown with the ones above: graph-Build.salam

RemoveSelfLoops

func RemoveSelfLoops(g &: Graph): Graph
Without self-loops.

The example for this item is shown with the ones above: graph-Build.salam

SelfLoopCount

func SelfLoopCount(g &: Graph): int
The number of self-loops.

The example for this item is shown with the ones above: graph-Build.salam

HasSelfLoop

func HasSelfLoop(g &: Graph): bool
True when there is a self-loop.

The example for this item is shown with the ones above: graph-Build.salam

ParallelEdgeCount

func ParallelEdgeCount(g &: Graph): int
The number of parallel edges.

The example for this item is shown with the ones above: graph-Build.salam

IsSimple

func IsSimple(g &: Graph): bool
True when the graph is simple.

The example for this item is shown with the ones above: graph-Build.salam

TotalWeight

func TotalWeight(g &: Graph): f64
The sum of the edge weights.

The example for this item is shown with the ones above: graph-Build.salam

FloydWarshall

func FloydWarshall(g &: Graph): Matrix
The distance of every pair.

The example for this item is shown with the ones above: graph-Paths.salam

FloydWarshallPaths

func FloydWarshallPaths(g &: Graph, next &: IntMatrix): Matrix
The same, with a next-step matrix.

The example for this item is shown with the ones above: graph-Paths.salam

FloydPath

func FloydPath(next &: IntMatrix, s: int, t: int): Vector<int>
A path from the next-step matrix.

The example for this item is shown with the ones above: graph-Paths.salam

Johnson

func Johnson(g &: Graph): Matrix
The distance of every pair in a sparse graph with negative weights.

The example for this item is shown with the ones above: graph-Paths.salam

AStar

func AStar(g &: Graph, src: int, target: int, heuristic: Vector<f64>): Vector<int>
A* search with an estimate of the distance to the target.

The example for this item is shown with the ones above: graph-Paths.salam

KShortestLengths

func KShortestLengths(g &: Graph, s: int, t: int, k: int): Vector<f64>
The lengths of the k shortest paths.

The example for this item is shown with the ones above: graph-Paths.salam

AllPairsHops

func AllPairsHops(g &: Graph): IntMatrix
The hop distance of every pair.

The example for this item is shown with the ones above: graph-Search.salam

IsTree

func IsTree(g &: Graph): bool
True when the graph is a tree.

The example for this item is shown with the ones above: graph-Trees.salam

IsForest

func IsForest(g &: Graph): bool
True when the graph is a forest.

The example for this item is shown with the ones above: graph-Trees.salam

RootTree

func RootTree(g &: Graph, root: int, parent &: Vector<int>, order &: Vector<int>)
Roots the tree, filling in the parents and the order.

The example for this item is shown with the ones above: graph-Trees.salam

SubtreeSizes

func SubtreeSizes(g &: Graph, root: int): Vector<int>
The size of each node's subtree.

The example for this item is shown with the ones above: graph-Trees.salam

TreeDiameter

func TreeDiameter(g &: Graph, ends &: Vector<int>): int
The diameter of the tree and its two ends.

The example for this item is shown with the ones above: graph-Trees.salam

TreeCenter

func TreeCenter(g &: Graph): Vector<int>
The center of the tree.

The example for this item is shown with the ones above: graph-Trees.salam

TreeCentroid

func TreeCentroid(g &: Graph): Vector<int>
The centroid of the tree.

The example for this item is shown with the ones above: graph-Trees.salam

New

func New(n: int, directed: bool): Graph
A graph with n nodes, directed or undirected.

The example for this item is shown with the ones above: graph-Build.salam

NewUndirected

func NewUndirected(n: int): Graph
An undirected graph.

The example for this item is shown with the ones above: graph-Build.salam

NewDirected

func NewDirected(n: int): Graph
A directed graph.

The example for this item is shown with the ones above: graph-Build.salam

FromEdges

func FromEdges(n: int, us: Vector<int>, vs: Vector<int>, directed: bool): Graph
A graph from two lists of edge start and end nodes.

The example for this item is shown with the ones above: graph-Build.salam

IsClose

func IsClose(a: f64, b: f64): bool
True when two floats are equal within a tolerance.

The example for this item is shown with the ones above: graph-Build.salam

Determinant

func Determinant(x &: Matrix): f64
The determinant.

The example for this item is shown with the ones above: graph-Analysis.salam

SpanningTreeCount

func SpanningTreeCount(g &: Graph): f64
The number of spanning trees, by Kirchhoff's theorem.

The example for this item is shown with the ones above: graph-Trees.salam

SymmetricEigenvalues

func SymmetricEigenvalues(x &: Matrix): Vector<f64>
The eigenvalues of a symmetric matrix.

The example for this item is shown with the ones above: graph-Analysis.salam

AdjacencySpectrum

func AdjacencySpectrum(g &: Graph): Vector<f64>
The adjacency spectrum.

The example for this item is shown with the ones above: graph-Analysis.salam

LaplacianSpectrum

func LaplacianSpectrum(g &: Graph): Vector<f64>
The Laplacian spectrum.

The example for this item is shown with the ones above: graph-Analysis.salam

SpectralRadius

func SpectralRadius(g &: Graph): f64
The spectral radius.

The example for this item is shown with the ones above: graph-Analysis.salam

AlgebraicConnectivity

func AlgebraicConnectivity(g &: Graph): f64
The algebraic connectivity, the second eigenvalue of the Laplacian.

The example for this item is shown with the ones above: graph-Analysis.salam

GlobalMinCut

func GlobalMinCut(g &: Graph): f64
The global minimum cut, with Stoer-Wagner.

The example for this item is shown with the ones above: graph-Flow.salam

EdgeConnectivity

func EdgeConnectivity(g &: Graph): int
The fewest edges whose removal disconnects the graph.

The example for this item is shown with the ones above: graph-Flow.salam

VertexConnectivity

func VertexConnectivity(g &: Graph): int
The fewest nodes whose removal disconnects the graph.

The example for this item is shown with the ones above: graph-Flow.salam

BipartiteMatching

func BipartiteMatching(g &: Graph, mate &: Vector<int>): int
The maximum bipartite matching, with Hopcroft-Karp.

The example for this item is shown with the ones above: graph-Flow.salam

MaximalMatching

func MaximalMatching(g &: Graph, mate &: Vector<int>): int
A greedy maximal matching.

The example for this item is shown with the ones above: graph-Flow.salam

MinimumVertexCover

func MinimumVertexCover(g &: Graph, cover &: Vector<bool>): int
The minimum vertex cover of a bipartite graph.

The example for this item is shown with the ones above: graph-Flow.salam

MaximumIndependentSetBipartite

func MaximumIndependentSetBipartite(g &: Graph, pick &: Vector<bool>): int
The maximum independent set of a bipartite graph.

The example for this item is shown with the ones above: graph-Flow.salam

EmptyGraph

func EmptyGraph(n: int): Graph
A graph with no edges.

The example for this item is shown with the ones above: graph-Build.salam

CompleteGraph

func CompleteGraph(n: int): Graph
The complete graph.

The example for this item is shown with the ones above: graph-Build.salam

CompleteBipartite

func CompleteBipartite(a: int, b: int): Graph
The complete bipartite graph.

The example for this item is shown with the ones above: graph-Build.salam

PathGraph

func PathGraph(n: int): Graph
The path graph.

The example for this item is shown with the ones above: graph-Build.salam

CycleGraph

func CycleGraph(n: int): Graph
The cycle graph.

The example for this item is shown with the ones above: graph-Build.salam

StarGraph

func StarGraph(n: int): Graph
The star graph.

The example for this item is shown with the ones above: graph-Build.salam

WheelGraph

func WheelGraph(n: int): Graph
The wheel graph.

The example for this item is shown with the ones above: graph-Build.salam

GridGraph

func GridGraph(rows: int, cols: int): Graph
The grid graph.

The example for this item is shown with the ones above: graph-Build.salam

HypercubeGraph

func HypercubeGraph(d: int): Graph
The hypercube graph.

The example for this item is shown with the ones above: graph-Build.salam

PetersenGraph

func PetersenGraph(): Graph
The Petersen graph.

The example for this item is shown with the ones above: graph-Build.salam

CirculantGraph

func CirculantGraph(n: int, offsets: Vector<int>): Graph
The circulant graph with the given offsets.

The example for this item is shown with the ones above: graph-Build.salam

BalancedTree

func BalancedTree(branch: int, depth: int): Graph
A balanced tree with the given branching and depth.

The example for this item is shown with the ones above: graph-Build.salam

ErdosRenyi

func ErdosRenyi(n: int, p: f64): Graph
An Erdos-Renyi random graph with an edge probability.

The example for this item is shown with the ones above: graph-Build.salam

RandomGraph

func RandomGraph(n: int, m: int): Graph
A random graph with m edges.

The example for this item is shown with the ones above: graph-Build.salam

RandomTree

func RandomTree(n: int): Graph
A random tree.

The example for this item is shown with the ones above: graph-Build.salam

BarabasiAlbert

func BarabasiAlbert(n: int, m: int): Graph
A Barabasi-Albert scale-free random graph.

The example for this item is shown with the ones above: graph-Build.salam

WattsStrogatz

func WattsStrogatz(n: int, k: int, p: f64): Graph
A Watts-Strogatz small-world graph.

The example for this item is shown with the ones above: graph-Build.salam

Density

func Density(g &: Graph): f64
The density.

The example for this item is shown with the ones above: graph-Analysis.salam

AverageDegree

func AverageDegree(g &: Graph): f64
The average degree.

The example for this item is shown with the ones above: graph-Analysis.salam

MaxDegree

func MaxDegree(g &: Graph): int
The largest degree.

The example for this item is shown with the ones above: graph-Analysis.salam

MinDegree

func MinDegree(g &: Graph): int
The smallest degree.

The example for this item is shown with the ones above: graph-Analysis.salam

DegreeSequence

func DegreeSequence(g &: Graph): Vector<int>
The degree sequence, in descending order.

The example for this item is shown with the ones above: graph-Analysis.salam

DegreeHistogram

func DegreeHistogram(g &: Graph): Vector<int>
The number of nodes with each degree.

The example for this item is shown with the ones above: graph-Analysis.salam

IsRegular

func IsRegular(g &: Graph): bool
True when every degree is the same.

The example for this item is shown with the ones above: graph-Analysis.salam

IsComplete

func IsComplete(g &: Graph): bool
True when the graph is complete.

The example for this item is shown with the ones above: graph-Analysis.salam

Eccentricity

func Eccentricity(g &: Graph, u: int): int
The farthest distance from a node.

The example for this item is shown with the ones above: graph-Analysis.salam

EccentricityAll

func EccentricityAll(g &: Graph): Vector<int>
The eccentricity of every node.

The example for this item is shown with the ones above: graph-Analysis.salam

Diameter

func Diameter(g &: Graph): int
The diameter.

The example for this item is shown with the ones above: graph-Trees.salam

Radius

func Radius(g &: Graph): int
The radius.

The example for this item is shown with the ones above: graph-Analysis.salam

Center

func Center(g &: Graph): Vector<int>
The central nodes.

The example for this item is shown with the ones above: graph-Trees.salam

Periphery

func Periphery(g &: Graph): Vector<int>
The peripheral nodes.

The example for this item is shown with the ones above: graph-Analysis.salam

AveragePathLength

func AveragePathLength(g &: Graph): f64
The average distance.

The example for this item is shown with the ones above: graph-Analysis.salam

WienerIndex

func WienerIndex(g &: Graph): f64
The sum of the distances.

The example for this item is shown with the ones above: graph-Analysis.salam

Girth

func Girth(g &: Graph): int
The shortest cycle.

The example for this item is shown with the ones above: graph-Analysis.salam

HasEulerianCircuit

func HasEulerianCircuit(g &: Graph): bool
True when there is an Eulerian circuit.

The example for this item is shown with the ones above: graph-Paths.salam

HasEulerianPath

func HasEulerianPath(g &: Graph): bool
True when there is an Eulerian path.

The example for this item is shown with the ones above: graph-Paths.salam

EulerianCircuit

func EulerianCircuit(g &: Graph): Vector<int>
A cycle that passes every edge once.

The example for this item is shown with the ones above: graph-Paths.salam

EulerianPath

func EulerianPath(g &: Graph): Vector<int>
A path that passes every edge once.

The example for this item is shown with the ones above: graph-Paths.salam

HamiltonianPath

func HamiltonianPath(g &: Graph): Vector<int>
A path that passes every node once; for small graphs.

The example for this item is shown with the ones above: graph-Paths.salam

HamiltonianCycle

func HamiltonianCycle(g &: Graph): Vector<int>
A Hamiltonian cycle.

The example for this item is shown with the ones above: graph-Paths.salam

HasHamiltonianCycle

func HasHamiltonianCycle(g &: Graph): bool
True when there is a Hamiltonian cycle.

The example for this item is shown with the ones above: graph-Paths.salam

TourLength

func TourLength(g &: Graph, tour: Vector<int>): f64
The length of a tour.

The example for this item is shown with the ones above: graph-Paths.salam

TSPNearestNeighbor

func TSPNearestNeighbor(g &: Graph, start: int): Vector<int>
A traveling salesman tour by nearest neighbor.

The example for this item is shown with the ones above: graph-Paths.salam

TSPTwoOpt

func TSPTwoOpt(g &: Graph, tour &: Vector<int>): f64
Improves the tour with 2-opt swaps and returns the new length.

The example for this item is shown with the ones above: graph-Paths.salam

TSPHeuristic

func TSPHeuristic(g &: Graph, start: int): Vector<int>
The two methods above combined.

The example for this item is shown with the ones above: graph-Paths.salam

NewFlowNet

func NewFlowNet(n: int): FlowNet
A flow network with n nodes.

The example for this item is shown with the ones above: graph-Flow.salam

FlowFromGraph

func FlowFromGraph(g &: Graph): FlowNet
A flow network from a graph, with the weights as capacities.

The example for this item is shown with the ones above: graph-Flow.salam

MaxFlow

func MaxFlow(f &: FlowNet, s: int, t: int): f64
The maximum flow, with Dinic.

The example for this item is shown with the ones above: graph-Flow.salam

MaxFlowEdmondsKarp

func MaxFlowEdmondsKarp(f &: FlowNet, s: int, t: int): f64
The maximum flow, with Edmonds-Karp.

The example for this item is shown with the ones above: graph-Flow.salam

MinCut

func MinCut(f &: FlowNet, s: int, t: int, side &: Vector<bool>): f64
The minimum cut and the source side.

The example for this item is shown with the ones above: graph-Flow.salam

MaxFlowValue

func MaxFlowValue(g &: Graph, s: int, t: int): f64
The maximum flow in a graph.

The example for this item is shown with the ones above: graph-Flow.salam

MinCutEdges

func MinCutEdges(g &: Graph, s: int, t: int, cut &: Vector<int>): f64
The edges of the minimum cut.

The example for this item is shown with the ones above: graph-Flow.salam

MinCostFlow

func MinCostFlow(f &: FlowNet, s: int, t: int, want: f64, sent &: f64): f64
The flow with the lowest cost; also fills in the amount sent.

The example for this item is shown with the ones above: graph-Flow.salam

Kruskal

func Kruskal(g &: Graph, chosen &: Vector<int>): f64
The minimum spanning tree with Kruskal; returns the weight.

The example for this item is shown with the ones above: graph-Trees.salam

MaximumSpanningTree

func MaximumSpanningTree(g &: Graph, chosen &: Vector<int>): f64
The maximum spanning tree.

The example for this item is shown with the ones above: graph-Trees.salam

Prim

func Prim(g &: Graph, root: int, parent &: Vector<int>): f64
The minimum spanning tree with Prim.

The example for this item is shown with the ones above: graph-Trees.salam

Boruvka

func Boruvka(g &: Graph, chosen &: Vector<int>): f64
The minimum spanning tree with Boruvka.

The example for this item is shown with the ones above: graph-Trees.salam

MSTWeight

func MSTWeight(g &: Graph): f64
The weight of the minimum spanning tree.

The example for this item is shown with the ones above: graph-Trees.salam

MinimumSpanningTree

func MinimumSpanningTree(g &: Graph): Graph
The minimum spanning tree as a graph.

The example for this item is shown with the ones above: graph-Trees.salam

SpanningAgreement

func SpanningAgreement(g &: Graph): bool
True when the three algorithms give the same weight; for tests.

The example for this item is shown with the ones above: graph-Trees.salam

DAGShortestPath

func DAGShortestPath(g &: Graph, src: int, dist &: Vector<f64>, parent &: Vector<int>): bool
The shortest path in an acyclic graph.

The example for this item is shown with the ones above: graph-Paths.salam

DAGLongestPath

func DAGLongestPath(g &: Graph, src: int, dist &: Vector<f64>, parent &: Vector<int>): bool
The longest path in an acyclic graph.

The example for this item is shown with the ones above: graph-Paths.salam

CriticalPath

func CriticalPath(g &: Graph): Vector<int>
The critical path of a project.

The example for this item is shown with the ones above: graph-Paths.salam

CountPaths

func CountPaths(g &: Graph, s: int, t: int): f64
The number of paths in an acyclic graph.

The example for this item is shown with the ones above: graph-Paths.salam

PathCounts

func PathCounts(g &: Graph, src: int): Vector<f64>
The number of paths from the source to each node.

The example for this item is shown with the ones above: graph-Paths.salam

TransitiveClosure

func TransitiveClosure(g &: Graph): IntMatrix
The transitive closure: who can reach whom.

The example for this item is shown with the ones above: graph-Paths.salam

TransitiveReduction

func TransitiveReduction(g &: Graph): Graph
The smallest graph with the same reachability.

The example for this item is shown with the ones above: graph-Paths.salam

TopologicalLayers

func TopologicalLayers(g &: Graph, layer &: Vector<int>): int
The layer of each node; the tasks that can run at the same time.

The example for this item is shown with the ones above: graph-Paths.salam

IsTotalOrder

func IsTotalOrder(g &: Graph): bool
True when the topological order is unique.

The example for this item is shown with the ones above: graph-Paths.salam

BuildLCA

func BuildLCA(g &: Graph, root: int): LCAIndex
A lowest common ancestor index, by binary lifting.

The example for this item is shown with the ones above: graph-Trees.salam

LCA

func LCA(ix &: LCAIndex, u0: int, v0: int): int
The lowest common ancestor of two nodes.

The example for this item is shown with the ones above: graph-Trees.salam

TreeDistance

func TreeDistance(ix &: LCAIndex, u: int, v: int): int
The distance between two nodes in the tree.

The example for this item is shown with the ones above: graph-Trees.salam

PruferEncode

func PruferEncode(g &: Graph): Vector<int>
The Prufer code of the tree.

The example for this item is shown with the ones above: graph-Trees.salam

PruferDecode

func PruferDecode(code: Vector<int>): Graph
A tree from a Prufer code.

The example for this item is shown with the ones above: graph-Trees.salam

TreeIsomorphic

func TreeIsomorphic(a &: Graph, b &: Graph): bool
True when two trees are isomorphic.

The example for this item is shown with the ones above: graph-Trees.salam

TreeCanonicalForm

func TreeCanonicalForm(g &: Graph): str
The canonical form of the tree, in parentheses.

The example for this item is shown with the ones above: graph-Trees.salam

LabeledTreeCount

func LabeledTreeCount(n: int): f64
The number of labeled trees, n to the power n minus two.

The example for this item is shown with the ones above: graph-Trees.salam

TreeToString

func TreeToString(g &: Graph, root: int): str
The tree as parenthesized text.

The example for this item is shown with the ones above: graph-Trees.salam

StronglyConnected

func StronglyConnected(g &: Graph, comp &: Vector<int>): int
The strongly connected components, with Tarjan's algorithm.

The example for this item is shown with the ones above: graph-Search.salam

SCCCount

func SCCCount(g &: Graph): int
The number of strong components.

The example for this item is shown with the ones above: graph-Search.salam

IsStronglyConnected

func IsStronglyConnected(g &: Graph): bool
True when the graph is strongly connected.

The example for this item is shown with the ones above: graph-Search.salam

Kosaraju

func Kosaraju(g &: Graph, comp &: Vector<int>): int
The strong components, with Kosaraju's algorithm.

The example for this item is shown with the ones above: graph-Search.salam

Condensation

func Condensation(g &: Graph, comp &: Vector<int>): Graph
The graph of the components, which never has a cycle.

The example for this item is shown with the ones above: graph-Search.salam

Bridges

func Bridges(g &: Graph): Vector<int>
The edges whose removal disconnects the graph.

The example for this item is shown with the ones above: graph-Search.salam

ArticulationPoints

func ArticulationPoints(g &: Graph): Vector<int>
The nodes whose removal disconnects the graph.

The example for this item is shown with the ones above: graph-Search.salam

BiconnectedComponents

func BiconnectedComponents(g &: Graph, ecomp &: Vector<int>): int
The biconnected components of the edges.

The example for this item is shown with the ones above: graph-Search.salam

IsBiconnected

func IsBiconnected(g &: Graph): bool
True when the graph is biconnected.

The example for this item is shown with the ones above: graph-Search.salam

IsTwoEdgeConnected

func IsTwoEdgeConnected(g &: Graph): bool
True when the graph is connected and has no bridge.

The example for this item is shown with the ones above: graph-Search.salam

TwoEdgeComponents

func TwoEdgeComponents(g &: Graph, comp &: Vector<int>): int
The two-edge-connected components.

The example for this item is shown with the ones above: graph-Search.salam

NewDisjointSet

func NewDisjointSet(n: int): DisjointSet
n single-member sets.

The example for this item is shown with the ones above: graph-Analysis.salam

FillInt

func FillInt(v &: Vector<int>, n: int, x: int)
An int vector with n copies of one value.

The example for this item is shown with the ones above: graph-Analysis.salam

FillFloat

func FillFloat(v &: Vector<f64>, n: int, x: f64)
A float vector with n copies of one value.

The example for this item is shown with the ones above: graph-Paths.salam

FillBool

func FillBool(v &: Vector<bool>, n: int, x: bool)
A bool vector with n copies of one value.

The example for this item is shown with the ones above: graph-Build.salam

Iota

func Iota(v &: Vector<int>, n: int)
0 to n minus one.

The example for this item is shown with the ones above: graph-Analysis.salam

MaxInt

func MaxInt(v: Vector<int>): int
The largest value.

The example for this item is shown with the ones above: graph-Analysis.salam

SumInt

func SumInt(v: Vector<int>): int
The integer sum.

The example for this item is shown with the ones above: graph-Analysis.salam

SumFloat

func SumFloat(v: Vector<f64>): f64
The float sum.

The example for this item is shown with the ones above: graph-Analysis.salam

ReverseInt

func ReverseInt(v &: Vector<int>)
Reverses the vector in place.

The example for this item is shown with the ones above: graph-Analysis.salam

ToEdgeList

func ToEdgeList(g &: Graph): str
The edge list as text.

The example for this item is shown with the ones above: graph-Build.salam

FromEdgeList

func FromEdgeList(text: str, n: int, directed: bool): Graph
A graph from text, one "from to weight" per line, where the weight is optional.

The example for this item is shown with the ones above: graph-Build.salam

ToAdjacencyList

func ToAdjacencyList(g &: Graph): str
The adjacency list as text.

The example for this item is shown with the ones above: graph-Build.salam

ToMatrixText

func ToMatrixText(g &: Graph): str
The adjacency matrix as text.

The example for this item is shown with the ones above: graph-Build.salam

ToDot

func ToDot(g &: Graph): str
Graphviz DOT text, for drawing.

The example for this item is shown with the ones above: graph-Build.salam

ToMermaid

func ToMermaid(g &: Graph): str
Mermaid text, for drawing in Markdown.

The example for this item is shown with the ones above: graph-Build.salam

ToJSON

func ToJSON(g &: Graph): str
JSON of the nodes and edges, suited to D3.

The example for this item is shown with the ones above: graph-Build.salam

Describe

func Describe(g &: Graph): str
A one-line summary of the properties.

The example for this item is shown with the ones above: graph-Build.salam

Dijkstra

func Dijkstra(g &: Graph, src: int, dist &: Vector<f64>, parent &: Vector<int>): bool
The shortest distances from the source, with non-negative weights.

The example for this item is shown with the ones above: graph-Paths.salam

DijkstraDist

func DijkstraDist(g &: Graph, src: int): Vector<f64>
Only the distances.

The example for this item is shown with the ones above: graph-Paths.salam

ShortestPath

func ShortestPath(g &: Graph, s: int, t: int): Vector<int>
The shortest weighted path.

The example for this item is shown with the ones above: graph-Paths.salam

ShortestPathLength

func ShortestPathLength(g &: Graph, s: int, t: int): f64
Its length.

The example for this item is shown with the ones above: graph-Paths.salam

BellmanFord

func BellmanFord(g &: Graph, src: int, dist &: Vector<f64>, parent &: Vector<int>): bool
The shortest distances with negative weights; false when there is a negative cycle.

The example for this item is shown with the ones above: graph-Paths.salam

FindNegativeCycle

func FindNegativeCycle(g &: Graph): Vector<int>
A negative cycle.

The example for this item is shown with the ones above: graph-Paths.salam

HasNegativeCycle

func HasNegativeCycle(g &: Graph): bool
True when there is a negative cycle.

The example for this item is shown with the ones above: graph-Paths.salam

ZeroOneBFS

func ZeroOneBFS(g &: Graph, src: int, dist &: Vector<f64>, parent &: Vector<int>): bool
The shortest distances when the weights are zero and one.

The example for this item is shown with the ones above: graph-Paths.salam

MaxClique

func MaxClique(g &: Graph): Vector<int>
The largest clique; for small graphs.

The example for this item is shown with the ones above: graph-Flow.salam

CliqueNumber

func CliqueNumber(g &: Graph): int
The size of the largest clique.

The example for this item is shown with the ones above: graph-Flow.salam

MaximumIndependentSet

func MaximumIndependentSet(g &: Graph): Vector<int>
The largest independent set.

The example for this item is shown with the ones above: graph-Flow.salam

IndependenceNumber

func IndependenceNumber(g &: Graph): int
The independence number.

The example for this item is shown with the ones above: graph-Flow.salam

VertexCoverNumber

func VertexCoverNumber(g &: Graph): int
The vertex cover number.

The example for this item is shown with the ones above: graph-Flow.salam

GreedyVertexCover

func GreedyVertexCover(g &: Graph, cover &: Vector<bool>): int
A greedy vertex cover.

The example for this item is shown with the ones above: graph-Flow.salam

LocalClustering

func LocalClustering(g &: Graph, u: int): f64
The clustering coefficient of a node.

The example for this item is shown with the ones above: graph-Analysis.salam

AverageClustering

func AverageClustering(g &: Graph): f64
The average clustering.

The example for this item is shown with the ones above: graph-Analysis.salam

Transitivity

func Transitivity(g &: Graph): f64
The transitivity, the ratio of triangles.

The example for this item is shown with the ones above: graph-Paths.salam

TriangleCount

func TriangleCount(g &: Graph): int
The number of triangles.

The example for this item is shown with the ones above: graph-Analysis.salam

Assortativity

func Assortativity(g &: Graph): f64
The degree assortativity.

The example for this item is shown with the ones above: graph-Analysis.salam

CircuitRank

func CircuitRank(g &: Graph): int
The circuit rank.

The example for this item is shown with the ones above: graph-Analysis.salam

WeightedDiameter

func WeightedDiameter(g &: Graph): f64
The weighted diameter.

The example for this item is shown with the ones above: graph-Analysis.salam

Isomorphic

func Isomorphic(a &: Graph, b &: Graph): bool
True when two graphs are isomorphic.

The example for this item is shown with the ones above: graph-Trees.salam

IsomorphismMap

func IsomorphismMap(a &: Graph, b &: Graph, map &: Vector<int>): bool
The isomorphism mapping.

The example for this item is shown with the ones above: graph-Analysis.salam

AutomorphismCount

func AutomorphismCount(g &: Graph): int
The number of automorphisms.

The example for this item is shown with the ones above: graph-Analysis.salam

IsGraphical

func IsGraphical(seq: Vector<int>): bool
True when a degree sequence can be a simple graph.

The example for this item is shown with the ones above: graph-Analysis.salam

HavelHakimi

func HavelHakimi(seq: Vector<int>): Graph
A simple graph with the given degree sequence.

The example for this item is shown with the ones above: graph-Analysis.salam

SameDegreeSequence

func SameDegreeSequence(a &: Graph, b &: Graph): bool
True when the degree sequences are the same.

The example for this item is shown with the ones above: graph-Analysis.salam

Components

func Components(g &: Graph, comp &: Vector<int>): int
The component number of each node; returns the number of components.

The example for this item is shown with the ones above: graph-Search.salam

ComponentCount

func ComponentCount(g &: Graph): int
The number of components.

The example for this item is shown with the ones above: graph-Search.salam

ComponentSizes

func ComponentSizes(g &: Graph): Vector<int>
The sizes of the components.

The example for this item is shown with the ones above: graph-Search.salam

IsConnected

func IsConnected(g &: Graph): bool
True when the graph is connected.

The example for this item is shown with the ones above: graph-Search.salam

IsBipartite

func IsBipartite(g &: Graph, color &: Vector<int>): bool
True when the graph is bipartite; fills in the two-side coloring.

The example for this item is shown with the ones above: graph-Search.salam

Bipartite

func Bipartite(g &: Graph): bool
True when the graph is bipartite.

The example for this item is shown with the ones above: graph-Build.salam

TopologicalSort

func TopologicalSort(g &: Graph, order &: Vector<int>): bool
The topological order of a directed graph; false when there is a cycle.

The example for this item is shown with the ones above: graph-Search.salam

TopologicalSortLex

func TopologicalSortLex(g &: Graph, order &: Vector<int>): bool
The topological order, taking the smallest number at each step.

The example for this item is shown with the ones above: graph-Search.salam

IsDAG

func IsDAG(g &: Graph): bool
True when the directed graph has no cycle.

The example for this item is shown with the ones above: graph-Search.salam

FindCycle

func FindCycle(g &: Graph): Vector<int>
A cycle.

The example for this item is shown with the ones above: graph-Search.salam

HasCycle

func HasCycle(g &: Graph): bool
True when there is a cycle.

The example for this item is shown with the ones above: graph-Search.salam