91 ListGraph(const ListGraph &_g) |
91 ListGraph(const ListGraph &_g) |
92 : nodes(_g.nodes), first_node(_g.first_node), |
92 : nodes(_g.nodes), first_node(_g.first_node), |
93 first_free_node(_g.first_free_node), edges(_g.edges), |
93 first_free_node(_g.first_free_node), edges(_g.edges), |
94 first_free_edge(_g.first_free_edge) {} |
94 first_free_edge(_g.first_free_edge) {} |
95 |
95 |
96 int nodeNum() const { return nodes.size(); } //FIXME: What is this? |
96 ///Number of nodes. |
97 int edgeNum() const { return edges.size(); } //FIXME: What is this? |
97 int nodeNum() const { return nodes.size(); } |
98 |
98 ///Number of edges. |
99 ///Set the expected number of edges |
99 int edgeNum() const { return edges.size(); } |
|
100 |
|
101 ///Set the expected maximum number of edges. |
100 |
102 |
101 ///With this function, it is possible to set the expected number of edges. |
103 ///With this function, it is possible to set the expected number of edges. |
102 ///The use of this fasten the building of the graph and makes |
104 ///The use of this fasten the building of the graph and makes |
103 ///it possible to avoid the superfluous memory allocation. |
105 ///it possible to avoid the superfluous memory allocation. |
104 void reserveEdge(int n) { edges.reserve(n); }; |
106 void reserveEdge(int n) { edges.reserve(n); }; |
105 |
107 |
106 ///\bug This function does something different than |
108 /// Maximum node ID. |
107 ///its name would suggests... |
109 |
108 int maxNodeId() const { return nodes.size(); } //FIXME: What is this? |
110 /// Maximum node ID. |
109 ///\bug This function does something different than |
111 ///\sa id(Node) |
110 ///its name would suggests... |
112 int maxNodeId() const { return nodes.size()-1; } |
111 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
113 /// Maximum edge ID. |
|
114 |
|
115 /// Maximum edge ID. |
|
116 ///\sa id(Edge) |
|
117 int maxEdgeId() const { return edges.size()-1; } |
112 |
118 |
113 Node tail(Edge e) const { return edges[e.n].tail; } |
119 Node tail(Edge e) const { return edges[e.n].tail; } |
114 Node head(Edge e) const { return edges[e.n].head; } |
120 Node head(Edge e) const { return edges[e.n].head; } |
115 |
121 |
116 NodeIt& first(NodeIt& v) const { |
122 NodeIt& first(NodeIt& v) const { |
120 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
126 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
121 e=OutEdgeIt(*this,v); return e; } |
127 e=OutEdgeIt(*this,v); return e; } |
122 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
128 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
123 e=InEdgeIt(*this,v); return e; } |
129 e=InEdgeIt(*this,v); return e; } |
124 |
130 |
|
131 /// Node ID. |
|
132 |
|
133 /// The ID of a valid Node is a nonnegative integer not greater than |
|
134 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
135 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
136 /// |
|
137 /// The ID of the \ref INVALID node is -1. |
|
138 ///\return The ID of the node \c v. |
125 static int id(Node v) { return v.n; } |
139 static int id(Node v) { return v.n; } |
|
140 /// Edge ID. |
|
141 |
|
142 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
143 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
144 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
145 /// |
|
146 /// The ID of the \ref INVALID edge is -1. |
|
147 ///\return The ID of the edge \c e. |
126 static int id(Edge e) { return e.n; } |
148 static int id(Edge e) { return e.n; } |
127 |
149 |
128 /// Adds a new node to the graph. |
150 /// Adds a new node to the graph. |
129 |
151 |
130 /// \todo It adds the nodes in a reversed order. |
152 /// \warning It adds the new node to the front of the list. |
131 /// (i.e. the lastly added node becomes the first.) |
153 /// (i.e. the lastly added node becomes the first.) |
132 Node addNode() { |
154 Node addNode() { |
133 int n; |
155 int n; |
134 |
156 |
135 if(first_free_node==-1) |
157 if(first_free_node==-1) |
518 ///Copy constructor |
540 ///Copy constructor |
519 NodeSet(const NodeSet &_g) |
541 NodeSet(const NodeSet &_g) |
520 : nodes(_g.nodes), first_node(_g.first_node), |
542 : nodes(_g.nodes), first_node(_g.first_node), |
521 first_free_node(_g.first_free_node) {} |
543 first_free_node(_g.first_free_node) {} |
522 |
544 |
523 int nodeNum() const { return nodes.size(); } //FIXME: What is this? |
545 ///Number of nodes. |
524 int edgeNum() const { return 0; } //FIXME: What is this? |
546 int nodeNum() const { return nodes.size(); } |
525 |
547 ///Number of edges. |
526 ///\bug This function does something different than |
548 int edgeNum() const { return 0; } |
527 ///its name would suggests... |
549 |
528 int maxNodeId() const { return nodes.size(); } //FIXME: What is this? |
550 /// Maximum node ID. |
529 ///\bug This function does something different than |
551 |
530 ///its name would suggests... |
552 /// Maximum node ID. |
531 int maxEdgeId() const { return 0; } //FIXME: What is this? |
553 ///\sa id(Node) |
|
554 int maxNodeId() const { return nodes.size()-1; } |
|
555 /// Maximum edge ID. |
|
556 |
|
557 /// Maximum edge ID. |
|
558 ///\sa id(Edge) |
|
559 int maxEdgeId() const { return 0; } |
532 |
560 |
533 Node tail(Edge e) const { return INVALID; } |
561 Node tail(Edge e) const { return INVALID; } |
534 Node head(Edge e) const { return INVALID; } |
562 Node head(Edge e) const { return INVALID; } |
535 |
563 |
536 NodeIt& first(NodeIt& v) const { |
564 NodeIt& first(NodeIt& v) const { |
540 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
568 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
541 e=OutEdgeIt(*this,v); return e; } |
569 e=OutEdgeIt(*this,v); return e; } |
542 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
570 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
543 e=InEdgeIt(*this,v); return e; } |
571 e=InEdgeIt(*this,v); return e; } |
544 |
572 |
|
573 /// Node ID. |
|
574 |
|
575 /// The ID of a valid Node is a nonnegative integer not greater than |
|
576 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
577 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
578 /// |
|
579 /// The ID of the \ref INVALID node is -1. |
|
580 ///\return The ID of the node \c v. |
545 int id(Node v) const { return v.n; } |
581 int id(Node v) const { return v.n; } |
|
582 /// Edge ID. |
|
583 |
|
584 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
585 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
586 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
587 /// |
|
588 /// The ID of the \ref INVALID edge is -1. |
|
589 ///\return The ID of the edge \c e. |
546 int id(Edge e) const { return -1; } |
590 int id(Edge e) const { return -1; } |
547 |
591 |
548 /// Adds a new node to the graph. |
592 /// Adds a new node to the graph. |
549 |
593 |
550 /// \todo It adds the nodes in a reversed order. |
594 /// \warning It adds the new node to the front of the list. |
551 /// (i.e. the lastly added node becomes the first.) |
595 /// (i.e. the lastly added node becomes the first.) |
552 Node addNode() { |
596 Node addNode() { |
553 int n; |
597 int n; |
554 |
598 |
555 if(first_free_node==-1) |
599 if(first_free_node==-1) |
825 ///It will be based on the same graph. |
869 ///It will be based on the same graph. |
826 EdgeSet(const EdgeSet &_g) |
870 EdgeSet(const EdgeSet &_g) |
827 : G(_g.G), nodes(_g.G), edges(_g.edges), |
871 : G(_g.G), nodes(_g.G), edges(_g.edges), |
828 first_free_edge(_g.first_free_edge) {} |
872 first_free_edge(_g.first_free_edge) {} |
829 |
873 |
830 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this? |
874 ///Number of nodes. |
831 int edgeNum() const { return edges.size(); } //FIXME: What is this? |
875 int nodeNum() const { return G.nodeNum(); } |
832 |
876 ///Number of edges. |
833 ///\bug This function does something different than |
877 int edgeNum() const { return edges.size(); } |
834 ///its name would suggests... |
878 |
835 int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this? |
879 /// Maximum node ID. |
836 ///\bug This function does something different than |
880 |
837 ///its name would suggests... |
881 /// Maximum node ID. |
838 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
882 ///\sa id(Node) |
|
883 int maxNodeId() const { return G.maxNodeId(); } |
|
884 /// Maximum edge ID. |
|
885 |
|
886 /// Maximum edge ID. |
|
887 ///\sa id(Edge) |
|
888 int maxEdgeId() const { return edges.size()-1; } |
839 |
889 |
840 Node tail(Edge e) const { return edges[e.n].tail; } |
890 Node tail(Edge e) const { return edges[e.n].tail; } |
841 Node head(Edge e) const { return edges[e.n].head; } |
891 Node head(Edge e) const { return edges[e.n].head; } |
842 |
892 |
843 NodeIt& first(NodeIt& v) const { |
893 NodeIt& first(NodeIt& v) const { |
847 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
897 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
848 e=OutEdgeIt(*this,v); return e; } |
898 e=OutEdgeIt(*this,v); return e; } |
849 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
899 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
850 e=InEdgeIt(*this,v); return e; } |
900 e=InEdgeIt(*this,v); return e; } |
851 |
901 |
|
902 /// Node ID. |
|
903 |
|
904 /// The ID of a valid Node is a nonnegative integer not greater than |
|
905 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
906 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
907 /// |
|
908 /// The ID of the \ref INVALID node is -1. |
|
909 ///\return The ID of the node \c v. |
|
910 int id(Node v) { return G.id(v); } |
|
911 /// Edge ID. |
|
912 |
|
913 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
914 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
915 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
916 /// |
|
917 /// The ID of the \ref INVALID edge is -1. |
|
918 ///\return The ID of the edge \c e. |
852 int id(Edge e) const { return e.n; } |
919 int id(Edge e) const { return e.n; } |
853 |
920 |
854 /// Adds a new node to the graph. |
921 /// Adds a new node to the graph. |
855 Node addNode() { return G.addNode(); } |
922 Node addNode() { return G.addNode(); } |
856 |
923 |