wiki:WikiStart

Version 8 (modified by hpwalton, 15 years ago) (diff)

--

Purpose of Coin Graph Classes (Cgc)

The purpose of the Cgc collection of Network Representations and Algorithms is to facilitate the development and implementation of Network Algorithms. The library was designed with some key ideas in mind:

Key ideas

  • Use STL and STL-like interfaces
  • Allow for common iteration through the network containers regardless of representation
  • Provide the ability to access the data structures named "nodes" and "arcs" for clarity
  • Any Network representation should be able to survive more than one Algorithm
  • Any Algorithm should be able to survive more than one Network Representation
  • Make the representations as compact as possible without sacrificing speed or time complexity

CgcTerminology

CgcComponents

GetCgc

UseCgc?

CgcTechnology

An example is the PathFindExample?.cpp example code. Some Sample Code: Simple Simple construction of a graph with just a few nodes and arcs. SimpleShortestPath? This is a simple example that tests the network as well as the simple algorithm to solve the Shortest Path problem in a directed acyclic network. PathFindExample? This is a little more complex, but not overwhelming. There are 3 main points to this example: @li Demonstrate the use of the PathFind? algorithm @li Demonstrate having "empty data" on the graph thus reducing ram consumption @li Demonstrate the use of a DynNet? and a destructive example of removing a node on the fly SSPSolver This is a comprehensive example showing much more complex usage of the graph @li more complex data storage on nodes @li more complex data storea on arcs @li implements a well known algorithm for solving min cost network flow problems (Successive Shortest Paths) There is a reference in the code to the source of the algorithm. More detailed code information See the doxygen generated comments for more information on the particular classes. In particular, peruse the "Public Interface" module comments.