lemon-1.2: comparison lemon/list

equal deleted inserted replaced

-:c534af49375c
+:e51dfcdb46b1
 void next(Node& node) const {
 node.id = nodes[node.id].next;
 }
-void first(Arc& e) const {
+void first(Arc& arc) const {
 int n;
 for(n = first_node;
 	  n!=-1 && nodes[n].first_in == -1;
 	  n = nodes[n].next);
-e.id = (n == -1) ? -1 : nodes[n].first_in;
+arc.id = (n == -1) ? -1 : nodes[n].first_in;
 }
 void next(Arc& arc) const {
 if (arcs[arc.id].next_in != -1) {
 	arc.id = arcs[arc.id].next_in;
 };
 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
-/// \addtogroup digraphs
+/// \addtogroup graphs
 /// @{
-///A list digraph class.
+///A general directed graph structure.
-///This is a simple and fast digraph implementation.
+///\ref ListDigraph is a simple and fast <em>directed graph</em>
+///implementation based on static linked lists that are stored in
+///\c std::vector structures.
 ///
 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
-///also provides several additional useful extra functionalities.
+///also provides several useful additional functionalities.
-///The most of the member functions and nested classes are
+///Most of the member functions and nested classes are documented
-///documented only in the concept class.
+///only in the concept class.
 ///
 ///An important extra feature of this digraph implementation is that
 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
 ///
-///\sa concepts::Digraph.
+///\sa concepts::Digraph
 class ListDigraph : public ExtendedListDigraphBase {
 private:
-///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
+///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
-///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
+///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 ///
 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
 ///\brief Assignment of ListDigraph to another one is \e not allowed.
-///Use DigraphCopy() instead.
+///Use copyDigraph() instead.
 ///Assignment of ListDigraph to another one is \e not allowed.
-///Use DigraphCopy() instead.
+///Use copyDigraph() instead.
 void operator=(const ListDigraph &) {}
 public:
 typedef ExtendedListDigraphBase Parent;
 ///
 ListDigraph() {}
 ///Add a new node to the digraph.
-/// \return the new node.
+///Add a new node to the digraph.
-///
+///\return the new node.
 Node addNode() { return Parent::addNode(); }
 ///Add a new arc to the digraph.
 ///Add a new arc to the digraph with source node \c s
 ///\return the new arc.
 Arc addArc(const Node& s, const Node& t) {
 return Parent::addArc(s, t);
 }
-/// Changes the target of \c e to \c n
+/// Change the target of \c e to \c n
-/// Changes the target of \c e to \c n
+/// Change the target of \c e to \c n
 ///
 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
 ///the changed arc remain valid. However <tt>InArcIt</tt>s are
 ///invalidated.
+///
 ///\warning This functionality cannot be used together with the Snapshot
 ///feature.
 void changeTarget(Arc e, Node n) {
 Parent::changeTarget(e,n);
 }
-/// Changes the source of \c e to \c n
+/// Change the source of \c e to \c n
-/// Changes the source of \c e to \c n
+/// Change the source of \c e to \c n
 ///
 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
 ///invalidated.
+///
 ///\warning This functionality cannot be used together with the Snapshot
 ///feature.
 void changeSource(Arc e, Node n) {
 Parent::changeSource(e,n);
 }
 /// Invert the direction of an arc.
 ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
 ///invalidated.
+///
 ///\warning This functionality cannot be used together with the Snapshot
 ///feature.
 void reverseArc(Arc e) {
 Node t=target(e);
 changeTarget(e,source(e));
 changeSource(e,t);
 }
-/// Using this it is possible to avoid the superfluous memory
+/// Reserve memory for nodes.
+/// Using this function it is possible to avoid the superfluous memory
 /// allocation: if you know that the digraph you want to build will
 /// be very 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.
 /// \sa reserveArc
 void reserveNode(int n) { nodes.reserve(n); };
-/// \brief Using this it is possible to avoid the superfluous memory
+/// Reserve memory for arcs.
-/// allocation.
+/// Using this function it is possible to avoid the superfluous memory
-/// Using this it is possible to avoid the superfluous memory
 /// allocation: if you know that the digraph you want to build will
 /// be very 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.
 /// \sa reserveNode
 void reserveArc(int m) { arcs.reserve(m); };
 ///Contract two nodes.
 ///This function contracts two nodes.
-///
 ///Node \p b will be removed but instead of deleting
 ///incident arcs, they will be joined to \p a.
 ///The last parameter \p r controls whether to remove loops. \c true
 ///means that loops will be removed.
 ///
-///\note The <tt>ArcIt</tt>s
+///\note The <tt>ArcIt</tt>s referencing a moved arc remain
-///referencing a moved arc remain
 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
 ///may be invalidated.
+///
 ///\warning This functionality cannot be used together with the Snapshot
 ///feature.
 void contract(Node a, Node b, bool r = true)
 {
 for(OutArcIt e(*this,b);e!=INVALID;) {
 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
 ///be invalidated.
 ///
 ///\warning This functionality cannot be used together with the
-///Snapshot feature.  \todo It could be implemented in a bit
+///Snapshot feature.
-///faster way.
+///
+///\todo It could be implemented in a bit faster way.
 Node split(Node n, bool connect = true) {
 Node b = addNode();
 for(OutArcIt e(*this,n);e!=INVALID;) {
 	OutArcIt f=e;
 	++f;
 ///Split an arc.
 ///This function splits an arc. First a new node \c b is added to
 ///the digraph, then the original arc is re-targeted to \c
 ///b. Finally an arc from \c b to the original target is added.
-///\return The newly created node.
+///
-///\warning This functionality
+///\return The newly created node.
-///cannot be used together with the Snapshot feature.
+///
+///\warning This functionality cannot be used together with the
+///Snapshot feature.
 Node split(Arc e) {
 Node b = addNode();
 addArc(b,target(e));
 changeTarget(e,b);
 return b;
 }
 /// \brief Class to make a snapshot of the digraph and restore
-/// to it later.
+/// it later.
 ///
-/// Class to make a snapshot of the digraph and to restore it
+/// Class to make a snapshot of the digraph and restore it later.
-/// later.
 ///
 /// The newly added nodes and arcs can be removed using the
 /// restore() function.
 ///
-/// \warning Arc and node deletions cannot be restored. This
+/// \warning Arc and node deletions and other modifications (e.g.
-/// events invalidate the snapshot.
+/// contracting, splitting, reversing arcs or nodes) cannot be
+/// restored. These events invalidate the snapshot.
 class Snapshot {
 protected:
 typedef Parent::NodeNotifier NodeNotifier;
 explicit Edge(int pid) { id = pid;}
 public:
 Edge() {}
 Edge (Invalid) { id = -1; }
-bool operator==(const Edge& arc) const {return id == arc.id;}
+bool operator==(const Edge& edge) const {return id == edge.id;}
-bool operator!=(const Edge& arc) const {return id != arc.id;}
+bool operator!=(const Edge& edge) const {return id != edge.id;}
-bool operator<(const Edge& arc) const {return id < arc.id;}
+bool operator<(const Edge& edge) const {return id < edge.id;}
 };
 class Arc {
 friend class ListGraphBase;
 protected:
 e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
 if (e.id == -2) e.id = -1;
 }
 void firstInc(Edge &e, bool& d, const Node& v) const {
-int de = nodes[v.id].first_out;
+int a = nodes[v.id].first_out;
-if (de != -1 ) {
+if (a != -1 ) {
-e.id = de / 2;
+e.id = a / 2;
-d = ((de & 1) == 1);
+d = ((a & 1) == 1);
 } else {
 e.id = -1;
 d = true;
 }
 }
 void nextInc(Edge &e, bool& d) const {
-int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
+int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
-if (de != -1 ) {
+if (a != -1 ) {
-e.id = de / 2;
+e.id = a / 2;
-d = ((de & 1) == 1);
+d = ((a & 1) == 1);
 } else {
 e.id = -1;
 d = true;
 }
 }
 nodes[n].next = first_free_node;
 first_free_node = n;
 }
-void erase(const Edge& arc) {
+void erase(const Edge& edge) {
-int n = arc.id * 2;
+int n = edge.id * 2;
 if (arcs[n].next_out != -1) {
 	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
 }
 nodes[n.id].first_out = ((2 * e.id) | 1);
 }
 };
-//   typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> >
-//   ExtendedListGraphBase;
 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
+/// \addtogroup graphs
-/// \addtogroup digraphs
 /// @{
-///An undirected list digraph class.
+///A general undirected graph structure.
-///This is a simple and fast undirected digraph implementation.
+///\ref ListGraph is a simple and fast <em>undirected graph</em>
+///implementation based on static linked lists that are stored in
+///\c std::vector structures.
 ///
-///An important extra feature of this digraph implementation is that
+///It conforms to the \ref concepts::Graph "Graph concept" and it
+///also provides several useful additional functionalities.
+///Most of the member functions and nested classes are documented
+///only in the concept class.
+///
+///An important extra feature of this graph implementation is that
 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
 ///
-///It conforms to the
+///\sa concepts::Graph
-///\ref concepts::Graph "Graph concept".
-///
-///\sa concepts::Graph.
-///
 class ListGraph : public ExtendedListGraphBase {
 private:
-///ListGraph is \e not copy constructible. Use GraphCopy() instead.
+///ListGraph is \e not copy constructible. Use copyGraph() instead.
-///ListGraph is \e not copy constructible. Use GraphCopy() instead.
+///ListGraph is \e not copy constructible. Use copyGraph() instead.
 ///
 ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
 ///\brief Assignment of ListGraph to another one is \e not allowed.
-///Use GraphCopy() instead.
+///Use copyGraph() instead.
 ///Assignment of ListGraph to another one is \e not allowed.
-///Use GraphCopy() instead.
+///Use copyGraph() instead.
 void operator=(const ListGraph &) {}
 public:
 /// Constructor
 /// Constructor.
 ///
 ListGraph() {}
 typedef ExtendedListGraphBase Parent;
-typedef Parent::OutArcIt IncArcIt;
+typedef Parent::OutArcIt IncEdgeIt;
-/// \brief Add a new node to the digraph.
+/// \brief Add a new node to the graph.
 ///
+/// Add a new node to the graph.
 /// \return the new node.
-///
 Node addNode() { return Parent::addNode(); }
-/// \brief Add a new edge to the digraph.
+/// \brief Add a new edge to the graph.
 ///
-/// Add a new arc to the digraph with source node \c s
+/// Add a new edge to the graph with source node \c s
 /// and target node \c t.
 /// \return the new edge.
 Edge addEdge(const Node& s, const Node& t) {
 return Parent::addEdge(s, t);
 }
-/// \brief Changes the source of \c e to \c n
+/// \brief Change the source of \c e to \c n
 ///
-/// Changes the source of \c e to \c n
+/// This function changes the source of \c e to \c n.
 ///
 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
 ///referencing the changed arc remain
 ///valid. However <tt>OutArcIt</tt>s are invalidated.
+///
+///\warning This functionality cannot be used together with the
+///Snapshot feature.
 void changeSource(Edge e, Node n) {
 Parent::changeSource(e,n);
 }
-/// \brief Changes the target of \c e to \c n
+/// \brief Change the target of \c e to \c n
 ///
-/// Changes the target of \c e to \c n
+/// This function changes the target of \c e to \c n.
 ///
 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
 /// valid. However the other iterators may be invalidated.
+///
+///\warning This functionality cannot be used together with the
+///Snapshot feature.
 void changeTarget(Edge e, Node n) {
 Parent::changeTarget(e,n);
 }
-/// \brief Changes the source of \c e to \c n
+/// \brief Change the source of \c e to \c n
 ///
-/// Changes the source of \c e to \c n. It changes the proper
+/// This function changes the source of \c e to \c n.
-/// node of the represented edge.
+/// It also changes the proper node of the represented edge.
 ///
 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
 ///referencing the changed arc remain
 ///valid. However <tt>OutArcIt</tt>s are invalidated.
+///
+///\warning This functionality cannot be used together with the
+///Snapshot feature.
 void changeSource(Arc e, Node n) {
 if (Parent::direction(e)) {
 Parent::changeSource(e,n);
 } else {
 Parent::changeTarget(e,n);
 }
 }
-/// \brief Changes the target of \c e to \c n
+/// \brief Change the target of \c e to \c n
 ///
-/// Changes the target of \c e to \c n. It changes the proper
+/// This function changes the target of \c e to \c n.
-/// node of the represented edge.
+/// It also changes the proper node of the represented edge.
 ///
 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
 ///referencing the changed arc remain
 ///valid. However <tt>InArcIt</tt>s are invalidated.
+///
+///\warning This functionality cannot be used together with the
+///Snapshot feature.
 void changeTarget(Arc e, Node n) {
 if (Parent::direction(e)) {
 Parent::changeTarget(e,n);
 } else {
 Parent::changeSource(e,n);
 }
 }
 /// \brief Contract two nodes.
 ///
 /// This function contracts two nodes.
-///
 /// Node \p b will be removed but instead of deleting
 /// its neighboring arcs, they will be joined to \p a.
 /// The last parameter \p r controls whether to remove loops. \c true
 /// means that loops will be removed.
 ///
 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
 /// valid.
+///
+///\warning This functionality cannot be used together with the
+///Snapshot feature.
 void contract(Node a, Node b, bool r = true) {
-for(IncArcIt e(*this, b); e!=INVALID;) {
+for(IncEdgeIt e(*this, b); e!=INVALID;) {
-	IncArcIt f = e; ++f;
+	IncEdgeIt f = e; ++f;
 	if (r && runningNode(e) == a) {
 	  erase(e);
 	} else if (source(e) == b) {
 	  changeSource(e, a);
 	} else {
 }
 erase(b);
 }
-/// \brief Class to make a snapshot of the digraph and restore
+/// \brief Class to make a snapshot of the graph and restore
-/// to it later.
+/// it later.
 ///
-/// Class to make a snapshot of the digraph and to restore it
+/// Class to make a snapshot of the graph and restore it later.
-/// later.
 ///
 /// The newly added nodes and edges can be removed
 /// using the restore() function.
 ///
-/// \warning Arc and node deletions cannot be restored. This
+/// \warning Edge and node deletions and other modifications
-/// events invalidate the snapshot.
+/// (e.g. changing nodes of edges, contracting nodes) cannot be
+/// restored. These events invalidate the snapshot.
 class Snapshot {
 protected:
 typedef Parent::NodeNotifier NodeNotifier;
 using EdgeNotifier::ObserverBase::detach;
 using EdgeNotifier::ObserverBase::attached;
 protected:
-virtual void add(const Edge& arc) {
+virtual void add(const Edge& edge) {
-snapshot.addEdge(arc);
+snapshot.addEdge(edge);
 }
-virtual void add(const std::vector<Edge>& arcs) {
+virtual void add(const std::vector<Edge>& edges) {
-for (int i = arcs.size() - 1; i >= 0; ++i) {
+for (int i = edges.size() - 1; i >= 0; ++i) {
-snapshot.addEdge(arcs[i]);
+snapshot.addEdge(edges[i]);
 }
 }
-virtual void erase(const Edge& arc) {
+virtual void erase(const Edge& edge) {
-snapshot.eraseEdge(arc);
+snapshot.eraseEdge(edge);
 }
-virtual void erase(const std::vector<Edge>& arcs) {
+virtual void erase(const std::vector<Edge>& edges) {
-for (int i = 0; i < int(arcs.size()); ++i) {
+for (int i = 0; i < int(edges.size()); ++i) {
-snapshot.eraseEdge(arcs[i]);
+snapshot.eraseEdge(edges[i]);
 }
 }
 virtual void build() {
-Edge arc;
+Edge edge;
-std::vector<Edge> arcs;
+std::vector<Edge> edges;
-for (notifier()->first(arc); arc != INVALID;
+for (notifier()->first(edge); edge != INVALID;
-notifier()->next(arc)) {
+notifier()->next(edge)) {
-arcs.push_back(arc);
+edges.push_back(edge);
 }
-for (int i = arcs.size() - 1; i >= 0; --i) {
+for (int i = edges.size() - 1; i >= 0; --i) {
-snapshot.addEdge(arcs[i]);
+snapshot.addEdge(edges[i]);
 }
 }
 virtual void clear() {
-Edge arc;
+Edge edge;
-for (notifier()->first(arc); arc != INVALID;
+for (notifier()->first(edge); edge != INVALID;
-notifier()->next(arc)) {
+notifier()->next(edge)) {
-snapshot.eraseEdge(arc);
+snapshot.eraseEdge(edge);
 }
 }
 Snapshot& snapshot;
 };
-ListGraph *digraph;
+ListGraph *graph;
 NodeObserverProxy node_observer_proxy;
-EdgeObserverProxy arc_observer_proxy;
+EdgeObserverProxy edge_observer_proxy;
 std::list<Node> added_nodes;
-std::list<Edge> added_arcs;
+std::list<Edge> added_edges;
 void addNode(const Node& node) {
 added_nodes.push_front(node);
 }
 void eraseNode(const Node& node) {
 std::list<Node>::iterator it =
 std::find(added_nodes.begin(), added_nodes.end(), node);
 if (it == added_nodes.end()) {
 clear();
-arc_observer_proxy.detach();
+edge_observer_proxy.detach();
 throw NodeNotifier::ImmediateDetach();
 } else {
 added_nodes.erase(it);
 }
 }
-void addEdge(const Edge& arc) {
+void addEdge(const Edge& edge) {
-added_arcs.push_front(arc);
+added_edges.push_front(edge);
 }
-void eraseEdge(const Edge& arc) {
+void eraseEdge(const Edge& edge) {
 std::list<Edge>::iterator it =
-std::find(added_arcs.begin(), added_arcs.end(), arc);
+std::find(added_edges.begin(), added_edges.end(), edge);
-if (it == added_arcs.end()) {
+if (it == added_edges.end()) {
 clear();
 node_observer_proxy.detach();
 throw EdgeNotifier::ImmediateDetach();
 } else {
-added_arcs.erase(it);
+added_edges.erase(it);
 }
 }
-void attach(ListGraph &_digraph) {
+void attach(ListGraph &_graph) {
-	digraph = &_digraph;
+	graph = &_graph;
-	node_observer_proxy.attach(digraph->notifier(Node()));
+	node_observer_proxy.attach(graph->notifier(Node()));
-arc_observer_proxy.attach(digraph->notifier(Edge()));
+edge_observer_proxy.attach(graph->notifier(Edge()));
 }
 void detach() {
 	node_observer_proxy.detach();
-	arc_observer_proxy.detach();
+	edge_observer_proxy.detach();
 }
 bool attached() const {
 return node_observer_proxy.attached();
 }
 void clear() {
 added_nodes.clear();
-added_arcs.clear();
+added_edges.clear();
 }
 public:
 /// \brief Default constructor.
 ///
 /// Default constructor.
 /// To actually make a snapshot you must call save().
 Snapshot()
-: digraph(0), node_observer_proxy(*this),
+: graph(0), node_observer_proxy(*this),
-arc_observer_proxy(*this) {}
+edge_observer_proxy(*this) {}
 /// \brief Constructor that immediately makes a snapshot.
 ///
-/// This constructor immediately makes a snapshot of the digraph.
+/// This constructor immediately makes a snapshot of the graph.
-/// \param _digraph The digraph we make a snapshot of.
+/// \param _graph The graph we make a snapshot of.
-Snapshot(ListGraph &_digraph)
+Snapshot(ListGraph &_graph)
 : node_observer_proxy(*this),
-arc_observer_proxy(*this) {
+edge_observer_proxy(*this) {
-	attach(_digraph);
+	attach(_graph);
 }
 /// \brief Make a snapshot.
 ///
-/// Make a snapshot of the digraph.
+/// Make a snapshot of the graph.
 ///
 /// This function can be called more than once. In case of a repeated
 /// call, the previous snapshot gets lost.
-/// \param _digraph The digraph we make the snapshot of.
+/// \param _graph The graph we make the snapshot of.
-void save(ListGraph &_digraph) {
+void save(ListGraph &_graph) {
 if (attached()) {
 detach();
 clear();
 }
-attach(_digraph);
+attach(_graph);
 }
 /// \brief Undo the changes until the last snapshot.
 //
 /// Undo the changes until the last snapshot created by save().
 void restore() {
 	detach();
-	for(std::list<Edge>::iterator it = added_arcs.begin();
+	for(std::list<Edge>::iterator it = added_edges.begin();
-it != added_arcs.end(); ++it) {
+it != added_edges.end(); ++it) {
-	  digraph->erase(*it);
+	  graph->erase(*it);
 	}
 	for(std::list<Node>::iterator it = added_nodes.begin();
 it != added_nodes.end(); ++it) {
-	  digraph->erase(*it);
+	  graph->erase(*it);
 	}
 clear();
 }
 /// \brief Gives back true when the snapshot is valid.

changeset 135	6e7aee618f03
parent 57	c1acf0018c0a
child 149	2f7ae34e1333