graph
Graph theory: traversal, shortest paths, spanning trees, flow, coloring, communities and centrality.
import graph
This package has more than two hundred graph algorithms. Make a graph with NewUndirected or NewDirected, add edges with add_edge and add_weighted, or read the whole thing from text in one go with FromEdgeList. Nodes are numbered from zero to n minus one; adding an edge to a higher number grows the graph.
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.
Use it whenever the data is "things and the links between them": roads, dependencies, networks, social ties, state machines. For linear algebra on grids of numbers use matrix; this package has its own small Matrix type for AdjacencyMatrix and the spectral functions.
Things to know
- A distance that cannot be reached is
GRAPH_INF(1e300), not an error. Test for it before you print or add distances. Dijkstrareturns false and leaves every distance atGRAPH_INFwhen any weight is negative.ShortestPathandShortestPathLengthswitch to Bellman-Ford by themselves.- Functions that return edges give edge numbers in the order the edges were added;
edge_from,edge_toandedge_weightread them back. - The graph prepares its adjacency lists on first use and again after you add edges.
builddoes that work up front, which only matters for timing.
Shortest route on a road map
Give each city a node number and a name with set_name, add the roads with their length using add_weighted, and call build to prepare the lookup tables (the first algorithm would do it anyway). ShortestPath returns the list of nodes on the shortest weighted route and ShortestPathLength its length. HopPath ignores the weights and finds the route with the fewest stops, which is not the same thing. DijkstraDist gives the distance from one city to all the others in one call.
import graph
func route_text(g &: graph.Graph, path: Vector<int>): str:
mut text := ""
each i, node in path:
if i > 0: text += " -> " end
text += g.name(node)
end
ret text
end
func main:
mut roads := graph.NewUndirected(6)
defer roads.Free()
each i, city in ["Tehran", "Qom", "Kashan", "Isfahan", "Arak", "Yazd"]:
roads.set_name(i, city)
end
roads.add_weighted(0, 1, 140.0)
roads.add_weighted(1, 2, 105.0)
roads.add_weighted(2, 3, 210.0)
roads.add_weighted(1, 4, 135.0)
roads.add_weighted(4, 3, 280.0)
roads.add_weighted(3, 5, 320.0)
roads.add_weighted(2, 5, 560.0)
roads.build()
trip := graph.ShortestPath(roads, 0, 5)
println route_text(roads, trip), "|", graph.ShortestPathLength(roads, 0, 5), "km"
hops := graph.HopPath(roads, 0, 5)
println "fewest stops:", route_text(roads, hops)
dist := graph.DijkstraDist(roads, 0)
each i, d in dist:
println " Tehran to", roads.name(i), d, "km"
end
endThe weights must not be negative for Dijkstra; it returns false if one is. When some are, for example costs that can be refunds, ShortestPath switches to Bellman-Ford on its own, and BellmanFord called directly also reports a negative cycle.
Task order and the critical path
A plan where some tasks must wait for others is a directed graph without cycles. TopologicalSort gives an order that respects every dependency and returns false when there is a cycle, that is, when the plan is impossible. TopologicalLayers groups tasks into stages that can run in parallel. With the duration of each task as the weight of its outgoing edges, CriticalPath gives the chain of tasks that decides how long the whole project takes: a delay on any of them delays the release.
import graph
func main:
tasks := ["design", "database", "backend", "frontend", "tests", "release"]
days := [3.0, 2.0, 5.0, 4.0, 2.0, 1.0]
mut plan := graph.NewDirected(6)
defer plan.Free()
each i, name in tasks:
plan.set_name(i, name)
end
each pair in ["0 1", "0 3", "1 2", "2 4", "3 4", "4 5"]:
parts := pair.Split(" ")
from := parts.Get(0).ToInt()
plan.add_weighted(from, parts.Get(1).ToInt(), days[from])
end
plan.build()
mut order := Vector {} as Vector<int>
defer order.Free()
if graph.TopologicalSort(plan, order) == false:
println "the plan has a cycle"
ret 1
end
mut line := "order:"
each t in order:
line = line + " " + plan.name(t)
end
println line
mut layer := Vector {} as Vector<int>
defer layer.Free()
stages := graph.TopologicalLayers(plan, layer)
println "stages:", stages
each i, name in tasks:
println " stage", layer.Get(i), name
end
critical := graph.CriticalPath(plan)
mut path := "critical path:"
each t in critical:
path = path + " " + plan.name(t)
end
println path
endWeak points of a network
For a computer network, a road system or a group of friends, the first questions are whether everything is connected and what breaks it. ComponentCount and ComponentSizes describe the separate parts and Components says which part each node belongs to. ArticulationPoints lists the nodes and Bridges the edges whose failure splits a part in two. FromEdgeList reads the edges from text, one pair per line.
import graph
func main:
mut net := graph.FromEdgeList("0 1\n1 2\n2 0\n2 3\n3 4\n4 5\n5 3\n6 7", 8, false)
defer net.Free()
println net.order(), "machines,", net.Size(), "links"
println "connected:", graph.IsConnected(net), "parts:", graph.ComponentCount(net)
sizes := graph.ComponentSizes(net)
println "part sizes:", sizes
mut comp := Vector {} as Vector<int>
defer comp.Free()
_ := graph.Components(net, comp)
println "machine 7 is in part", comp.Get(7), "with machine 6:", comp.Get(6) == comp.Get(7)
cut := graph.ArticulationPoints(net)
println "machines that split the network if they fail:", cut
bridges := graph.Bridges(net)
each e in bridges:
println "single link:", net.edge_from(e), "-", net.edge_to(e)
end
endBridges returns edge numbers, in the order the edges were added; edge_from and edge_to turn them back into nodes.
Connect every site at the lowest cost
To link all offices with the least cable, choose a minimum spanning tree: a set of edges that connects every node with the smallest total weight. Kruskal fills in the chosen edge numbers and returns the total; MinimumSpanningTree returns the tree as a new graph. ToMermaid and ToDot turn any graph into text that Mermaid or Graphviz can draw.
import graph
func main:
offices := ["HQ", "North", "South", "East", "West"]
mut sites := graph.NewUndirected(5)
defer sites.Free()
each i, name in offices:
sites.set_name(i, name)
end
sites.add_weighted(0, 1, 4.0)
sites.add_weighted(0, 2, 3.0)
sites.add_weighted(0, 3, 6.0)
sites.add_weighted(0, 4, 5.0)
sites.add_weighted(1, 3, 2.0)
sites.add_weighted(2, 4, 2.5)
sites.add_weighted(3, 4, 7.0)
sites.build()
mut chosen := Vector {} as Vector<int>
defer chosen.Free()
total := graph.Kruskal(sites, chosen)
println "lay", chosen.Len(), "cables,", total, "km in all:"
each e in chosen:
println " " + sites.name(sites.edge_from(e)), "-", sites.name(sites.edge_to(e)), sites.edge_weight(e), "km"
end
println "every candidate together:", graph.TotalWeight(sites), "km"
mut tree := graph.MinimumSpanningTree(sites)
defer tree.Free()
print graph.ToMermaid(tree)
end| Question | Use |
|---|---|
| Shortest weighted route | ShortestPath, Dijkstra, AStar |
| Fewest hops | HopPath, BFS |
| Order of dependent tasks | TopologicalSort, TopologicalLayers, CriticalPath |
| Is it connected, and where is it weak | Components, ArticulationPoints, Bridges |
| Cheapest way to connect everything | Kruskal, Prim, MinimumSpanningTree |
| Most important nodes | PageRank, BetweennessCentrality |
| Groups of closely linked nodes | Louvain, LabelPropagation |
Types
TreeIndex
struct TreeIndex| Name | Type | Description |
|---|---|---|
n | int = 0 | |
depth | Vector | |
log | int = 0 | |
up | Vector | |
tin | Vector | |
tout | Vector |
Ancestor
func Ancestor(k: int, v: int): intancestor
func ancestor(k: int, v: int): intFree
func Free()free
func free()MinHeap
struct MinHeap| Name | Type | Description |
|---|---|---|
key | Vector | The keys. |
val | Vector | The values. |
import graph
func list(text: str): Vector<int>:
mut out := Vector {} as Vector<int>
each num in text.Split(" "):
out.Push(num.ToInt())
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.IsEmpty()
heap.Clear()
println heap.IsEmpty()
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)
endPush
func Push(k: f64, v: int)push
func push(k: f64, v: int)The example for this item is shown with the ones above: graph-Analysis.salam
Size
func Size(): intsize
func size(): intThe example for this item is shown with the ones above: graph-Analysis.salam
IsEmpty
func IsEmpty(): boolis_empty
func is_empty(): boolThe example for this item is shown with the ones above: graph-Analysis.salam
TopKey
func TopKey(): f64top_key
func top_key(): f64The example for this item is shown with the ones above: graph-Analysis.salam
TopValue
func TopValue(): inttop_value
func top_value(): intThe example for this item is shown with the ones above: graph-Analysis.salam
Pop
func Pop(): intpop
func pop(): intThe example for this item is shown with the ones above: graph-Analysis.salam
Clear
func Clear()clear
func clear()The example for this item is shown with the ones above: graph-Analysis.salam
Free
func Free()free
func free()The example for this item is shown with the ones above: graph-Analysis.salam
DisjointSet
struct DisjointSet| Name | Type | Description |
|---|---|---|
parent | Vector | The parents. |
sz | Vector | The sizes. |
groups | int = 0 | The number of sets. |
The example for this item is shown with the ones above: graph-Analysis.salam
Reset
func Reset(n: int)reset
func reset(n: int)The example for this item is shown with the ones above: graph-Analysis.salam
Find
func Find(x: int): intfind
func find(x: int): intThe example for this item is shown with the ones above: graph-Analysis.salam
Union
func Union(a: int, b: int): boolunion
func union(a: int, b: int): boolThe example for this item is shown with the ones above: graph-Analysis.salam
Connected
func Connected(a: int, b: int): boolconnected
func connected(a: int, b: int): boolThe example for this item is shown with the ones above: graph-Analysis.salam
SetSize
func SetSize(a: int): intset_size
func set_size(a: int): intThe example for this item is shown with the ones above: graph-Analysis.salam
Count
func Count(): intcount
func count(): intThe example for this item is shown with the ones above: graph-Analysis.salam
Free
func Free()free
func free()The example for this item is shown with the ones above: graph-Analysis.salam
Matrix
struct Matrix| Name | Type | Description |
|---|---|---|
rows | int = 0 | The rows. |
cols | int = 0 | The columns. |
a | Vector | The entries. |
import graph
func list(text: str): Vector<int>:
mut out := Vector {} as Vector<int>
each num in text.Split(" "):
out.Push(num.ToInt())
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()
endAt
func At(i: int, j: int): f64at
func at(i: int, j: int): f64The example for this item is shown with the ones above: graph-Build.salam
Set
func Set(i: int, j: int, v: f64)set
func set(i: int, j: int, v: f64)The example for this item is shown with the ones above: graph-Build.salam
AddAt
func AddAt(i: int, j: int, v: f64)add_at
func add_at(i: int, j: int, v: f64)The example for this item is shown with the ones above: graph-Build.salam
Trace
func Trace(): f64trace
func trace(): f64The example for this item is shown with the ones above: graph-Build.salam
RowSum
func RowSum(i: int): f64row_sum
func row_sum(i: int): f64The example for this item is shown with the ones above: graph-Build.salam
Free
func Free()free
func free()The example for this item is shown with the ones above: graph-Build.salam
IntMatrix
struct IntMatrix| Name | Type | Description |
|---|---|---|
rows | int = 0 | The rows. |
cols | int = 0 | The columns. |
a | Vector | The entries. |
import graph
func list(text: str): Vector<int>:
mut out := Vector {} as Vector<int>
each num in text.Split(" "):
out.Push(num.ToInt())
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))
endAt
func At(i: int, j: int): intat
func at(i: int, j: int): intThe example for this item is shown with the ones above: graph-Paths.salam
Set
func Set(i: int, j: int, v: int)set
func set(i: int, j: int, v: int)The example for this item is shown with the ones above: graph-Paths.salam
Free
func Free()free
func free()The example for this item is shown with the ones above: graph-Paths.salam
FlowNet
struct FlowNet| Name | Type | Description |
|---|---|---|
n | int = 0 | The number of nodes. |
head | Vector | Where each node's arcs start. |
to | Vector | The target of each arc. |
cap | Vector | The remaining capacity. |
cost | Vector | The cost. |
orig | Vector | The original capacity. |
nxt | Vector | The next arc. |
import graph
func list(text: str): Vector<int>:
mut out := Vector {} as Vector<int>
each num in text.Split(" "):
out.Push(num.ToInt())
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)
endArcCount
func ArcCount(): intarc_count
func arc_count(): intThe example for this item is shown with the ones above: graph-Flow.salam
AddArc
func AddArc(u: int, v: int, c: f64): intadd_arc
func add_arc(u: int, v: int, c: f64): intThe example for this item is shown with the ones above: graph-Flow.salam
AddCostArc
func AddCostArc(u: int, v: int, c: f64, k: f64): intadd_cost_arc
func add_cost_arc(u: int, v: int, c: f64, k: f64): intThe example for this item is shown with the ones above: graph-Flow.salam
AddEdge
func AddEdge(u: int, v: int, c: f64): intadd_edge
func add_edge(u: int, v: int, c: f64): intThe example for this item is shown with the ones above: graph-Flow.salam
FlowOn
func FlowOn(e: int): f64flow_on
func flow_on(e: int): f64The example for this item is shown with the ones above: graph-Flow.salam
Reset
func Reset()reset
func reset()The example for this item is shown with the ones above: graph-Flow.salam
Free
func Free()free
func free()The example for this item is shown with the ones above: graph-Flow.salam
Graph
struct Graph| Name | Type | Description |
|---|---|---|
directed | bool = false | Whether the graph is directed. |
n | int = 0 | The number of nodes. |
eu | Vector | The start node of each edge. |
ev | Vector | The end node of each edge. |
ew | Vector | The edge weights. |
names | Vector | The node names. |
off | Vector | Where each node's adjacency list starts. |
nbr | Vector | The adjacent nodes. |
eix | Vector | The adjacent edges. |
roff | Vector | Where each node's incoming list starts. |
rnbr | Vector | The incoming nodes. |
reix | Vector | The incoming edges. |
built | bool = false | Whether the adjacency lists have been built. |
The example for this item is shown with the ones above: graph-Build.salam
AddNode
func AddNode(): intadd_node
func add_node(): intThe example for this item is shown with the ones above: graph-Build.salam
AddNodes
func AddNodes(k: int)add_nodes
func add_nodes(k: int)The example for this item is shown with the ones above: graph-Build.salam
AddEdge
func AddEdge(u: int, v: int): intadd_edge
func add_edge(u: int, v: int): intThe example for this item is shown with the ones above: graph-Build.salam
AddWeighted
func AddWeighted(u: int, v: int, w: f64): intadd_weighted
func add_weighted(u: int, v: int, w: f64): intThe example for this item is shown with the ones above: graph-Build.salam
Order
func Order(): intorder
func order(): intThe example for this item is shown with the ones above: graph-Build.salam
Size
func Size(): intsize
func size(): intThe example for this item is shown with the ones above: graph-Build.salam
EdgeFrom
func EdgeFrom(e: int): intedge_from
func edge_from(e: int): intThe example for this item is shown with the ones above: graph-Build.salam
EdgeTo
func EdgeTo(e: int): intedge_to
func edge_to(e: int): intThe example for this item is shown with the ones above: graph-Build.salam
EdgeWeight
func EdgeWeight(e: int): f64edge_weight
func edge_weight(e: int): f64The example for this item is shown with the ones above: graph-Build.salam
SetWeight
func SetWeight(e: int, w: f64)set_weight
func set_weight(e: int, w: f64)The example for this item is shown with the ones above: graph-Build.salam
SetName
func SetName(u: int, s: str)set_name
func set_name(u: int, s: str)The example for this item is shown with the ones above: graph-Build.salam
Name
func Name(u: int): strname
func name(u: int): strThe example for this item is shown with the ones above: graph-Build.salam
Build
func Build()build
func build()The example for this item is shown with the ones above: graph-Build.salam
AdjStart
func AdjStart(u: int): intadj_start
func adj_start(u: int): intThe example for this item is shown with the ones above: graph-Build.salam
AdjStop
func AdjStop(u: int): intadj_stop
func adj_stop(u: int): intThe example for this item is shown with the ones above: graph-Build.salam
AdjNode
func AdjNode(k: int): intadj_node
func adj_node(k: int): intThe example for this item is shown with the ones above: graph-Build.salam
AdjEdge
func AdjEdge(k: int): intadj_edge
func adj_edge(k: int): intThe example for this item is shown with the ones above: graph-Build.salam
AdjWeight
func AdjWeight(k: int): f64adj_weight
func adj_weight(k: int): f64The example for this item is shown with the ones above: graph-Build.salam
InStart
func InStart(u: int): intin_start
func in_start(u: int): intThe example for this item is shown with the ones above: graph-Build.salam
InStop
func InStop(u: int): intin_stop
func in_stop(u: int): intThe example for this item is shown with the ones above: graph-Build.salam
InNode
func InNode(k: int): intin_node
func in_node(k: int): intThe example for this item is shown with the ones above: graph-Build.salam
InEdge
func InEdge(k: int): intin_edge
func in_edge(k: int): intThe example for this item is shown with the ones above: graph-Build.salam
OutDegree
func OutDegree(u: int): intout_degree
func out_degree(u: int): intThe example for this item is shown with the ones above: graph-Build.salam
InDegree
func InDegree(u: int): intin_degree
func in_degree(u: int): intThe example for this item is shown with the ones above: graph-Build.salam
Degree
func Degree(u: int): intdegree
func degree(u: int): intThe example for this item is shown with the ones above: graph-Build.salam
HasEdge
func HasEdge(u: int, v: int): boolhas_edge
func has_edge(u: int, v: int): boolThe example for this item is shown with the ones above: graph-Build.salam
FindEdge
func FindEdge(u: int, v: int): intfind_edge
func find_edge(u: int, v: int): intThe example for this item is shown with the ones above: graph-Build.salam
WeightBetween
func WeightBetween(u: int, v: int): f64weight_between
func weight_between(u: int, v: int): f64The example for this item is shown with the ones above: graph-Build.salam
Neighbors
func Neighbors(u: int): Vector<int>neighbors
func neighbors(u: int): Vector<int>The example for this item is shown with the ones above: graph-Build.salam
Free
func Free()free
func free()The example for this item is shown with the ones above: graph-Build.salam
Constants and variables
GRAPH_INF
const GRAPH_INF: f64 = 1e+300The example for this item is shown with the ones above: graph-Build.salam
GRAPH_NONE
const GRAPH_NONE: i32 = -1The example for this item is shown with the ones above: graph-Build.salam
Functions
HasEulerianCircuit
func HasEulerianCircuit(g &: Graph): boolThe example for this item is shown with the ones above: graph-Paths.salam
HasEulerianPath
func HasEulerianPath(g &: Graph): boolThe example for this item is shown with the ones above: graph-Paths.salam
EulerianCircuit
func EulerianCircuit(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Paths.salam
EulerianPath
func EulerianPath(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Paths.salam
HamiltonianPath
func HamiltonianPath(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Paths.salam
HamiltonianCycle
func HamiltonianCycle(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Paths.salam
HasHamiltonianCycle
func HasHamiltonianCycle(g &: Graph): boolThe example for this item is shown with the ones above: graph-Paths.salam
TourLength
func TourLength(g &: Graph, tour: Vector<int>): f64The example for this item is shown with the ones above: graph-Paths.salam
TSPNearestNeighbor
func TSPNearestNeighbor(g &: Graph, start: int): Vector<int>The example for this item is shown with the ones above: graph-Paths.salam
TSPTwoOpt
func TSPTwoOpt(g &: Graph, tour &: Vector<int>): f64The example for this item is shown with the ones above: graph-Paths.salam
TSPHeuristic
func TSPHeuristic(g &: Graph, start: int): Vector<int>The example for this item is shown with the ones above: graph-Paths.salam
Dijkstra
func Dijkstra(g &: Graph, src: int, dist &: Vector<f64>, parent &: Vector<int>): boolGRAPH_INF, when any weight is negative.The example for this item is shown with the ones above: graph-Paths.salam
DijkstraDist
func DijkstraDist(g &: Graph, src: int): Vector<f64>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 example for this item is shown with the ones above: graph-Paths.salam
ShortestPathLength
func ShortestPathLength(g &: Graph, s: int, t: int): f64GRAPH_INF when there is no route. Uses Bellman-Ford when a weight is negative.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>): boolThe example for this item is shown with the ones above: graph-Paths.salam
FindNegativeCycle
func FindNegativeCycle(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Paths.salam
HasNegativeCycle
func HasNegativeCycle(g &: Graph): boolThe 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>): boolThe example for this item is shown with the ones above: graph-Paths.salam
GreedyColoring
func GreedyColoring(g &: Graph, order: Vector<int>): Vector<int>The example for this item is shown with the ones above: graph-Flow.salam
GreedyColoringNatural
func GreedyColoringNatural(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Flow.salam
WelshPowell
func WelshPowell(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Flow.salam
DSatur
func DSatur(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Flow.salam
ColorCount
func ColorCount(color: Vector<int>): intThe example for this item is shown with the ones above: graph-Flow.salam
IsProperColoring
func IsProperColoring(g &: Graph, color: Vector<int>): boolThe example for this item is shown with the ones above: graph-Flow.salam
ChromaticNumber
func ChromaticNumber(g &: Graph): intThe example for this item is shown with the ones above: graph-Flow.salam
EdgeColoringGreedy
func EdgeColoringGreedy(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Flow.salam
KCore
func KCore(g &: Graph, k: int, alive &: Vector<bool>): intThe example for this item is shown with the ones above: graph-Flow.salam
CoreNumbers
func CoreNumbers(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Flow.salam
Degeneracy
func Degeneracy(g &: Graph): intThe example for this item is shown with the ones above: graph-Flow.salam
Modularity
func Modularity(g &: Graph, comm: Vector<int>): f64The example for this item is shown with the ones above: graph-Flow.salam
LabelPropagation
func LabelPropagation(g &: Graph, comm &: Vector<int>): intThe example for this item is shown with the ones above: graph-Flow.salam
Louvain
func Louvain(g &: Graph, comm &: Vector<int>): intThe example for this item is shown with the ones above: graph-Flow.salam
GirvanNewman
func GirvanNewman(g &: Graph, want: int, comm &: Vector<int>): intThe example for this item is shown with the ones above: graph-Flow.salam
Density
func Density(g &: Graph): f64The example for this item is shown with the ones above: graph-Analysis.salam
AverageDegree
func AverageDegree(g &: Graph): f64The example for this item is shown with the ones above: graph-Analysis.salam
MaxDegree
func MaxDegree(g &: Graph): intThe example for this item is shown with the ones above: graph-Analysis.salam
MinDegree
func MinDegree(g &: Graph): intThe example for this item is shown with the ones above: graph-Analysis.salam
DegreeSequence
func DegreeSequence(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Analysis.salam
DegreeHistogram
func DegreeHistogram(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Analysis.salam
IsRegular
func IsRegular(g &: Graph): boolThe example for this item is shown with the ones above: graph-Analysis.salam
IsComplete
func IsComplete(g &: Graph): boolThe example for this item is shown with the ones above: graph-Analysis.salam
Eccentricity
func Eccentricity(g &: Graph, u: int): intThe example for this item is shown with the ones above: graph-Analysis.salam
EccentricityAll
func EccentricityAll(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Analysis.salam
Diameter
func Diameter(g &: Graph): intThe example for this item is shown with the ones above: graph-Analysis.salam
Radius
func Radius(g &: Graph): intThe example for this item is shown with the ones above: graph-Analysis.salam
Center
func Center(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Analysis.salam
Periphery
func Periphery(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Analysis.salam
AveragePathLength
func AveragePathLength(g &: Graph): f64The example for this item is shown with the ones above: graph-Analysis.salam
WienerIndex
func WienerIndex(g &: Graph): f64The example for this item is shown with the ones above: graph-Analysis.salam
Girth
func Girth(g &: Graph): intThe example for this item is shown with the ones above: graph-Analysis.salam
StronglyConnected
func StronglyConnected(g &: Graph, comp &: Vector<int>): intimport 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()
endSCCCount
func SCCCount(g &: Graph): intThe example for this item is shown with the ones above: graph-Search.salam
IsStronglyConnected
func IsStronglyConnected(g &: Graph): boolThe example for this item is shown with the ones above: graph-Search.salam
Kosaraju
func Kosaraju(g &: Graph, comp &: Vector<int>): intThe example for this item is shown with the ones above: graph-Search.salam
Condensation
func Condensation(g &: Graph, comp &: Vector<int>): GraphThe example for this item is shown with the ones above: graph-Search.salam
Bridges
func Bridges(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Search.salam
ArticulationPoints
func ArticulationPoints(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Search.salam
BiconnectedComponents
func BiconnectedComponents(g &: Graph, ecomp &: Vector<int>): intThe example for this item is shown with the ones above: graph-Search.salam
IsBiconnected
func IsBiconnected(g &: Graph): boolThe example for this item is shown with the ones above: graph-Search.salam
IsTwoEdgeConnected
func IsTwoEdgeConnected(g &: Graph): boolThe example for this item is shown with the ones above: graph-Search.salam
TwoEdgeComponents
func TwoEdgeComponents(g &: Graph, comp &: Vector<int>): intThe example for this item is shown with the ones above: graph-Search.salam
LocalClustering
func LocalClustering(g &: Graph, u: int): f64The example for this item is shown with the ones above: graph-Analysis.salam
AverageClustering
func AverageClustering(g &: Graph): f64The example for this item is shown with the ones above: graph-Analysis.salam
Transitivity
func Transitivity(g &: Graph): f64The example for this item is shown with the ones above: graph-Analysis.salam
TriangleCount
func TriangleCount(g &: Graph): intThe example for this item is shown with the ones above: graph-Analysis.salam
Assortativity
func Assortativity(g &: Graph): f64The example for this item is shown with the ones above: graph-Analysis.salam
CircuitRank
func CircuitRank(g &: Graph): intThe example for this item is shown with the ones above: graph-Analysis.salam
WeightedDiameter
func WeightedDiameter(g &: Graph): f64The example for this item is shown with the ones above: graph-Analysis.salam
FloydWarshall
func FloydWarshall(g &: Graph): MatrixThe example for this item is shown with the ones above: graph-Paths.salam
FloydWarshallPaths
func FloydWarshallPaths(g &: Graph, next &: IntMatrix): MatrixThe example for this item is shown with the ones above: graph-Paths.salam
FloydPath
func FloydPath(next &: IntMatrix, s: int, t: int): Vector<int>The example for this item is shown with the ones above: graph-Paths.salam
Johnson
func Johnson(g &: Graph): MatrixThe 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>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 example for this item is shown with the ones above: graph-Paths.salam
AllPairsHops
func AllPairsHops(g &: Graph): IntMatrixThe example for this item is shown with the ones above: graph-Search.salam
Components
func Components(g &: Graph, comp &: Vector<int>): intThe example for this item is shown with the ones above: graph-Search.salam
ComponentCount
func ComponentCount(g &: Graph): intThe example for this item is shown with the ones above: graph-Search.salam
ComponentSizes
func ComponentSizes(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Search.salam
IsConnected
func IsConnected(g &: Graph): boolThe example for this item is shown with the ones above: graph-Search.salam
IsBipartite
func IsBipartite(g &: Graph, color &: Vector<int>): boolThe example for this item is shown with the ones above: graph-Search.salam
Bipartite
func Bipartite(g &: Graph): boolThe example for this item is shown with the ones above: graph-Search.salam
TopologicalSort
func TopologicalSort(g &: Graph, order &: Vector<int>): boolThe example for this item is shown with the ones above: graph-Search.salam
TopologicalSortLex
func TopologicalSortLex(g &: Graph, order &: Vector<int>): boolThe example for this item is shown with the ones above: graph-Search.salam
IsDAG
func IsDAG(g &: Graph): boolThe example for this item is shown with the ones above: graph-Search.salam
FindCycle
func FindCycle(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Search.salam
HasCycle
func HasCycle(g &: Graph): boolThe example for this item is shown with the ones above: graph-Search.salam
BFSFrom
func BFSFrom(g &: Graph, src: int, dist &: Vector<int>, parent &: Vector<int>)The example for this item is shown with the ones above: graph-Search.salam
BFS
func BFS(g &: Graph, src: int): Vector<int>The example for this item is shown with the ones above: graph-Search.salam
BFSOrder
func BFSOrder(g &: Graph, src: int): Vector<int>The example for this item is shown with the ones above: graph-Search.salam
DFSOrder
func DFSOrder(g &: Graph, src: int): Vector<int>The example for this item is shown with the ones above: graph-Search.salam
DFSPostOrder
func DFSPostOrder(g &: Graph, src: int): Vector<int>The example for this item is shown with the ones above: graph-Search.salam
DFSForest
func DFSForest(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Search.salam
Reachable
func Reachable(g &: Graph, src: int): Vector<bool>The example for this item is shown with the ones above: graph-Search.salam
ReachableCount
func ReachableCount(g &: Graph, src: int): intThe example for this item is shown with the ones above: graph-Search.salam
HopDistance
func HopDistance(g &: Graph, s: int, t: int): intThe 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>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 example for this item is shown with the ones above: graph-Search.salam
CountColorings
func CountColorings(g &: Graph, k: int): f64The example for this item is shown with the ones above: graph-Flow.salam
Kruskal
func Kruskal(g &: Graph, chosen &: Vector<int>): f64import 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)
endMaximumSpanningTree
func MaximumSpanningTree(g &: Graph, chosen &: Vector<int>): f64The example for this item is shown with the ones above: graph-Trees.salam
Prim
func Prim(g &: Graph, root: int, parent &: Vector<int>): f64The example for this item is shown with the ones above: graph-Trees.salam
Boruvka
func Boruvka(g &: Graph, chosen &: Vector<int>): f64The example for this item is shown with the ones above: graph-Trees.salam
MSTWeight
func MSTWeight(g &: Graph): f64The example for this item is shown with the ones above: graph-Trees.salam
MinimumSpanningTree
func MinimumSpanningTree(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Trees.salam
SpanningAgreement
func SpanningAgreement(g &: Graph): boolThe example for this item is shown with the ones above: graph-Trees.salam
NewFlowNet
func NewFlowNet(n: int): FlowNetThe example for this item is shown with the ones above: graph-Flow.salam
FlowFromGraph
func FlowFromGraph(g &: Graph): FlowNetThe example for this item is shown with the ones above: graph-Flow.salam
MaxFlow
func MaxFlow(f &: FlowNet, s: int, t: int): f64The example for this item is shown with the ones above: graph-Flow.salam
MaxFlowEdmondsKarp
func MaxFlowEdmondsKarp(f &: FlowNet, s: int, t: int): f64The 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>): f64The example for this item is shown with the ones above: graph-Flow.salam
MaxFlowValue
func MaxFlowValue(g &: Graph, s: int, t: int): f64The 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>): f64The 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): f64The example for this item is shown with the ones above: graph-Flow.salam
Determinant
func Determinant(x &: Matrix): f64The example for this item is shown with the ones above: graph-Analysis.salam
SpanningTreeCount
func SpanningTreeCount(g &: Graph): f64The example for this item is shown with the ones above: graph-Trees.salam
SymmetricEigenvalues
func SymmetricEigenvalues(x &: Matrix): Vector<f64>The example for this item is shown with the ones above: graph-Analysis.salam
AdjacencySpectrum
func AdjacencySpectrum(g &: Graph): Vector<f64>The example for this item is shown with the ones above: graph-Analysis.salam
LaplacianSpectrum
func LaplacianSpectrum(g &: Graph): Vector<f64>The example for this item is shown with the ones above: graph-Analysis.salam
SpectralRadius
func SpectralRadius(g &: Graph): f64The example for this item is shown with the ones above: graph-Analysis.salam
AlgebraicConnectivity
func AlgebraicConnectivity(g &: Graph): f64The example for this item is shown with the ones above: graph-Analysis.salam
EmptyGraph
func EmptyGraph(n: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
CompleteGraph
func CompleteGraph(n: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
CompleteBipartite
func CompleteBipartite(a: int, b: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
PathGraph
func PathGraph(n: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
CycleGraph
func CycleGraph(n: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
StarGraph
func StarGraph(n: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
WheelGraph
func WheelGraph(n: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
GridGraph
func GridGraph(rows: int, cols: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
HypercubeGraph
func HypercubeGraph(d: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
PetersenGraph
func PetersenGraph(): GraphThe example for this item is shown with the ones above: graph-Build.salam
CirculantGraph
func CirculantGraph(n: int, offsets: Vector<int>): GraphThe example for this item is shown with the ones above: graph-Build.salam
BalancedTree
func BalancedTree(branch: int, depth: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
ErdosRenyi
func ErdosRenyi(n: int, p: f64): GraphThe example for this item is shown with the ones above: graph-Build.salam
RandomGraph
func RandomGraph(n: int, m: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
RandomTree
func RandomTree(n: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
BarabasiAlbert
func BarabasiAlbert(n: int, m: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
WattsStrogatz
func WattsStrogatz(n: int, k: int, p: f64): GraphThe example for this item is shown with the ones above: graph-Build.salam
NewDisjointSet
func NewDisjointSet(n: int): DisjointSetThe example for this item is shown with the ones above: graph-Analysis.salam
FillInt
func FillInt(v &: Vector<int>, n: int, x: int)The example for this item is shown with the ones above: graph-Analysis.salam
FillFloat
func FillFloat(v &: Vector<f64>, n: int, x: f64)The example for this item is shown with the ones above: graph-Paths.salam
FillBool
func FillBool(v &: Vector<bool>, n: int, x: bool)The example for this item is shown with the ones above: graph-Build.salam
Iota
func Iota(v &: Vector<int>, n: int)The example for this item is shown with the ones above: graph-Analysis.salam
MaxInt
func MaxInt(v: Vector<int>): intThe example for this item is shown with the ones above: graph-Analysis.salam
SumInt
func SumInt(v: Vector<int>): intThe example for this item is shown with the ones above: graph-Analysis.salam
SumFloat
func SumFloat(v: Vector<f64>): f64The example for this item is shown with the ones above: graph-Analysis.salam
ReverseInt
func ReverseInt(v &: Vector<int>)The example for this item is shown with the ones above: graph-Analysis.salam
Isomorphic
func Isomorphic(a &: Graph, b &: Graph): boolThe example for this item is shown with the ones above: graph-Analysis.salam
IsomorphismMap
func IsomorphismMap(a &: Graph, b &: Graph, map &: Vector<int>): boolThe example for this item is shown with the ones above: graph-Analysis.salam
AutomorphismCount
func AutomorphismCount(g &: Graph): intThe example for this item is shown with the ones above: graph-Analysis.salam
IsGraphical
func IsGraphical(seq: Vector<int>): boolThe example for this item is shown with the ones above: graph-Analysis.salam
HavelHakimi
func HavelHakimi(seq: Vector<int>): GraphThe example for this item is shown with the ones above: graph-Analysis.salam
SameDegreeSequence
func SameDegreeSequence(a &: Graph, b &: Graph): boolThe example for this item is shown with the ones above: graph-Analysis.salam
NewMatrix
func NewMatrix(rows: int, cols: int): MatrixThe example for this item is shown with the ones above: graph-Analysis.salam
NewIntMatrix
func NewIntMatrix(rows: int, cols: int, fill: int): IntMatrixThe example for this item is shown with the ones above: graph-Paths.salam
AdjacencyMatrix
func AdjacencyMatrix(g &: Graph): MatrixThe example for this item is shown with the ones above: graph-Analysis.salam
WeightMatrix
func WeightMatrix(g &: Graph): MatrixThe example for this item is shown with the ones above: graph-Analysis.salam
DegreeMatrix
func DegreeMatrix(g &: Graph): MatrixThe example for this item is shown with the ones above: graph-Analysis.salam
LaplacianMatrix
func LaplacianMatrix(g &: Graph): MatrixThe example for this item is shown with the ones above: graph-Analysis.salam
NormalizedLaplacian
func NormalizedLaplacian(g &: Graph): MatrixThe example for this item is shown with the ones above: graph-Analysis.salam
IncidenceMatrix
func IncidenceMatrix(g &: Graph): MatrixThe example for this item is shown with the ones above: graph-Analysis.salam
MatrixMultiply
func MatrixMultiply(x &: Matrix, y &: Matrix): MatrixThe example for this item is shown with the ones above: graph-Analysis.salam
MatrixIdentity
func MatrixIdentity(n: int): MatrixThe example for this item is shown with the ones above: graph-Analysis.salam
MatrixPower
func MatrixPower(x &: Matrix, k: int): MatrixThe example for this item is shown with the ones above: graph-Analysis.salam
WalkCount
func WalkCount(g &: Graph, k: int, u: int, v: int): f64The example for this item is shown with the ones above: graph-Paths.salam
GlobalMinCut
func GlobalMinCut(g &: Graph): f64The example for this item is shown with the ones above: graph-Flow.salam
EdgeConnectivity
func EdgeConnectivity(g &: Graph): intThe example for this item is shown with the ones above: graph-Flow.salam
VertexConnectivity
func VertexConnectivity(g &: Graph): intThe example for this item is shown with the ones above: graph-Flow.salam
BipartiteMatching
func BipartiteMatching(g &: Graph, mate &: Vector<int>): intThe example for this item is shown with the ones above: graph-Flow.salam
MaximalMatching
func MaximalMatching(g &: Graph, mate &: Vector<int>): intThe example for this item is shown with the ones above: graph-Flow.salam
MinimumVertexCover
func MinimumVertexCover(g &: Graph, cover &: Vector<bool>): intThe example for this item is shown with the ones above: graph-Flow.salam
MaximumIndependentSetBipartite
func MaximumIndependentSetBipartite(g &: Graph, pick &: Vector<bool>): intThe example for this item is shown with the ones above: graph-Flow.salam
ToEdgeList
func ToEdgeList(g &: Graph): strThe example for this item is shown with the ones above: graph-Build.salam
FromEdgeList
func FromEdgeList(text: str, n: int, directed: bool): GraphThe example for this item is shown with the ones above: graph-Build.salam
ToAdjacencyList
func ToAdjacencyList(g &: Graph): strThe example for this item is shown with the ones above: graph-Build.salam
ToMatrixText
func ToMatrixText(g &: Graph): strThe example for this item is shown with the ones above: graph-Build.salam
ToDot
func ToDot(g &: Graph): strThe example for this item is shown with the ones above: graph-Build.salam
ToMermaid
func ToMermaid(g &: Graph): strThe example for this item is shown with the ones above: graph-Build.salam
ToJSON
func ToJSON(g &: Graph): strThe example for this item is shown with the ones above: graph-Build.salam
Describe
func Describe(g &: Graph): strThe example for this item is shown with the ones above: graph-Build.salam
DegreeCentrality
func DegreeCentrality(g &: Graph): Vector<f64>The example for this item is shown with the ones above: graph-Analysis.salam
InDegreeCentrality
func InDegreeCentrality(g &: Graph): Vector<f64>The example for this item is shown with the ones above: graph-Analysis.salam
OutDegreeCentrality
func OutDegreeCentrality(g &: Graph): Vector<f64>The example for this item is shown with the ones above: graph-Analysis.salam
ClosenessCentrality
func ClosenessCentrality(g &: Graph): Vector<f64>The example for this item is shown with the ones above: graph-Analysis.salam
HarmonicCentrality
func HarmonicCentrality(g &: Graph): Vector<f64>The example for this item is shown with the ones above: graph-Analysis.salam
BetweennessCentrality
func BetweennessCentrality(g &: Graph): Vector<f64>The example for this item is shown with the ones above: graph-Analysis.salam
EdgeBetweenness
func EdgeBetweenness(g &: Graph): Vector<f64>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 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 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>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 example for this item is shown with the ones above: graph-Analysis.salam
TopNode
func TopNode(score: Vector<f64>): intThe example for this item is shown with the ones above: graph-Analysis.salam
ScaleToSum
func ScaleToSum(v &: Vector<f64>)The example for this item is shown with the ones above: graph-Analysis.salam
IsTree
func IsTree(g &: Graph): boolThe example for this item is shown with the ones above: graph-Trees.salam
IsForest
func IsForest(g &: Graph): boolThe 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>)The example for this item is shown with the ones above: graph-Trees.salam
SubtreeSizes
func SubtreeSizes(g &: Graph, root: int): Vector<int>The example for this item is shown with the ones above: graph-Trees.salam
TreeDiameter
func TreeDiameter(g &: Graph, ends &: Vector<int>): intThe example for this item is shown with the ones above: graph-Trees.salam
TreeCenter
func TreeCenter(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Trees.salam
TreeCentroid
func TreeCentroid(g &: Graph): Vector<int>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>): boolThe 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>): boolThe example for this item is shown with the ones above: graph-Paths.salam
CriticalPath
func CriticalPath(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Paths.salam
CountPaths
func CountPaths(g &: Graph, s: int, t: int): f64The example for this item is shown with the ones above: graph-Paths.salam
PathCounts
func PathCounts(g &: Graph, src: int): Vector<f64>The example for this item is shown with the ones above: graph-Paths.salam
TransitiveClosure
func TransitiveClosure(g &: Graph): IntMatrixThe example for this item is shown with the ones above: graph-Paths.salam
TransitiveReduction
func TransitiveReduction(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Paths.salam
TopologicalLayers
func TopologicalLayers(g &: Graph, layer &: Vector<int>): intThe example for this item is shown with the ones above: graph-Paths.salam
IsTotalOrder
func IsTotalOrder(g &: Graph): boolThe example for this item is shown with the ones above: graph-Paths.salam
New
func New(n: int, directed: bool): GraphThe example for this item is shown with the ones above: graph-Build.salam
NewUndirected
func NewUndirected(n: int): GraphThe example for this item is shown with the ones above: graph-Build.salam
NewDirected
func NewDirected(n: int): GraphThe 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): GraphThe example for this item is shown with the ones above: graph-Build.salam
IsClose
func IsClose(a: f64, b: f64): boolThe example for this item is shown with the ones above: graph-Build.salam
Clone
func Clone(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
Transpose
func Transpose(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
Reverse
func Reverse(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
ToUndirected
func ToUndirected(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
ToDirected
func ToDirected(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
SubgraphMap
func SubgraphMap(g &: Graph, keep: Vector<bool>, map &: Vector<int>): GraphThe example for this item is shown with the ones above: graph-Build.salam
Subgraph
func Subgraph(g &: Graph, keep: Vector<bool>): GraphThe example for this item is shown with the ones above: graph-Build.salam
EdgeSubgraph
func EdgeSubgraph(g &: Graph, keep: Vector<bool>): GraphThe example for this item is shown with the ones above: graph-Build.salam
Complement
func Complement(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
Union
func Union(a &: Graph, b &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
DisjointUnion
func DisjointUnion(a &: Graph, b &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
Intersection
func Intersection(a &: Graph, b &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
LineGraph
func LineGraph(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
Simplify
func Simplify(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
RemoveSelfLoops
func RemoveSelfLoops(g &: Graph): GraphThe example for this item is shown with the ones above: graph-Build.salam
SelfLoopCount
func SelfLoopCount(g &: Graph): intThe example for this item is shown with the ones above: graph-Build.salam
HasSelfLoop
func HasSelfLoop(g &: Graph): boolThe example for this item is shown with the ones above: graph-Build.salam
ParallelEdgeCount
func ParallelEdgeCount(g &: Graph): intThe example for this item is shown with the ones above: graph-Build.salam
IsSimple
func IsSimple(g &: Graph): boolThe example for this item is shown with the ones above: graph-Build.salam
TotalWeight
func TotalWeight(g &: Graph): f64The example for this item is shown with the ones above: graph-Build.salam
MaxClique
func MaxClique(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Flow.salam
CliqueNumber
func CliqueNumber(g &: Graph): intThe example for this item is shown with the ones above: graph-Flow.salam
MaximumIndependentSet
func MaximumIndependentSet(g &: Graph): Vector<int>The example for this item is shown with the ones above: graph-Flow.salam
IndependenceNumber
func IndependenceNumber(g &: Graph): intThe example for this item is shown with the ones above: graph-Flow.salam
VertexCoverNumber
func VertexCoverNumber(g &: Graph): intThe example for this item is shown with the ones above: graph-Flow.salam
GreedyVertexCover
func GreedyVertexCover(g &: Graph, cover &: Vector<bool>): intThe example for this item is shown with the ones above: graph-Flow.salam