Graphs

History

• Graph theory, the study of graphs is said to have originated in 1736 with Euler’s problem about traversing through the bridges of K ̈onigsberg, a city in Russia.
• Graphs have applications in several different areas including Computer Science, Data Science, Sociology, Economics, Chemistry and Biology.
• In this course, we will consider graphs as models of software artifacts and use them to design test cases.

Basic Concepts

• A graph is a tuple $G = (V,E)$ where
  • $V$ is a set of nodes/vertices.
  • $E \subseteq (V \times V)$ is a set of edges.
• Graphs can be directed or undirected.
  • In an undirected graph, the pair of vertices constituting an edge is unordered, i.e. whenever $(u,v) \in E$, then $(v,u) \in E$ and vice versa.
  • In a directed graph, the pair of vertices constituting an edge is ordered.
• Graphs can be finite or infinite.
  • Finite graphs have finite number of vertices.
  • Infinite graphs have infinite number of vertices.
• The degree of a vertex is the number of edges that are connected to it.
• Edges connected to a vertex are said to be incident on the vertex.

Initial and final nodes

• For many graphs, there are designated special vertices like initial and final vertices.
• These vertices indicate beginning and end of a property that the graph is modelling.
• Typically there is only one initial vertex but there could be several final vertices.
• Initial vertex represents the beginning of a computation (of a piece of code) and the computation ends in one of the final vertices.

Graphs in Testing: Coverage Criteria

• Graphs can come from different software artifacts:
  • Control flow graphs
  • Data flow graphs
  • Call graphs
  • Design elements modelled as finite state machines and statecharts
  • Use case diagrams
  • Activity diagrams
• Most of these graphs will have labels associated with vertices and/or edges. Labels or annotations could be details about the software artifact that the graphs are modelling.