Aleph::Karger_Min_Cut< GT, SA >::ArcIndex Class Reference

Arc index with O(1) operations and deterministic ordering. More...

Collaboration diagram for Aleph::Karger_Min_Cut< GT, SA >::ArcIndex:

Public Member Functions
void	insert (Karc *a)
Karc *	select (size_t i) const
void	remove (Karc *a)
void	empty ()
size_t	size () const
void	swap (ArcIndex &other) noexcept

Private Attributes
std::vector< Karc * >	arcs

Detailed Description

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Karger_Min_Cut< GT, SA >::ArcIndex

Arc index with O(1) operations and deterministic ordering.

Uses arc counter to store position for O(1) swap-remove. This ensures reproducible results with the same random seed.

Definition at line 170 of file Karger.H.

Member Function Documentation

empty()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::empty ( )

inline

Definition at line 205 of file Karger.H.

References Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::arcs.

insert()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::insert ( Karc *  a )

inline

Definition at line 175 of file Karger.H.

References ARC_COUNTER, and Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::arcs.

remove()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::remove ( Karc *  a )

inline

Definition at line 187 of file Karger.H.

References ARC_COUNTER, Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::arcs, and Aleph::maps().

select()

template<class GT , class SA = Dft_Show_Arc<GT>>

Karc * Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::select ( size_t  i ) const

inline

Definition at line 181 of file Karger.H.

References Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::arcs, and Aleph::maps().

size()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::size ( ) const

inline

Definition at line 207 of file Karger.H.

References Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::arcs.

swap()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::swap ( ArcIndex &  other )

inlinenoexcept

Definition at line 209 of file Karger.H.

References Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::arcs, and Aleph::maps().

Member Data Documentation

arcs

template<class GT , class SA = Dft_Show_Arc<GT>>

std::vector<Karc *> Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::arcs

private

Definition at line 172 of file Karger.H.

Referenced by Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::empty(), Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::insert(), Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::remove(), Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::select(), Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::size(), and Aleph::Karger_Min_Cut< GT, SA >::ArcIndex::swap().

---

The documentation for this class was generated from the following file:

• Karger.H