equal
deleted
inserted
replaced
30 #include <vector> |
30 #include <vector> |
31 #include <list> |
31 #include <list> |
32 |
32 |
33 namespace lemon { |
33 namespace lemon { |
34 |
34 |
|
35 class ListDigraph; |
|
36 |
35 class ListDigraphBase { |
37 class ListDigraphBase { |
36 |
38 |
37 protected: |
39 protected: |
38 struct NodeT { |
40 struct NodeT { |
39 int first_in, first_out; |
41 int first_in, first_out; |
60 |
62 |
61 typedef ListDigraphBase Digraph; |
63 typedef ListDigraphBase Digraph; |
62 |
64 |
63 class Node { |
65 class Node { |
64 friend class ListDigraphBase; |
66 friend class ListDigraphBase; |
|
67 friend class ListDigraph; |
65 protected: |
68 protected: |
66 |
69 |
67 int id; |
70 int id; |
68 explicit Node(int pid) { id = pid;} |
71 explicit Node(int pid) { id = pid;} |
69 |
72 |
75 bool operator<(const Node& node) const {return id < node.id;} |
78 bool operator<(const Node& node) const {return id < node.id;} |
76 }; |
79 }; |
77 |
80 |
78 class Arc { |
81 class Arc { |
79 friend class ListDigraphBase; |
82 friend class ListDigraphBase; |
|
83 friend class ListDigraph; |
80 protected: |
84 protected: |
81 |
85 |
82 int id; |
86 int id; |
83 explicit Arc(int pid) { id = pid;} |
87 explicit Arc(int pid) { id = pid;} |
84 |
88 |
465 ///If the second parameter \c connect is \c true (this is the default |
469 ///If the second parameter \c connect is \c true (this is the default |
466 ///value), then a new arc from node \c n to the newly created node |
470 ///value), then a new arc from node \c n to the newly created node |
467 ///is also added. |
471 ///is also added. |
468 ///\return The newly created node. |
472 ///\return The newly created node. |
469 /// |
473 /// |
470 ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing |
474 ///\note All iterators remain valid. |
471 ///arcs of node \c n are invalidated. Other iterators remain valid. |
|
472 /// |
475 /// |
473 ///\warning This functionality cannot be used together with the |
476 ///\warning This functionality cannot be used together with the |
474 ///Snapshot feature. |
477 ///Snapshot feature. |
475 Node split(Node n, bool connect = true) { |
478 Node split(Node n, bool connect = true) { |
476 Node b = addNode(); |
479 Node b = addNode(); |
477 for(OutArcIt e(*this,n);e!=INVALID;) { |
480 nodes[b.id].first_out=nodes[n.id].first_out; |
478 OutArcIt f=e; |
481 nodes[n.id].first_out=-1; |
479 ++f; |
482 for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) { |
480 changeSource(e,b); |
483 arcs[i].source=b.id; |
481 e=f; |
|
482 } |
484 } |
483 if (connect) addArc(n,b); |
485 if (connect) addArc(n,b); |
484 return b; |
486 return b; |
485 } |
487 } |
486 |
488 |