Skip to content

Graph ​

Graph<N, W> representa um grafo direcionado com pesos. Os nós são identificados por valores do tipo N e as arestas carregam um peso do tipo W. Os nós são criados automaticamente quando uma aresta é adicionada, então construir um grafo nunca exige registro separado.

Construção ​

SintaxeDescrição
Graph<N, W>()Cria um novo grafo direcionado vazio com tipo de nó N e tipo de peso W

Os tipos de nó e peso suportados são string, bool e os tipos numéricos i8–i64, u8–u64, f32 e f64. Os dois parâmetros de tipo devem ser declarados explicitamente; eles não podem ser inferidos.

Métodos ​

MétodoAssinaturaRetornaDescrição
addEdge(source: N, target: N, weight: W) => voidvoidAdiciona uma aresta; cria os nós se ausentes, substitui o peso se o par ordenado já tiver aresta
addNode(node: N) => voidvoidAdiciona um nó isolado
removeNode(node: N) => booleanbooleanRemove um nó e todas as suas arestas incidentes; retorna true se o nó existia
removeEdge(source: N, target: N) => booleanbooleanRemove a aresta entre source e target; os nós permanecem
hasNode(node: N) => booleanbooleanSe o nó existe
hasEdge(source: N, target: N) => booleanbooleanSe o par ordenado tem uma aresta
edge(source: N, target: N) => W?W?O peso da aresta, ou vazio quando não há aresta
neighbors(node: N) => N[]N[]Os vizinhos de saída de um nó, em ordem de inserção
degree(node: N) => numbernumberO grau de saída de um nó
nodeCount() => numbernumberO número total de nós
edgeCount() => numbernumberO número total de arestas
isEmpty() => booleanbooleanSe o grafo não tem nenhum nó
nodes() => N[]N[]Todos os nós, em ordem de inserção
edges() => [N, N, W][][N, N, W][]Todas as arestas como tuplas (source, target, weight)
reverse() => Graph<N, W>Graph<N, W>Um novo grafo com a direção de todas as arestas invertida
mapEdges((weight: W) => W') => Graph<N, W'>Graph<N, W'>Um novo grafo com pesos transformados pelo callback
mapNodes((node: N) => N') => Graph<N', W>Graph<N', W>Um novo grafo com valores de nó transformados pelo callback
toDot() => stringstringO grafo renderizado como DOT do Graphviz
toString() => stringstringUma representação compacta de adjacência em uma linha

neighbors, nodes e edges retornam arrays recém-alocados pertencentes ao chamador. O handle nativo do grafo é liberado automaticamente quando a variável sai de escopo.

Complexidade ​

OperaçãoComplexidade Temporal
addEdge / addNodeO(1) amortizado, O(1) esperado
hasNode / edge / hasEdgeO(1) esperado
removeNodeO(V + E)
removeEdgeO(grau(source))
neighbors / degreeO(grau(node))
nodes / nodeCount / isEmptyO(V) / O(1)
edges / edgeCountO(E) / O(1)
reverse / mapEdges / mapNodesO(V + E)
toDot / toStringO(V + E)

Exemplos ​

Construindo um grafo ​

tyrus
import { Graph } from "tyrus:algorithm";

const g = Graph<string, i32>();
g.addEdge("a", "b", 1);
g.addEdge("b", "c", 2);
g.addEdge("a", "c", 3);
g.addNode("isolated");

print(g.nodeCount());  // 4
print(g.edgeCount());  // 3
print(g.isEmpty());    // false

Consultas ​

tyrus
print(g.hasNode("a"));     // true
print(g.hasEdge("a", "b"));  // true
print(g.edge("a", "b") ?? 0);  // 1
print(g.edge("b", "a") ?? 0);  // 0

print(g.degree("a"));  // 2
print(g.neighbors("a"));  // ["b", "c"]

Iteração ​

tyrus
for (const node of g.nodes()) {
    print(node);
}

for (const [source, target, weight] of g.edges()) {
    print(source, "->", target, "(", weight, ")");
}

Mutação ​

tyrus
print(g.removeEdge("a", "b"));  // true
print(g.hasEdge("a", "b"));     // false

print(g.removeNode("isolated"));  // true
print(g.hasNode("isolated"));     // false

Transformações ​

tyrus
const doubled = g.mapEdges((w: i32): i32 => w * 2);
print(doubled.edge("b", "c") ?? 0);  // 4

const upper = g.mapNodes((n: string): string => n.toUpperCase());
print(upper.hasNode("A"));  // true
print(upper.edge("A", "C") ?? 0);  // 6

const reversed = g.reverse();
print(reversed.hasEdge("c", "b"));  // true
print(reversed.hasEdge("b", "c"));  // false

Renderização ​

tyrus
print(g.toString());
// Graph { "a" -> "b" [label="1"], "a" -> "c" [label="3"], "b" -> "c" [label="2"] }

print(g.toDot());
// digraph {
//     "a" -> "b" [label="1"];
//     "a" -> "c" [label="3"];
//     "b" -> "c" [label="2"];
// }

Nós numéricos e pesos float ​

tyrus
const net = Graph<i32, f64>();
net.addEdge(1, 2, 1.5);
net.addEdge(2, 3, 2.5);

print(net.edge(1, 2) ?? 0.0);  // 1.5
print(net.degree(2));          // 1
print(net.nodes());            // [1, 2, 3]