CompactDigraph
Declared in lemon/compact_graph.h, in the group Graph Structures; the same class on the Doxygen site.
-
class CompactDigraph : public DigraphExtender< CompactDigraphBase >
A static directed graph class.
CompactDigraph is a highly efficient digraph implementation similar to StaticDigraph. It is more memory efficient but does not provide efficient iteration over incoming arcs.
It stores only one
intvalue for each node and oneintvalue for each arc. ItsInArcItis provided only for compatibility with the Digraph concept: with no index of the incoming arcs, it scans the arcs, so that visiting the incoming arcs of one node takes \(O(m)\) time, and of all nodes \(O(nm)\). An algorithm that visits them (e.g., one on the reverse digraph) should use StaticDigraph, which stores the incoming arcs too.This type fully conforms to the Digraph concept. Most of its member functions and nested classes are documented only in the concept class.
See also
Public Types
-
typedef ExtendedCompactDigraphBase Parent
Public Functions
-
inline CompactDigraph()
Constructor.
Default constructor.
-
inline Arc arc( int ix ) const
The arc with the given index.
This function returns the arc with the given index.
See also
-
inline int nodeNum() const
Number of nodes.
This function returns the number of nodes.
-
inline int arcNum() const
Number of arcs.
This function returns the number of arcs.
-
template< typename Digraph , typename NodeRefMap , typename ArcRefMap >
inline void build( - const Digraph & digraph,
- NodeRefMap & nodeRef,
- ArcRefMap & arcRef
Build the digraph copying another digraph.
This function builds the digraph copying another digraph of any kind. It can be called more than once, but in such case, the whole structure and all maps will be cleared and rebuilt.
This method also makes possible to copy a digraph to a CompactDigraph structure using DigraphCopy.
Note
If you do not need the arc references, then you could use NullMap for the last parameter. However the node references are required by the function itself, thus they must be readable from the map.
- Parameters:
digraph – An existing digraph to be copied.
nodeRef – The node references will be copied into this map. Its key type must be
Digraph::Nodeand its value type must beCompactDigraph::Node. It must conform to the ReadWriteMap concept.arcRef – The arc references will be copied into this map. Its key type must be
Digraph::Arcand its value type must beCompactDigraph::Arc. It must conform to the WriteMap concept.
-
template< typename ArcListIterator >
inline void build( - int n,
- ArcListIterator begin,
- ArcListIterator end
Build the digraph from an arc list.
This function builds the digraph from the given arc list. It can be called more than once, but in such case, the whole structure and all maps will be cleared and rebuilt.
The list of the arcs must be given in the range
[begin, end)specified by STL compatible itartors whosevalue_typemust bestd::pair< int , int >. Each arc must be specified by a pair of integer indices from the range[0..n-1]. The pairs must be in a non-decreasing order with respect to their first values. If the k-th pair in the list is(i,j), thenarc(k-1)will connectnode(i)tonode(j).For example, a simple digraph can be constructed like this.
std::vector< std::pair< int , int > > arcs; arcs.push_back( std::make_pair( 0 , 1 ) ); arcs.push_back( std::make_pair( 0 , 2 ) ); arcs.push_back( std::make_pair( 1 , 3 ) ); arcs.push_back( std::make_pair( 1 , 2 ) ); arcs.push_back( std::make_pair( 3 , 0 ) ); CompactDigraph gr; gr.build( 4 , arcs.begin() , arcs.end() );
- Parameters:
n – The number of nodes.
begin – An iterator pointing to the beginning of the arc list.
end – An iterator pointing to the end of the arc list.
-
inline void clear()
Clear the digraph.
This function erases all nodes and arcs from the digraph.
-
inline Node baseNode( const OutArcIt & arc ) const
-
inline Node runningNode( const OutArcIt & arc ) const
-
inline Node baseNode( const InArcIt & arc ) const
-
inline Node runningNode( const InArcIt & arc ) const
-
typedef ExtendedCompactDigraphBase Parent