CsGraph Repository

Supports constructing and querying a directed graph

Quick Status

Code functions correctly

no known defects

Demonstration code

yes

Documentation

yes

Test cases

none, but planned

Static library

no, but planned

Build requires

C# 7.0

Planned design changes

Add more demonstration code

1.0 Concept

Fig 1. Directed Graph Diagram

Graphs are very useful for capturing relationships, e.g., dependencies between packages. This repository contains a class CsGraph , where V is an application specific Vertex class designed to hold whatever information a graph vertex needs, and E is an application specific Edge class designed to hold whatever information a graph edge needs.

Fig 2. Comm Class Diagram

For example, if we are using a CsGraph to hold type information for a C# application, V might hold class name, namespace, and file location. E would then hold class relationship information, e.g., a destination Vertex, the other class in a class relationship, and the relationship type: inheritance, composition, aggregation, or using, as shown in Fig 1. and Fig 2.

The intent of this design is to support Vertices and Edges that may contain information as data members. For example, if we need to capture relationships between a set of classes, each vertex contains a class name and each edge contains a relationship type, e.g., inheritence, composition, aggregation, or using.

2.0 Design

Class CsNode<V, E> represents graph vertices. Each CsNode holds properties:

List<pair<V,E>> children
bool visited
string name
V nodeValue

And a class CsGraph<V,E> that contains properties:

List<CsNode<V,E>> adjList - list of all the graph's nodes
int startNode - index into adjList
string name

and methods:

void walk() - DFS walk through graph starting at startNode
Operation<V,E> - user defined and applied to each vertex during walk

3.0 Build

All code was built with Visual Studio, Community Edition - 2019, and tested on Windows 10.