# HG changeset patch # User alpar # Date 1100350408 0 # Node ID e997802b855ce873e201a5cd0e9c23a8128e807d # Parent 741f3108a90f740f5b99af8d18a448d87a0b29d3 Naming changes: - head -> target - tail -> source diff -r 741f3108a90f -r e997802b855c doc/graphs.dox --- a/doc/graphs.dox Sat Nov 13 12:24:01 2004 +0000 +++ b/doc/graphs.dox Sat Nov 13 12:53:28 2004 +0000 @@ -125,7 +125,7 @@ \code std::cout << "Edges:"; for (EdgeIt i(g); i!=INVALID; ++i) - std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")"; + std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; std::cout << std::endl; \endcode @@ -133,20 +133,20 @@ Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0) \endcode -We can also iterate through all edges of the graph very similarly. The head and -tail member functions can be used to access the endpoints of an edge. +We can also iterate through all edges of the graph very similarly. The target and +source member functions can be used to access the endpoints of an edge. \code NodeIt first_node(g); std::cout << "Out-edges of node " << g.id(first_node) << ":"; for (OutEdgeIt i(g, first_node); i!=INVALID; ++i) - std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")"; + std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; std::cout << std::endl; std::cout << "In-edges of node " << g.id(first_node) << ":"; for (InEdgeIt i(g, first_node); i!=INVALID; ++i) - std::cout << " (" << g.id(g.tail(i)) << "," << g.id(g.head(i)) << ")"; + std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")"; std::cout << std::endl; \endcode @@ -166,7 +166,7 @@ std::cout << "Id Edge Value" << std::endl; for (EdgeIt e(g); e!=INVALID; ++e) - std::cout << g.id(e) << " (" << g.id(g.tail(e)) << "," << g.id(g.head(e)) + std::cout << g.id(e) << " (" << g.id(g.source(e)) << "," << g.id(g.target(e)) << ") " << m[e] << std::endl; \endcode diff -r 741f3108a90f -r e997802b855c doc/maps.dox --- a/doc/maps.dox Sat Nov 13 12:24:01 2004 +0000 +++ b/doc/maps.dox Sat Nov 13 12:53:28 2004 +0000 @@ -112,7 +112,7 @@ public: ValueType operator[](KeyType e) const { - return orig_len.get(e)-pot.get(G.head(e))-pot.get(G.tail(e)); + return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e)); } MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p) diff -r 741f3108a90f -r e997802b855c src/benchmark/bfs-bench.cc --- a/src/benchmark/bfs-bench.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/benchmark/bfs-bench.cc Sat Nov 13 12:53:28 2004 +0000 @@ -46,7 +46,7 @@ Node m; Q.pop(); for(OutEdgeIt e(G,n);e!=INVALID;++e) - if(!visited[m=G.head(e)]) { + if(!visited[m=G.target(e)]) { Q.push(m); visited.set(m,true); } @@ -74,7 +74,7 @@ Node m; Node n=Q[Qt++]; for(OutEdgeIt e(G,n);e!=INVALID;++e) - if(!visited[m=G.head(e)]) { + if(!visited[m=G.target(e)]) { Q[Qh++]=m; visited.set(m,true); } diff -r 741f3108a90f -r e997802b855c src/demo/dim_to_dot.cc --- a/src/demo/dim_to_dot.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/demo/dim_to_dot.cc Sat Nov 13 12:53:28 2004 +0000 @@ -51,7 +51,7 @@ } cout << " edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];" << endl; for(EdgeIt e(g); e!=INVALID; ++e) { - cout << " n" << g.id(g.tail(e)) << " -> " << " n" << g.id(g.head(e)) + cout << " n" << g.id(g.source(e)) << " -> " << " n" << g.id(g.target(e)) << " [ label=\"" << g.id(e) << ", length:" << length[e] << "\" ]; " << endl; } diff -r 741f3108a90f -r e997802b855c src/demo/sub_graph_wrapper_demo.cc --- a/src/demo/sub_graph_wrapper_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/demo/sub_graph_wrapper_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -37,10 +37,10 @@ readDimacs(std::cin, g, length, s, t); - cout << "edges with lengths (of form id, tail--length->head): " << endl; + cout << "edges with lengths (of form id, source--length->target): " << endl; for(EdgeIt e(g); e!=INVALID; ++e) - cout << " " << g.id(e) << ", " << g.id(g.tail(e)) << "--" - << length[e] << "->" << g.id(g.head(e)) << endl; + cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--" + << length[e] << "->" << g.id(g.target(e)) << endl; cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; @@ -75,6 +75,6 @@ for(EdgeIt e(g); e!=INVALID; ++e) if (flow[e]) cout << " " << g.id(e) << ", " - << g.id(g.tail(e)) << "--" - << length[e] << "->" << g.id(g.head(e)) << endl; + << g.id(g.source(e)) << "--" + << length[e] << "->" << g.id(g.target(e)) << endl; } diff -r 741f3108a90f -r e997802b855c src/demo/tight_edge_filter_map.h --- a/src/demo/tight_edge_filter_map.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/demo/tight_edge_filter_map.h Sat Nov 13 12:53:28 2004 +0000 @@ -31,8 +31,8 @@ /// /// A node-map node_potential is said to be a potential w.r.t. /// an edge-map edge_distance - /// if and only if for each edge e, node_potential[g.head(e)] - /// <= edge_distance[e]+node_potential[g.tail(e)] + /// if and only if for each edge e, node_potential[g.target(e)] + /// <= edge_distance[e]+node_potential[g.source(e)] /// (or the reverse inequality holds for each edge). /// An edge is said to be tight if this inequality holds with equality, /// and the map returns true exactly for those edges. @@ -51,8 +51,8 @@ g(&_g), node_potential(&_node_potential), edge_distance(&_edge_distance) { } bool operator[](const typename Graph::Edge& e) const { - return ((*node_potential)[g->head(e)] == - (*edge_distance)[e]+(*node_potential)[g->tail(e)]); + return ((*node_potential)[g->target(e)] == + (*edge_distance)[e]+(*node_potential)[g->source(e)]); } }; diff -r 741f3108a90f -r e997802b855c src/lemon/bfs.h --- a/src/lemon/bfs.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/bfs.h Sat Nov 13 12:53:28 2004 +0000 @@ -209,7 +209,7 @@ int d= (*distance)[n]+1; for(OutEdgeIt e(*G,n);e!=INVALID;++e) - if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) { + if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) { Q[Qh++]=m; predecessor->set(m,e); pred_node->set(m,n); diff -r 741f3108a90f -r e997802b855c src/lemon/concept/graph.h --- a/src/lemon/concept/graph.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/concept/graph.h Sat Nov 13 12:53:28 2004 +0000 @@ -363,16 +363,16 @@ // /// // EdgeIt& first(EdgeIt& i) const { return i; } -// ///Gives back the head node of an edge. +// ///Gives back the target node of an edge. -// ///Gives back the head node of an edge. +// ///Gives back the target node of an edge. // /// -// Node head(Edge) const { return INVALID; } -// ///Gives back the tail node of an edge. +// Node target(Edge) const { return INVALID; } +// ///Gives back the source node of an edge. -// ///Gives back the tail node of an edge. +// ///Gives back the source node of an edge. // /// -// Node tail(Edge) const { return INVALID; } +// Node source(Edge) const { return INVALID; } // ///Gives back the \e id of a node. @@ -538,8 +538,8 @@ // n=m=INVALID; // Edge e; // e=INVALID; -// n=G.tail(e); -// n=G.head(e); +// n=G.source(e); +// n=G.target(e); // } // // id tests // { Node n; int i=G.id(n); i=i; } @@ -665,8 +665,8 @@ // Node addNode() { return INVALID; } // ///Add a new edge to the graph. -// ///Add a new edge to the graph with tail node \c t -// ///and head node \c h. +// ///Add a new edge to the graph with source node \c t +// ///and target node \c h. // ///\return the new edge. // Edge addEdge(Node h, Node t) { return INVALID; } @@ -800,8 +800,8 @@ void nextOutEdge(Edge &e) const { } void nextInEdge(Edge &e) const { } - Node head(Edge) const { return Node(); } - Node tail(Edge) const { return Node(); } + Node target(Edge) const { return Node(); } + Node source(Edge) const { return Node(); } // Do we need id, nodeNum, edgeNum and co. in this basic graphbase diff -r 741f3108a90f -r e997802b855c src/lemon/concept/graph_component.h --- a/src/lemon/concept/graph_component.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/concept/graph_component.h Sat Nov 13 12:53:28 2004 +0000 @@ -242,17 +242,17 @@ bool operator<(const Edge&) const { return true;} }; - ///Gives back the head node of an edge. + ///Gives back the target node of an edge. - ///Gives back the head node of an edge. + ///Gives back the target node of an edge. /// - Node head(const Edge&) const { return INVALID;} + Node target(const Edge&) const { return INVALID;} - ///Gives back the tail node of an edge. + ///Gives back the source node of an edge. - ///Gives back the tail node of an edge. + ///Gives back the source node of an edge. /// - Node tail(const Edge&) const { return INVALID;} + Node source(const Edge&) const { return INVALID;} }; @@ -272,8 +272,8 @@ { Node n; Edge e; - n = graph.tail(e); - n = graph.head(e); + n = graph.source(e); + n = graph.target(e); } } diff -r 741f3108a90f -r e997802b855c src/lemon/concept/path.h --- a/src/lemon/concept/path.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/concept/path.h Sat Nov 13 12:53:28 2004 +0000 @@ -66,12 +66,12 @@ /// /// Starting point of the path. /// Returns INVALID if the path is empty. - GraphNode/*It*/ head() const {return INVALID;} + GraphNode/*It*/ target() const {return INVALID;} /// \brief End point of the path. /// /// End point of the path. /// Returns INVALID if the path is empty. - GraphNode/*It*/ tail() const {return INVALID;} + GraphNode/*It*/ source() const {return INVALID;} /// \brief First NodeIt/EdgeIt. /// @@ -80,17 +80,17 @@ template It& first(It &i) const { return i=It(*this); } - /// \brief The head of an edge. + /// \brief The target of an edge. /// - /// Returns node iterator pointing to the head node of the + /// Returns node iterator pointing to the target node of the /// given edge iterator. - NodeIt head(const EdgeIt& e) const {return INVALID;} + NodeIt target(const EdgeIt& e) const {return INVALID;} - /// \brief The tail of an edge. + /// \brief The source of an edge. /// - /// Returns node iterator pointing to the tail node of the + /// Returns node iterator pointing to the source node of the /// given edge iterator. - NodeIt tail(const EdgeIt& e) const {return INVALID;} + NodeIt source(const EdgeIt& e) const {return INVALID;} /* Iterator classes */ diff -r 741f3108a90f -r e997802b855c src/lemon/concept/sym_graph.h --- a/src/lemon/concept/sym_graph.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/concept/sym_graph.h Sat Nov 13 12:53:28 2004 +0000 @@ -450,27 +450,27 @@ /// SymEdgeIt& first(SymEdgeIt& i) const { return i; } - ///Gives back the head node of an edge. + ///Gives back the target node of an edge. - ///Gives back the head node of an edge. + ///Gives back the target node of an edge. /// - Node head(Edge) const { return INVALID; } - ///Gives back the tail node of an edge. + Node target(Edge) const { return INVALID; } + ///Gives back the source node of an edge. - ///Gives back the tail node of an edge. + ///Gives back the source node of an edge. /// - Node tail(Edge) const { return INVALID; } + Node source(Edge) const { return INVALID; } ///Gives back the first node of an symmetric edge. ///Gives back the first node of an symmetric edge. /// - Node head(SymEdge) const { return INVALID; } + Node target(SymEdge) const { return INVALID; } ///Gives back the second node of an symmetric edge. ///Gives back the second node of an symmetric edge. /// - Node tail(SymEdge) const { return INVALID; } + Node source(SymEdge) const { return INVALID; } ///Gives back the \e id of a node. ///\warning Not all graph structures provide this feature. @@ -607,8 +607,8 @@ Node addNode() { return INVALID; } ///Add a new edge to the graph. - ///Add a new symmetric edge to the graph with tail node \c t - ///and head node \c h. + ///Add a new symmetric edge to the graph with source node \c t + ///and target node \c h. ///\return the new edge. SymEdge addEdge(Node h, Node t) { return INVALID; } diff -r 741f3108a90f -r e997802b855c src/lemon/concept/undir_graph.h --- a/src/lemon/concept/undir_graph.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/concept/undir_graph.h Sat Nov 13 12:53:28 2004 +0000 @@ -47,8 +47,8 @@ ue = e; Node n; - n = graph.head(ue); - n = graph.tail(ue); + n = graph.target(ue); + n = graph.source(ue); graph.first(ue); graph.next(ue); diff -r 741f3108a90f -r e997802b855c src/lemon/concept_check.h --- a/src/lemon/concept_check.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/concept_check.h Sat Nov 13 12:53:28 2004 +0000 @@ -25,7 +25,7 @@ /* "inline" is used for ignore_unused_variable_warning() and function_requires() to make sure there is no - overhead with g++. + overtarget with g++. */ template inline void ignore_unused_variable_warning(const T&) { } diff -r 741f3108a90f -r e997802b855c src/lemon/dfs.h --- a/src/lemon/dfs.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/dfs.h Sat Nov 13 12:53:28 2004 +0000 @@ -206,7 +206,7 @@ OutEdgeIt e; do { if((e=Q[Qh])!=INVALID) - if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) { + if((m=G->target(e))!=s && (*predecessor)[m=G->target(e)]==INVALID) { predecessor->set(m,e); pred_node->set(m,n); Q[++Qh] = OutEdgeIt(*G, m); @@ -214,7 +214,7 @@ n=m; } else ++Q[Qh]; - else if(--Qh>=0) n=G->tail(Q[Qh]); + else if(--Qh>=0) n=G->source(Q[Qh]); } while(Qh>=0); } diff -r 741f3108a90f -r e997802b855c src/lemon/dijkstra.h --- a/src/lemon/dijkstra.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/dijkstra.h Sat Nov 13 12:53:28 2004 +0000 @@ -254,7 +254,7 @@ for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { - Node w=G->head(e); + Node w=G->target(e); switch(heap.state(w)) { case HeapType::PRE_HEAP: heap.push(w,oldvalue+(*length)[e]); diff -r 741f3108a90f -r e997802b855c src/lemon/dimacs.h --- a/src/lemon/dimacs.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/dimacs.h Sat Nov 13 12:53:28 2004 +0000 @@ -208,7 +208,7 @@ os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; for(EdgeIt e(g); e!=INVALID; ++e) { - os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl; + os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl; } } diff -r 741f3108a90f -r e997802b855c src/lemon/full_graph.h --- a/src/lemon/full_graph.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/full_graph.h Sat Nov 13 12:53:28 2004 +0000 @@ -78,8 +78,8 @@ ///\sa id(Edge) int maxId(Edge = INVALID) const { return EdgeNum-1; } - Node tail(Edge e) const { return e.id % NodeNum; } - Node head(Edge e) const { return e.id / NodeNum; } + Node source(Edge e) const { return e.id % NodeNum; } + Node target(Edge e) const { return e.id / NodeNum; } /// Node ID. @@ -136,12 +136,12 @@ friend class FullGraphBase; protected: - int id; // NodeNum * head + tail; + int id; // NodeNum * target + source; Edge(int _id) : id(_id) {} - Edge(const FullGraphBase& _graph, int tail, int head) - : id(_graph.NodeNum * head+tail) {} + Edge(const FullGraphBase& _graph, int source, int target) + : id(_graph.NodeNum * target+source) {} public: Edge() { } Edge (Invalid) { id = -1; } @@ -250,14 +250,14 @@ ///\sa id(Edge) int maxId(Edge = INVALID) const { return EdgeNum-1; } - Node tail(Edge e) const { + Node source(Edge e) const { /// \todo we may do it faster return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; } - Node head(Edge e) const { - int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; - return e.id - (tail) * (tail - 1) / 2; + Node target(Edge e) const { + int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; + return e.id - (source) * (source - 1) / 2; } @@ -315,12 +315,12 @@ friend class UndirFullGraphBase; protected: - int id; // NodeNum * head + tail; + int id; // NodeNum * target + source; Edge(int _id) : id(_id) {} - Edge(const UndirFullGraphBase& _graph, int tail, int head) - : id(_graph.NodeNum * head+tail) {} + Edge(const UndirFullGraphBase& _graph, int source, int target) + : id(_graph.NodeNum * target+source) {} public: Edge() { } Edge (Invalid) { id = -1; } @@ -351,10 +351,10 @@ /// \todo with specialized iterators we can make faster iterating void nextOut(Edge& e) const { - int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; - int head = e.id - (tail) * (tail - 1) / 2; - ++head; - e.id = head < tail ? tail * (tail - 1) / 2 + head : -1; + int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; + int target = e.id - (source) * (source - 1) / 2; + ++target; + e.id = target < source ? source * (source - 1) / 2 + target : -1; } void firstIn(Edge& edge, const Node& node) const { @@ -362,10 +362,10 @@ } void nextIn(Edge& e) const { - int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; - int head = e.id - (tail) * (tail - 1) / 2; ++head; - ++tail; - e.id = tail < NodeNum ? tail * (tail - 1) / 2 + head : -1; + int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; + int target = e.id - (source) * (source - 1) / 2; ++target; + ++source; + e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1; } }; diff -r 741f3108a90f -r e997802b855c src/lemon/graph_utils.h --- a/src/lemon/graph_utils.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/graph_utils.h Sat Nov 13 12:53:28 2004 +0000 @@ -149,7 +149,7 @@ typename Graph::OutEdgeIt e(g,prev); if(prev==INVALID) g.first(e,u); else ++e; - while(e!=INVALID && g.tail(e)!=v) ++e; + while(e!=INVALID && g.source(e)!=v) ++e; return e; } @@ -192,7 +192,7 @@ void copyEdges(DestinationGraph& _d, const SourceGraph& _s, const NodeBijection& _nb, EdgeBijection& _eb) { for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) { - _eb[it] = _d.addEdge(_nb[_s.tail(it)], _nb[_s.head(it)]); + _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]); } } diff -r 741f3108a90f -r e997802b855c src/lemon/graph_wrapper.h --- a/src/lemon/graph_wrapper.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/graph_wrapper.h Sat Nov 13 12:53:28 2004 +0000 @@ -150,19 +150,19 @@ void nextIn(Edge& i) const { graph->nextIn(i); } void nextOut(Edge& i) const { graph->nextOut(i); } - Node tail(const Edge& e) const { return graph->tail(e); } - Node head(const Edge& e) const { return graph->head(e); } -// Node tail(const Edge& e) const { -// return Node(graph->tail(static_cast(e))); } -// Node head(const Edge& e) const { -// return Node(graph->head(static_cast(e))); } + Node source(const Edge& e) const { return graph->source(e); } + Node target(const Edge& e) const { return graph->target(e); } +// Node source(const Edge& e) const { +// return Node(graph->source(static_cast(e))); } +// Node target(const Edge& e) const { +// return Node(graph->target(static_cast(e))); } int nodeNum() const { return graph->nodeNum(); } int edgeNum() const { return graph->edgeNum(); } Node addNode() const { return Node(graph->addNode()); } - Edge addEdge(const Node& tail, const Node& head) const { - return Edge(graph->addEdge(tail, head)); } + Edge addEdge(const Node& source, const Node& target) const { + return Edge(graph->addEdge(source, target)); } void erase(const Node& i) const { graph->erase(i); } void erase(const Edge& i) const { graph->erase(i); } @@ -290,10 +290,10 @@ i=InEdgeIt(*this, p); return i; } - Node tail(const Edge& e) const { - return GraphWrapper::head(e); } - Node head(const Edge& e) const { - return GraphWrapper::tail(e); } + Node source(const Edge& e) const { + return GraphWrapper::target(e); } + Node target(const Edge& e) const { + return GraphWrapper::source(e); } // KEEP_MAPS(Parent, RevGraphWrapper); @@ -625,10 +625,10 @@ readDimacs(std::cin, g, length, s, t); - cout << "edges with lengths (of form id, tail--length->head): " << endl; + cout << "edges with lengths (of form id, source--length->target): " << endl; for(EdgeIt e(g); e!=INVALID; ++e) - cout << g.id(e) << ", " << g.id(g.tail(e)) << "--" - << length[e] << "->" << g.id(g.head(e)) << endl; + cout << g.id(e) << ", " << g.id(g.source(e)) << "--" + << length[e] << "->" << g.id(g.target(e)) << endl; cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; \endcode @@ -665,12 +665,12 @@ << endl; for(EdgeIt e(g); e!=INVALID; ++e) if (flow[e]) - cout << " " << g.id(g.tail(e)) << "--" - << length[e] << "->" << g.id(g.head(e)) << endl; + cout << " " << g.id(g.source(e)) << "--" + << length[e] << "->" << g.id(g.target(e)) << endl; \endcode The program has the following (expected :-)) output: \code - edges with lengths (of form id, tail--length->head): + edges with lengths (of form id, source--length->target): 9, 5--4->6 8, 4--2->6 7, 3--1->5 @@ -756,7 +756,7 @@ OutEdgeIt& next(OutEdgeIt& e) const { if (e.out_or_in) { - typename Graph::Node n=this->graph->tail(e.out); + typename Graph::Node n=this->graph->source(e.out); this->graph->next(e.out); if (!this->graph->valid(e.out)) { e.out_or_in=false; this->graph->first(e.in, n); } @@ -767,11 +767,11 @@ } Node aNode(const OutEdgeIt& e) const { - if (e.out_or_in) return this->graph->tail(e); else - return this->graph->head(e); } + if (e.out_or_in) return this->graph->source(e); else + return this->graph->target(e); } Node bNode(const OutEdgeIt& e) const { - if (e.out_or_in) return this->graph->head(e); else - return this->graph->tail(e); } + if (e.out_or_in) return this->graph->target(e); else + return this->graph->source(e); } // KEEP_MAPS(Parent, UndirGraphWrapper); @@ -937,7 +937,7 @@ Edge(e), gw(&_gw) { } OutEdgeIt& operator++() { if (!this->backward) { - Node n=gw->tail(*this); + Node n=gw->source(*this); *(static_cast(this))= ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); while (*static_cast(this)!=INVALID && @@ -994,7 +994,7 @@ Edge(e), gw(&_gw) { } InEdgeIt& operator++() { if (!this->backward) { - Node n=gw->tail(*this); + Node n=gw->source(*this); *(static_cast(this))= ++(typename Graph::InEdgeIt(*(gw->graph), *this)); while (*static_cast(this)!=INVALID && @@ -1089,10 +1089,10 @@ // } - Node tail(Edge e) const { - return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } - Node head(Edge e) const { - return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } + Node source(Edge e) const { + return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); } + Node target(Edge e) const { + return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); } /// Gives back the opposite edge. Edge opposite(const Edge& e) const { @@ -1413,7 +1413,7 @@ // i=OutEdgeIt(*this, p); return i; // } void erase(const Edge& e) const { - Node n=tail(e); + Node n=source(e); typename Graph::OutEdgeIt f(*Parent::graph, n); ++f; first_out_edges->set(n, f); diff -r 741f3108a90f -r e997802b855c src/lemon/kruskal.h --- a/src/lemon/kruskal.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/kruskal.h Sat Nov 13 12:53:28 2004 +0000 @@ -82,8 +82,8 @@ EdgeCost tot_cost = 0; for (typename IN::const_iterator p = in.begin(); p!=in.end(); ++p ) { - if ( uf.join(G.head((*p).first), - G.tail((*p).first)) ) { + if ( uf.join(G.target((*p).first), + G.source((*p).first)) ) { out.set((*p).first, true); tot_cost += (*p).second; } diff -r 741f3108a90f -r e997802b855c src/lemon/list_graph.h --- a/src/lemon/list_graph.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/list_graph.h Sat Nov 13 12:53:28 2004 +0000 @@ -43,7 +43,7 @@ }; struct EdgeT { - int head, tail; + int target, source; int prev_in, prev_out; int next_in, next_out; }; @@ -111,8 +111,8 @@ ///\sa id(Edge) int maxId(Edge = INVALID) const { return edges.size()-1; } - Node tail(Edge e) const { return edges[e.id].tail; } - Node head(Edge e) const { return edges[e.id].head; } + Node source(Edge e) const { return edges[e.id].source; } + Node target(Edge e) const { return edges[e.id].target; } void first(Node& node) const { @@ -137,7 +137,7 @@ edge.id = edges[edge.id].next_in; } else { int n; - for(n = nodes[edges[edge.id].head].next; + for(n = nodes[edges[edge.id].target].next; n!=-1 && nodes[n].first_in == -1; n = nodes[n].next); edge.id = (n == -1) ? -1 : nodes[n].first_in; @@ -198,8 +198,8 @@ first_free_edge = edges[n].next_in; } - edges[n].tail = u.id; - edges[n].head = v.id; + edges[n].source = u.id; + edges[n].target = v.id; edges[n].next_out = nodes[u.id].first_out; if(nodes[u.id].first_out != -1) { @@ -246,7 +246,7 @@ if(edges[n].prev_in!=-1) { edges[edges[n].prev_in].next_in = edges[n].next_in; } else { - nodes[edges[n].head].first_in = edges[n].next_in; + nodes[edges[n].target].first_in = edges[n].next_in; } @@ -257,7 +257,7 @@ if(edges[n].prev_out!=-1) { edges[edges[n].prev_out].next_out = edges[n].next_out; } else { - nodes[edges[n].tail].first_out = edges[n].next_out; + nodes[edges[n].source].first_out = edges[n].next_out; } edges[n].next_in = first_free_edge; @@ -272,26 +272,26 @@ } protected: - void _moveHead(Edge e, Node n) + void _moveTarget(Edge e, Node n) { if(edges[e.id].next_in != -1) edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in; if(edges[e.id].prev_in != -1) edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; - else nodes[edges[e.id].head].first_in = edges[e.id].next_in; - edges[e.id].head = n.id; + else nodes[edges[e.id].target].first_in = edges[e.id].next_in; + edges[e.id].target = n.id; edges[e.id].prev_in = -1; edges[e.id].next_in = nodes[n.id].first_in; nodes[n.id].first_in = e.id; } - void _moveTail(Edge e, Node n) + void _moveSource(Edge e, Node n) { if(edges[e.id].next_out != -1) edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; if(edges[e.id].prev_out != -1) edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; - else nodes[edges[e.id].tail].first_out = edges[e.id].next_out; - edges[e.id].tail = n.id; + else nodes[edges[e.id].source].first_out = edges[e.id].next_out; + edges[e.id].source = n.id; edges[e.id].prev_out = -1; edges[e.id].next_out = nodes[n.id].first_out; nodes[n.id].first_out = e.id; @@ -320,16 +320,16 @@ class ListGraph : public ErasableListGraphBase { public: - /// Moves the head of \c e to \c n + /// Moves the target of \c e to \c n - /// Moves the head of \c e to \c n + /// Moves the target of \c e to \c n /// - void moveHead(Edge e, Node n) { _moveHead(e,n); } - /// Moves the tail of \c e to \c n + void moveTarget(Edge e, Node n) { _moveTarget(e,n); } + /// Moves the source of \c e to \c n - /// Moves the tail of \c e to \c n + /// Moves the source of \c e to \c n /// - void moveTail(Edge e, Node n) { _moveTail(e,n); } + void moveSource(Edge e, Node n) { _moveSource(e,n); } ///Using this it possible to avoid the superfluous memory allocation. ///\todo more docs... diff -r 741f3108a90f -r e997802b855c src/lemon/min_cost_flow.h --- a/src/lemon/min_cost_flow.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/min_cost_flow.h Sat Nov 13 12:53:28 2004 +0000 @@ -103,9 +103,9 @@ ValueType operator[](typename ResGW::Edge e) const { if (g.forward(e)) - return length[e]-(pot[g.head(e)]-pot[g.tail(e)]); + return length[e]-(pot[g.target(e)]-pot[g.source(e)]); else - return -length[e]-(pot[g.head(e)]-pot[g.tail(e)]); + return -length[e]-(pot[g.target(e)]-pot[g.source(e)]); } }; //ModLengthMap @@ -235,7 +235,7 @@ Length fl_e; for(typename Graph::EdgeIt e(g); e!=INVALID; ++e) { //C^{\Pi}_{i,j} - mod_pot = length[e]-potential[g.head(e)]+potential[g.tail(e)]; + mod_pot = length[e]-potential[g.target(e)]+potential[g.source(e)]; fl_e = flow[e]; if (0tail(edges[0]); + GraphNode source() const { + return empty() ? INVALID : gr->source(edges[0]); } /// \brief End point of the path. /// /// End point of the path. /// Returns INVALID if the path is empty. - GraphNode head() const { - return empty() ? INVALID : gr->head(edges[length()-1]); + GraphNode target() const { + return empty() ? INVALID : gr->target(edges[length()-1]); } /// \brief Initializes node or edge iterator to point to the first @@ -139,15 +139,15 @@ return i=EdgeIt(*this, n); } - /// \brief Returns node iterator pointing to the head node of the + /// \brief Returns node iterator pointing to the target node of the /// given edge iterator. - NodeIt head(const EdgeIt& e) const { + NodeIt target(const EdgeIt& e) const { return NodeIt(*this, e.idx+1); } - /// \brief Returns node iterator pointing to the tail node of the + /// \brief Returns node iterator pointing to the source node of the /// given edge iterator. - NodeIt tail(const EdgeIt& e) const { + NodeIt source(const EdgeIt& e) const { return NodeIt(*this, e.idx); } @@ -230,9 +230,9 @@ ///Conversion to Graph::Node operator const GraphNode& () const { if(idx >= p->length()) - return p->head(); + return p->target(); else if(idx >= 0) - return p->gr->tail(p->edges[idx]); + return p->gr->source(p->edges[idx]); else return INVALID; } @@ -335,23 +335,23 @@ return front.empty() && back.empty() && P.empty(); } - GraphNode tail() const { + GraphNode source() const { if( ! front.empty() ) - return P.gr->tail(front[front.size()-1]); + return P.gr->source(front[front.size()-1]); else if( ! P.empty() ) - return P.gr->tail(P.edges[0]); + return P.gr->source(P.edges[0]); else if( ! back.empty() ) - return P.gr->tail(back[0]); + return P.gr->source(back[0]); else return INVALID; } - GraphNode head() const { + GraphNode target() const { if( ! back.empty() ) - return P.gr->head(back[back.size()-1]); + return P.gr->target(back[back.size()-1]); else if( ! P.empty() ) - return P.gr->head(P.edges[P.length()-1]); + return P.gr->target(P.edges[P.length()-1]); else if( ! front.empty() ) - return P.gr->head(front[0]); + return P.gr->target(front[0]); else return INVALID; } @@ -437,15 +437,15 @@ /// /// Starting point of the path. /// Returns INVALID if the path is empty. - GraphNode tail() const { - return empty() ? INVALID : gr->tail(edges[0]); + GraphNode source() const { + return empty() ? INVALID : gr->source(edges[0]); } /// \brief End point of the path. /// /// End point of the path. /// Returns INVALID if the path is empty. - GraphNode head() const { - return empty() ? INVALID : gr->head(edges[length()-1]); + GraphNode target() const { + return empty() ? INVALID : gr->target(edges[length()-1]); } /// \brief Initializes node or edge iterator to point to the first @@ -477,15 +477,15 @@ return ++e; } - /// \brief Returns node iterator pointing to the head node of the + /// \brief Returns node iterator pointing to the target node of the /// given edge iterator. - NodeIt head(const EdgeIt& e) const { + NodeIt target(const EdgeIt& e) const { return NodeIt(*this, e.idx+1); } - /// \brief Returns node iterator pointing to the tail node of the + /// \brief Returns node iterator pointing to the source node of the /// given edge iterator. - NodeIt tail(const EdgeIt& e) const { + NodeIt source(const EdgeIt& e) const { return NodeIt(*this, e.idx); } @@ -570,9 +570,9 @@ ///Conversion to Graph::Node operator const GraphNode& () const { if(idx >= p->length()) - return p->head(); + return p->target(); else if(idx >= 0) - return p->gr->tail(p->edges[idx]); + return p->gr->source(p->edges[idx]); else return INVALID; } @@ -676,23 +676,23 @@ return front.empty() && back.empty() && P.empty(); } - GraphNode tail() const { + GraphNode source() const { if( ! front.empty() ) - return P.gr->tail(front[front.size()-1]); + return P.gr->source(front[front.size()-1]); else if( ! P.empty() ) - return P.gr->tail(P.edges[0]); + return P.gr->source(P.edges[0]); else if( ! back.empty() ) - return P.gr->tail(back[0]); + return P.gr->source(back[0]); else return INVALID; } - GraphNode head() const { + GraphNode target() const { if( ! back.empty() ) - return P.gr->head(back[back.size()-1]); + return P.gr->target(back[back.size()-1]); else if( ! P.empty() ) - return P.gr->head(P.edges[P.length()-1]); + return P.gr->target(P.edges[P.length()-1]); else if( ! front.empty() ) - return P.gr->head(front[0]); + return P.gr->target(front[0]); else return INVALID; } diff -r 741f3108a90f -r e997802b855c src/lemon/preflow.h --- a/src/lemon/preflow.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/preflow.h Sat Nov 13 12:53:28 2004 +0000 @@ -305,7 +305,7 @@ for(InEdgeIt e(*g,v); e!=INVALID; ++e) { if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node u=g->tail(e); + Node u=g->source(e); if ( level[u] >= n ) { bfs_queue.push(u); level.set(u, l); @@ -318,7 +318,7 @@ for(OutEdgeIt e(*g,v); e!=INVALID; ++e) { if ( 0 >= (*flow)[e] ) continue; - Node u=g->head(e); + Node u=g->target(e); if ( level[u] >= n ) { bfs_queue.push(u); level.set(u, l); @@ -410,7 +410,7 @@ queue.pop(); for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->head(e); + Node v=g->target(e); if (!M[v] && (*flow)[e] < (*capacity)[e] ) { queue.push(v); M.set(v, true); @@ -418,7 +418,7 @@ } for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->tail(e); + Node v=g->source(e); if (!M[v] && (*flow)[e] > 0 ) { queue.push(v); M.set(v, true); @@ -448,7 +448,7 @@ queue.pop(); for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->tail(e); + Node v=g->source(e); if (M[v] && (*flow)[e] < (*capacity)[e] ) { queue.push(v); M.set(v, false); @@ -456,7 +456,7 @@ } for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->head(e); + Node v=g->target(e); if (M[v] && (*flow)[e] > 0 ) { queue.push(v); M.set(v, false); @@ -515,7 +515,7 @@ for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { if ( (*flow)[e] >= (*capacity)[e] ) continue; - Node v=g->head(e); + Node v=g->target(e); if( lev > level[v] ) { //Push is allowed now @@ -547,7 +547,7 @@ for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { if( (*flow)[e] <= 0 ) continue; - Node v=g->tail(e); + Node v=g->source(e); if( lev > level[v] ) { //Push is allowed now @@ -602,7 +602,7 @@ for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node w=g->tail(e); + Node w=g->source(e); if ( level[w] == n && w != s ) { bfs_queue.push(w); Node z=level_list[l]; @@ -615,7 +615,7 @@ for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) { if ( 0 >= (*flow)[e] ) continue; - Node w=g->head(e); + Node w=g->target(e); if ( level[w] == n && w != s ) { bfs_queue.push(w); Node z=level_list[l]; @@ -646,7 +646,7 @@ int l=level[v]+1; for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { - Node w=g->tail(e); + Node w=g->source(e); if ( level[w] == n && w != s ) { bfs_queue.push(w); Node z=level_list[l]; @@ -662,7 +662,7 @@ for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { Num c=(*capacity)[e]; if ( c <= 0 ) continue; - Node w=g->head(e); + Node w=g->target(e); if ( level[w] < n ) { if ( excess[w] <= 0 && w!=t ) { //putting into the stack next.set(w,first[level[w]]); @@ -687,7 +687,7 @@ for(OutEdgeIt e(*g,s); e!=INVALID; ++e) { Num rem=(*capacity)[e]-(*flow)[e]; if ( rem <= 0 ) continue; - Node w=g->head(e); + Node w=g->target(e); if ( level[w] < n ) { if ( excess[w] <= 0 && w!=t ) { //putting into the stack next.set(w,first[level[w]]); @@ -700,7 +700,7 @@ for(InEdgeIt e(*g,s); e!=INVALID; ++e) { if ( (*flow)[e] <= 0 ) continue; - Node w=g->tail(e); + Node w=g->source(e); if ( level[w] < n ) { if ( excess[w] <= 0 && w!=t ) { next.set(w,first[level[w]]); @@ -717,13 +717,13 @@ for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { Num rem=(*capacity)[e]-(*flow)[e]; if ( rem <= 0 ) continue; - Node w=g->head(e); + Node w=g->target(e); if ( level[w] < n ) flow->set(e, (*capacity)[e]); } for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) { if ( (*flow)[e] <= 0 ) continue; - Node w=g->tail(e); + Node w=g->source(e); if ( level[w] < n ) flow->set(e, 0); } diff -r 741f3108a90f -r e997802b855c src/lemon/smart_graph.h --- a/src/lemon/smart_graph.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/smart_graph.h Sat Nov 13 12:53:28 2004 +0000 @@ -55,7 +55,7 @@ }; struct EdgeT { - int head, tail, next_in, next_out; + int target, source, next_in, next_out; //FIXME: is this necessary? EdgeT() : next_in(-1), next_out(-1) {} }; @@ -97,8 +97,8 @@ ///\sa id(Edge) int maxId(Edge = INVALID) const { return edges.size()-1; } - Node tail(Edge e) const { return edges[e.n].tail; } - Node head(Edge e) const { return edges[e.n].head; } + Node source(Edge e) const { return edges[e.n].source; } + Node target(Edge e) const { return edges[e.n].target; } /// Node ID. @@ -127,7 +127,7 @@ Edge addEdge(Node u, Node v) { Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... - edges[e.n].tail=u.n; edges[e.n].head=v.n; + edges[e.n].source=u.n; edges[e.n].target=v.n; edges[e.n].next_out=nodes[u.n].first_out; edges[e.n].next_in=nodes[v.n].first_in; nodes[u.n].first_out=nodes[v.n].first_in=e.n; @@ -211,7 +211,7 @@ Edge _findEdge(Node u,Node v, Edge prev = INVALID) { int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; - while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; + while(e!=-1 && edges[e].source!=v.n) e = edges[e].next_out; prev.n=e; return prev; } @@ -307,8 +307,8 @@ { while(s.edge_num>edges.size()) { edge_observers.erase(Edge(edges.size()-1)); - nodes[edges.back().head].first_in=edges.back().next_in; - nodes[edges.back().tail].first_out=edges.back().next_out; + nodes[edges.back().target].first_in=edges.back().next_in; + nodes[edges.back().source].first_out=edges.back().next_out; edges.pop_back(); } //nodes.resize(s.nodes_num); diff -r 741f3108a90f -r e997802b855c src/lemon/suurballe.h --- a/src/lemon/suurballe.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/suurballe.h Sat Nov 13 12:53:28 2004 +0000 @@ -133,7 +133,7 @@ while (!reversed[e]){ ++e; } - n = G.head(e); + n = G.target(e); paths[j].push_back(e); //total_length += length[e]; reversed[e] = 1-reversed[e]; diff -r 741f3108a90f -r e997802b855c src/lemon/undir_graph_extender.h --- a/src/lemon/undir_graph_extender.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/lemon/undir_graph_extender.h Sat Nov 13 12:53:28 2004 +0000 @@ -70,23 +70,23 @@ return Edge(e,!e.forward); } - /// Tail of the given Edge. - Node tail(const Edge &e) const { - return e.forward ? Parent::tail(e) : Parent::head(e); + /// Source of the given Edge. + Node source(const Edge &e) const { + return e.forward ? Parent::source(e) : Parent::target(e); } - /// \todo Shouldn't the "tail" of an undirected edge be called "aNode" + /// \todo Shouldn't the "source" of an undirected edge be called "aNode" /// or something??? - using Parent::tail; + using Parent::source; - /// Head of the given Edge. - Node head(const Edge &e) const { - return e.forward ? Parent::head(e) : Parent::tail(e); + /// Target of the given Edge. + Node target(const Edge &e) const { + return e.forward ? Parent::target(e) : Parent::source(e); } - /// \todo Shouldn't the "head" of an undirected edge be called "bNode" + /// \todo Shouldn't the "target" of an undirected edge be called "bNode" /// or something??? - using Parent::head; + using Parent::target; /// Returns whether the given directed edge is same orientation as the /// corresponding undirected edge. @@ -96,10 +96,10 @@ bool forward(const Edge &e) const { return e.forward; } Node oppsiteNode(const Node &n, const Edge &e) const { - if( n == Parent::tail(e)) - return Parent::head(e); - else if( n == Parent::head(e)) - return Parent::tail(e); + if( n == Parent::source(e)) + return Parent::target(e); + else if( n == Parent::target(e)) + return Parent::source(e); else return INVALID; } @@ -147,7 +147,7 @@ if( e.forward ) { Parent::nextOut(e); if( UndirEdge(e) == INVALID ) { - Parent::firstIn(e, Parent::tail(e)); + Parent::firstIn(e, Parent::source(e)); e.forward = false; } } @@ -159,7 +159,7 @@ if( e.forward ) { Parent::nextIn(e); if( UndirEdge(e) == INVALID ) { - Parent::firstOut(e, Parent::head(e)); + Parent::firstOut(e, Parent::target(e)); e.forward = false; } } diff -r 741f3108a90f -r e997802b855c src/test/bfs_test.cc --- a/src/test/bfs_test.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/test/bfs_test.cc Sat Nov 13 12:53:28 2004 +0000 @@ -83,8 +83,8 @@ for(EdgeIt e(G); e==INVALID; ++e) { - Node u=G.tail(e); - Node v=G.head(e); + Node u=G.source(e); + Node v=G.target(e); check( !bfs_test.reached(u) || (bfs_test.dist(v) > bfs_test.dist(u)+1), "Wrong output."); @@ -94,7 +94,7 @@ check(bfs_test.reached(v),"Each node should be reached."); if ( bfs_test.pred(v)!=INVALID ) { Edge e=bfs_test.pred(v); - Node u=G.tail(e); + Node u=G.source(e); check(u==bfs_test.predNode(v),"Wrong tree."); check(bfs_test.dist(v) - bfs_test.dist(u) == 1, "Wrong distance. Difference: " diff -r 741f3108a90f -r e997802b855c src/test/dfs_test.cc --- a/src/test/dfs_test.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/test/dfs_test.cc Sat Nov 13 12:53:28 2004 +0000 @@ -83,7 +83,7 @@ check(dfs_test.reached(v),"Each node should be reached."); if ( dfs_test.pred(v)!=INVALID ) { Edge e=dfs_test.pred(v); - Node u=G.tail(e); + Node u=G.source(e); check(u==dfs_test.predNode(v),"Wrong tree."); check(dfs_test.dist(v) - dfs_test.dist(u) == 1, "Wrong distance." << dfs_test.dist(v) << " " < cap[e] ) if ( dijkstra_test.reached(u) ) { - std::cout<<"Error! dist(head)-dist(tail)- edge_length= " + std::cout<<"Error! dist(target)-dist(source)- edge_length= " < cap[e] ) if ( dijkstra_test2.reached(u) ) { - std::cout<<"Error! dist(head)-dist(tail)- edge_length= " + std::cout<<"Error! dist(target)-dist(source)- edge_length= " <::iterator p=ee.begin();p!=ee.end();p++) - G.addEdge(G.head(*p),G.tail(*p)); + G.addEdge(G.target(*p),G.source(*p)); } template void checkPetersen(Graph &G) diff -r 741f3108a90f -r e997802b855c src/test/graph_test.h --- a/src/test/graph_test.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/test/graph_test.h Sat Nov 13 12:53:28 2004 +0000 @@ -53,7 +53,7 @@ typename Graph::OutEdgeIt e(G,n); for(int i=0;i::iterator p=ee.begin();p!=ee.end();p++) - G.addEdge(G.head(*p),G.tail(*p)); + G.addEdge(G.target(*p),G.source(*p)); } diff -r 741f3108a90f -r e997802b855c src/work/alpar/bfs-named-param.cc --- a/src/work/alpar/bfs-named-param.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/alpar/bfs-named-param.cc Sat Nov 13 12:53:28 2004 +0000 @@ -10,34 +10,39 @@ struct _BFS_DEFAULT_VIS {}; struct _BFS_CUSTOM_VIS {}; -template -class _BFS + +class _Bfs_Traits +{ + typedef ListGraph Graph; +} + +template +class _Bfs { public: - typedef GT Graph; - typedef VT Visited; - typedef PNT PredNode; - typedef PET PredEdge; - typedef PT Priority; - // typedef QDT QueueData; + typedef typename T::Graph Graph; + typedef typename T::Reached Reached; + typedef typename T::PredNode PredNode; + typedef typename T::PredEdge PredEdge; + typedef typename T::Priority Priority; + + typedef typename T::DefaultReachedTag DefaultReachedTag; typedef typename Graph::Node Node; typedef typename Graph::OutEdgeIt OutEdgeIt; - typedef DVT DefaultVisitedTag; - const Graph &_graph; Node _source; - Visited *_visited; + Reached *_visited; PredNode _predNode; PredEdge _predEdge; Priority _priority; - _BFS(const Graph &g, + _Bfs(const Graph &g, Node s, - Visited *v, + Reached *v, PredNode &pn, PredEdge &pe, Priority &pr) :_graph(g), _source(s), @@ -45,7 +50,7 @@ _predNode(pn), _predEdge(pe), _priority(pr) { } - int run(const _BFS_CUSTOM_VIS &) + int run(const _Bfs_CUSTOM_VIS &) { using namespace std; @@ -63,7 +68,7 @@ Node m; Node n=Q[Qt++]; for(OutEdgeIt e(_graph,n);e!=INVALID;++e) - if(!(*_visited)[m=_graph.head(e)]) { + if(!(*_visited)[m=_graph.target(e)]) { Q[Qh++]=m; _visited->set(m,true); _predNode.set(m,n); @@ -75,44 +80,44 @@ } int run(const _BFS_DEFAULT_VIS &) { - _visited= new Visited(_graph); + _visited= new Reached(_graph); int r = run(_BFS_CUSTOM_VIS()); delete _visited; return r; } - int run() { return run(DefaultVisitedTag());} + int run() { return run(DefaultReachedTag());} - template _BFS + template _Bfs setVisitMap(T &t) { - return _BFS + return _Bfs (_graph,_source,&t,_predNode,_predEdge,_priority); } template - _BFS + _Bfs setPredNodeMap(T &t) { - return _BFS + return _BFS (_graph,_source, _visited, t,_predEdge,_priority); } template - _BFS + _BFS setPredEdgeMap(T &t) { - return _BFS + return _BFS (_graph,_source, _visited, _predNode,t,_priority); } - _BFS + _Bfs setNothing() { - return _BFS + return _Bfs (_graph,_source, _visited, _predNode,_predEdge,_priority); @@ -121,7 +126,7 @@ template -_BFS, _BFS_DEFAULT_VIS, NullMap, @@ -131,7 +136,7 @@ { // typename G::template NodeMap v(g); - return _BFS < G, + return _Bfs < G, typename G::template NodeMap, _BFS_DEFAULT_VIS, NullMap, @@ -146,11 +151,11 @@ } -class MyVisitedMap : public SmartGraph::NodeMap +class MyReachedMap : public SmartGraph::NodeMap { const SmartGraph &_G; public: - MyVisitedMap(const SmartGraph &G) : SmartGraph::NodeMap(G), _G(G) {} + MyReachedMap(const SmartGraph &G) : SmartGraph::NodeMap(G), _G(G) {} void set(SmartGraph::Node n,bool b) { SmartGraph::NodeMap::set(n,b); @@ -180,7 +185,7 @@ SmartGraph::NodeMap m(G); SmartGraph::NodeMap em(G); - MyVisitedMap vm(G); + MyReachedMap vm(G); //Runs BFS on graph 'G' from node 's'. diff -r 741f3108a90f -r e997802b855c src/work/alpar/boolmap_iter.cc --- a/src/work/alpar/boolmap_iter.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/alpar/boolmap_iter.cc Sat Nov 13 12:53:28 2004 +0000 @@ -119,13 +119,13 @@ std::cout << true << '\n'; for(EdgeIt e(G);G.valid(e);G.next(e)) - std::cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) + std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) << ": " << map[e] << '\n'; std::cout << "True Edges:\n"; for(BoolIterEdgeMap::TrueIterator i(map);i;++i) - std::cout << G.id(G.tail(i)) << "->" << G.id(G.head(i)) << '\n'; + std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n'; std::cout << "False Edges:\n"; for(BoolIterEdgeMap::FalseIterator i(map);i;++i) - std::cout << G.id(G.tail(i)) << "->" << G.id(G.head(i)) << '\n'; + std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n'; } diff -r 741f3108a90f -r e997802b855c src/work/alpar/dijkstra.h --- a/src/work/alpar/dijkstra.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/alpar/dijkstra.h Sat Nov 13 12:53:28 2004 +0000 @@ -393,7 +393,7 @@ for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { - Node w=G->head(e); + Node w=G->target(e); switch(heap.state(w)) { case Heap::PRE_HEAP: heap.push(w,oldvalue+(*length)[e]); diff -r 741f3108a90f -r e997802b855c src/work/alpar/f_ed_ka.h --- a/src/work/alpar/f_ed_ka.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/alpar/f_ed_ka.h Sat Nov 13 12:53:28 2004 +0000 @@ -84,17 +84,17 @@ aug_val = visited.get(t)==1 ? c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t)); //FIXME: I would need 'G.opposite(e,n)' - gn = visited.get(t)==1 ? G.tail(tree.get(t)) : G.head(tree.get(t)); + gn = visited.get(t)==1 ? G.source(tree.get(t)) : G.target(tree.get(t)); while(gn!=s) if(visited.get(gn)==1) { //FIXME: nonstandard gcc extension! aug_val (); e.valid(); ++e) { - // std::cout<<"("<"<"<From();return i;} - NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;} + NodeIterator source() const {NodeIterator i;i.G=G;i.n=e->From();return i;} + NodeIterator target() const {NodeIterator i;i.G=G;i.n=e->To();return i;} NodeIterator opposite(const NodeIterator &n) const - {return n==tail()?head():tail();} + {return n==source()?target():source();} bool valid() {return e;} E &operator*() const { return G->Data(e); } @@ -190,8 +190,8 @@ OutEdgeIterator operator++(int) {OutEdgeIterator tmp(*this); goNext(); return tmp;} - NodeIterator aNode() const {return tail();} - NodeIterator bNode() const {return head();} + NodeIterator aNode() const {return source();} + NodeIterator bNode() const {return target();} operator const InEdgeIterator () {InEdgeIterator i; i.G=G;i.e=e;return i;} @@ -218,7 +218,7 @@ {SymEdgeIterator tmp(*this); goNext(); return tmp;} NodeIterator aNode() const {return n;} - NodeIterator bNode() const {return n.n==tail().n?head():tail();} + NodeIterator bNode() const {return n.n==source().n?target():source();} operator const InEdgeIterator () {InEdgeIterator i; i.G=G;i.e=e;return i;} @@ -254,7 +254,7 @@ NodeIterator aNode() const {return n;} - NodeIterator bNode() const {return n.n==tail().n?head():tail();} + NodeIterator bNode() const {return n.n==source().n?target():source();} operator const EdgeIterator () {EdgeIterator i; i.G=G;i.e=e;return i;} @@ -463,14 +463,14 @@ NodeIterator GetNode(int n) // What about path of length 1? { return n? - reversed[n-1]?path[n-1].tail():path[n-1].head(): - reversed[0]?path[0].head():path[0].tail(); + reversed[n-1]?path[n-1].source():path[n-1].target(): + reversed[0]?path[0].target():path[0].source(); } void setRevert(int n,bool r=true) {reversed[n]=r;} void setEdge(int n,SymEdgeIterator i) { path[n]=i; - reversed[n] = i.head()==i.aNode(); + reversed[n] = i.target()==i.aNode(); } void setEdge(int n,EdgeIterator i,bool r) { @@ -478,8 +478,8 @@ reversed[n] = r; } - NodeIterator tail() { return getNode(0); } - NodeIterator head() { return getNode(getLength()); } + NodeIterator source() { return getNode(0); } + NodeIterator target() { return getNode(getLength()); } }; /* Ez itt a fiam kommentje: diff -r 741f3108a90f -r e997802b855c src/work/alpar/gwrapper.h --- a/src/work/alpar/gwrapper.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/alpar/gwrapper.h Sat Nov 13 12:53:28 2004 +0000 @@ -27,10 +27,10 @@ template I next(const I i); { return graph->goNext(i); } template I &goNext(I &i); { return graph->goNext(i); } - NodeIt head(const EdgeIt &e); - { return graph->head(e); } - NodeIt tail(const EdgeIt &e); - { return graph->tail(e); } + NodeIt target(const EdgeIt &e); + { return graph->target(e); } + NodeIt source(const EdgeIt &e); + { return graph->source(e); } template NodeIt aNode(const I e); { return graph->aNode(e); } @@ -83,10 +83,10 @@ template I next(const I i); { return graph->goNext(i); } template I &goNext(I &i); { return graph->goNext(i); } - NodeIt head(const EdgeIt &e); - { return graph->tail(e); } - NodeIt tail(const EdgeIt &e); - { return graph->head(e); } + NodeIt target(const EdgeIt &e); + { return graph->source(e); } + NodeIt source(const EdgeIt &e); + { return graph->target(e); } template NodeIt aNode(const I e); { return graph->aNode(e); } @@ -137,10 +137,10 @@ // template I next(const I i); { return graph->goNext(i); } // template I &goNext(I &i); { return graph->goNext(i); } - NodeIt head(const EdgeIt &e); - { return G::tail(e); } - NodeIt tail(const EdgeIt &e); - { return G::head(e); } + NodeIt target(const EdgeIt &e); + { return G::source(e); } + NodeIt source(const EdgeIt &e); + { return G::target(e); } // template NodeIt aNode(const I e); // { return graph->aNode(e); } @@ -194,10 +194,10 @@ template I next(const I i); { return graph->goNext(i); } template I &goNext(I &i); { return graph->goNext(i); } - NodeIt head(const EdgeIt &e); - { return graph->head(e); } - NodeIt tail(const EdgeIt &e); - { return graph->tail(e); } + NodeIt target(const EdgeIt &e); + { return graph->target(e); } + NodeIt source(const EdgeIt &e); + { return graph->source(e); } template NodeIt aNode(const I e); { return graph->aNode(e); } @@ -343,10 +343,10 @@ template I &goNext(I &i); { return graph->goNext(i); } template I next(const I i); { return graph->goNext(i); } - NodeIt head(const EdgeIt &e); - { return graph->head(e); } - NodeIt tail(const EdgeIt &e); - { return graph->tail(e); } + NodeIt target(const EdgeIt &e); + { return graph->target(e); } + NodeIt source(const EdgeIt &e); + { return graph->source(e); } template NodeIt aNode(const I e); { return graph->aNode(e); } diff -r 741f3108a90f -r e997802b855c src/work/alpar/list_graph_demo.cc --- a/src/work/alpar/list_graph_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/alpar/list_graph_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -111,10 +111,10 @@ Graph::SymEdgeMap sm(G); for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e); for(EdgeIt e(G);G.valid(e);G.next(e)) - if(G.tail(e)" << G.id(G.head(e)) + std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e)) << " em=" << em[e] << " sm=" << sm[e] << "\n"; diff -r 741f3108a90f -r e997802b855c src/work/alpar/rw_nonref_map.cc --- a/src/work/alpar/rw_nonref_map.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/alpar/rw_nonref_map.cc Sat Nov 13 12:53:28 2004 +0000 @@ -23,15 +23,15 @@ operator ValueType() const { ValueType tmp; - std::cout << G.id(G.tail(e)) << "->" - << G.id(G.head(e)) << ": "; + std::cout << G.id(G.source(e)) << "->" + << G.id(G.target(e)) << ": "; std::cin >> tmp; return tmp; } ValueType operator = (ValueType v) const { - std::cout << G.id(G.tail(e)) << "->" - << G.id(G.head(e)) << ": " << v << '\n'; + std::cout << G.id(G.source(e)) << "->" + << G.id(G.target(e)) << ": " << v << '\n'; return v; } }; diff -r 741f3108a90f -r e997802b855c src/work/alpar/smart_graph_demo.cc --- a/src/work/alpar/smart_graph_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/alpar/smart_graph_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -111,10 +111,10 @@ Graph::SymEdgeMap sm(G); for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e); for(EdgeIt e(G);G.valid(e);G.next(e)) - if(G.tail(e)" << G.id(G.head(e)) + std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e)) << " em=" << em[e] << " sm=" << sm[e] << "\n"; diff -r 741f3108a90f -r e997802b855c src/work/athos/bfs_test.cc --- a/src/work/athos/bfs_test.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/athos/bfs_test.cc Sat Nov 13 12:53:28 2004 +0000 @@ -41,7 +41,7 @@ bfs_queue.pop(); OutEdgeIt e; for(g.first(e,v); g.valid(e); g.next(e)) { - Node w=g.head(e); + Node w=g.target(e); if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); diff -r 741f3108a90f -r e997802b855c src/work/athos/dijkstra_demo.cc --- a/src/work/athos/dijkstra_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/athos/dijkstra_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -129,10 +129,10 @@ std::cout << node_name.get(i) << ": "; std::cout << "out edges: "; for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) - std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; + std::cout << node_name.get(flow_test.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.target(j)) << " "; std::cout << "in edges: "; for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) - std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; + std::cout << node_name.get(flow_test.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.target(j)) << " "; std::cout << std::endl; } */ diff -r 741f3108a90f -r e997802b855c src/work/athos/mincostflow.h --- a/src/work/athos/mincostflow.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/athos/mincostflow.h Sat Nov 13 12:53:28 2004 +0000 @@ -73,9 +73,9 @@ ValueType operator[](typename ResGraph::Edge e) const { if (res_graph.forward(e)) - return ol[e]-(pot[res_graph.head(e)]-pot[res_graph.tail(e)]); + return ol[e]-(pot[res_graph.target(e)]-pot[res_graph.source(e)]); else - return -ol[e]-(pot[res_graph.head(e)]-pot[res_graph.tail(e)]); + return -ol[e]-(pot[res_graph.target(e)]-pot[res_graph.source(e)]); } ModCostMap(const ResGraph& _res_graph, @@ -258,8 +258,8 @@ typename std::list::iterator i = nonabundant_arcs.begin(); while ( i != nonabundant_arcs.end() ){ if (flow[*i]>=buf){ - Node a = abundant_components.find(res_graph.head(*i)); - Node b = abundant_components.find(res_graph.tail(*i)); + Node a = abundant_components.find(res_graph.target(*i)); + Node b = abundant_components.find(res_graph.source(*i)); //Merge if (a != b){ abundant_components.join(a,b); @@ -284,7 +284,7 @@ ResGraphEdge e; while (n!=non_root){ e = bfs_pred[n]; - n = res_graph.tail(e); + n = res_graph.source(e); res_graph.augment(e,qty_to_augment); } @@ -454,7 +454,7 @@ Cost fl_e; FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){ //C^{\Pi}_{i,j} - mod_pot = cost[e]-potential[graph.head(e)]+potential[graph.tail(e)]; + mod_pot = cost[e]-potential[graph.target(e)]+potential[graph.source(e)]; fl_e = flow[e]; // std::cout << fl_e << std::endl; if (mod_pot > 0 && fl_e != 0) @@ -483,8 +483,8 @@ return false; } - supdem[graph.tail(e)] += flow[e]; - supdem[graph.head(e)] -= flow[e]; + supdem[graph.source(e)] += flow[e]; + supdem[graph.target(e)] -= flow[e]; } //write_property_vector(supdem, "supdem"); //write_property_vector(supply_demand, "supply_demand"); diff -r 741f3108a90f -r e997802b855c src/work/athos/old/minlengthpaths.h --- a/src/work/athos/old/minlengthpaths.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/athos/old/minlengthpaths.h Sat Nov 13 12:53:28 2004 +0000 @@ -53,10 +53,10 @@ typedef typename LengthMap::ValueType ValueType; ValueType operator[](typename ResGraphType::Edge e) const { - //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){ + //if ( (1-2*rev[e])*ol[e]-(pot[G.target(e)]-pot[G.source(e)] ) <0 ){ // std::cout<<"Negative length!!"<(s); G.valid(j); G.next(j)){ modify_preflow(j,capacity[j] ); - make_active(G.head(j)); - int lev=level[G.head(j)]; + make_active(G.target(j)); + int lev=level[G.target(j)]; if(highest_activepreflow[j]){ - if(level[G.tail(j)]==level[G.head(j)]+1){ + if(level[G.source(j)]==level[G.target(j)]+1){ return true; } else{ - if (level[G.head(j)] < new_level) - new_level=level[G.head(j)]; + if (level[G.target(j)] < new_level) + new_level=level[G.target(j)]; } } return false; @@ -341,13 +341,13 @@ bool is_admissible_backward_edge(Edge j, int& new_level){ if (0first(e,w) ; g->valid(e); g->next(e)) { - Node v=g->head(e); + Node v=g->target(e); if (!M[v] && (*flow)[e] < (*capacity)[e] ) { queue.push(v); M.set(v, true); @@ -335,7 +335,7 @@ InEdgeIt f; for(g->first(f,w) ; g->valid(f); g->next(f)) { - Node v=g->tail(f); + Node v=g->source(f); if (!M[v] && (*flow)[f] > 0 ) { queue.push(v); M.set(v, true); @@ -370,7 +370,7 @@ InEdgeIt e; for(g->first(e,w) ; g->valid(e); g->next(e)) { - Node v=g->tail(e); + Node v=g->source(e); if (M[v] && (*flow)[e] < (*capacity)[e] ) { queue.push(v); M.set(v, false); @@ -379,7 +379,7 @@ OutEdgeIt f; for(g->first(f,w) ; g->valid(f); g->next(f)) { - Node v=g->head(f); + Node v=g->target(f); if (M[v] && (*flow)[f] > 0 ) { queue.push(v); M.set(v, false); @@ -433,7 +433,7 @@ for(g->first(e,w); g->valid(e); g->next(e)) { if ( (*flow)[e] >= (*capacity)[e] ) continue; - Node v=g->head(e); + Node v=g->target(e); if( lev > level[v] ) { //Push is allowed now @@ -466,7 +466,7 @@ for(g->first(e,w); g->valid(e); g->next(e)) { if( (*flow)[e] <= 0 ) continue; - Node v=g->tail(e); + Node v=g->source(e); if( lev > level[v] ) { //Push is allowed now @@ -521,7 +521,7 @@ InEdgeIt e; for(g->first(e,v); g->valid(e); g->next(e)) { - Node w=g->tail(e); + Node w=g->source(e); if ( level[w] == n && w != s ) { bfs_queue.push(w); Node first=level_list[l]; @@ -539,7 +539,7 @@ { Num c=(*capacity)[e]; if ( c <= 0 ) continue; - Node w=g->head(e); + Node w=g->target(e); if ( level[w] < n ) { if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); flow->set(e, c); @@ -566,7 +566,7 @@ InEdgeIt e; for(g->first(e,v); g->valid(e); g->next(e)) { if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node w=g->tail(e); + Node w=g->source(e); if ( level[w] == n && w != s ) { bfs_queue.push(w); Node first=level_list[l]; @@ -580,7 +580,7 @@ OutEdgeIt f; for(g->first(f,v); g->valid(f); g->next(f)) { if ( 0 >= (*flow)[f] ) continue; - Node w=g->head(f); + Node w=g->target(f); if ( level[w] == n && w != s ) { bfs_queue.push(w); Node first=level_list[l]; @@ -599,7 +599,7 @@ { Num rem=(*capacity)[e]-(*flow)[e]; if ( rem <= 0 ) continue; - Node w=g->head(e); + Node w=g->target(e); if ( level[w] < n ) { if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); flow->set(e, (*capacity)[e]); @@ -611,7 +611,7 @@ for(g->first(f,s); g->valid(f); g->next(f)) { if ( (*flow)[f] <= 0 ) continue; - Node w=g->tail(f); + Node w=g->source(f); if ( level[w] < n ) { if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); excess.set(w, excess[w]+(*flow)[f]); @@ -710,9 +710,9 @@ // int get(const typename MapGraphWrapper::Node& n) const { // return dist[n]; } // bool get(const typename MapGraphWrapper::Edge& e) const { - // return (dist.get(g->tail(e))head(e))); } + // return (dist.get(g->source(e))target(e))); } bool operator[](const typename MapGraphWrapper::Edge& e) const { - return (dist[g->tail(e)]head(e)]); + return (dist[g->source(e)]target(e)]); } }; @@ -860,7 +860,7 @@ InEdgeIt e; for(g->first(e,v); g->valid(e); g->next(e)) { if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node u=g->tail(e); + Node u=g->source(e); if ( level[u] >= n ) { bfs_queue.push(u); level.set(u, l); @@ -871,7 +871,7 @@ OutEdgeIt f; for(g->first(f,v); g->valid(f); g->next(f)) { if ( 0 >= (*flow)[f] ) continue; - Node u=g->head(f); + Node u=g->target(f); if ( level[u] >= n ) { bfs_queue.push(u); level.set(u, l); @@ -925,15 +925,15 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); + Node v=res_graph.source(e); + Node w=res_graph.target(e); pred.set(w, e); if (res_graph.valid(pred[v])) { free.set(w, std::min(free[v], res_graph.resCap(e))); } else { free.set(w, res_graph.resCap(e)); } - if (res_graph.head(e)==t) { _augment=true; break; } + if (res_graph.target(e)==t) { _augment=true; break; } } ++bfs; @@ -945,7 +945,7 @@ while (res_graph.valid(pred[n])) { ResGWEdge e=pred[n]; res_graph.augment(e, augment_value); - n=res_graph.tail(e); + n=res_graph.source(e); } } @@ -983,15 +983,15 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); + Node v=res_graph.source(e); + Node w=res_graph.target(e); pred.set(w, e); if (res_graph.valid(pred[v])) { free.set(w, std::min(free[v], res_graph.resCap(e))); } else { free.set(w, res_graph.resCap(e)); } - if (res_graph.head(e)==t) { _augment=true; break; } + if (res_graph.target(e)==t) { _augment=true; break; } } ++bfs; @@ -1003,7 +1003,7 @@ while (res_graph.valid(pred[n])) { ResGWEdge e=pred[n]; res_graph.augment(e, augment_value); - n=res_graph.tail(e); + n=res_graph.source(e); } } @@ -1050,17 +1050,17 @@ ResGWOutEdgeIt e=bfs; if (res_graph.valid(e)) { if (bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], - res_graph_to_F[res_graph.head(e)]); + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], + res_graph_to_F[res_graph.target(e)]); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); residual_capacity.set(f, res_graph.resCap(e)); } else { - if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], - res_graph_to_F[res_graph.head(e)]); + if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], + res_graph_to_F[res_graph.target(e)]); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); @@ -1114,7 +1114,7 @@ while (F.valid(pred[n])) { typename MG::Edge e=pred[n]; res_graph.augment(original_edge[e], augment_value); - n=F.tail(e); + n=F.source(e); if (residual_capacity[e]==augment_value) F.erase(e); else @@ -1147,7 +1147,7 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); } ++bfs; } //computing distances from s in the residual graph @@ -1247,7 +1247,7 @@ while (erasing_res_graph.valid(pred[n])) { typename ErasingResGW::OutEdgeIt e=pred[n]; res_graph.augment(e, augment_value); - n=erasing_res_graph.tail(e); + n=erasing_res_graph.source(e); if (res_graph.resCap(e)==0) erasing_res_graph.erase(e); } diff -r 741f3108a90f -r e997802b855c src/work/jacint/max_flow_bug.cc --- a/src/work/jacint/max_flow_bug.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/jacint/max_flow_bug.cc Sat Nov 13 12:53:28 2004 +0000 @@ -42,14 +42,14 @@ int min_min_cut_value=0; EdgeIt e; for(G.first(e); G.valid(e); G.next(e)) { - if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e]; + if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; } Graph::NodeMap cut(G); max_flow_test_no_stack.minCut(cut); int min_cut_value=0; for(G.first(e); G.valid(e); G.next(e)) { - if (cut[G.tail(e)] && !cut[G.head(e)]) + if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=cap[e]; } @@ -57,7 +57,7 @@ max_flow_test_no_stack.maxMinCut(maxcut); int max_min_cut_value=0; for(G.first(e); G.valid(e); G.next(e)) { - if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) + if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=cap[e]; } @@ -88,14 +88,14 @@ max_flow_test.minMinCut(mincut2); int min_min_cut_value2=0; for(G.first(e); G.valid(e); G.next(e)) { - if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e]; + if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; } Graph::NodeMap cut2(G); max_flow_test.minCut(cut2); int min_cut_value2=0; for(G.first(e); G.valid(e); G.next(e)) { - if (cut2[G.tail(e)] && !cut2[G.head(e)]) + if (cut2[G.source(e)] && !cut2[G.target(e)]) min_cut_value2+=cap[e]; } @@ -103,7 +103,7 @@ max_flow_test.maxMinCut(maxcut2); int max_min_cut_value2=0; for(G.first(e); G.valid(e); G.next(e)) { - if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) + if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) max_min_cut_value2+=cap[e]; } @@ -127,14 +127,14 @@ max_flow_test3.minMinCut(mincut3); int min_min_cut_value3=0; for(G.first(e); G.valid(e); G.next(e)) { - if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e]; + if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; } Graph::NodeMap cut3(G); max_flow_test3.minCut(cut3); int min_cut_value3=0; for(G.first(e); G.valid(e); G.next(e)) { - if (cut3[G.tail(e)] && !cut3[G.head(e)]) + if (cut3[G.source(e)] && !cut3[G.target(e)]) min_cut_value3+=cap[e]; } @@ -142,7 +142,7 @@ max_flow_test3.maxMinCut(maxcut3); int max_min_cut_value3=0; for(G.first(e); G.valid(e); G.next(e)) { - if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) + if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) max_min_cut_value3+=cap[e]; } diff -r 741f3108a90f -r e997802b855c src/work/jacint/max_flow_test.cc --- a/src/work/jacint/max_flow_test.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/jacint/max_flow_test.cc Sat Nov 13 12:53:28 2004 +0000 @@ -45,14 +45,14 @@ int min_min_cut_value=0; EdgeIt e; for(G.first(e); G.valid(e); G.next(e)) { - if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e]; + if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; } Graph::NodeMap cut(G); max_flow_test_no_stack.minCut(cut); int min_cut_value=0; for(G.first(e); G.valid(e); G.next(e)) { - if (cut[G.tail(e)] && !cut[G.head(e)]) + if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=cap[e]; } @@ -60,7 +60,7 @@ max_flow_test_no_stack.maxMinCut(maxcut); int max_min_cut_value=0; for(G.first(e); G.valid(e); G.next(e)) { - if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) + if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=cap[e]; } @@ -91,14 +91,14 @@ max_flow_test.minMinCut(mincut2); int min_min_cut_value2=0; for(G.first(e); G.valid(e); G.next(e)) { - if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e]; + if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; } Graph::NodeMap cut2(G); max_flow_test.minCut(cut2); int min_cut_value2=0; for(G.first(e); G.valid(e); G.next(e)) { - if (cut2[G.tail(e)] && !cut2[G.head(e)]) + if (cut2[G.source(e)] && !cut2[G.target(e)]) min_cut_value2+=cap[e]; } @@ -106,7 +106,7 @@ max_flow_test.maxMinCut(maxcut2); int max_min_cut_value2=0; for(G.first(e); G.valid(e); G.next(e)) { - if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) + if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) max_min_cut_value2+=cap[e]; } @@ -130,14 +130,14 @@ max_flow_test3.minMinCut(mincut3); int min_min_cut_value3=0; for(G.first(e); G.valid(e); G.next(e)) { - if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e]; + if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; } Graph::NodeMap cut3(G); max_flow_test3.minCut(cut3); int min_cut_value3=0; for(G.first(e); G.valid(e); G.next(e)) { - if (cut3[G.tail(e)] && !cut3[G.head(e)]) + if (cut3[G.source(e)] && !cut3[G.target(e)]) min_cut_value3+=cap[e]; } @@ -145,7 +145,7 @@ max_flow_test3.maxMinCut(maxcut3); int max_min_cut_value3=0; for(G.first(e); G.valid(e); G.next(e)) { - if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) + if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) max_min_cut_value3+=cap[e]; } diff -r 741f3108a90f -r e997802b855c src/work/jacint/max_matching.cc --- a/src/work/jacint/max_matching.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/jacint/max_matching.cc Sat Nov 13 12:53:28 2004 +0000 @@ -190,8 +190,8 @@ bool noedge=true; EdgeIt e; for(G.first(e); G.valid(e); G.next(e) ) { - if ( (pos[G.head(e)]==max_matching.C && pos[G.tail(e)]==max_matching.D) || - (pos[G.head(e)]==max_matching.D && pos[G.tail(e)]==max_matching.C) ) + if ( (pos[G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) || + (pos[G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) ) noedge=false; } if ( noedge ) std::cout<<"OK"<first(e,w) ; g->valid(e); g->next(e)) { - Node v=g->head(e); + Node v=g->target(e); if (!M[v] && (*flow)[e] < (*capacity)[e] ) { queue.push(v); M.set(v, true); @@ -267,7 +267,7 @@ InEdgeIt f; for(g->first(f,w) ; g->valid(f); g->next(f)) { - Node v=g->tail(f); + Node v=g->source(f); if (!M[v] && (*flow)[f] > 0 ) { queue.push(v); M.set(v, true); @@ -304,7 +304,7 @@ InEdgeIt e; for(g->first(e,w) ; g->valid(e); g->next(e)) { - Node v=g->tail(e); + Node v=g->source(e); if (M[v] && (*flow)[e] < (*capacity)[e] ) { queue.push(v); M.set(v, false); @@ -313,7 +313,7 @@ OutEdgeIt f; for(g->first(f,w) ; g->valid(f); g->next(f)) { - Node v=g->head(f); + Node v=g->target(f); if (M[v] && (*flow)[f] > 0 ) { queue.push(v); M.set(v, false); @@ -369,7 +369,7 @@ for(g->first(e,w); g->valid(e); g->next(e)) { if ( (*flow)[e] >= (*capacity)[e] ) continue; - Node v=g->head(e); + Node v=g->target(e); if( lev > level[v] ) { //Push is allowed now @@ -402,7 +402,7 @@ for(g->first(e,w); g->valid(e); g->next(e)) { if( (*flow)[e] <= 0 ) continue; - Node v=g->tail(e); + Node v=g->source(e); if( lev > level[v] ) { //Push is allowed now @@ -456,7 +456,7 @@ InEdgeIt e; for(g->first(e,v); g->valid(e); g->next(e)) { - Node w=g->tail(e); + Node w=g->source(e); if ( level[w] == n && w != s ) { bfs_queue.push(w); Node first=level_list[l]; @@ -474,7 +474,7 @@ { Num c=(*capacity)[e]; if ( c <= 0 ) continue; - Node w=g->head(e); + Node w=g->target(e); if ( level[w] < n ) { if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); flow->set(e, c); @@ -501,7 +501,7 @@ InEdgeIt e; for(g->first(e,v); g->valid(e); g->next(e)) { if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node w=g->tail(e); + Node w=g->source(e); if ( level[w] == n && w != s ) { bfs_queue.push(w); Node first=level_list[l]; @@ -515,7 +515,7 @@ OutEdgeIt f; for(g->first(f,v); g->valid(f); g->next(f)) { if ( 0 >= (*flow)[f] ) continue; - Node w=g->head(f); + Node w=g->target(f); if ( level[w] == n && w != s ) { bfs_queue.push(w); Node first=level_list[l]; @@ -534,7 +534,7 @@ { Num rem=(*capacity)[e]-(*flow)[e]; if ( rem <= 0 ) continue; - Node w=g->head(e); + Node w=g->target(e); if ( level[w] < n ) { if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); flow->set(e, (*capacity)[e]); @@ -546,7 +546,7 @@ for(g->first(f,s); g->valid(f); g->next(f)) { if ( (*flow)[f] <= 0 ) continue; - Node w=g->tail(f); + Node w=g->source(f); if ( level[w] < n ) { if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); excess.set(w, excess[w]+(*flow)[f]); @@ -644,9 +644,9 @@ // int get(const typename MapGraphWrapper::Node& n) const { // return dist[n]; } // bool get(const typename MapGraphWrapper::Edge& e) const { - // return (dist.get(g->tail(e))head(e))); } + // return (dist.get(g->source(e))target(e))); } bool operator[](const typename MapGraphWrapper::Edge& e) const { - return (dist[g->tail(e)]head(e)]); + return (dist[g->source(e)]target(e)]); } }; @@ -783,7 +783,7 @@ InEdgeIt e; for(g->first(e,v); g->valid(e); g->next(e)) { if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node u=g->tail(e); + Node u=g->source(e); if ( level[u] >= n ) { bfs_queue.push(u); level.set(u, l); @@ -794,7 +794,7 @@ OutEdgeIt f; for(g->first(f,v); g->valid(f); g->next(f)) { if ( 0 >= (*flow)[f] ) continue; - Node u=g->head(f); + Node u=g->target(f); if ( level[u] >= n ) { bfs_queue.push(u); level.set(u, l); @@ -846,15 +846,15 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); + Node v=res_graph.source(e); + Node w=res_graph.target(e); pred.set(w, e); if (res_graph.valid(pred[v])) { free.set(w, std::min(free[v], res_graph.resCap(e))); } else { free.set(w, res_graph.resCap(e)); } - if (res_graph.head(e)==t) { _augment=true; break; } + if (res_graph.target(e)==t) { _augment=true; break; } } ++bfs; @@ -866,7 +866,7 @@ while (res_graph.valid(pred[n])) { ResGWEdge e=pred[n]; res_graph.augment(e, augment_value); - n=res_graph.tail(e); + n=res_graph.source(e); } } @@ -919,15 +919,15 @@ ResGWOutEdgeIt e=bfs; if (res_graph.valid(e)) { if (bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); residual_capacity.set(f, res_graph.resCap(e)); } else { - if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); + if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); @@ -981,7 +981,7 @@ while (F.valid(pred[n])) { typename MG::Edge e=pred[n]; res_graph.augment(original_edge[e], augment_value); - n=F.tail(e); + n=F.source(e); if (residual_capacity[e]==augment_value) F.erase(e); else @@ -1015,7 +1015,7 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); } ++bfs; } //computing distances from s in the residual graph @@ -1112,7 +1112,7 @@ while (erasing_res_graph.valid(pred[n])) { typename ErasingResGW::OutEdgeIt e=pred[n]; res_graph.augment(e, augment_value); - n=erasing_res_graph.tail(e); + n=erasing_res_graph.source(e); if (res_graph.resCap(e)==0) erasing_res_graph.erase(e); } diff -r 741f3108a90f -r e997802b855c src/work/jacint/preflow.cc --- a/src/work/jacint/preflow.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/jacint/preflow.cc Sat Nov 13 12:53:28 2004 +0000 @@ -46,9 +46,9 @@ EdgeIt e; for(G.first(e); G.valid(e); G.next(e)) { int c=cap[e]; - if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=c; - if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=c; - if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) max_min_cut_value+=c; + if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=c; + if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=c; + if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=c; } std::cout << "\nChecking the result: " <= n ) { bfs_queue.push(u); level.set(u, l); @@ -314,7 +314,7 @@ OutEdgeIt f; for(G.first(f,v); G.valid(f); G.next(f)) { if ( 0 == flow[f] ) continue; - Node u=G.head(f); + Node u=G.target(f); if ( level[u] >= n ) { bfs_queue.push(u); level.set(u, l); @@ -343,7 +343,7 @@ for(G.first(e,w); G.valid(e); G.next(e)) { if ( flow[e] == capacity[e] ) continue; - Node v=G.head(e); + Node v=G.target(e); //e=wv if( lev > level[v] ) { @@ -385,7 +385,7 @@ for(G.first(e,w); G.valid(e); G.next(e)) { if( flow[e] == 0 ) continue; - Node v=G.tail(e); + Node v=G.source(e); //e=vw if( lev > level[v] ) { @@ -569,7 +569,7 @@ OutEdgeIt e; for(G.first(e,w) ; G.valid(e); G.next(e)) { - Node v=G.head(e); + Node v=G.target(e); if (!M[v] && flow[e] < capacity[e] ) { queue.push(v); M.set(v, true); @@ -578,7 +578,7 @@ InEdgeIt f; for(G.first(f,w) ; G.valid(f); G.next(f)) { - Node v=G.tail(f); + Node v=G.source(f); if (!M[v] && flow[f] > 0 ) { queue.push(v); M.set(v, true); @@ -609,7 +609,7 @@ InEdgeIt e; for(G.first(e,w) ; G.valid(e); G.next(e)) { - Node v=G.tail(e); + Node v=G.source(e); if (!M[v] && flow[e] < capacity[e] ) { queue.push(v); M.set(v, true); @@ -618,7 +618,7 @@ OutEdgeIt f; for(G.first(f,w) ; G.valid(f); G.next(f)) { - Node v=G.head(f); + Node v=G.target(f); if (!M[v] && flow[f] > 0 ) { queue.push(v); M.set(v, true); diff -r 741f3108a90f -r e997802b855c src/work/jacint/preflow_excess_test.cc --- a/src/work/jacint/preflow_excess_test.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/jacint/preflow_excess_test.cc Sat Nov 13 12:53:28 2004 +0000 @@ -52,14 +52,14 @@ int min_min_cut_value=0; EdgeIt e; for(G.first(e); G.valid(e); G.next(e)) { - if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e]; + if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; } Graph::NodeMap cut(G); max_flow_test.minCut(cut); int min_cut_value=0; for(G.first(e); G.valid(e); G.next(e)) { - if (cut[G.tail(e)] && !cut[G.head(e)]) + if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=cap[e]; } @@ -67,7 +67,7 @@ max_flow_test.maxMinCut(maxcut); int max_min_cut_value=0; for(G.first(e); G.valid(e); G.next(e)) { - if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) + if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=cap[e]; } @@ -99,14 +99,14 @@ max_flow_test2.minMinCut(mincut2); int min_min_cut_value2=0; for(G.first(e); G.valid(e); G.next(e)) { - if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e]; + if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; } Graph::NodeMap cut2(G); max_flow_test2.minCut(cut2); int min_cut_value2=0; for(G.first(e); G.valid(e); G.next(e)) { - if (cut2[G.tail(e)] && !cut2[G.head(e)]) + if (cut2[G.source(e)] && !cut2[G.target(e)]) min_cut_value2+=cap[e]; } @@ -114,7 +114,7 @@ max_flow_test2.maxMinCut(maxcut2); int max_min_cut_value2=0; for(G.first(e); G.valid(e); G.next(e)) { - if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) + if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) max_min_cut_value2+=cap[e]; } @@ -144,14 +144,14 @@ max_flow_test3.minMinCut(mincut3); int min_min_cut_value3=0; for(G.first(e); G.valid(e); G.next(e)) { - if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e]; + if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; } Graph::NodeMap cut3(G); max_flow_test3.minCut(cut3); int min_cut_value3=0; for(G.first(e); G.valid(e); G.next(e)) { - if (cut3[G.tail(e)] && !cut3[G.head(e)]) + if (cut3[G.source(e)] && !cut3[G.target(e)]) min_cut_value3+=cap[e]; } @@ -159,7 +159,7 @@ max_flow_test3.maxMinCut(maxcut3); int max_min_cut_value3=0; for(G.first(e); G.valid(e); G.next(e)) { - if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) + if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) max_min_cut_value3+=cap[e]; } diff -r 741f3108a90f -r e997802b855c src/work/jacint/preflow_res.h --- a/src/work/jacint/preflow_res.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/jacint/preflow_res.h Sat Nov 13 12:53:28 2004 +0000 @@ -102,7 +102,7 @@ ResInEdgeIt e; for(res_graph.first(e,v); res_graph.valid(e); res_graph.next(e)) { - Node w=res_graph.tail(e); + Node w=res_graph.source(e); if ( level[w] == n && w != s ) { bfs_queue.push(w); Node first=level_list[l]; @@ -145,7 +145,7 @@ ResOutEdgeIt e; for(res_graph.first(e,s); res_graph.valid(e); res_graph.next(e)) { - Node w=res_graph.head(e); + Node w=res_graph.target(e); if ( level[w] < n ) { if ( excess[w] == 0 && w!=t ) { next.set(w,active[level[w]]); @@ -190,7 +190,7 @@ ResInEdgeIt e; for(res_graph.first(e,v); res_graph.valid(e); res_graph.next(e)) { - Node u=res_graph.tail(e); + Node u=res_graph.source(e); if ( level[u] >= n ) { bfs_queue.push(u); level.set(u, l); @@ -221,7 +221,7 @@ ResOutEdgeIt e; for(res_graph.first(e,w); res_graph.valid(e); res_graph.next(e)) { - Node v=res_graph.head(e); + Node v=res_graph.target(e); if( lev > level[v] ) { /*Push is allowed now*/ @@ -400,7 +400,7 @@ OutEdgeIt e; for(G.first(e,w) ; G.valid(e); G.next(e)) { - Node v=G.head(e); + Node v=G.target(e); if (!M[v] && flow[e] < capacity[e] ) { queue.push(v); M.set(v, true); @@ -409,7 +409,7 @@ InEdgeIt f; for(G.first(f,w) ; G.valid(f); G.next(f)) { - Node v=G.tail(f); + Node v=G.source(f); if (!M[v] && flow[f] > 0 ) { queue.push(v); M.set(v, true); @@ -440,7 +440,7 @@ InEdgeIt e; for(G.first(e,w) ; G.valid(e); G.next(e)) { - Node v=G.tail(e); + Node v=G.source(e); if (!M[v] && flow[e] < capacity[e] ) { queue.push(v); M.set(v, true); @@ -449,7 +449,7 @@ OutEdgeIt f; for(G.first(f,w) ; G.valid(f); G.next(f)) { - Node v=G.head(f); + Node v=G.target(f); if (!M[v] && flow[f] > 0 ) { queue.push(v); M.set(v, true); diff -r 741f3108a90f -r e997802b855c src/work/jacint/prim.h --- a/src/work/jacint/prim.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/jacint/prim.h Sat Nov 13 12:53:28 2004 +0000 @@ -95,7 +95,7 @@ OutEdgeIt e; for( G.first(e,v); G.valid(e); G.next(e)) { - Node w=G.head(e); + Node w=G.target(e); if ( !scanned[w] ) { if ( !reach[w] ) { @@ -111,7 +111,7 @@ InEdgeIt f; for( G.first(f,v); G.valid(f); G.next(f)) { - Node w=G.tail(f); + Node w=G.source(f); if ( !scanned[w] ) { if ( !reach[w] ) { diff -r 741f3108a90f -r e997802b855c src/work/johanna/ma_order.h --- a/src/work/johanna/ma_order.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/johanna/ma_order.h Sat Nov 13 12:53:28 2004 +0000 @@ -57,7 +57,7 @@ OutEdgeIt e; G.first(e,a); for (;G.valid(e);G.next(e)) { - Node v = G.head(e); // hmm + Node v = G.target(e); // hmm if (heap.state(v) == Heap::IN_HEAP ) { heap.decrease(v, heap[v]+1); } diff -r 741f3108a90f -r e997802b855c src/work/marci/augmenting_flow.h --- a/src/work/marci/augmenting_flow.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/augmenting_flow.h Sat Nov 13 12:53:28 2004 +0000 @@ -210,7 +210,7 @@ OutEdgeIt e; for(g->first(e,w) ; e!=INVALID; ++e) { - Node v=g->head(e); + Node v=g->target(e); if (!M[v] && (*flow)[e] < (*capacity)[e] ) { queue.push(v); M.set(v, true); @@ -219,7 +219,7 @@ InEdgeIt f; for(g->first(f,w) ; f!=INVALID; ++f) { - Node v=g->tail(f); + Node v=g->source(f); if (!M[v] && (*flow)[f] > 0 ) { queue.push(v); M.set(v, true); @@ -270,15 +270,15 @@ while ( !bfs.finished() ) { ResGWEdge e=bfs; if (e!=INVALID && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); + Node v=res_graph.source(e); + Node w=res_graph.target(e); pred.set(w, e); if (pred[v]!=INVALID) { free.set(w, std::min(free[v], res_cap[e])); } else { free.set(w, res_cap[e]); } - if (res_graph.head(e)==t) { _augment=true; break; } + if (res_graph.target(e)==t) { _augment=true; break; } } ++bfs; @@ -290,7 +290,7 @@ while (pred[n]!=INVALID) { ResGWEdge e=pred[n]; res_graph.augment(e, augment_value); - n=res_graph.tail(e); + n=res_graph.source(e); } } @@ -329,15 +329,15 @@ while ( !bfs.finished() ) { ResGWEdge e=bfs; if (e!=INVALID && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); + Node v=res_graph.source(e); + Node w=res_graph.target(e); pred.set(w, e); if (pred[v]!=INVALID) { free.set(w, std::min(free[v], res_cap[e])); } else { free.set(w, res_cap[e]); } - if (res_graph.head(e)==t) { _augment=true; break; } + if (res_graph.target(e)==t) { _augment=true; break; } } ++bfs; @@ -349,7 +349,7 @@ while (pred[n]!=INVALID) { ResGWEdge e=pred[n]; res_graph.augment(e, augment_value); - n=res_graph.tail(e); + n=res_graph.source(e); } } @@ -395,17 +395,17 @@ ResGWEdge e=bfs; if (e!=INVALID) { if (bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], - res_graph_to_F[res_graph.head(e)]); + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], + res_graph_to_F[res_graph.target(e)]); //original_edge.update(); original_edge.set(f, e); //residual_capacity.update(); residual_capacity.set(f, res_cap[e]); } else { - if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], - res_graph_to_F[res_graph.head(e)]); + if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], + res_graph_to_F[res_graph.target(e)]); //original_edge.update(); original_edge.set(f, e); //residual_capacity.update(); @@ -433,8 +433,8 @@ ++dfs; if (typename MG::Edge(dfs)!=INVALID) { if (dfs.isBNodeNewlyReached()) { - typename MG::Node v=F.tail(dfs); - typename MG::Node w=F.head(dfs); + typename MG::Node v=F.source(dfs); + typename MG::Node w=F.target(dfs); pred.set(w, dfs); if (pred[v]!=INVALID) { free.set(w, std::min(free[v], residual_capacity[dfs])); @@ -459,7 +459,7 @@ while (pred[n]!=INVALID) { typename MG::Edge e=pred[n]; res_graph.augment(original_edge[e], augment_value); - n=F.tail(e); + n=F.source(e); if (residual_capacity[e]==augment_value) F.erase(e); else @@ -498,7 +498,7 @@ while ( !bfs.finished() ) { ResGWEdge e=bfs; if (e!=INVALID && bfs.isBNodeNewlyReached()) - potential.set(res_graph.head(e), potential[res_graph.tail(e)]+1); + potential.set(res_graph.target(e), potential[res_graph.source(e)]+1); ++bfs; } @@ -553,8 +553,8 @@ if (typename ErasingResGW::Edge(dfs)!=INVALID) { if (dfs.isBNodeNewlyReached()) { - typename ErasingResGW::Node v=erasing_res_graph.tail(dfs); - typename ErasingResGW::Node w=erasing_res_graph.head(dfs); + typename ErasingResGW::Node v=erasing_res_graph.source(dfs); + typename ErasingResGW::Node w=erasing_res_graph.target(dfs); pred.set(w, typename ErasingResGW::Edge(dfs)); if (pred[v]!=INVALID) { @@ -585,7 +585,7 @@ while (pred[n]!=INVALID) { typename ErasingResGW::Edge e=pred[n]; res_graph.augment(e, augment_value); - n=erasing_res_graph.tail(e); + n=erasing_res_graph.source(e); if (res_cap[e]==0) erasing_res_graph.erase(e); } diff -r 741f3108a90f -r e997802b855c src/work/marci/bfs_dfs.h --- a/src/work/marci/bfs_dfs.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/bfs_dfs.h Sat Nov 13 12:53:28 2004 +0000 @@ -63,7 +63,7 @@ actual_edge=OutEdgeIt(*graph, s); //graph->first(actual_edge, s); if (actual_edge!=INVALID) { - Node w=graph->head(actual_edge); + Node w=graph->target(actual_edge); if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); @@ -85,7 +85,7 @@ actual_edge=++OutEdgeIt(*graph, actual_edge); //++actual_edge; if (actual_edge!=INVALID) { - Node w=graph->head(actual_edge); + Node w=graph->target(actual_edge); if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); @@ -100,7 +100,7 @@ actual_edge=OutEdgeIt(*graph, bfs_queue.front()); //graph->first(actual_edge, bfs_queue.front()); if (actual_edge!=INVALID) { - Node w=graph->head(actual_edge); + Node w=graph->target(actual_edge); if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); @@ -124,9 +124,9 @@ /// Returns if a-node is examined. bool isANodeExamined() const { return actual_edge==INVALID; } /// Returns a-node of the actual edge, so does if the edge is invalid. - Node tail() const { return bfs_queue.front(); } + Node source() const { return bfs_queue.front(); } /// \pre The actual edge have to be valid. - Node head() const { return graph->head(actual_edge); } + Node target() const { return graph->target(actual_edge); } /// Guess what? /// \deprecated const ReachedMap& getReachedMap() const { return reached; } @@ -186,8 +186,8 @@ Parent::operator++(); if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) { - pred.set(this->head(), this->actual_edge); - dist.set(this->head(), dist[this->tail()]); + pred.set(this->target(), this->actual_edge); + dist.set(this->target(), dist[this->source()]); } return *this; } @@ -246,7 +246,7 @@ operator++() { actual_edge=dfs_stack.top(); if (actual_edge!=INVALID/*.valid()*/) { - Node w=graph->head(actual_edge); + Node w=graph->target(actual_edge); actual_node=w; if (!reached[w]) { OutEdgeIt e(*graph, w); @@ -255,7 +255,7 @@ reached.set(w, true); b_node_newly_reached=true; } else { - actual_node=graph->tail(actual_edge); + actual_node=graph->source(actual_edge); ++dfs_stack.top(); b_node_newly_reached=false; } @@ -276,10 +276,10 @@ /// Returns if a-node is examined. bool isANodeExamined() const { return actual_edge==INVALID; } /// Returns a-node of the actual edge, so does if the edge is invalid. - Node tail() const { return actual_node; /*FIXME*/} + Node source() const { return actual_node; /*FIXME*/} /// Returns b-node of the actual edge. /// \pre The actual edge have to be valid. - Node head() const { return graph->head(actual_edge); } + Node target() const { return graph->target(actual_edge); } /// Guess what? /// \deprecated const ReachedMap& getReachedMap() const { return reached; } @@ -333,7 +333,7 @@ Parent::operator++(); if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) { - pred.set(this->head(), this->actual_edge); + pred.set(this->target(), this->actual_edge); } return *this; } diff -r 741f3108a90f -r e997802b855c src/work/marci/bfs_mm.h --- a/src/work/marci/bfs_mm.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/bfs_mm.h Sat Nov 13 12:53:28 2004 +0000 @@ -71,7 +71,7 @@ actual_edge=OutEdgeIt(*graph, s); //graph->first(actual_edge, s); if (actual_edge!=INVALID) { - Node w=graph->head(actual_edge); + Node w=graph->target(actual_edge); if (!(*reached_map)[w]) { bfs_queue.push(w); reached_map->set(w, true); @@ -93,7 +93,7 @@ actual_edge=++OutEdgeIt(*graph, actual_edge); //++actual_edge; if (actual_edge!=INVALID) { - Node w=graph->head(actual_edge); + Node w=graph->target(actual_edge); if (!(*reached_map)[w]) { bfs_queue.push(w); reached_map->set(w, true); @@ -108,7 +108,7 @@ actual_edge=OutEdgeIt(*graph, bfs_queue.front()); //graph->first(actual_edge, bfs_queue.front()); if (actual_edge!=INVALID) { - Node w=graph->head(actual_edge); + Node w=graph->target(actual_edge); if (!(*reached_map)[w]) { bfs_queue.push(w); reached_map->set(w, true); @@ -132,9 +132,9 @@ /// Returns if a-node is examined. bool isANodeExamined() const { return actual_edge==INVALID; } /// Returns a-node of the actual edge, so does if the edge is invalid. - Node tail() const { return bfs_queue.front(); } + Node source() const { return bfs_queue.front(); } /// \pre The actual edge have to be valid. - Node head() const { return graph->head(actual_edge); } + Node target() const { return graph->target(actual_edge); } /// Guess what? /// \deprecated const ReachedMap& reachedMap() const { return *reached_map; } @@ -231,9 +231,9 @@ Parent::operator++(); if ((this->actual_edge)!=INVALID && this->b_node_newly_reached) { - pred_map->set(this->head(), this->actual_edge); - pred_node_map->set(this->head(), this->tail()); - dist_map->set(this->head(), (*dist_map)[this->tail()]); + pred_map->set(this->target(), this->actual_edge); + pred_node_map->set(this->target(), this->source()); + dist_map->set(this->target(), (*dist_map)[this->source()]); } return *this; } @@ -457,7 +457,7 @@ operator++() { actual_edge=dfs_stack.top(); if (actual_edge!=INVALID/*.valid()*/) { - Node w=graph->head(actual_edge); + Node w=graph->target(actual_edge); actual_node=w; if (!reached[w]) { OutEdgeIt e(*graph, w); @@ -466,7 +466,7 @@ reached.set(w, true); b_node_newly_reached=true; } else { - actual_node=graph->tail(actual_edge); + actual_node=graph->source(actual_edge); ++dfs_stack.top(); b_node_newly_reached=false; } @@ -487,10 +487,10 @@ /// Returns if a-node is examined. bool isANodeExamined() const { return actual_edge==INVALID; } /// Returns a-node of the actual edge, so does if the edge is invalid. - Node tail() const { return actual_node; /*FIXME*/} + Node source() const { return actual_node; /*FIXME*/} /// Returns b-node of the actual edge. /// \pre The actual edge have to be valid. - Node head() const { return graph->head(actual_edge); } + Node target() const { return graph->target(actual_edge); } /// Guess what? /// \deprecated const ReachedMap& getReachedMap() const { return reached; } @@ -544,7 +544,7 @@ Parent::operator++(); if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) { - pred.set(this->head(), this->actual_edge); + pred.set(this->target(), this->actual_edge); } return *this; } diff -r 741f3108a90f -r e997802b855c src/work/marci/bfs_mm_test.cc --- a/src/work/marci/bfs_mm_test.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/bfs_mm_test.cc Sat Nov 13 12:53:28 2004 +0000 @@ -91,8 +91,8 @@ // for(EdgeIt e(G); e==INVALID; ++e) { -// Node u=G.tail(e); -// Node v=G.head(e); +// Node u=G.source(e); +// Node v=G.target(e); // check( !bfs_test.reached(u) || // (bfs_test.dist(v) > bfs_test.dist(u)+1), // "Wrong output."); @@ -102,7 +102,7 @@ // check(bfs_test.reached(v),"Each node should be reached."); // if ( bfs_test.pred(v)!=INVALID ) { // Edge e=bfs_test.pred(v); -// Node u=G.tail(e); +// Node u=G.source(e); // check(u==bfs_test.predNode(v),"Wrong tree."); // check(bfs_test.dist(v) - bfs_test.dist(u) == 1, // "Wrong distance. Difference: " diff -r 741f3108a90f -r e997802b855c src/work/marci/bfsit_vs_byhand.cc --- a/src/work/marci/bfsit_vs_byhand.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/bfsit_vs_byhand.cc Sat Nov 13 12:53:28 2004 +0000 @@ -48,7 +48,7 @@ Node v=bfs_queue.front(); bfs_queue.pop(); for(OutEdgeIt e(g,v); e!=INVALID; ++e) { - Node w=g.head(e); + Node w=g.target(e); if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); @@ -70,7 +70,7 @@ while (!bfs.finished()) { ++bfs; if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached()) - pred.set(bfs.head(), Graph::Edge(bfs)); + pred.set(bfs.target(), Graph::Edge(bfs)); } } std::cout << ts << std::endl; diff -r 741f3108a90f -r e997802b855c src/work/marci/bipartite_graph_wrapper.h --- a/src/work/marci/bipartite_graph_wrapper.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/bipartite_graph_wrapper.h Sat Nov 13 12:53:28 2004 +0000 @@ -167,17 +167,17 @@ // OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } // InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } -// Node tail(const Edge& e) { -// if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) -// return Node(this->graph->tail(e)); +// Node source(const Edge& e) { +// if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) +// return Node(this->graph->source(e)); // else -// return Node(this->graph->head(e)); +// return Node(this->graph->target(e)); // } -// Node head(const Edge& e) { -// if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) -// return Node(this->graph->head(e)); +// Node target(const Edge& e) { +// if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) +// return Node(this->graph->target(e)); // else -// return Node(this->graph->tail(e)); +// return Node(this->graph->source(e)); // } // Node aNode(const OutEdgeIt& e) const { @@ -252,9 +252,9 @@ } /// A new edge is inserted. - ///\pre \c tail have to be in \c S_Class and \c head in \c T_Class. - Edge addEdge(const Node& tail, const Node& head) { - return Parent::graph->addEdge(tail, head); + ///\pre \c source have to be in \c S_Class and \c target in \c T_Class. + Edge addEdge(const Node& source, const Node& target) { + return Parent::graph->addEdge(source, target); } void erase(const Node& n) { @@ -695,10 +695,10 @@ return i; } - Node tail(const Edge& e) const { + Node source(const Edge& e) const { switch (e.spec) { case 0: - return Node(this->graph->tail(e)); + return Node(this->graph->source(e)); break; case 1: return S_NODE; @@ -709,10 +709,10 @@ break; } } - Node head(const Edge& e) const { + Node target(const Edge& e) const { switch (e.spec) { case 0: - return Node(this->graph->head(e)); + return Node(this->graph->target(e)); break; case 1: return Node(e.n); @@ -732,17 +732,17 @@ return this->graph->edgeNum()+this->graph->nodeNum(); } - Node aNode(const OutEdgeIt& e) const { return tail(e); } - Node aNode(const InEdgeIt& e) const { return head(e); } - Node bNode(const OutEdgeIt& e) const { return head(e); } - Node bNode(const InEdgeIt& e) const { return tail(e); } + Node aNode(const OutEdgeIt& e) const { return source(e); } + Node aNode(const InEdgeIt& e) const { return target(e); } + Node bNode(const OutEdgeIt& e) const { return target(e); } + Node bNode(const InEdgeIt& e) const { return source(e); } void addNode() const { } void addEdge() const { } // Node addNode() const { return Node(this->graph->addNode()); } -// Edge addEdge(const Node& tail, const Node& head) const { -// return Edge(this->graph->addEdge(tail, head)); } +// Edge addEdge(const Node& source, const Node& target) const { +// return Edge(this->graph->addEdge(source, target)); } // void erase(const Node& i) const { this->graph->erase(i); } // void erase(const Edge& i) const { this->graph->erase(i); } diff -r 741f3108a90f -r e997802b855c src/work/marci/bipartite_graph_wrapper_test.cc --- a/src/work/marci/bipartite_graph_wrapper_test.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc Sat Nov 13 12:53:28 2004 +0000 @@ -87,7 +87,7 @@ cout << "Edges of the bipartite graph:" << endl; for (BGW::EdgeIt e(bgw); e!=INVALID; ++e) - cout << g.id(bgw.tail(e)) << "->" << g.id(bgw.head(e)) << endl; + cout << g.id(bgw.source(e)) << "->" << g.id(bgw.target(e)) << endl; BGW::NodeMap dbyj(bgw); BGW::EdgeMap dbyxcj(bgw); diff -r 741f3108a90f -r e997802b855c src/work/marci/experiment/edmonds_karp.h --- a/src/work/marci/experiment/edmonds_karp.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/experiment/edmonds_karp.h Sat Nov 13 12:53:28 2004 +0000 @@ -40,7 +40,7 @@ Edge() { } //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } Number free() const { - if (resG->G.aNode(sym)==resG->G.tail(sym)) { + if (resG->G.aNode(sym)==resG->G.source(sym)) { return (resG->capacity.get(sym)-resG->flow.get(sym)); } else { return (resG->flow.get(sym)); @@ -48,7 +48,7 @@ } bool valid() const { return sym.valid(); } void augment(Number a) const { - if (resG->G.aNode(sym)==resG->G.tail(sym)) { + if (resG->G.aNode(sym)==resG->G.source(sym)) { resG->flow.set(sym, resG->flow.get(sym)+a); //resG->flow[sym]+=a; } else { @@ -96,8 +96,8 @@ return e; } - Node tail(Edge e) const { return G.aNode(e.sym); } - Node head(Edge e) const { return G.bNode(e.sym); } + Node source(Edge e) const { return G.aNode(e.sym); } + Node target(Edge e) const { return G.bNode(e.sym); } Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } @@ -223,9 +223,9 @@ return e; } - Node tail(Edge e) const { + Node source(Edge e) const { return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } - Node head(Edge e) const { + Node target(Edge e) const { return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } Node aNode(OutEdgeIt e) const { @@ -287,15 +287,15 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); + Node v=res_graph.source(e); + Node w=res_graph.target(e); pred.set(w, e); if (res_graph.valid(pred.get(v))) { free.set(w, std::min(free.get(v), res_graph.resCap(e))); } else { free.set(w, res_graph.resCap(e)); } - if (res_graph.head(e)==t) { _augment=true; break; } + if (res_graph.target(e)==t) { _augment=true; break; } } ++bfs; @@ -307,7 +307,7 @@ while (res_graph.valid(pred.get(n))) { ResGWEdge e=pred.get(n); res_graph.augment(e, augment_value); - n=res_graph.tail(e); + n=res_graph.source(e); } } @@ -324,7 +324,7 @@ void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } bool get(const typename MapGraphWrapper::Edge& e) const { - return (dist.get(gw.tail(e))::OutEdgeIt e=bfs; // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); +// dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); // } // ++bfs; // } //computing distances from s in the residual graph @@ -722,7 +722,7 @@ // while (res_graph.valid(pred.get(n))) { // EAugEdge e=pred.get(n); // res_graph.augment(e, augment_value); -// n=res_graph.tail(e); +// n=res_graph.source(e); // if (res_graph.free(e)==0) // res_graph.erase(e); // } @@ -817,15 +817,15 @@ // while ( !bfs.finished() ) { // AugOutEdgeIt e=bfs; // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// Node v=res_graph.tail(e); -// Node w=res_graph.head(e); +// Node v=res_graph.source(e); +// Node w=res_graph.target(e); // pred.set(w, e); // if (res_graph.valid(pred.get(v))) { // free.set(w, std::min(free.get(v), res_graph.free(e))); // } else { // free.set(w, res_graph.free(e)); // } -// n=res_graph.head(e); +// n=res_graph.target(e); // if (T->get(n) && (used.get(n)<1) ) { // //Number u=0; // //for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) @@ -847,7 +847,7 @@ // while (res_graph.valid(pred.get(n))) { // AugEdge e=pred.get(n); // res_graph.augment(e, augment_value); -// n=res_graph.tail(e); +// n=res_graph.source(e); // } // used.set(n, 1); //mind2 vegen jav // } @@ -888,7 +888,7 @@ // // while ( !bfs.finished() ) { // // AugOutEdgeIt e=bfs; // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); +// // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); // // } // // ++bfs; @@ -910,8 +910,8 @@ // // //Making F to the graph containing the edges of the residual graph // // //which are in some shortest paths // // for(typename AugGraph::EdgeIt e=res_graph.template first(); res_graph.valid(e); res_graph.next(e)) { -// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { -// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); +// // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { +// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); // // original_edge.update(); // // original_edge.set(f, e); // // residual_capacity.update(); @@ -963,7 +963,7 @@ // // while (F.valid(pred.get(n))) { // // typename MutableGraph::Edge e=pred.get(n); // // res_graph.augment(original_edge.get(e), augment_value); -// // n=F.tail(e); +// // n=F.source(e); // // if (residual_capacity.get(e)==augment_value) // // F.erase(e); // // else @@ -1014,7 +1014,7 @@ // while ( !bfs.finished() ) { // typename ErasingResGraphWrapper::OutEdgeIt e=bfs; // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); +// dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); // } // ++bfs; // } //computing distances from s in the residual graph @@ -1091,7 +1091,7 @@ // while (res_graph.valid(pred.get(n))) { // EAugEdge e=pred.get(n); // res_graph.augment(e, augment_value); -// n=res_graph.tail(e); +// n=res_graph.source(e); // if (res_graph.free(e)==0) // res_graph.erase(e); // } @@ -1184,17 +1184,17 @@ // // while ( !bfs.finished() ) { // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); // // if (e.valid() && bfs.isBNodeNewlyReached()) { -// // Node v=res_graph.tail(e); -// // Node w=res_graph.head(e); +// // Node v=res_graph.source(e); +// // Node w=res_graph.target(e); // // pred.set(w, e); // // if (pred.get(v).valid()) { // // free.set(w, std::min(free.get(v), e.free())); // // } else { // // free.set(w, e.free()); // // } -// // if (TMap.get(res_graph.head(e))) { +// // if (TMap.get(res_graph.target(e))) { // // _augment=true; -// // reached_t_node=res_graph.head(e); +// // reached_t_node=res_graph.target(e); // // break; // // } // // } @@ -1208,7 +1208,7 @@ // // while (pred.get(n).valid()) { // // AugEdge e=pred.get(n); // // e.augment(augment_value); -// // n=res_graph.tail(e); +// // n=res_graph.source(e); // // } // // } diff -r 741f3108a90f -r e997802b855c src/work/marci/experiment/edmonds_karp_1.h --- a/src/work/marci/experiment/edmonds_karp_1.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/experiment/edmonds_karp_1.h Sat Nov 13 12:53:28 2004 +0000 @@ -41,7 +41,7 @@ Edge() { } //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } Number free() const { - if (resG->G.aNode(sym)==resG->G.tail(sym)) { + if (resG->G.aNode(sym)==resG->G.source(sym)) { return (resG->capacity.get(sym)-resG->flow.get(sym)); } else { return (resG->flow.get(sym)); @@ -49,7 +49,7 @@ } bool valid() const { return sym.valid(); } void augment(Number a) const { - if (resG->G.aNode(sym)==resG->G.tail(sym)) { + if (resG->G.aNode(sym)==resG->G.source(sym)) { resG->flow.set(sym, resG->flow.get(sym)+a); //resG->flow[sym]+=a; } else { @@ -97,8 +97,8 @@ return e; } - Node tail(Edge e) const { return G.aNode(e.sym); } - Node head(Edge e) const { return G.bNode(e.sym); } + Node source(Edge e) const { return G.aNode(e.sym); } + Node target(Edge e) const { return G.bNode(e.sym); } Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } @@ -224,9 +224,9 @@ return e; } - Node tail(Edge e) const { + Node source(Edge e) const { return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } - Node head(Edge e) const { + Node target(Edge e) const { return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } Node aNode(OutEdgeIt e) const { @@ -286,15 +286,15 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); + Node v=res_graph.source(e); + Node w=res_graph.target(e); pred.set(w, e); if (res_graph.valid(pred.get(v))) { free.set(w, std::min(free.get(v), res_graph.resCap(e))); } else { free.set(w, res_graph.resCap(e)); } - if (res_graph.head(e)==t) { _augment=true; break; } + if (res_graph.target(e)==t) { _augment=true; break; } } ++bfs; @@ -306,7 +306,7 @@ while (res_graph.valid(pred.get(n))) { ResGWEdge e=pred.get(n); res_graph.augment(e, augment_value); - n=res_graph.tail(e); + n=res_graph.source(e); } } @@ -323,7 +323,7 @@ void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } bool get(const typename MapGraphWrapper::Edge& e) const { - return (dist.get(g->tail(e))head(e))); + return (dist.get(g->source(e))target(e))); } }; @@ -342,7 +342,7 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); + dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); } ++bfs; } //computing distances from s in the residual graph @@ -368,8 +368,8 @@ { typename FilterResGW::EdgeIt e; for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { - //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); @@ -422,7 +422,7 @@ while (F.valid(pred.get(n))) { typename MG::Edge e=pred.get(n); res_graph.augment(original_edge.get(e), augment_value); - n=F.tail(e); + n=F.source(e); if (residual_capacity.get(e)==augment_value) F.erase(e); else @@ -467,15 +467,15 @@ ResGWOutEdgeIt e=bfs; if (res_graph.valid(e)) { if (bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); residual_capacity.set(f, res_graph.resCap(e)); } else { - if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) { + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); @@ -530,7 +530,7 @@ while (F.valid(pred.get(n))) { typename MG::Edge e=pred.get(n); res_graph.augment(original_edge.get(e), augment_value); - n=F.tail(e); + n=F.source(e); if (residual_capacity.get(e)==augment_value) F.erase(e); else @@ -556,7 +556,7 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); + dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); } ++bfs; } //computing distances from s in the residual graph @@ -632,7 +632,7 @@ while (erasing_res_graph.valid(pred.get(n))) { typename ErasingResGW::OutEdgeIt e=pred.get(n); res_graph.augment(e, augment_value); - n=erasing_res_graph.tail(e); + n=erasing_res_graph.source(e); if (res_graph.resCap(e)==0) erasing_res_graph.erase(e); } @@ -727,15 +727,15 @@ // while ( !bfs.finished() ) { // AugOutEdgeIt e=bfs; // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// Node v=res_graph.tail(e); -// Node w=res_graph.head(e); +// Node v=res_graph.source(e); +// Node w=res_graph.target(e); // pred.set(w, e); // if (res_graph.valid(pred.get(v))) { // free.set(w, std::min(free.get(v), res_graph.free(e))); // } else { // free.set(w, res_graph.free(e)); // } -// n=res_graph.head(e); +// n=res_graph.target(e); // if (T->get(n) && (used.get(n)<1) ) { // //Number u=0; // //for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) @@ -757,7 +757,7 @@ // while (res_graph.valid(pred.get(n))) { // AugEdge e=pred.get(n); // res_graph.augment(e, augment_value); -// n=res_graph.tail(e); +// n=res_graph.source(e); // } // used.set(n, 1); //mind2 vegen jav // } @@ -798,7 +798,7 @@ // // while ( !bfs.finished() ) { // // AugOutEdgeIt e=bfs; // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); +// // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); // // } // // ++bfs; @@ -820,8 +820,8 @@ // // //Making F to the graph containing the edges of the residual graph // // //which are in some shortest paths // // for(typename AugGraph::EdgeIt e=res_graph.template first(); res_graph.valid(e); res_graph.next(e)) { -// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { -// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); +// // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { +// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); // // original_edge.update(); // // original_edge.set(f, e); // // residual_capacity.update(); @@ -873,7 +873,7 @@ // // while (F.valid(pred.get(n))) { // // typename MutableGraph::Edge e=pred.get(n); // // res_graph.augment(original_edge.get(e), augment_value); -// // n=F.tail(e); +// // n=F.source(e); // // if (residual_capacity.get(e)==augment_value) // // F.erase(e); // // else @@ -924,7 +924,7 @@ // while ( !bfs.finished() ) { // typename ErasingResGraphWrapper::OutEdgeIt e=bfs; // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); +// dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); // } // ++bfs; // } //computing distances from s in the residual graph @@ -1001,7 +1001,7 @@ // while (res_graph.valid(pred.get(n))) { // EAugEdge e=pred.get(n); // res_graph.augment(e, augment_value); -// n=res_graph.tail(e); +// n=res_graph.source(e); // if (res_graph.free(e)==0) // res_graph.erase(e); // } @@ -1094,17 +1094,17 @@ // // while ( !bfs.finished() ) { // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); // // if (e.valid() && bfs.isBNodeNewlyReached()) { -// // Node v=res_graph.tail(e); -// // Node w=res_graph.head(e); +// // Node v=res_graph.source(e); +// // Node w=res_graph.target(e); // // pred.set(w, e); // // if (pred.get(v).valid()) { // // free.set(w, std::min(free.get(v), e.free())); // // } else { // // free.set(w, e.free()); // // } -// // if (TMap.get(res_graph.head(e))) { +// // if (TMap.get(res_graph.target(e))) { // // _augment=true; -// // reached_t_node=res_graph.head(e); +// // reached_t_node=res_graph.target(e); // // break; // // } // // } @@ -1118,7 +1118,7 @@ // // while (pred.get(n).valid()) { // // AugEdge e=pred.get(n); // // e.augment(augment_value); -// // n=res_graph.tail(e); +// // n=res_graph.source(e); // // } // // } diff -r 741f3108a90f -r e997802b855c src/work/marci/experiment/edmonds_karp_demo.cc --- a/src/work/marci/experiment/edmonds_karp_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/experiment/edmonds_karp_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -104,7 +104,7 @@ int i=0; while (max_flow_test.augmentOnBlockingFlow()) { // for(EdgeIt e=G.template first(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<()) { // for(EdgeIt e=G.template first(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<()) { // for(EdgeIt e=G.template first(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<()) { // for(EdgeIt e=G.template first(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"< It first(const Node& v) const { It e; first(e, v); return e; } - Node head(const Edge& e) const { return graph->head(e); } - Node tail(const Edge& e) const { return graph->tail(e); } + Node target(const Edge& e) const { return graph->target(e); } + Node source(const Edge& e) const { return graph->source(e); } template bool valid(const I& i) const { return graph->valid(i); } @@ -114,8 +114,8 @@ return graph->bNode(e); } Node addNode() const { return graph->addNode(); } - Edge addEdge(const Node& tail, const Node& head) const { - return graph->addEdge(tail, head); } + Edge addEdge(const Node& source, const Node& target) const { + return graph->addEdge(source, target); } template void erase(const I& i) const { graph->erase(i); } @@ -245,8 +245,8 @@ template< typename It > It first(const Node& v) const { It e; this->first(e, v); return e; } - Node head(const Edge& e) const { return gw.head(e); } - Node tail(const Edge& e) const { return gw.tail(e); } + Node target(const Edge& e) const { return gw.target(e); } + Node source(const Edge& e) const { return gw.source(e); } template bool valid(const I& i) const { return gw.valid(i); } @@ -260,8 +260,8 @@ template Node bNode(const I& e) const { return gw.bNode(e); } Node addNode() const { return gw.addNode(); } - Edge addEdge(const Node& tail, const Node& head) const { - return gw.addEdge(tail, head); } + Edge addEdge(const Node& source, const Node& target) const { + return gw.addEdge(source, target); } template void erase(const I& i) const { gw.erase(i); } @@ -322,8 +322,8 @@ // template< typename It > It first(const Node& v) const { // It e; first(e, v); return e; } -// Node head(const Edge& e) const { return graph->tail(e); } -// Node tail(const Edge& e) const { return graph->head(e); } +// Node target(const Edge& e) const { return graph->source(e); } +// Node source(const Edge& e) const { return graph->target(e); } // template bool valid(const I& i) const // { return graph->valid(i); } @@ -337,8 +337,8 @@ // return graph->bNode(e); } // Node addNode() const { return graph->addNode(); } -// Edge addEdge(const Node& tail, const Node& head) const { -// return graph->addEdge(tail, head); } +// Edge addEdge(const Node& source, const Node& target) const { +// return graph->addEdge(source, target); } // int nodeNum() const { return graph->nodeNum(); } // int edgeNum() const { return graph->edgeNum(); } @@ -403,8 +403,8 @@ // //template< typename It > It first(const Node& v) const { // // It e; first(e, v); return e; } -// //Node head(const Edge& e) const { return graph->tail(e); } -// //Node tail(const Edge& e) const { return graph->head(e); } +// //Node target(const Edge& e) const { return graph->source(e); } +// //Node source(const Edge& e) const { return graph->target(e); } // //template bool valid(const I& i) const // // { return graph->valid(i); } @@ -418,8 +418,8 @@ // // return graph->bNode(e); } // //Node addNode() const { return graph->addNode(); } -// //Edge addEdge(const Node& tail, const Node& head) const { -// // return graph->addEdge(tail, head); } +// //Edge addEdge(const Node& source, const Node& target) const { +// // return graph->addEdge(source, target); } // //int nodeNum() const { return graph->nodeNum(); } // //int edgeNum() const { return graph->edgeNum(); } @@ -467,10 +467,10 @@ RevGraphWrapper(GraphWrapper _gw) : GraphWrapper(_gw) { } - Node head(const Edge& e) const - { return GraphWrapper::tail(e); } - Node tail(const Edge& e) const - { return GraphWrapper::head(e); } + Node target(const Edge& e) const + { return GraphWrapper::source(e); } + Node source(const Edge& e) const + { return GraphWrapper::target(e); } }; //Subgraph on the same node-set and partial edge-set @@ -599,7 +599,7 @@ // OutEdgeIt& next(OutEdgeIt& e) const { // if (e.out_or_in) { -// Node n=gw.tail(e.out); +// Node n=gw.source(e.out); // gw.next(e.out); // if (!gw.valid(e.out)) { // e.out_or_in=false; @@ -612,9 +612,9 @@ // } // Node aNode(const OutEdgeIt& e) const { -// if (e.out_or_in) return gw.tail(e); else return gw.head(e); } +// if (e.out_or_in) return gw.source(e); else return gw.target(e); } // Node bNode(const OutEdgeIt& e) const { -// if (e.out_or_in) return gw.head(e); else return gw.tail(e); } +// if (e.out_or_in) return gw.target(e); else return gw.source(e); } // typedef OutEdgeIt InEdgeIt; @@ -632,8 +632,8 @@ // template< typename It > It first(const Node& v) const { // It e; first(e, v); return e; } -// Node head(const Edge& e) const { return gw.head(e); } -// Node tail(const Edge& e) const { return gw.tail(e); } +// Node target(const Edge& e) const { return gw.target(e); } +// Node source(const Edge& e) const { return gw.source(e); } // template bool valid(const I& i) const // { return gw.valid(i); } @@ -651,8 +651,8 @@ // Node addNode() const { return gw.addNode(); } // // FIXME: ez igy nem jo, mert nem -// // Edge addEdge(const Node& tail, const Node& head) const { -// // return graph->addEdge(tail, head); } +// // Edge addEdge(const Node& source, const Node& target) const { +// // return graph->addEdge(source, target); } // template void erase(const I& i) const { gw.erase(i); } @@ -798,7 +798,7 @@ OutEdgeIt& next(OutEdgeIt& e) const { if (e.out_or_in) { - Node n=gw.tail(e.out); + Node n=gw.source(e.out); gw.next(e.out); if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); } } else { @@ -808,7 +808,7 @@ } EdgeIt& next(EdgeIt& e) const { - //NodeIt v=tail(e); + //NodeIt v=source(e); gw.next(e.out); while (valid(e.v) && !gw.valid(e.out)) { next(e.v); @@ -826,8 +826,8 @@ template< typename It > It first(const Node& v) const { It e; first(e, v); return e; } -// Node head(const Edge& e) const { return gw.head(e); } -// Node tail(const Edge& e) const { return gw.tail(e); } +// Node target(const Edge& e) const { return gw.target(e); } +// Node source(const Edge& e) const { return gw.source(e); } // template bool valid(const I& i) const // { return gw.valid(i); } @@ -841,15 +841,15 @@ // return graph->bNode(e); } Node aNode(const OutEdgeIt& e) const { - if (e.out_or_in) return gw.tail(e); else return gw.head(e); } + if (e.out_or_in) return gw.source(e); else return gw.target(e); } Node bNode(const OutEdgeIt& e) const { - if (e.out_or_in) return gw.head(e); else return gw.tail(e); } + if (e.out_or_in) return gw.target(e); else return gw.source(e); } // Node addNode() const { return gw.addNode(); } // FIXME: ez igy nem jo, mert nem -// Edge addEdge(const Node& tail, const Node& head) const { -// return graph->addEdge(tail, head); } +// Edge addEdge(const Node& source, const Node& target) const { +// return graph->addEdge(source, target); } // template void erase(const I& i) const { gw.erase(i); } @@ -913,8 +913,8 @@ // template< typename It > It first(Node v) const { // It e; first(e, v); return e; } -// Node head(const Edge& e) const { return graph->head(e); } -// Node tail(const Edge& e) const { return graph->tail(e); } +// Node target(const Edge& e) const { return graph->target(e); } +// Node source(const Edge& e) const { return graph->source(e); } // template Node aNode(const I& e) const { // return graph->aNode(e); } @@ -928,8 +928,8 @@ // //{ return graph->setInvalid(i); } // Node addNode() { return graph->addNode(); } -// Edge addEdge(const Node& tail, const Node& head) { -// return graph->addEdge(tail, head); } +// Edge addEdge(const Node& source, const Node& target) { +// return graph->addEdge(source, target); } // template void erase(const I& i) { graph->erase(i); } @@ -1180,9 +1180,9 @@ return e; } - Node tail(Edge e) const { + Node source(Edge e) const { return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); } - Node head(Edge e) const { + Node target(Edge e) const { return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); } Node aNode(OutEdgeIt e) const { @@ -1311,7 +1311,7 @@ void erase(const OutEdgeIt& e) const { OutEdgeIt f=e; this->next(f); - first_out_edges->set(this->tail(e), f); + first_out_edges->set(this->source(e), f); } }; @@ -1381,8 +1381,8 @@ // template< typename It > It first(const Node& v) const { // It e; first(e, v); return e; } -// //Node head(const Edge& e) const { return gw.head(e); } -// //Node tail(const Edge& e) const { return gw.tail(e); } +// //Node target(const Edge& e) const { return gw.target(e); } +// //Node source(const Edge& e) const { return gw.source(e); } // //template bool valid(const I& i) const // // { return gw.valid(i); } @@ -1396,16 +1396,16 @@ // // return gw.bNode(e); } // //Node addNode() const { return gw.addNode(); } -// //Edge addEdge(const Node& tail, const Node& head) const { -// // return gw.addEdge(tail, head); } +// //Edge addEdge(const Node& source, const Node& target) const { +// // return gw.addEdge(source, target); } // //void erase(const OutEdgeIt& e) { -// // first_out_edge(this->tail(e))=e; +// // first_out_edge(this->source(e))=e; // //} // void erase(const Edge& e) { // OutEdgeIt f(e); // next(f); -// first_out_edges.set(this->tail(e), f); +// first_out_edges.set(this->source(e), f); // } // //template void erase(const I& i) const { gw.erase(i); } @@ -1459,7 +1459,7 @@ // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { // ErasingResGraphWrapper::first(e, n); -// while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e)))) +// while (valid(e) && (dist.get(source(e))/*+1!=*/>=dist.get(target(e)))) // ErasingResGraphWrapper::next(e); // return e; // } @@ -1470,7 +1470,7 @@ // OutEdgeIt& next(OutEdgeIt& e) const { // ErasingResGraphWrapper::next(e); -// while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e)))) +// while (valid(e) && (dist.get(source(e))/*+1!*/>=dist.get(target(e)))) // ErasingResGraphWrapper::next(e); // return e; // } @@ -1482,9 +1482,9 @@ // void erase(const Edge& e) { // OutEdgeIt f(e); // ErasingResGraphWrapper::next(f); -// while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f)))) +// while (valid(f) && (dist.get(source(f))/*+1!=*/>=dist.get(target(f)))) // ErasingResGraphWrapper::next(f); -// first_out_edges.set(this->tail(e), f); +// first_out_edges.set(this->source(e), f); // } // //TrivGraphWrapper() : graph(0) { } @@ -1507,8 +1507,8 @@ // template< typename It > It first(const Node& v) const { // It e; first(e, v); return e; } -// //Node head(const Edge& e) const { return gw.head(e); } -// //Node tail(const Edge& e) const { return gw.tail(e); } +// //Node target(const Edge& e) const { return gw.target(e); } +// //Node source(const Edge& e) const { return gw.source(e); } // //template bool valid(const I& i) const // // { return gw.valid(i); } @@ -1525,8 +1525,8 @@ // // return gw.bNode(e); } // //Node addNode() const { return gw.addNode(); } -// //Edge addEdge(const Node& tail, const Node& head) const { -// // return gw.addEdge(tail, head); } +// //Edge addEdge(const Node& source, const Node& target) const { +// // return gw.addEdge(source, target); } // //template void erase(const I& i) const { gw.erase(i); } @@ -1669,8 +1669,8 @@ // template< typename It > It first(Node v) const { // It e; first(e, v); return e; } -// Node head(const Edge& e) const { return gw.head(e); } -// Node tail(const Edge& e) const { return gw.tail(e); } +// Node target(const Edge& e) const { return gw.target(e); } +// Node source(const Edge& e) const { return gw.source(e); } // template Node aNode(const I& e) const { // return gw.aNode(e); } @@ -1684,8 +1684,8 @@ // //{ return gw.setInvalid(i); } // Node addNode() { return gw.addNode(); } -// Edge addEdge(const Node& tail, const Node& head) { -// return gw.addEdge(tail, head); } +// Edge addEdge(const Node& source, const Node& target) { +// return gw.addEdge(source, target); } // template void erase(const I& i) { gw.erase(i); } diff -r 741f3108a90f -r e997802b855c src/work/marci/experiment/graph_wrapper_1.h --- a/src/work/marci/experiment/graph_wrapper_1.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/experiment/graph_wrapper_1.h Sat Nov 13 12:53:28 2004 +0000 @@ -90,8 +90,8 @@ template< typename It > It first(const Node& v) const { It e; this->first(e, v); return e; } - Node head(const Edge& e) const { return graph->head(e); } - Node tail(const Edge& e) const { return graph->tail(e); } + Node target(const Edge& e) const { return graph->target(e); } + Node source(const Edge& e) const { return graph->source(e); } template bool valid(const I& i) const { return graph->valid(i); } @@ -108,8 +108,8 @@ return graph->bNode(e); } Node addNode() const { return graph->addNode(); } - Edge addEdge(const Node& tail, const Node& head) const { - return graph->addEdge(tail, head); } + Edge addEdge(const Node& source, const Node& target) const { + return graph->addEdge(source, target); } template void erase(const I& i) const { graph->erase(i); } @@ -235,8 +235,8 @@ template< typename It > It first(const Node& v) const { It e; this->first(e, v); return e; } - Node head(const Edge& e) const { return graph->head(e); } - Node tail(const Edge& e) const { return graph->tail(e); } + Node target(const Edge& e) const { return graph->target(e); } + Node source(const Edge& e) const { return graph->source(e); } template bool valid(const I& i) const { return graph->valid(i); } @@ -253,8 +253,8 @@ return graph->bNode(e); } Node addNode() const { return graph->addNode(); } - Edge addEdge(const Node& tail, const Node& head) const { - return graph->addEdge(tail, head); } + Edge addEdge(const Node& source, const Node& target) const { + return graph->addEdge(source, target); } template void erase(const I& i) const { graph->erase(i); } @@ -316,8 +316,8 @@ // template< typename It > It first(const Node& v) const { // It e; first(e, v); return e; } -// Node head(const Edge& e) const { return graph->tail(e); } -// Node tail(const Edge& e) const { return graph->head(e); } +// Node target(const Edge& e) const { return graph->source(e); } +// Node source(const Edge& e) const { return graph->target(e); } // template bool valid(const I& i) const // { return graph->valid(i); } @@ -331,8 +331,8 @@ // return graph->bNode(e); } // Node addNode() const { return graph->addNode(); } -// Edge addEdge(const Node& tail, const Node& head) const { -// return graph->addEdge(tail, head); } +// Edge addEdge(const Node& source, const Node& target) const { +// return graph->addEdge(source, target); } // int nodeNum() const { return graph->nodeNum(); } // int edgeNum() const { return graph->edgeNum(); } @@ -378,10 +378,10 @@ // RevGraphWrapper() : GraphWrapper() { } RevGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } - Node head(const Edge& e) const - { return GraphWrapper::tail(e); } - Node tail(const Edge& e) const - { return GraphWrapper::head(e); } + Node target(const Edge& e) const + { return GraphWrapper::source(e); } + Node source(const Edge& e) const + { return GraphWrapper::target(e); } }; //Subgraph on the same node-set and partial edge-set @@ -511,7 +511,7 @@ // OutEdgeIt& next(OutEdgeIt& e) const { // if (e.out_or_in) { -// Node n=gw.tail(e.out); +// Node n=gw.source(e.out); // gw.next(e.out); // if (!gw.valid(e.out)) { // e.out_or_in=false; @@ -524,9 +524,9 @@ // } // Node aNode(const OutEdgeIt& e) const { -// if (e.out_or_in) return gw.tail(e); else return gw.head(e); } +// if (e.out_or_in) return gw.source(e); else return gw.target(e); } // Node bNode(const OutEdgeIt& e) const { -// if (e.out_or_in) return gw.head(e); else return gw.tail(e); } +// if (e.out_or_in) return gw.target(e); else return gw.source(e); } // typedef OutEdgeIt InEdgeIt; @@ -544,8 +544,8 @@ // template< typename It > It first(const Node& v) const { // It e; first(e, v); return e; } -// Node head(const Edge& e) const { return gw.head(e); } -// Node tail(const Edge& e) const { return gw.tail(e); } +// Node target(const Edge& e) const { return gw.target(e); } +// Node source(const Edge& e) const { return gw.source(e); } // template bool valid(const I& i) const // { return gw.valid(i); } @@ -563,8 +563,8 @@ // Node addNode() const { return gw.addNode(); } // // FIXME: ez igy nem jo, mert nem -// // Edge addEdge(const Node& tail, const Node& head) const { -// // return graph->addEdge(tail, head); } +// // Edge addEdge(const Node& source, const Node& target) const { +// // return graph->addEdge(source, target); } // template void erase(const I& i) const { gw.erase(i); } @@ -692,7 +692,7 @@ OutEdgeIt& next(OutEdgeIt& e) const { if (e.out_or_in) { - Node n=graph->tail(e.out); + Node n=graph->source(e.out); graph->next(e.out); if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } } else { @@ -702,7 +702,7 @@ } EdgeIt& next(EdgeIt& e) const { - //NodeIt v=tail(e); + //NodeIt v=source(e); graph->next(e.out); while (valid(e.v) && !graph->valid(e.out)) { next(e.v); @@ -720,8 +720,8 @@ template< typename It > It first(const Node& v) const { It e; this->first(e, v); return e; } -// Node head(const Edge& e) const { return gw.head(e); } -// Node tail(const Edge& e) const { return gw.tail(e); } +// Node target(const Edge& e) const { return gw.target(e); } +// Node source(const Edge& e) const { return gw.source(e); } // template bool valid(const I& i) const // { return gw.valid(i); } @@ -735,15 +735,15 @@ // return graph->bNode(e); } Node aNode(const OutEdgeIt& e) const { - if (e.out_or_in) return graph->tail(e); else return graph->head(e); } + if (e.out_or_in) return graph->source(e); else return graph->target(e); } Node bNode(const OutEdgeIt& e) const { - if (e.out_or_in) return graph->head(e); else return graph->tail(e); } + if (e.out_or_in) return graph->target(e); else return graph->source(e); } // Node addNode() const { return gw.addNode(); } // FIXME: ez igy nem jo, mert nem -// Edge addEdge(const Node& tail, const Node& head) const { -// return graph->addEdge(tail, head); } +// Edge addEdge(const Node& source, const Node& target) const { +// return graph->addEdge(source, target); } // template void erase(const I& i) const { gw.erase(i); } @@ -807,8 +807,8 @@ // template< typename It > It first(Node v) const { // It e; first(e, v); return e; } -// Node head(const Edge& e) const { return graph->head(e); } -// Node tail(const Edge& e) const { return graph->tail(e); } +// Node target(const Edge& e) const { return graph->target(e); } +// Node source(const Edge& e) const { return graph->source(e); } // template Node aNode(const I& e) const { // return graph->aNode(e); } @@ -822,8 +822,8 @@ // //{ return graph->setInvalid(i); } // Node addNode() { return graph->addNode(); } -// Edge addEdge(const Node& tail, const Node& head) { -// return graph->addEdge(tail, head); } +// Edge addEdge(const Node& source, const Node& target) { +// return graph->addEdge(source, target); } // template void erase(const I& i) { graph->erase(i); } @@ -1063,9 +1063,9 @@ return e; } - Node tail(Edge e) const { + Node source(Edge e) const { return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } - Node head(Edge e) const { + Node target(Edge e) const { return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } Node aNode(OutEdgeIt e) const { @@ -1192,7 +1192,7 @@ void erase(const OutEdgeIt& e) const { OutEdgeIt f=e; this->next(f); - first_out_edges->set(this->tail(e), f); + first_out_edges->set(this->source(e), f); } }; @@ -1310,8 +1310,8 @@ // template< typename It > It first(Node v) const { // It e; first(e, v); return e; } -// Node head(const Edge& e) const { return gw.head(e); } -// Node tail(const Edge& e) const { return gw.tail(e); } +// Node target(const Edge& e) const { return gw.target(e); } +// Node source(const Edge& e) const { return gw.source(e); } // template Node aNode(const I& e) const { // return gw.aNode(e); } @@ -1325,8 +1325,8 @@ // //{ return gw.setInvalid(i); } // Node addNode() { return gw.addNode(); } -// Edge addEdge(const Node& tail, const Node& head) { -// return gw.addEdge(tail, head); } +// Edge addEdge(const Node& source, const Node& target) { +// return gw.addEdge(source, target); } // template void erase(const I& i) { gw.erase(i); } diff -r 741f3108a90f -r e997802b855c src/work/marci/experiment/graph_wrapper_st_ostream_op.h --- a/src/work/marci/experiment/graph_wrapper_st_ostream_op.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/experiment/graph_wrapper_st_ostream_op.h Sat Nov 13 12:53:28 2004 +0000 @@ -166,10 +166,10 @@ InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } - Node tail(const Edge& e) const { - return Node(graph->tail(static_cast(e))); } - Node head(const Edge& e) const { - return Node(graph->head(static_cast(e))); } + Node source(const Edge& e) const { + return Node(graph->source(static_cast(e))); } + Node target(const Edge& e) const { + return Node(graph->target(static_cast(e))); } bool valid(const Node& n) const { return graph->valid(static_cast(n)); } @@ -185,8 +185,8 @@ Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } Node addNode() const { return Node(graph->addNode()); } - Edge addEdge(const Node& tail, const Node& head) const { - return Edge(graph->addEdge(tail, head)); } + Edge addEdge(const Node& source, const Node& target) const { + return Edge(graph->addEdge(source, target)); } void erase(const Node& i) const { graph->erase(i); } void erase(const Edge& i) const { graph->erase(i); } @@ -272,10 +272,10 @@ Node bNode(const InEdgeIt& e) const { return Node(this->graph->bNode(e.e)); } - Node tail(const Edge& e) const { - return GraphWrapper::head(e); } - Node head(const Edge& e) const { - return GraphWrapper::tail(e); } + Node source(const Edge& e) const { + return GraphWrapper::target(e); } + Node target(const Edge& e) const { + return GraphWrapper::source(e); } }; @@ -489,7 +489,7 @@ // } OutEdgeIt& next(OutEdgeIt& e) const { if (e.out_or_in) { - typename Graph::Node n=this->graph->tail(e.out); + typename Graph::Node n=this->graph->source(e.out); this->graph->next(e.out); if (!this->graph->valid(e.out)) { e.out_or_in=false; this->graph->first(e.in, n); } @@ -506,11 +506,11 @@ // } Node aNode(const OutEdgeIt& e) const { - if (e.out_or_in) return this->graph->tail(e); else - return this->graph->head(e); } + if (e.out_or_in) return this->graph->source(e); else + return this->graph->target(e); } Node bNode(const OutEdgeIt& e) const { - if (e.out_or_in) return this->graph->head(e); else - return this->graph->tail(e); } + if (e.out_or_in) return this->graph->target(e); else + return this->graph->source(e); } }; /// A wrapper for composing the residual graph for directed flow and circulation problems. @@ -724,10 +724,10 @@ return e; } - Node tail(Edge e) const { - return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); } - Node head(Edge e) const { - return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); } + Node source(Edge e) const { + return ((e.forward) ? this->graph->source(e) : this->graph->target(e)); } + Node target(Edge e) const { + return ((e.forward) ? this->graph->target(e) : this->graph->source(e)); } Node aNode(OutEdgeIt e) const { return ((e.forward) ? this->graph->aNode(e.out) : @@ -913,7 +913,7 @@ void erase(const OutEdgeIt& e) const { OutEdgeIt f=e; this->next(f); - first_out_edges->set(this->tail(e), f.e); + first_out_edges->set(this->source(e), f.e); } }; @@ -1041,17 +1041,17 @@ OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } - Node tail(const Edge& e) { - if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) - return Node(this->graph->tail(e)); + Node source(const Edge& e) { + if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) + return Node(this->graph->source(e)); else - return Node(this->graph->head(e)); + return Node(this->graph->target(e)); } - Node head(const Edge& e) { - if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) - return Node(this->graph->head(e)); + Node target(const Edge& e) { + if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) + return Node(this->graph->target(e)); else - return Node(this->graph->tail(e)); + return Node(this->graph->source(e)); } Node aNode(const OutEdgeIt& e) const { @@ -1469,10 +1469,10 @@ return i; } - Node tail(const Edge& e) const { + Node source(const Edge& e) const { switch (e.spec) { case 0: - return Node(this->graph->tail(e)); + return Node(this->graph->source(e)); break; case 1: return S_NODE; @@ -1483,10 +1483,10 @@ break; } } - Node head(const Edge& e) const { + Node target(const Edge& e) const { switch (e.spec) { case 0: - return Node(this->graph->head(e)); + return Node(this->graph->target(e)); break; case 1: return Node(e.n); @@ -1506,17 +1506,17 @@ return this->graph->edgeNum()+this->graph->nodeNum(); } - Node aNode(const OutEdgeIt& e) const { return tail(e); } - Node aNode(const InEdgeIt& e) const { return head(e); } - Node bNode(const OutEdgeIt& e) const { return head(e); } - Node bNode(const InEdgeIt& e) const { return tail(e); } + Node aNode(const OutEdgeIt& e) const { return source(e); } + Node aNode(const InEdgeIt& e) const { return target(e); } + Node bNode(const OutEdgeIt& e) const { return target(e); } + Node bNode(const InEdgeIt& e) const { return source(e); } void addNode() const { } void addEdge() const { } // Node addNode() const { return Node(this->graph->addNode()); } -// Edge addEdge(const Node& tail, const Node& head) const { -// return Edge(this->graph->addEdge(tail, head)); } +// Edge addEdge(const Node& source, const Node& target) const { +// return Edge(this->graph->addEdge(source, target)); } // void erase(const Node& i) const { this->graph->erase(i); } // void erase(const Edge& i) const { this->graph->erase(i); } diff -r 741f3108a90f -r e997802b855c src/work/marci/experiment/iterator_bfs_demo.cc --- a/src/work/marci/experiment/iterator_bfs_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/experiment/iterator_bfs_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -22,7 +22,7 @@ graph(_graph), node_name_map(_node_name_map) { } string get(typename Graph::Edge e) const { return - (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); + (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e))); } }; diff -r 741f3108a90f -r e997802b855c src/work/marci/experiment/iterator_bfs_demo_1.cc --- a/src/work/marci/experiment/iterator_bfs_demo_1.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/experiment/iterator_bfs_demo_1.cc Sat Nov 13 12:53:28 2004 +0000 @@ -22,7 +22,7 @@ graph(_graph), node_name_map(_node_name_map) { } string get(typename Graph::Edge e) const { return - (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); + (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e))); } }; diff -r 741f3108a90f -r e997802b855c src/work/marci/experiment/list_graph.h --- a/src/work/marci/experiment/list_graph.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/experiment/list_graph.h Sat Nov 13 12:53:28 2004 +0000 @@ -122,8 +122,8 @@ friend std::ostream& operator<<(std::ostream& os, const Edge& i); //ListGraph* G; int id; - node_item* _tail; - node_item* _head; + node_item* _source; + node_item* _target; edge_item* _next_out; edge_item* _prev_out; edge_item* _next_in; @@ -149,22 +149,22 @@ return p; } - edge_item* _add_edge(node_item* _tail, node_item* _head) { + edge_item* _add_edge(node_item* _source, node_item* _target) { edge_item* e=new edge_item; e->id=edge_id++; - e->_tail=_tail; - e->_head=_head; + e->_source=_source; + e->_target=_target; - e->_prev_out=_tail->_last_out_edge; - if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e; - _tail->_last_out_edge=e; - if (!_tail->_first_out_edge) _tail->_first_out_edge=e; + e->_prev_out=_source->_last_out_edge; + if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e; + _source->_last_out_edge=e; + if (!_source->_first_out_edge) _source->_first_out_edge=e; e->_next_out=0; - e->_prev_in=_head->_last_in_edge; - if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e; - _head->_last_in_edge=e; - if (!_head->_first_in_edge) { _head->_first_in_edge=e; } + e->_prev_in=_target->_last_in_edge; + if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e; + _target->_last_in_edge=e; + if (!_target->_first_in_edge) { _target->_first_in_edge=e; } e->_next_in=0; ++_edge_num; @@ -184,45 +184,45 @@ void _delete_edge(edge_item* e) { if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else - (e->_tail)->_last_out_edge=e->_prev_out; + (e->_source)->_last_out_edge=e->_prev_out; if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else - (e->_tail)->_first_out_edge=e->_next_out; + (e->_source)->_first_out_edge=e->_next_out; if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else - (e->_head)->_last_in_edge=e->_prev_in; + (e->_target)->_last_in_edge=e->_prev_in; if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else - (e->_head)->_first_in_edge=e->_next_in; + (e->_target)->_first_in_edge=e->_next_in; delete e; --_edge_num; } - void _set_tail(edge_item* e, node_item* _tail) { + void _set_source(edge_item* e, node_item* _source) { if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else - (e->_tail)->_last_out_edge=e->_prev_out; + (e->_source)->_last_out_edge=e->_prev_out; if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else - (e->_tail)->_first_out_edge=e->_next_out; + (e->_source)->_first_out_edge=e->_next_out; - e->_tail=_tail; + e->_source=_source; - e->_prev_out=_tail->_last_out_edge; - if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e; - _tail->_last_out_edge=e; - if (!_tail->_first_out_edge) _tail->_first_out_edge=e; + e->_prev_out=_source->_last_out_edge; + if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e; + _source->_last_out_edge=e; + if (!_source->_first_out_edge) _source->_first_out_edge=e; e->_next_out=0; } - void _set_head(edge_item* e, node_item* _head) { + void _set_target(edge_item* e, node_item* _target) { if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else - (e->_head)->_last_in_edge=e->_prev_in; + (e->_target)->_last_in_edge=e->_prev_in; if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else - (e->_head)->_first_in_edge=e->_next_in; + (e->_target)->_first_in_edge=e->_next_in; - e->_head=_head; + e->_target=_target; - e->_prev_in=_head->_last_in_edge; - if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e; - _head->_last_in_edge=e; - if (!_head->_first_in_edge) { _head->_first_in_edge=e; } + e->_prev_in=_target->_last_in_edge; + if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e; + _target->_last_in_edge=e; + if (!_target->_first_in_edge) { _target->_first_in_edge=e; } e->_next_in=0; } @@ -247,8 +247,8 @@ //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); } //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); } //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); } - Node tail(Edge e) const { return e.tailNode(); } - Node head(Edge e) const { return e.headNode(); } + Node source(Edge e) const { return e.sourceNode(); } + Node target(Edge e) const { return e.targetNode(); } Node aNode(const OutEdgeIt& e) const { return e.aNode(); } Node aNode(const InEdgeIt& e) const { return e.aNode(); } @@ -277,8 +277,8 @@ e=InEdgeIt(*this, v); return e; } SymEdgeIt& /*getF*/first(SymEdgeIt& e, Node v) const { e=SymEdgeIt(*this, v); return e; } - //void getTail(Node& n, const Edge& e) const { n=tail(e); } - //void getHead(Node& n, const Edge& e) const { n=head(e); } + //void getSource(Node& n, const Edge& e) const { n=source(e); } + //void getTarget(Node& n, const Edge& e) const { n=target(e); } //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); } //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); } @@ -345,12 +345,12 @@ while (first().valid()) erase(first()); } - void setTail(Edge e, Node tail) { - _set_tail(e.edge, tail.node); + void setSource(Edge e, Node source) { + _set_source(e.edge, source.node); } - void setHead(Edge e, Node head) { - _set_head(e.edge, head.node); + void setTarget(Edge e, Node target) { + _set_target(e.edge, target.node); } /* stream operations, for testing purpose */ @@ -359,7 +359,7 @@ os << i.node->id; return os; } friend std::ostream& operator<<(std::ostream& os, const Edge& i) { - os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")"; + os << "(" << i.edge->_source->id << "--" << i.edge->id << "->" << i.edge->_target->id << ")"; return os; } @@ -426,8 +426,8 @@ friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; } friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; } protected: - Node tailNode() const { return Node(edge->_tail); } - Node headNode() const { return Node(edge->_head); } + Node sourceNode() const { return Node(edge->_source); } + Node targetNode() const { return Node(edge->_target); } public: friend std::ostream& operator<<(std::ostream& os, const Edge& i); }; @@ -447,7 +447,7 @@ protected: EdgeIt(edge_item* _e) : Edge(_e) { } EdgeIt& operator++() { - node_item* v=edge->_tail; + node_item* v=edge->_source; edge=edge->_next_out; while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } return *this; @@ -467,8 +467,8 @@ protected: OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } protected: - Node aNode() const { return Node(edge->_tail); } - Node bNode() const { return Node(edge->_head); } + Node aNode() const { return Node(edge->_source); } + Node bNode() const { return Node(edge->_target); } }; class InEdgeIt : public Edge { @@ -484,8 +484,8 @@ protected: InEdgeIt& operator++() { edge=edge->_next_in; return *this; } protected: - Node aNode() const { return Node(edge->_head); } - Node bNode() const { return Node(edge->_tail); } + Node aNode() const { return Node(edge->_target); } + Node bNode() const { return Node(edge->_source); } }; class SymEdgeIt : public Edge { @@ -510,7 +510,7 @@ protected: SymEdgeIt& operator++() { if (out_or_in) { - node_item* v=edge->_tail; + node_item* v=edge->_source; edge=edge->_next_out; if (!edge) { out_or_in=0; edge=v->_first_in_edge; } } else { @@ -520,9 +520,9 @@ } protected: Node aNode() const { - return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); } + return (out_or_in) ? Node(edge->_source) : Node(edge->_target); } Node bNode() const { - return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); } + return (out_or_in) ? Node(edge->_target) : Node(edge->_source); } }; }; diff -r 741f3108a90f -r e997802b855c src/work/marci/graph_concept.h --- a/src/work/marci/graph_concept.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/graph_concept.h Sat Nov 13 12:53:28 2004 +0000 @@ -103,10 +103,10 @@ //SymEdgeIt &next(SymEdgeIt &) const {} - /// Gives back the head node of an edge. - Node head(const Edge&) const { return INVALID; } - /// Gives back the tail node of an edge. - Node tail(const Edge&) const { return INVALID; } + /// Gives back the target node of an edge. + Node target(const Edge&) const { return INVALID; } + /// Gives back the source node of an edge. + Node source(const Edge&) const { return INVALID; } // Node aNode(SymEdgeIt) const {} // Node bNode(SymEdgeIt) const {} @@ -142,10 +142,10 @@ Node addNode() { return INVALID; } /// \brief Add a new edge to the graph. /// - /// Add a new edge to the graph with tail node \c tail - /// and head node \c head. + /// Add a new edge to the graph with source node \c source + /// and target node \c target. /// \return the new edge. - Edge addEdge(const Node& tail, const Node& head) { return INVALID; } + Edge addEdge(const Node& source, const Node& target) { return INVALID; } /// \brief Resets the graph. /// diff -r 741f3108a90f -r e997802b855c src/work/marci/iterator_bfs_demo.cc --- a/src/work/marci/iterator_bfs_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/iterator_bfs_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -23,7 +23,7 @@ graph(_graph), node_name_map(_node_name_map) { } string operator[](typename Graph::Edge e) const { return - (node_name_map[graph.tail(e)]+"->"+node_name_map[graph.head(e)]); + (node_name_map[graph.source(e)]+"->"+node_name_map[graph.target(e)]); } }; @@ -95,14 +95,14 @@ //cout << "edge: "; if (Graph::Edge(bfs)!=INVALID) { cout << edge_name[bfs] << /*endl*/", " << - node_name[G.tail(bfs)] << + node_name[G.source(bfs)] << (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[G.head(bfs)] << + node_name[G.target(bfs)] << (bfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { cout << "invalid" << /*endl*/", " << - node_name[bfs.tail()] << + node_name[bfs.source()] << (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << "invalid."; @@ -129,14 +129,14 @@ //cout << "edge: "; if (Graph::Edge(dfs)!=INVALID) { cout << edge_name[dfs] << /*endl*/", " << - node_name[G.tail(dfs)] << + node_name[G.source(dfs)] << (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[G.head(dfs)] << + node_name[G.target(dfs)] << (dfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { cout << "invalid" << /*endl*/", " << - node_name[dfs.tail()] << + node_name[dfs.source()] << (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << "invalid."; @@ -171,14 +171,14 @@ //cout << "edge: "; if (GW::Edge(bfs)!=INVALID) { cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << - node_name[gw.tail(bfs)] << + node_name[gw.source(bfs)] << (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[gw.head(bfs)] << + node_name[gw.target(bfs)] << (bfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { cout << "invalid" << /*endl*/", " << - node_name[bfs.tail()] << + node_name[bfs.source()] << (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << "invalid."; @@ -205,14 +205,14 @@ //cout << "edge: "; if (GW::Edge(dfs)!=INVALID) { cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << - node_name[gw.tail(dfs)] << + node_name[gw.source(dfs)] << (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[gw.head(dfs)] << + node_name[gw.target(dfs)] << (dfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { cout << "invalid" << /*endl*/", " << - node_name[dfs.tail()] << + node_name[dfs.source()] << (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << "invalid."; @@ -310,7 +310,7 @@ cout << "bfs and dfs iterator demo on the bidirected graph" << endl; // for(GW::EdgeIt e(gw); e!=INVALID; ++e) { -// cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " "; +// cout << node_name[gw.source(e)] << "->" << node_name[gw.target(e)] << " "; // } for(GW::NodeIt n(gw); n!=INVALID; ++n) { cout << node_name[GW::Node(n)] << ": "; @@ -334,14 +334,14 @@ //cout << "edge: "; if (GW::Edge(bfs)!=INVALID) { cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << - node_name[gw.tail(bfs)] << + node_name[gw.source(bfs)] << (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[gw.head(bfs)] << + node_name[gw.target(bfs)] << (bfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { cout << "invalid" << /*endl*/", " << - node_name[bfs.tail()] << + node_name[bfs.source()] << (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << "invalid."; @@ -368,14 +368,14 @@ //cout << "edge: "; if (GW::Edge(dfs)!=INVALID) { cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << - node_name[gw.tail(dfs)] << + node_name[gw.source(dfs)] << (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[gw.head(dfs)] << + node_name[gw.target(dfs)] << (dfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { cout << "invalid" << /*endl*/", " << - node_name[dfs.tail()] << + node_name[dfs.source()] << (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << "invalid."; diff -r 741f3108a90f -r e997802b855c src/work/marci/leda/bipartite_matching_comparison.cc --- a/src/work/marci/leda/bipartite_matching_comparison.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/leda/bipartite_matching_comparison.cc Sat Nov 13 12:53:28 2004 +0000 @@ -129,7 +129,7 @@ } FOR_EACH_LOC(BGW::EdgeIt, e, bgw) - hg.addEdge(b_s_nodes[bgw.tail(e)], b_t_nodes[bgw.head(e)]); + hg.addEdge(b_s_nodes[bgw.source(e)], b_t_nodes[bgw.target(e)]); ConstMap cm(1); SageGraph::EdgeMap flow(hg); //0 diff -r 741f3108a90f -r e997802b855c src/work/marci/leda/leda_graph_wrapper.h --- a/src/work/marci/leda/leda_graph_wrapper.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/leda/leda_graph_wrapper.h Sat Nov 13 12:53:28 2004 +0000 @@ -213,21 +213,21 @@ // return e; // } - ///Gives back the head node of an edge. - Node head(Edge e) const { + ///Gives back the target node of an edge. + Node target(Edge e) const { return Node(l_graph->target(e.l_e)); } - ///Gives back the tail node of an edge. - Node tail(Edge e) const { + ///Gives back the source node of an edge. + Node source(Edge e) const { return Node(l_graph->source(e.l_e)); } - Node aNode(InEdgeIt e) const { return head(e); } - Node aNode(OutEdgeIt e) const { return tail(e); } + Node aNode(InEdgeIt e) const { return target(e); } + Node aNode(OutEdgeIt e) const { return source(e); } // Node aNode(SymEdgeIt) const {} - Node bNode(InEdgeIt e) const { return tail(e); } - Node bNode(OutEdgeIt e) const { return head(e); } + Node bNode(InEdgeIt e) const { return source(e); } + Node bNode(OutEdgeIt e) const { return target(e); } // Node bNode(SymEdgeIt) const {} /// Checks if a node iterator is valid @@ -244,8 +244,8 @@ //void setInvalid(Edge &) const {}; Node addNode() const { return Node(l_graph->new_node()); } - Edge addEdge(Node tail, Node head) const { - return Edge(l_graph->new_edge(tail.l_n, head.l_n)); + Edge addEdge(Node source, Node target) const { + return Edge(l_graph->new_edge(source.l_n, target.l_n)); } void erase(Node n) const { l_graph->del_node(n.l_n); } diff -r 741f3108a90f -r e997802b855c src/work/marci/leda/max_bipartite_matching_demo.cc --- a/src/work/marci/leda/max_bipartite_matching_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/leda/max_bipartite_matching_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -103,10 +103,10 @@ // cout << G.id(n) << ": "; // cout << "out edges: "; // for(OutEdgeIt e=G.first(n); G.valid(e); G.next(e)) -// cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " "; +// cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) << " "; // cout << "in edges: "; // for(InEdgeIt e=G.first(n); G.valid(e); G.next(e)) -// cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " "; +// cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) << " "; // cout << endl; // } @@ -123,7 +123,7 @@ int i=0; while (max_flow_test.augmentOnShortestPath()) { // for(EdgeIt e=G.first(); G.valid(e); G.next(e)) -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; +// std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; // std::cout<(); G.valid(e); G.next(e)) // if (flow.get(e)) -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; +// std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; // std::cout<(); G.valid(e); G.next(e)) // if (!flow.get(e)) -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; +// std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; // std::cout<(); G.valid(e); G.next(e)) -// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; +// // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; // // std::cout<(); G.valid(e); G.next(e)) // // if (flow.get(e)) -// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; +// // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; // // std::cout<(); G.valid(e); G.next(e)) // // if (!flow.get(e)) -// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; +// // std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; // // std::cout<(); G.valid(e); G.next(e)) // if (flow.get(e)) -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; +// std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; // std::cout<(); G.valid(e); G.next(e)) // if (!flow.get(e)) -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; +// std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " "; // std::cout<"+node_name_map.get(graph.head(e))); + (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e))); } }; diff -r 741f3108a90f -r e997802b855c src/work/marci/leda_graph_demo.cc --- a/src/work/marci/leda_graph_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/leda_graph_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -38,10 +38,10 @@ // cout << G.id(n) << ": "; // cout << "out edges: "; // for(OutEdgeIt e=G.first(n); G.valid(e); G.next(e)) -// cout << G.id(G.tail(e)) << "-" << cap.get(e) << "->" << G.id(G.head(e)) << " "; +// cout << G.id(G.source(e)) << "-" << cap.get(e) << "->" << G.id(G.target(e)) << " "; // cout << "in edges: "; // for(InEdgeIt e=G.first(n); G.valid(e); G.next(e)) -// cout << G.id(G.tail(e)) << "-" << cap.get(e) << "->" << G.id(G.head(e)) << " "; +// cout << G.id(G.source(e)) << "-" << cap.get(e) << "->" << G.id(G.target(e)) << " "; // cout << endl; // } @@ -64,7 +64,7 @@ int i=0; while (max_flow_test.augmentOnShortestPath()) { // for(EdgeIt e=G.template first(); e.valid(); ++e) { -// std::cout<<"("<"<"<(); e.valid(); ++e) { -// std::cout<<"("<"<"<0) + if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) std::cout << "Slackness does not hold!" << std::endl; } } @@ -79,9 +79,9 @@ // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; // FOR_EACH_LOC(Graph::EdgeIt, e, g) { -// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) +// if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) // std::cout << "Slackness does not hold!" << std::endl; -// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) +// if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) // std::cout << "Slackness does not hold!" << std::endl; // } // } @@ -106,9 +106,9 @@ std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; FOR_EACH_LOC(Graph::EdgeIt, e, g) { - if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) + if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) std::cout << "Slackness does not hold!" << std::endl; - if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) + if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) std::cout << "Slackness does not hold!" << std::endl; } } @@ -135,9 +135,9 @@ std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; FOR_EACH_LOC(Graph::EdgeIt, e, g) { - if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) + if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) std::cout << "Slackness does not hold!" << std::endl; - if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) + if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) std::cout << "Slackness does not hold!" << std::endl; } } @@ -153,9 +153,9 @@ // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; // FOR_EACH_LOC(Graph::EdgeIt, e, g) { -// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) +// if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) // std::cout << "Slackness does not hold!" << std::endl; -// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) +// if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) // std::cout << "Slackness does not hold!" << std::endl; // } // } @@ -171,9 +171,9 @@ // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; // FOR_EACH_LOC(Graph::EdgeIt, e, g) { -// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) +// if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) // std::cout << "Slackness does not hold!" << std::endl; -// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) +// if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) // std::cout << "Slackness does not hold!" << std::endl; // } // } diff -r 741f3108a90f -r e997802b855c src/work/marci/max_flow_demo.cc --- a/src/work/marci/max_flow_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/max_flow_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -47,9 +47,9 @@ max_flow_test.minCut(cut); for(Graph::EdgeIt e(g); e!=INVALID; ++e) { - if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) + if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) std::cout << "Slackness does not hold!" << std::endl; - if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) + if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) std::cout << "Slackness does not hold!" << std::endl; } } @@ -63,9 +63,9 @@ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; for(Graph::EdgeIt e(g); e!=INVALID; ++e) { - if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) + if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) std::cout << "Slackness does not hold!" << std::endl; - if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) + if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) std::cout << "Slackness does not hold!" << std::endl; } } @@ -90,9 +90,9 @@ std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; for(Graph::EdgeIt e(g); e!=INVALID; ++e) { - if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) + if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) std::cout << "Slackness does not hold!" << std::endl; - if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) + if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) std::cout << "Slackness does not hold!" << std::endl; } } @@ -108,9 +108,9 @@ std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; for(Graph::EdgeIt e(g); e!=INVALID; ++e) { - if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) + if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) std::cout << "Slackness does not hold!" << std::endl; - if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) + if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) std::cout << "Slackness does not hold!" << std::endl; } } @@ -126,9 +126,9 @@ std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; for(Graph::EdgeIt e(g); e!=INVALID; ++e) { - if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) + if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) std::cout << "Slackness does not hold!" << std::endl; - if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) + if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) std::cout << "Slackness does not hold!" << std::endl; } } @@ -144,9 +144,9 @@ std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; for(Graph::EdgeIt e(g); e!=INVALID; ++e) { - if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) + if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) std::cout << "Slackness does not hold!" << std::endl; - if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) + if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) std::cout << "Slackness does not hold!" << std::endl; } } diff -r 741f3108a90f -r e997802b855c src/work/marci/oldies/edmonds_karp.h --- a/src/work/marci/oldies/edmonds_karp.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/oldies/edmonds_karp.h Sat Nov 13 12:53:28 2004 +0000 @@ -59,15 +59,15 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); + Node v=res_graph.source(e); + Node w=res_graph.target(e); pred.set(w, e); if (res_graph.valid(pred[v])) { free.set(w, std::min(free[v], res_graph.resCap(e))); } else { free.set(w, res_graph.resCap(e)); } - if (res_graph.head(e)==t) { _augment=true; break; } + if (res_graph.target(e)==t) { _augment=true; break; } } ++bfs; @@ -79,7 +79,7 @@ while (res_graph.valid(pred[n])) { ResGWEdge e=pred[n]; res_graph.augment(e, augment_value); - n=res_graph.tail(e); + n=res_graph.source(e); } } @@ -101,9 +101,9 @@ // int get(const typename MapGraphWrapper::Node& n) const { // return dist[n]; } // bool get(const typename MapGraphWrapper::Edge& e) const { -// return (dist.get(g->tail(e))head(e))); } +// return (dist.get(g->source(e))target(e))); } bool operator[](const typename MapGraphWrapper::Edge& e) const { - return (dist[g->tail(e)]head(e)]); + return (dist[g->source(e)]target(e)]); } }; @@ -123,7 +123,7 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); } ++bfs; } //computing distances from s in the residual graph @@ -152,8 +152,8 @@ { typename FilterResGW::EdgeIt e; for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { - //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); + //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); @@ -206,7 +206,7 @@ while (F.valid(pred[n])) { typename MG::Edge e=pred[n]; res_graph.augment(original_edge[e], augment_value); - n=F.tail(e); + n=F.source(e); if (residual_capacity[e]==augment_value) F.erase(e); else @@ -254,15 +254,15 @@ ResGWOutEdgeIt e=bfs; if (res_graph.valid(e)) { if (bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); residual_capacity.set(f, res_graph.resCap(e)); } else { - if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); + if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); @@ -316,7 +316,7 @@ while (F.valid(pred[n])) { typename MG::Edge e=pred[n]; res_graph.augment(original_edge[e], augment_value); - n=F.tail(e); + n=F.source(e); if (residual_capacity[e]==augment_value) F.erase(e); else @@ -343,7 +343,7 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); } ++bfs; } //computing distances from s in the residual graph @@ -440,7 +440,7 @@ while (erasing_res_graph.valid(pred[n])) { typename ErasingResGW::OutEdgeIt e=pred[n]; res_graph.augment(e, augment_value); - n=erasing_res_graph.tail(e); + n=erasing_res_graph.source(e); if (res_graph.resCap(e)==0) erasing_res_graph.erase(e); } @@ -535,15 +535,15 @@ // while ( !bfs.finished() ) { // AugOutEdgeIt e=bfs; // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// Node v=res_graph.tail(e); -// Node w=res_graph.head(e); +// Node v=res_graph.source(e); +// Node w=res_graph.target(e); // pred.set(w, e); // if (res_graph.valid(pred.get(v))) { // free.set(w, std::min(free.get(v), res_graph.free(e))); // } else { // free.set(w, res_graph.free(e)); // } -// n=res_graph.head(e); +// n=res_graph.target(e); // if (T->get(n) && (used.get(n)<1) ) { // //Num u=0; // //for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) @@ -565,7 +565,7 @@ // while (res_graph.valid(pred.get(n))) { // AugEdge e=pred.get(n); // res_graph.augment(e, augment_value); -// n=res_graph.tail(e); +// n=res_graph.source(e); // } // used.set(n, 1); //mind2 vegen jav // } @@ -606,7 +606,7 @@ // // while ( !bfs.finished() ) { // // AugOutEdgeIt e=bfs; // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); +// // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); // // } // // ++bfs; @@ -628,8 +628,8 @@ // // //Making F to the graph containing the edges of the residual graph // // //which are in some shortest paths // // for(typename AugGraph::EdgeIt e=res_graph.template first(); res_graph.valid(e); res_graph.next(e)) { -// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { -// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); +// // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { +// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); // // original_edge.update(); // // original_edge.set(f, e); // // residual_capacity.update(); @@ -681,7 +681,7 @@ // // while (F.valid(pred.get(n))) { // // typename MutableGraph::Edge e=pred.get(n); // // res_graph.augment(original_edge.get(e), augment_value); -// // n=F.tail(e); +// // n=F.source(e); // // if (residual_capacity.get(e)==augment_value) // // F.erase(e); // // else @@ -732,7 +732,7 @@ // while ( !bfs.finished() ) { // typename ErasingResGraphWrapper::OutEdgeIt e=bfs; // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); +// dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); // } // ++bfs; // } //computing distances from s in the residual graph @@ -809,7 +809,7 @@ // while (res_graph.valid(pred.get(n))) { // EAugEdge e=pred.get(n); // res_graph.augment(e, augment_value); -// n=res_graph.tail(e); +// n=res_graph.source(e); // if (res_graph.free(e)==0) // res_graph.erase(e); // } @@ -902,17 +902,17 @@ // // while ( !bfs.finished() ) { // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); // // if (e.valid() && bfs.isBNodeNewlyReached()) { -// // Node v=res_graph.tail(e); -// // Node w=res_graph.head(e); +// // Node v=res_graph.source(e); +// // Node w=res_graph.target(e); // // pred.set(w, e); // // if (pred.get(v).valid()) { // // free.set(w, std::min(free.get(v), e.free())); // // } else { // // free.set(w, e.free()); // // } -// // if (TMap.get(res_graph.head(e))) { +// // if (TMap.get(res_graph.target(e))) { // // _augment=true; -// // reached_t_node=res_graph.head(e); +// // reached_t_node=res_graph.target(e); // // break; // // } // // } @@ -926,7 +926,7 @@ // // while (pred.get(n).valid()) { // // AugEdge e=pred.get(n); // // e.augment(augment_value); -// // n=res_graph.tail(e); +// // n=res_graph.source(e); // // } // // } diff -r 741f3108a90f -r e997802b855c src/work/marci/oldies/marci_graph_demo.cc --- a/src/work/marci/oldies/marci_graph_demo.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/oldies/marci_graph_demo.cc Sat Nov 13 12:53:28 2004 +0000 @@ -31,7 +31,7 @@ std::cout << "node " << G.id(i) << std::endl; std::cout << " outdegree (OutEdgeIt): " << count(G.first(i)) << " "; for(OutEdgeIt j=G.first(i); G.valid(j); G.next(j)) { - std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") "; + std::cout << "(" << G.id(G.source(j)) << "--" << G.id(j) << "->" << G.id(G.target(j)) << ") "; } std::cout << std::endl; @@ -89,9 +89,9 @@ _i*=_ii; ++_ii; } - std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; + std::cout << "node and edge property values on the sources and targets of edges..." << std::endl; for(EdgeIt j=G.first(); G.valid(j); G.next(j)) { - std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " "; + std::cout << my_property_vector.get(G.source(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.target(j)) << " "; } std::cout << std::endl; /* @@ -158,10 +158,10 @@ std::cout << node_name.get(i) << ": "; std::cout << "out edges: "; for(OutEdgeIt j=flowG.first(i); flowG.valid(j); flowG.next(j)) - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; + std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; std::cout << "in edges: "; for(InEdgeIt j=flowG.first(i); flowG.valid(j); flowG.next(j)) - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; + std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; std::cout << std::endl; } @@ -171,22 +171,22 @@ //flowG.deleteEdge(v1_v3); - //flowG.setTail(v3_t, v2); - //flowG.setHead(v3_t, s); + //flowG.setSource(v3_t, v2); + //flowG.setTarget(v3_t, s); /* for(NodeIt i=flowG.first(); flowG.valid(i); flowG.next(i)) { std::cout << node_name.get(i) << ": "; std::cout << "out edges: "; for(OutEdgeIt j=flowG.first(i); flowG.valid(j); flowG.next(j)) - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; + std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; std::cout << "in edges: "; for(InEdgeIt j=flowG.first(i); flowG.valid(j); flowG.next(j)) - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; + std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; std::cout << std::endl; } for(EdgeIt e=flowG.first(); flowG.valid(e); flowG.next(e)) { - std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " "; + std::cout << node_name.get(flowG.source(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.target(e)) << " "; } */ /* @@ -196,10 +196,10 @@ std::cout << node_name.get(i) << ": "; std::cout << "out edges: "; for(OutEdgeIt j=flowG.first(i); flowG.valid(j); flowG.next(j)) - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; + std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; std::cout << "in edges: "; for(InEdgeIt j=flowG.first(i); flowG.valid(j); flowG.next(j)) - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; + std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; std::cout << std::endl; } } @@ -210,10 +210,10 @@ std::cout << node_name.get(i) << ": "; std::cout << "out edges: "; for(OutEdgeIt j=flowG.first(i); flowG.valid(j); flowG.next(j)) - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; + std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; std::cout << "in edges: "; for(InEdgeIt j=flowG.first(i); flowG.valid(j); flowG.next(j)) - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; + std::cout << node_name.get(flowG.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.target(j)) << " "; std::cout << std::endl; } } @@ -228,12 +228,12 @@ /* max_flow_test.augmentOnBlockingFlow(); for(EdgeIt e=flowG.template first(); flowG.valid(e); flowG.next(e)) { - std::cout<<"("<"<"<(); for(EdgeIt e=flowG.template first(); flowG.valid(e); flowG.next(e)) { - std::cout<<"("<"<"<(); flowG.valid(e); flowG.next(e)) { - std::cout<<"("<"<"<(); flowG.valid(e); flowG.next(e)) { - std::cout<<"("<"<"<" << 1+g.id(g.head(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl; + cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl; } { Graph::NodeIt n; @@ -75,15 +75,15 @@ Graph::EdgeIt e; for (g.first(e); g.valid(e); g.next(e)) { - if (cut[g.tail(e)] && !cut[g.head(e)]) { - cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e)) + if (cut[g.source(e)] && !cut[g.target(e)]) { + cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) << "(forward edge) flow: " << flow[e] << " cap: " << cap[e]<< endl; if (flow[e]!=cap[e]) std::cout << "Slackness does not hold!" << std::endl; } - if (!cut[g.tail(e)] && cut[g.head(e)]) { - cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e)) + if (!cut[g.source(e)] && cut[g.target(e)]) { + cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) << "(backward edge) flow: " << flow[e] << endl; if (flow[e]!=0) std::cout << "Slackness does not hold!" << std::endl; @@ -105,9 +105,9 @@ // max_flow_test.actMinCut(cut); // FOR_EACH_LOC(Graph::EdgeIt, e, g) { -// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) +// if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) // std::cout << "Slackness does not hold!" << std::endl; -// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) +// if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) // std::cout << "Slackness does not hold!" << std::endl; // } // } @@ -121,9 +121,9 @@ // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; // FOR_EACH_LOC(Graph::EdgeIt, e, g) { -// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) +// if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) // std::cout << "Slackness does not hold!" << std::endl; -// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) +// if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) // std::cout << "Slackness does not hold!" << std::endl; // } // } @@ -148,9 +148,9 @@ // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; // FOR_EACH_LOC(Graph::EdgeIt, e, g) { -// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) +// if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) // std::cout << "Slackness does not hold!" << std::endl; -// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) +// if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) // std::cout << "Slackness does not hold!" << std::endl; // } // } @@ -177,9 +177,9 @@ // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; // FOR_EACH_LOC(Graph::EdgeIt, e, g) { -// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) +// if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) // std::cout << "Slackness does not hold!" << std::endl; -// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) +// if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) // std::cout << "Slackness does not hold!" << std::endl; // } // } @@ -195,9 +195,9 @@ // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; // FOR_EACH_LOC(Graph::EdgeIt, e, g) { -// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) +// if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) // std::cout << "Slackness does not hold!" << std::endl; -// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) +// if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) // std::cout << "Slackness does not hold!" << std::endl; // } // } @@ -213,9 +213,9 @@ // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; // FOR_EACH_LOC(Graph::EdgeIt, e, g) { -// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) +// if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) // std::cout << "Slackness does not hold!" << std::endl; -// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) +// if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) // std::cout << "Slackness does not hold!" << std::endl; // } // } diff -r 741f3108a90f -r e997802b855c src/work/marci/preflow_demo_athos.cc --- a/src/work/marci/preflow_demo_athos.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/preflow_demo_athos.cc Sat Nov 13 12:53:28 2004 +0000 @@ -28,12 +28,12 @@ //ListGraph::NodeMap cut=max_flow_test.mincut(); //int cut_value=0; //for(EachEdgeIt e=G.first(); e.valid(); ++e) { - // if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e); + // if (cut.get(G.source(e)) && !cut.get(G.target(e))) cut_value+=cap.get(e); //} double post_time=currTime(); //std::cout << "maximum flow: "<< std::endl; //for(EachEdgeIt e=G.first(); e.valid(); ++e) { - // std::cout<<"("<"<"<(); e.valid(); ++e) { - if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e); + if (cut.get(G.source(e)) && !cut.get(G.target(e))) cut_value+=cap.get(e); } double post_time=currTime(); //std::cout << "maximum flow: "<< std::endl; //for(EachEdgeIt e=G.first(); e.valid(); ++e) { - // std::cout<<"("<"<"<(); e.valid(); ++e) { - if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e); + if (cut.get(G.source(e)) && !cut.get(G.target(e))) cut_value+=cap.get(e); } double post_time=currTime(); //std::cout << "maximum flow: "<< std::endl; //for(EachEdgeIt e=G.first(); e.valid(); ++e) { - // std::cout<<"("<"<"<first(f); edgepath[e]->valid(f); edgepath[e]->next(f)) { - //dep//cout << " " << sublayer->id(sublayer->tail(f)) << "-" << sublayer->id(sublayer->head(f)); + //dep//cout << " " << sublayer->id(sublayer->source(f)) << "-" << sublayer->id(sublayer->target(f)); submap[f]+=incr; } - //dep////cout << EPGr2.id(EPGr2.head(f)) << endl; + //dep////cout << EPGr2.id(EPGr2.target(f)) << endl; //dep//cout << endl; } else @@ -107,15 +107,15 @@ typedef typename P::EdgeIt PEdgeIt; PEdgeIt f; - cout << "Edge " << id(tail(e)) << " - " << id(head(e)) << " in actual layer is"; + cout << "Edge " << id(source(e)) << " - " << id(target(e)) << " in actual layer is"; if(edgepath[e]) { cout << endl << "Path"; for(edgepath[e]->first(f); edgepath[e]->valid(f); edgepath[e]->next(f)) { - cout << " " << sublayer->id(sublayer->tail(f)) << "-" << sublayer->id(sublayer->head(f)); + cout << " " << sublayer->id(sublayer->source(f)) << "-" << sublayer->id(sublayer->target(f)); } - //cout << EPGr2.id(EPGr2.head(f)) << endl; + //cout << EPGr2.id(EPGr2.target(f)) << endl; cout << endl; } else @@ -234,10 +234,10 @@ /// Go to the next edge. typename Gact::EdgeIt &next(typename Gact::EdgeIt &i) const { return actuallayer.next(i);} - ///Gives back the head node of an edge. - typename Gact::Node head(typename Gact::Edge edge) const { return actuallayer.head(edge); } - ///Gives back the tail node of an edge. - typename Gact::Node tail(typename Gact::Edge edge) const { return actuallayer.tail(edge); } + ///Gives back the target node of an edge. + typename Gact::Node target(typename Gact::Edge edge) const { return actuallayer.target(edge); } + ///Gives back the source node of an edge. + typename Gact::Node source(typename Gact::Edge edge) const { return actuallayer.source(edge); } // Node aNode(InEdgeIt) const {} // Node aNode(OutEdgeIt) const {} @@ -279,8 +279,8 @@ typename Gact::Node addNode() { return actuallayer.addNode();} ///Add a new edge to the graph. - ///Add a new edge to the graph with tail node \c tail - ///and head node \c head. + ///Add a new edge to the graph with source node \c source + ///and target node \c target. ///\return the new edge. typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);} diff -r 741f3108a90f -r e997802b855c src/work/peter/edgepathgraph_test.cc --- a/src/work/peter/edgepathgraph_test.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/peter/edgepathgraph_test.cc Sat Nov 13 12:53:28 2004 +0000 @@ -135,15 +135,15 @@ typedef DPath::EdgeIt PEdgeIt; PEdgeIt f; - cout << "Edge " << EPGr.id(EPGr.tail(e)) << " - " << EPGr.id(EPGr.head(e)) << " in actual layer is"; + cout << "Edge " << EPGr.id(EPGr.source(e)) << " - " << EPGr.id(EPGr.target(e)) << " in actual layer is"; if(EPGr.edgepath[e]) { cout << endl << "Path"; for(EPGr.edgepath[e]->first(f); EPGr.edgepath[e]->valid(f); EPGr.edgepath[e]->next(f)) { - cout << " " << EPGr2.id(EPGr2.tail(f)) << "-" << EPGr2.id(EPGr2.head(f)); + cout << " " << EPGr2.id(EPGr2.source(f)) << "-" << EPGr2.id(EPGr2.target(f)); } - //cout << EPGr2.id(EPGr2.head(f)) << endl; + //cout << EPGr2.id(EPGr2.target(f)) << endl; cout << endl; } else @@ -169,13 +169,13 @@ cout << "actlaymap: "; for(EdgeIt e(EPGr.actuallayer);EPGr.actuallayer.valid(e);EPGr.actuallayer.next(e)) { - cout << EPGr.id(EPGr.tail(e)) << "-" << EPGr.id(EPGr.head(e)) << ":" << actlaymap[e] << " "; + cout << EPGr.id(EPGr.source(e)) << "-" << EPGr.id(EPGr.target(e)) << ":" << actlaymap[e] << " "; } cout << endl; cout << "sublaymap: "; for(ListGraph::EdgeIt e(EPGr2.actuallayer);EPGr2.actuallayer.valid(e);EPGr2.actuallayer.next(e)) { - cout << EPGr2.id(EPGr2.tail(e)) << "-" << EPGr2.id(EPGr2.head(e)) << ":" << sublaymap[e] << " "; + cout << EPGr2.id(EPGr2.source(e)) << "-" << EPGr2.id(EPGr2.target(e)) << ":" << sublaymap[e] << " "; } cout << endl; //EdgeMap-ok kiirasa#vege @@ -190,13 +190,13 @@ cout << "actlaymap: "; for(EdgeIt e(EPGr.actuallayer);EPGr.actuallayer.valid(e);EPGr.actuallayer.next(e)) { - cout << EPGr.id(EPGr.tail(e)) << "-" << EPGr.id(EPGr.head(e)) << ":" << actlaymap[e] << " "; + cout << EPGr.id(EPGr.source(e)) << "-" << EPGr.id(EPGr.target(e)) << ":" << actlaymap[e] << " "; } cout << endl; cout << "sublaymap: "; for(ListGraph::EdgeIt e(EPGr2.actuallayer);EPGr2.actuallayer.valid(e);EPGr2.actuallayer.next(e)) { - cout << EPGr2.id(EPGr2.tail(e)) << "-" << EPGr2.id(EPGr2.head(e)) << ":" << sublaymap[e] << " "; + cout << EPGr2.id(EPGr2.source(e)) << "-" << EPGr2.id(EPGr2.target(e)) << ":" << sublaymap[e] << " "; } cout << endl; //EdgeMap-ok kiirasa#vege diff -r 741f3108a90f -r e997802b855c src/work/peter/hierarchygraph.h --- a/src/work/peter/hierarchygraph.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/peter/hierarchygraph.h Sat Nov 13 12:53:28 2004 +0000 @@ -60,9 +60,9 @@ cerr << "The given edge is not in the given network!" << endl; return -1; } - else if ((actuallayer->id (actuallayer->tail (actedge)) != + else if ((actuallayer->id (actuallayer->source (actedge)) != actuallayer->id (*actuallayernode)) - && (actuallayer->id (actuallayer->head (actedge)) != + && (actuallayer->id (actuallayer->target (actedge)) != actuallayer->id (*actuallayernode))) { cerr << "The given edge does not connect to the given node!" << @@ -132,23 +132,23 @@ { for (iei = actuallayer->first (iei, (*actuallayernode)); ((actuallayer->valid (iei)) - && (actuallayer->head (iei) == (*actuallayernode))); + && (actuallayer->target (iei) == (*actuallayernode))); actuallayer->next (iei)) { cout << actuallayer->id (actuallayer-> - tail (iei)) << " " << actuallayer-> - id (actuallayer->head (iei)) << endl; + source (iei)) << " " << actuallayer-> + id (actuallayer->target (iei)) << endl; edgenumber++; } //cout << "Number of in-edges: " << edgenumber << endl; for (oei = actuallayer->first (oei, (*actuallayernode)); ((actuallayer->valid (oei)) - && (actuallayer->tail (oei) == (*actuallayernode))); + && (actuallayer->source (oei) == (*actuallayernode))); actuallayer->next (oei)) { cout << actuallayer->id (actuallayer-> - tail (oei)) << " " << actuallayer-> - id (actuallayer->head (oei)) << endl; + source (oei)) << " " << actuallayer-> + id (actuallayer->target (oei)) << endl; edgenumber++; } //cout << "Number of in+out-edges: " << edgenumber << endl; @@ -327,15 +327,15 @@ return actuallayer.next (i); } - ///Gives back the head node of an edge. - typename Gact::Node head (typename Gact::Edge edge) const + ///Gives back the target node of an edge. + typename Gact::Node target (typename Gact::Edge edge) const { - return actuallayer.head (edge); + return actuallayer.target (edge); } - ///Gives back the tail node of an edge. - typename Gact::Node tail (typename Gact::Edge edge) const + ///Gives back the source node of an edge. + typename Gact::Node source (typename Gact::Edge edge) const { - return actuallayer.tail (edge); + return actuallayer.source (edge); } // Node aNode(InEdgeIt) const {} @@ -393,8 +393,8 @@ } ///Add a new edge to the graph. - ///Add a new edge to the graph with tail node \c tail - ///and head node \c head. + ///Add a new edge to the graph with source node \c source + ///and target node \c target. ///\return the new edge. typename Gact::Edge addEdge (typename Gact::Node node1, typename Gact::Node node2) diff -r 741f3108a90f -r e997802b855c src/work/peter/path/path.h --- a/src/work/peter/path/path.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/peter/path/path.h Sat Nov 13 12:53:28 2004 +0000 @@ -108,14 +108,14 @@ /// Starting point of the path. /// Returns INVALID if the path is empty. GraphNode from() const { - return empty() ? INVALID : gr->tail(edges[0]); + return empty() ? INVALID : gr->source(edges[0]); } /// \brief End point of the path. /// /// End point of the path. /// Returns INVALID if the path is empty. GraphNode to() const { - return empty() ? INVALID : gr->head(edges[length()-1]); + return empty() ? INVALID : gr->target(edges[length()-1]); } /// \brief Initializes node or edge iterator to point to the first @@ -153,19 +153,19 @@ return ++e; } - /// \brief Returns node iterator pointing to the head node of the + /// \brief Returns node iterator pointing to the target node of the /// given edge iterator. - NodeIt head(const EdgeIt& e) const { + NodeIt target(const EdgeIt& e) const { if( DM::range_check && !e.valid() ) - fault("DirPath::head() on invalid iterator"); + fault("DirPath::target() on invalid iterator"); return NodeIt(*this, e.idx+1); } - /// \brief Returns node iterator pointing to the tail node of the + /// \brief Returns node iterator pointing to the source node of the /// given edge iterator. - NodeIt tail(const EdgeIt& e) const { + NodeIt source(const EdgeIt& e) const { if( DM::range_check && !e.valid() ) - fault("DirPath::tail() on invalid iterator"); + fault("DirPath::source() on invalid iterator"); return NodeIt(*this, e.idx); } @@ -254,7 +254,7 @@ if(idx >= p->length()) return p->to(); else if(idx >= 0) - return p->gr->tail(p->edges[idx]); + return p->gr->source(p->edges[idx]); else return INVALID; } @@ -312,7 +312,7 @@ ///Push a new edge to the front of the path. ///\sa setStartNode void pushFront(const GraphEdge& e) { - if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) { + if( DM::consistensy_check && !empty() && P.gr->target(e)!=from() ) { fault("DirPath::Builder::pushFront: nonincident edge"); } front.push_back(e); @@ -323,7 +323,7 @@ ///Push a new edge to the back of the path. ///\sa setStartNode void pushBack(const GraphEdge& e) { - if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) { + if( DM::consistensy_check && !empty() && P.gr->source(e)!=to() ) { fault("DirPath::Builder::pushBack: nonincident edge"); } back.push_back(e); @@ -362,21 +362,21 @@ GraphNode from() const { if( ! front.empty() ) - return P.gr->tail(front[front.size()-1]); + return P.gr->source(front[front.size()-1]); else if( ! P.empty() ) - return P.gr->tail(P.edges[0]); + return P.gr->source(P.edges[0]); else if( ! back.empty() ) - return P.gr->tail(back[0]); + return P.gr->source(back[0]); else return INVALID; } GraphNode to() const { if( ! back.empty() ) - return P.gr->head(back[back.size()-1]); + return P.gr->target(back[back.size()-1]); else if( ! P.empty() ) - return P.gr->head(P.edges[P.length()-1]); + return P.gr->target(P.edges[P.length()-1]); else if( ! front.empty() ) - return P.gr->head(front[0]); + return P.gr->target(front[0]); else return INVALID; } @@ -471,14 +471,14 @@ /// Starting point of the path. /// Returns INVALID if the path is empty. GraphNode from() const { - return empty() ? INVALID : gr->tail(edges[0]); + return empty() ? INVALID : gr->source(edges[0]); } /// \brief End point of the path. /// /// End point of the path. /// Returns INVALID if the path is empty. GraphNode to() const { - return empty() ? INVALID : gr->head(edges[length()-1]); + return empty() ? INVALID : gr->target(edges[length()-1]); } /// \brief Initializes node or edge iterator to point to the first @@ -516,19 +516,19 @@ return ++e; } - /// \brief Returns node iterator pointing to the head node of the + /// \brief Returns node iterator pointing to the target node of the /// given edge iterator. - NodeIt head(const EdgeIt& e) const { + NodeIt target(const EdgeIt& e) const { if( DM::range_check && !e.valid() ) - fault("UndirPath::head() on invalid iterator"); + fault("UndirPath::target() on invalid iterator"); return NodeIt(*this, e.idx+1); } - /// \brief Returns node iterator pointing to the tail node of the + /// \brief Returns node iterator pointing to the source node of the /// given edge iterator. - NodeIt tail(const EdgeIt& e) const { + NodeIt source(const EdgeIt& e) const { if( DM::range_check && !e.valid() ) - fault("UndirPath::tail() on invalid iterator"); + fault("UndirPath::source() on invalid iterator"); return NodeIt(*this, e.idx); } @@ -615,7 +615,7 @@ if(idx >= p->length()) return p->to(); else if(idx >= 0) - return p->gr->tail(p->edges[idx]); + return p->gr->source(p->edges[idx]); else return INVALID; } @@ -673,7 +673,7 @@ ///Push a new edge to the front of the path. ///\sa setStartNode void pushFront(const GraphEdge& e) { - if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) { + if( DM::consistensy_check && !empty() && P.gr->target(e)!=from() ) { fault("UndirPath::Builder::pushFront: nonincident edge"); } front.push_back(e); @@ -684,7 +684,7 @@ ///Push a new edge to the back of the path. ///\sa setStartNode void pushBack(const GraphEdge& e) { - if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) { + if( DM::consistensy_check && !empty() && P.gr->source(e)!=to() ) { fault("UndirPath::Builder::pushBack: nonincident edge"); } back.push_back(e); @@ -723,21 +723,21 @@ GraphNode from() const { if( ! front.empty() ) - return P.gr->tail(front[front.size()-1]); + return P.gr->source(front[front.size()-1]); else if( ! P.empty() ) - return P.gr->tail(P.edges[0]); + return P.gr->source(P.edges[0]); else if( ! back.empty() ) - return P.gr->tail(back[0]); + return P.gr->source(back[0]); else return INVALID; } GraphNode to() const { if( ! back.empty() ) - return P.gr->head(back[back.size()-1]); + return P.gr->target(back[back.size()-1]); else if( ! P.empty() ) - return P.gr->head(P.edges[P.length()-1]); + return P.gr->target(P.edges[P.length()-1]); else if( ! front.empty() ) - return P.gr->head(front[0]); + return P.gr->target(front[0]); else return INVALID; } @@ -840,12 +840,12 @@ bool setFrom(const GraphNode &n); bool setTo(const GraphNode &n); - // WARNING: these two functions return the head/tail of an edge with + // WARNING: these two functions return the target/source of an edge with // respect to the direction of the path! - // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if + // So G.target(P.graphEdge(e)) == P.graphNode(P.target(e)) holds only if // P.forward(e) is true (or the edge is a loop)! - NodeIt head(const EdgeIt& e) const; - NodeIt tail(const EdgeIt& e) const; + NodeIt target(const EdgeIt& e) const; + NodeIt source(const EdgeIt& e) const; // FIXME: ezeknek valami jobb nev kellene!!! GraphEdge graphEdge(const EdgeIt& e) const; @@ -873,7 +873,7 @@ friend class DynamicPath; size_t idx; - bool tail; // Is this node the tail of the edge with same idx? + bool source; // Is this node the source of the edge with same idx? public: // FIXME: jarna neki ilyen is... @@ -896,7 +896,7 @@ if( e.it == edges.end() ) return e; - GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) ); + GraphNode common_node = ( e.forw ? G.target(*e.it) : G.source(*e.it) ); ++e.it; // Invalid edgeit is always forward :) @@ -905,7 +905,7 @@ return e; } - e.forw = ( G.tail(*e.it) == common_node ); + e.forw = ( G.source(*e.it) == common_node ); return e; } @@ -918,14 +918,14 @@ } - GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) : - G.tail(edges[n.idx]) ); + GraphNode next_node = ( n.source ? G.target(edges[n.idx]) : + G.source(edges[n.idx]) ); ++n.idx; if( n.idx < length() ) { - n.tail = ( next_node == G.tail(edges[n.idx]) ); + n.source = ( next_node == G.source(edges[n.idx]) ); } else { - n.tail = true; + n.source = true; } return n; @@ -934,12 +934,12 @@ template bool DynamicPath::edgeIncident(const GraphEdge &e, const GraphNode &a, GraphNode &b) { - if( G.tail(e) == a ) { - b=G.head(e); + if( G.source(e) == a ) { + b=G.target(e); return true; } - if( G.head(e) == a ) { - b=G.tail(e); + if( G.target(e) == a ) { + b=G.source(e); return true; } return false; @@ -948,12 +948,12 @@ template bool DynamicPath::connectTwoEdges(const GraphEdge &e, const GraphEdge &f) { - if( edgeIncident(f, G.tail(e), _last) ) { - _first = G.head(e); + if( edgeIncident(f, G.source(e), _last) ) { + _first = G.target(e); return true; } - if( edgeIncident(f, G.head(e), _last) ) { - _first = G.tail(e); + if( edgeIncident(f, G.target(e), _last) ) { + _first = G.source(e); return true; } return false; @@ -1039,31 +1039,31 @@ template typename DynamicPath::NodeIt - DynamicPath::tail(const EdgeIt& e) const { + DynamicPath::source(const EdgeIt& e) const { NodeIt n; if( e.it == edges.end() ) { // FIXME: invalid-> invalid n.idx = length() + 1; - n.tail = true; + n.source = true; return n; } n.idx = e.it-edges.begin(); - n.tail = e.forw; + n.source = e.forw; return n; } template typename DynamicPath::NodeIt - DynamicPath::head(const EdgeIt& e) const { + DynamicPath::target(const EdgeIt& e) const { if( e.it == edges.end()-1 ) { return _last; } EdgeIt next_edge = e; next(next_edge); - return tail(next_edge); + return source(next_edge); } template @@ -1081,7 +1081,7 @@ typename DynamicPath::GraphNode DynamicPath::graphNode(const NodeIt& n) const { if( n.idx < length() ) { - return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]); + return n.source ? G.source(edges[n.idx]) : G.target(edges[n.idx]); } else if( n.idx == length() ) { return _last; @@ -1103,11 +1103,11 @@ e.it = edges.begin()+k; if(k==0) { - e.forw = ( G.tail(*e.it) == _first ); + e.forw = ( G.source(*e.it) == _first ); } else { - e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) || - G.tail(*e.it) == G.head(edges[k-1]) ); + e.forw = ( G.source(*e.it) == G.source(edges[k-1]) || + G.source(*e.it) == G.target(edges[k-1]) ); } return e; } @@ -1118,15 +1118,15 @@ if( k>length() ) { // FIXME: invalid NodeIt n.idx = length()+1; - n.tail = true; + n.source = true; return n; } if( k==length() ) { n.idx = length(); - n.tail = true; + n.source = true; return n; } - n = tail(nth(k)); + n = source(nth(k)); return n; } @@ -1139,9 +1139,9 @@ G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up! { if( G.valid(P._first) && a.it < P.edges.end() ) { - _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) ); + _first = ( a.forw ? G.source(*a.it) : G.target(*a.it) ); if( b.it < P.edges.end() ) { - _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) ); + _last = ( b.forw ? G.source(*b.it) : G.target(*b.it) ); } else { _last = P._last; diff -r 741f3108a90f -r e997802b855c src/work/peter/path/path_skeleton.h --- a/src/work/peter/path/path_skeleton.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/peter/path/path_skeleton.h Sat Nov 13 12:53:28 2004 +0000 @@ -53,12 +53,12 @@ /// /// Starting point of the path. /// Returns INVALID if the path is empty. - GraphNode head() const {} + GraphNode target() const {} /// \brief End point of the path. /// /// End point of the path. /// Returns INVALID if the path is empty. - GraphNode tail() const {} + GraphNode source() const {} /// \brief First NodeIt/EdgeIt. /// @@ -67,17 +67,17 @@ template It& first(It &i) const { return i=It(*this); } - /// \brief The head of an edge. + /// \brief The target of an edge. /// - /// Returns node iterator pointing to the head node of the + /// Returns node iterator pointing to the target node of the /// given edge iterator. - NodeIt head(const EdgeIt& e) const {} + NodeIt target(const EdgeIt& e) const {} - /// \brief The tail of an edge. + /// \brief The source of an edge. /// - /// Returns node iterator pointing to the tail node of the + /// Returns node iterator pointing to the source node of the /// given edge iterator. - NodeIt tail(const EdgeIt& e) const {} + NodeIt source(const EdgeIt& e) const {} /* Iterator classes */ diff -r 741f3108a90f -r e997802b855c src/work/peter/path/path_test.cc --- a/src/work/peter/path/path_test.cc Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/peter/path/path_test.cc Sat Nov 13 12:53:28 2004 +0000 @@ -66,10 +66,10 @@ check(P.length() == 0); #ifdef SKELETON - cout << "P.tail() valid? " << (P.tail()!=INVALID) << endl; - check(! (P.tail()!=INVALID)); + cout << "P.source() valid? " << (P.source()!=INVALID) << endl; + check(! (P.source()!=INVALID)); #else - cout << "P.tail() valid? " << (P.from()!=INVALID) << endl; + cout << "P.source() valid? " << (P.from()!=INVALID) << endl; check(! (P.to()!=INVALID)); #endif { @@ -89,14 +89,14 @@ check(P.length() == 2); #ifdef SKELETON - cout << "P.tail() valid? " << (P.tail()!=INVALID) << endl; - check(P.tail()!=INVALID); - cout << "P.tail()==v1 ? " << (P.tail()==v1) << endl; - check(P.tail() == v1); + cout << "P.source() valid? " << (P.source()!=INVALID) << endl; + check(P.source()!=INVALID); + cout << "P.source()==v1 ? " << (P.source()==v1) << endl; + check(P.source() == v1); #else - cout << "P.tail() valid? " << (P.from()!=INVALID) << endl; + cout << "P.source() valid? " << (P.from()!=INVALID) << endl; check(P.from()!=INVALID); - cout << "P.tail()==v1 ? " << (P.from()==v1) << endl; + cout << "P.source()==v1 ? " << (P.from()==v1) << endl; check(P.from() == v1); #endif @@ -128,10 +128,10 @@ check(P.length() == 4); #ifdef SKELETON - cout << "P.head()==v3 ? " << (P.head()==v3) << endl; - check(P.head() == v3); + cout << "P.target()==v3 ? " << (P.target()==v3) << endl; + check(P.target() == v3); #else - cout << "P.head()==v3 ? " << (P.to()==v3) << endl; + cout << "P.target()==v3 ? " << (P.to()==v3) << endl; check(P.to() == v3); #endif diff -r 741f3108a90f -r e997802b855c src/work/sage_graph.h --- a/src/work/sage_graph.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/sage_graph.h Sat Nov 13 12:53:28 2004 +0000 @@ -96,8 +96,8 @@ struct edge_item { int id; - node_item* _tail; - node_item* _head; + node_item* _source; + node_item* _target; edge_item* _next_out; edge_item* _prev_out; edge_item* _next_in; @@ -121,22 +121,22 @@ return p; } - edge_item* _add_edge(node_item* _tail, node_item* _head) { + edge_item* _add_edge(node_item* _source, node_item* _target) { edge_item* e=new edge_item; e->id=edge_id++; - e->_tail=_tail; - e->_head=_head; + e->_source=_source; + e->_target=_target; - e->_prev_out=_tail->_last_out_edge; - if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e; - _tail->_last_out_edge=e; - if (!_tail->_first_out_edge) _tail->_first_out_edge=e; + e->_prev_out=_source->_last_out_edge; + if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e; + _source->_last_out_edge=e; + if (!_source->_first_out_edge) _source->_first_out_edge=e; e->_next_out=0; - e->_prev_in=_head->_last_in_edge; - if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e; - _head->_last_in_edge=e; - if (!_head->_first_in_edge) { _head->_first_in_edge=e; } + e->_prev_in=_target->_last_in_edge; + if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e; + _target->_last_in_edge=e; + if (!_target->_first_in_edge) { _target->_first_in_edge=e; } e->_next_in=0; ++_edge_num; @@ -156,45 +156,45 @@ void _delete_edge(edge_item* e) { if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else - (e->_tail)->_last_out_edge=e->_prev_out; + (e->_source)->_last_out_edge=e->_prev_out; if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else - (e->_tail)->_first_out_edge=e->_next_out; + (e->_source)->_first_out_edge=e->_next_out; if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else - (e->_head)->_last_in_edge=e->_prev_in; + (e->_target)->_last_in_edge=e->_prev_in; if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else - (e->_head)->_first_in_edge=e->_next_in; + (e->_target)->_first_in_edge=e->_next_in; delete e; --_edge_num; } - void _set_tail(edge_item* e, node_item* _tail) { + void _set_source(edge_item* e, node_item* _source) { if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else - (e->_tail)->_last_out_edge=e->_prev_out; + (e->_source)->_last_out_edge=e->_prev_out; if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else - (e->_tail)->_first_out_edge=e->_next_out; + (e->_source)->_first_out_edge=e->_next_out; - e->_tail=_tail; + e->_source=_source; - e->_prev_out=_tail->_last_out_edge; - if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e; - _tail->_last_out_edge=e; - if (!_tail->_first_out_edge) _tail->_first_out_edge=e; + e->_prev_out=_source->_last_out_edge; + if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e; + _source->_last_out_edge=e; + if (!_source->_first_out_edge) _source->_first_out_edge=e; e->_next_out=0; } - void _set_head(edge_item* e, node_item* _head) { + void _set_target(edge_item* e, node_item* _target) { if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else - (e->_head)->_last_in_edge=e->_prev_in; + (e->_target)->_last_in_edge=e->_prev_in; if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else - (e->_head)->_first_in_edge=e->_next_in; + (e->_target)->_first_in_edge=e->_next_in; - e->_head=_head; + e->_target=_target; - e->_prev_in=_head->_last_in_edge; - if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e; - _head->_last_in_edge=e; - if (!_head->_first_in_edge) { _head->_first_in_edge=e; } + e->_prev_in=_target->_last_in_edge; + if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e; + _target->_last_in_edge=e; + if (!_target->_first_in_edge) { _target->_first_in_edge=e; } e->_next_in=0; } @@ -221,8 +221,8 @@ //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); } //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); } //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); } - Node tail(Edge e) const { return e.tailNode(); } - Node head(Edge e) const { return e.headNode(); } + Node source(Edge e) const { return e.sourceNode(); } + Node target(Edge e) const { return e.targetNode(); } Node aNode(const OutEdgeIt& e) const { return e.aNode(); } Node aNode(const InEdgeIt& e) const { return e.aNode(); } @@ -251,8 +251,8 @@ e=InEdgeIt(*this, v); return e; } SymEdgeIt& first(SymEdgeIt& e, Node v) const { e=SymEdgeIt(*this, v); return e; } - //void getTail(Node& n, const Edge& e) const { n=tail(e); } - //void getHead(Node& n, const Edge& e) const { n=head(e); } + //void getSource(Node& n, const Edge& e) const { n=source(e); } + //void getTarget(Node& n, const Edge& e) const { n=target(e); } //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); } //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); } @@ -329,12 +329,12 @@ //while (first().valid()) erase(first()); } - void setTail(Edge e, Node tail) { - _set_tail(e.edge, tail.node); + void setSource(Edge e, Node source) { + _set_source(e.edge, source.node); } - void setHead(Edge e, Node head) { - _set_head(e.edge, head.node); + void setTarget(Edge e, Node target) { + _set_target(e.edge, target.node); } /* stream operations, for testing purpose */ @@ -348,7 +348,7 @@ // } // friend std::ostream& operator<<(std::ostream& os, const Edge& i) { // if (i.valid()) -// os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")"; +// os << "(" << i.edge->_source->id << "--" << i.edge->id << "->" << i.edge->_target->id << ")"; // else // os << "invalid"; // return os; @@ -419,8 +419,8 @@ friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; } friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; } protected: - Node tailNode() const { return Node(edge->_tail); } - Node headNode() const { return Node(edge->_head); } + Node sourceNode() const { return Node(edge->_source); } + Node targetNode() const { return Node(edge->_target); } public: friend std::ostream& operator<<(std::ostream& os, const Edge& i); }; @@ -440,7 +440,7 @@ // EdgeIt(edge_item* _e) : Edge(_e) { } public: EdgeIt& operator++() { - node_item* v=edge->_tail; + node_item* v=edge->_source; edge=edge->_next_out; while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } return *this; @@ -456,8 +456,8 @@ OutEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { } OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } protected: - Node aNode() const { return Node(edge->_tail); } - Node bNode() const { return Node(edge->_head); } + Node aNode() const { return Node(edge->_source); } + Node bNode() const { return Node(edge->_target); } }; class InEdgeIt : public Edge { @@ -469,8 +469,8 @@ InEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { } InEdgeIt& operator++() { edge=edge->_next_in; return *this; } protected: - Node aNode() const { return Node(edge->_head); } - Node bNode() const { return Node(edge->_tail); } + Node aNode() const { return Node(edge->_target); } + Node bNode() const { return Node(edge->_source); } }; class SymEdgeIt : public Edge { @@ -495,7 +495,7 @@ protected: SymEdgeIt& operator++() { if (out_or_in) { - node_item* v=edge->_tail; + node_item* v=edge->_source; edge=edge->_next_out; if (!edge) { out_or_in=0; edge=v->_first_in_edge; } } else { @@ -505,9 +505,9 @@ } protected: Node aNode() const { - return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); } + return (out_or_in) ? Node(edge->_source) : Node(edge->_target); } Node bNode() const { - return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); } + return (out_or_in) ? Node(edge->_target) : Node(edge->_source); } }; }; @@ -523,8 +523,8 @@ inline std::ostream& operator<<(std::ostream& os, const SageGraph::Edge& i) { if (i.valid()) - os << "(" << i.tailNode() << "--" << i.edge->id << "->" - << i.headNode() << ")"; + os << "(" << i.sourceNode() << "--" << i.edge->id << "->" + << i.targetNode() << ")"; else os << "invalid"; return os;