As the name indicates, subgraph multiplicities encode all kinds of subgraphs and flows, only restricted by the lower and upper capacity bounds.
Like register attributes, subgraph multiplicities are defined for all graph objects. Other than registers, subgraph multiplicities are represented by arrays only for sparse graphs. For dense graphs, a hash table is used. By that, the memory to store subgraphs grows proportional with the subgraph cardinality. For logical graph instances (e.g. network flow transformations), subgraph multiplicities are not stored separately, but synchronized with the subgraph multiplicities of the original graph.
[See API]
Degree labels denote the node degrees according to the current subgraph multiplicities. The degree label of a node cumulates the multiplicity of the arcs incident with this node. Actually there are different fuctions Deg(), DegIn() and DegOut(), the first to count the undirected edges, the second to count the entering directed arcs, and the third to count the emanating directed arcs.
The degree labels are indeed represented in memory. For the sake of efficiency, the following is implemented:
- The degree labels are only generated with a call to Deg(), DegIn() or DegOut(). But then all node degrees are computed in one pass.
- Once generated, with every change of a subgraph multiplicity, the degree labels of the respective end nodes are adjusted.
- The degree labels can be disallocated again to save this book keeping operations by calling ReleaseDegrees(). This in particular happens when the subgraph is reset by using InitSubgraph(). For the time being, the degree labels of a sparse graph are corrupted by graph skeleton manipulations.
[See API]
Return to main page