Skip to content
This repository has been archived by the owner on Apr 23, 2019. It is now read-only.

CgcTechnology

Stefan Vigerske edited this page Apr 23, 2019 · 1 revision

CgcTechnology

Cgc uses the STL and other unique C++ capabilities heavily. It has gotten easier to implemnt Cgc over the years because the C++ compilers have dramatically improved their template instantiation mechanisms. There are some differences with how containers and algorithms fit together with Cgc mostly due to the relational aspects of graphs which do not exist with a single-simple-container.

C++ and the Standard C++ Library

The introduction of STL into the C++ library will have significant impact on algorithm developers using C++. With the advent of common containers and basic Computer Science algorithms as part of the standard, code (hence algorithms) may be shared more readily and used with data types that more difficult to use in the past.

More information on STL is available either from books, or the web. This will not assist in teaching you STL. However, if you are familiar with STL and C++, then you should find using Cgc will be second nature.

Network Containers

There are some difficulties in building containers for Networks that do not arise with normal containers. Normal containers have a single data type (or structure or class) that are collected together and maybe compared or sorted, etc. In the case of a Network, there are two related/distinct types: Nodes and Arcs. The Arcs refer to Nodes, but otherwise, they are somewhat independent.

In the implementation of Networks in Cgc, every Cgc container has a collection of Nodes. The Nodes are containers for their outbound Arcs. (In some implementations, there are back-arcs too). Also, there may be data on the Nodes and there may be data on the arcs. Unlike normal containers, this may be different data types.

Maybe a simple example would help. In a simple Shortest Path problem, there are locations (nodes) and distances between them (represented by durations or distances on the arcs). The goal is to find the shortest way between two locations using only the distances specified(arcs). Clearly, there must be some way of storing the duration/distance of the arc on the arc. Also, in most algorithms, there must be some way of storing information regarding the 'current status of a solution at the nodes. The graph container template arguments (Node Info and Arc Info) allow the algorithm developer to specify their own storage and behavior.