ListDigraph
Declared in lemon/list_graph.h, in the group Graph Structures; the same class on the Doxygen site.
-
class ListDigraph : public DigraphExtender< ListDigraphBase >
A general directed graph structure.
ListDigraph is a versatile and fast directed graph implementation based on linked lists that are stored in
std::vectorstructures.This type fully conforms to the Digraph concept and it also provides several useful additional functionalities. Most of its member functions and nested classes are documented only in the concept class.
This class provides only linear time counting for nodes and arcs.
See also
See also
Public Functions
-
inline ListDigraph()
Constructor.
-
inline Node addNode()
Add a new node to the digraph.
This function adds a new node to the digraph.
- Returns:
The new node.
-
inline Arc addArc( Node s , Node t )
Add a new arc to the digraph.
This function adds a new arc to the digraph with source node
sand target nodet.- Returns:
The new arc.
-
inline void erase( Node n )
Erase a node from the digraph.
This function erases the given node along with its outgoing and incoming arcs from the digraph.
Note
All iterators referencing the removed node or the connected arcs are invalidated, of course.
-
inline void erase( Arc a )
Erase an arc from the digraph.
This function erases the given arc from the digraph.
Note
All iterators referencing the removed arc are invalidated, of course.
-
inline bool valid( Node n ) const
Node validity check.
This function gives back
trueif the given node is valid, i.e. it is a real node of the digraph.Warning
A removed node could become valid again if new nodes are added to the digraph.
-
inline bool valid( Arc a ) const
Arc validity check.
This function gives back
trueif the given arc is valid, i.e. it is a real arc of the digraph.Warning
A removed arc could become valid again if new arcs are added to the digraph.
-
inline void changeTarget( Arc a , Node n )
Change the target node of an arc.
This function changes the target node of the given arc
aton.Note
ArcItandOutArcItiterators referencing the changed arc remain valid, butInArcItiterators are invalidated.Warning
This functionality cannot be used together with the Snapshot feature.
-
inline void changeSource( Arc a , Node n )
Change the source node of an arc.
This function changes the source node of the given arc
aton.Note
InArcItiterators referencing the changed arc remain valid, butArcItandOutArcItiterators are invalidated.Warning
This functionality cannot be used together with the Snapshot feature.
-
inline void reverseArc( Arc a )
Reverse the direction of an arc.
This function reverses the direction of the given arc.
Note
ArcIt,OutArcItandInArcItiterators referencing the changed arc are invalidated.Warning
This functionality cannot be used together with the Snapshot feature.
-
inline void contract( Node u , Node v , bool r = true )
Contract two nodes.
This function contracts the given two nodes. Node
vis removed, but instead of deleting its incident arcs, they are joined to nodeu. If the last parameterristrue(this is the default value), then the newly created loops are removed.Note
The moved arcs are joined to node
uusing changeSource() or changeTarget(), thusArcItandOutArcItiterators are invalidated for the outgoing arcs of nodevandInArcItiterators are invalidated for the incoming arcs ofv. Moreover all iterators referencing nodevor the removed loops are also invalidated. Other iterators remain valid.Warning
This functionality cannot be used together with the Snapshot feature.
-
inline Node split( Node n , bool connect = true )
Split a node.
This function splits the given node. First, a new node is added to the digraph, then the source of each outgoing arc of node
nis moved to this new node. If the second parameterconnectistrue(this is the default value), then a new arc from nodento the newly created node is also added.Note
All iterators remain valid.
Warning
This functionality cannot be used together with the Snapshot feature.
- Returns:
The newly created node.
-
inline Node split( Arc a )
Split an arc.
This function splits the given arc. First, a new node
vis added to the digraph, then the target node of the original arc is set tov. Finally, an arc fromvto the original target is added.Note
InArcItiterators referencing the original arc are invalidated. Other iterators remain valid.Warning
This functionality cannot be used together with the Snapshot feature.
- Returns:
The newly created node.
-
inline void clear()
Clear the digraph.
This function erases all nodes and arcs from the digraph.
Note
All iterators of the digraph are invalidated, of course.
-
inline void reserveNode( int n )
Reserve memory for nodes.
Using this function, it is possible to avoid superfluous memory allocation: if you know that the digraph you want to build will be large (e.g. it will contain millions of nodes and/or arcs), then it is worth reserving space for this amount before starting to build the digraph.
See also
-
inline void reserveArc( int m )
Reserve memory for arcs.
Using this function, it is possible to avoid superfluous memory allocation: if you know that the digraph you want to build will be large (e.g. it will contain millions of nodes and/or arcs), then it is worth reserving space for this amount before starting to build the digraph.
See also
-
class Snapshot
Class to make a snapshot of the digraph and restore it later.
The newly added nodes and arcs can be removed using the restore() function.
Note
After a state is restored, you cannot restore a later state, i.e. you cannot add the removed nodes and arcs again using another Snapshot instance.
Warning
Node and arc deletions and other modifications (e.g. reversing, contracting, splitting arcs or nodes) cannot be restored. These events invalidate the snapshot. However, the arcs and nodes that were added to the digraph after making the current snapshot can be removed without invalidating it.
Public Functions
-
inline Snapshot( ListDigraph & gr )
Constructor that immediately makes a snapshot.
This constructor immediately makes a snapshot of the given digraph.
-
inline void save( ListDigraph & gr )
Make a snapshot.
This function makes a snapshot of the given digraph. It can be called more than once. In case of a repeated call, the previous snapshot gets lost.
-
inline void restore()
Undo the changes until the last snapshot.
This function undos the changes until the last snapshot created by save() or Snapshot(ListDigraph&).
Warning
This method invalidates the snapshot, i.e. repeated restoring is not supported unless you call save() again.
-
inline bool valid() const
Returns
trueif the snapshot is valid.This function returns
trueif the snapshot is valid.
Protected Types
-
typedef Parent::NodeNotifier NodeNotifier
Protected Functions
-
inline void addNode( const Node & node )
-
inline void eraseNode( const Node & node )
-
inline void addArc( const Arc & arc )
-
inline void eraseArc( const Arc & arc )
-
inline void attach( ListDigraph & _digraph )
-
inline void detach()
-
inline bool attached() const
-
inline void clear()
Protected Attributes
-
ListDigraph * digraph
-
NodeObserverProxy node_observer_proxy
-
ArcObserverProxy arc_observer_proxy
-
std::list< Node > added_nodes
-
std::list< Arc > added_arcs
-
class NodeObserverProxy : public AlterationNotifier< DigraphExtender , Node >::ObserverBase
-
class ArcObserverProxy : public ObserverBase
-
inline Snapshot( ListDigraph & gr )
-
inline ListDigraph()