BlockCount
The blocks: the maximal connected subgraphs with no cut vertex; an isolated vertex is a block.
✓ checked against that system · ! checked, with disagreements (hover a chip)FindStat
St000553via LabeledGraph✓BlockCount(graph)The blocks: the maximal connected subgraphs with no cut vertex; an isolated vertex is a block.Typed signatures
| Type | Package | Applies |
|---|---|---|
(labeled_graph) -> number | combinatorics | always |
Details
- Defined over
LabeledGraphas an expression in_x, evaluated by compute-engine — the definition IS the implementation. - Takes a
LabeledGraphand nothing else — it reads values against their positions, or walks the orbits, so it needs the bijection. Applying it to a bare list is a type error, not a wrong answer. - FindStat's St000553. The blocks of a component are one, plus for each cut vertex the components it leaves, less one; each vertex with an edge adds the components its deletion leaves in its own component, less one. The deleted vertex stays as an isolated one, a component of its own. The graph with no vertices gives 0.
Definition
Epsil, as the implementation runs it.
on LabeledGraph, over _x
0 if _x[1] == 0 else Apply((n: integer) => Apply((edges: list<list<integer>>) => Apply(
(adjacency: list<list<integer>>) => Apply(
(components: integer) => components +
Max(Sum(Map(Function(Apply(
(reach: list<list<integer>>) => Max(Sum(Map(Function(1 if Max(Sum(Map(Function((1 if reach[u][v] < n else 0) if u < v else 0, u), Range(1, n))), 0) ==
0 else 0, v), Range(1, n))), 0),
Apply(
(matrix: list<list<integer>>) => Apply(
(a_init: list<list<integer>>) => Fold((a: list<list<integer>>, k) => Apply(
(a_next: list<list<integer>>) => a_next,
Map(Function(Map(Function(Min(a[i][j], a[i][k] + a[k][j]), j), Range(1, n)), i), Range(1, n)),
), a_init, Range(1, n)),
Map(Function(Map(Function(0 if i == j else 1 if matrix[i][j] == 1 else 2n, j), Range(1, n)), i), Range(1, n)),
),
Map(Function(Map(Function(adjacency[i][j] *
(1 if (1 if i == v else 0) ==
0 else 0) *
(1 if (1 if j == v else 0) ==
0 else 0), j), Range(1, n)), i), Range(1, n)),
),
) -
(components + 1) if Max(Sum(Map(Function(adjacency[v][w], w), Range(1, n))), 0) >
0 else 0, v), Range(1, n))), 0),
Apply(
(reach: list<list<integer>>) => Max(Sum(Map(Function(1 if Max(Sum(Map(Function((1 if reach[u][v] < n else 0) if u < v else 0, u), Range(1, n))), 0) ==
0 else 0, v), Range(1, n))), 0),
Apply((matrix: list<list<integer>>) => Apply(
(a_init: list<list<integer>>) => Fold((a: list<list<integer>>, k) => Apply(
(a_next: list<list<integer>>) => a_next,
Map(Function(Map(Function(Min(a[i][j], a[i][k] + a[k][j]), j), Range(1, n)), i), Range(1, n)),
), a_init, Range(1, n)),
Map(
Function(Map(Function(0 if i == j else 1 if matrix[i][j] == 1 else 2n, j), Range(1, n)), i),
Range(1, n),
),
), adjacency),
),
),
Map(Function(Map(
Function(Max(Sum(Map(Function((1 if e[1] == i else 0) *
(1 if e[2] == j else 0) +
(1 if e[1] == j else 0) *
(1 if e[2] == i else 0), e), edges)), 0), j),
Range(1, n),
), i), Range(1, n)),
), _x[2]), _x[1])Examples
Properties #
About
| Examples | 4 |
|---|---|
| Crosswalk | FindStat |