# CMDBGraphQuery graph representation

You can represent a graph `G = (V, E)`

, in two standard ways: as a collection of adjacency lists or as an adjacency matrix. The adjacency-list representation is more common, because it provides a compact way to represent sparse graphs--those for which `|E|`

is much less than `|V|2`

. However, an adjacency-matrix representation might be better when the graph is dense, `|E|`

is close to `|V|2`

. The representation used by the `CMDBGraphQuery`

input query graph is an adjacency list.

The adjacency-list representation of a graph `G = (V, E)`

consists of an array `Adj`

of `|V|`

lists, one for each vertex in `V`

. For each `u`

in the set of `V`

, the adjacency list `Adj`

`u`

contains pointers to all the vertices `v`

such that there is an edge `(u, v)`

in the set of `E`

. That is, `Adj`

`u`

consists of all the vertices adjacent to `u`

in `G`

. The vertices in each adjacency list are typically stored in an arbitrary order. The following figure (b) is an adjacency-list representation in an arbitrary order of the undirected graph in the following figure (a).

**Undirected graph and its equivalent adjacency list**

Note

In an undirected graph `G = (V, E)`

, the edge set `E`

consists of unordered pairs of vertices, rather than ordered pairs. That is, an edge is a set {`u, v},`

where `(u, v)`

in the set of `E`

, and `u`

is not equal to `v`

. In an undirected graph, self-loops are forbidden, so every edge consists of exactly two distinct vertices.

Similarly, the following figure (b) is an adjacency-list representation of the directed graph in the following figure (a). In the BMC Atrium Core, all relationships are directional, so the query graph is a directed graph. In this graph, each relationship instance is like an edge and each CI instance is like a vertex.

**Directed graph and its equivalent adjacency list**

## Comments