I'm creating graph viewing utilities for real world use cases. My input is technically a directed acyclic graph with labelled edges and nodes.
As part of this I find myself generated graphs related to a graph in a number of different ways (subgraphs, edge-contraction). I am interested in using the correct terminology and common operations.
My question is twofold: What operations to produce related graphs are common / have accepted terminology? (i.e. like induced graphs, edge contraction)? (sorry this is a little vague but I'm looking for "where to start")
And is there a specific name for the follow graph operation (which I would be inclined to call a "reachability contraction over a subset of nodes."
$R(A, N) = G(N, \{(n, m): ( n, m \in N ) \land (\exists n_1...n_2)( P(n, n_1, n_2,..., n_i, m) \le A \land (\forall i)(n_i \notin N) \})$
Where
- $G(nodes, edges)$ is a graph of nodes and edges.
- $P(n_1,...n_i)$ is a path through nodes ($P(n_1,..., n_i) = G(\{n_1, ..., n_i\}, \{(n_a, n_{a+1}): 1 \le a \le i - 1 \})$)
- $G(A, B) \le G(C, D) \iff ( A \subseteq C ) \land (B \subseteq D)$