# Changeset 2116:b6a68c15a6a3 in lemon-0.x

Ignore:
Timestamp:
06/30/06 14:15:45 (18 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822
Message:

Revert splitted files

Files:
8 deleted
15 edited

Unmodified
Removed
• ## demo/coloring.cc

 r2115 #include #include #include #include #include
• ## demo/strongly_connected_orientation.cc

 r2115 #include #include #include #include #include
• ## demo/topology_demo.cc

 r2115 #include #include #include #include
• ## doc/graphs.dox

 r2115 provide a node list - edge list interface, i.e. they have functionalities to list the nodes and the edges of the graph as well as  incoming and outgoing edges of a given node. This functionalities are defined in the \ref lemon::concept::Graph "Graph" concept. as  incoming and outgoing edges of a given node. The next important graph type concept is the undirected graph concept what is defined in the \ref lemon::concept::UGraph "UGraph" concept class. Each undirected graphs provide node - undirected edge list interfaces. In addition the undirected graphs can be used as directed graphs so they are also conform to the \ref lemon::concept::Graph "Graph" concept. Each graph should meet the \ref lemon::concept::Graph "Graph" concept. This concept does not make it possible to change the graph (i.e. it is not possible to add or delete edges or nodes). Most of the graph algorithms will run on these graphs. Usually the graphs can be sorted to two group, the first is the general topology graph types which can store any graph and the second are the special topology graphs like the \ref FullUGraph or the \ref GridUGraph. In case of graphs meeting the full feature \ref lemon::concept::ErasableGraph "ErasableGraph" concept you can also erase individual edges and nodes in arbitrary order. The implemented graph structures are the following. \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets the \ref lemon::concept::ErasableGraph "ErasableGraph" concept
• ## lemon/Makefile.am

 r2115 lemon/floyd_warshall.h \ lemon/fredman_tarjan.h \ lemon/full_bpugraph.h \ lemon/full_graph.h \ lemon/full_ugraph.h \ lemon/graph_adaptor.h \ lemon/graph_reader.h \ lemon/lemon_reader.h \ lemon/lemon_writer.h \ lemon/list_bpugraph.h \ lemon/list_graph.h \ lemon/list_ugraph.h \ lemon/lp.h \ lemon/lp_base.h \ lemon/refptr.h \ lemon/simann.h \ lemon/smart_bpugraph.h \ lemon/smart_graph.h \ lemon/smart_ugraph.h \ lemon/sub_graph.h \ lemon/suurballe.h \ lemon/bits/array_map.h \ lemon/bits/base_extender.h \ lemon/bits/bpugraph_extender.h \ lemon/bits/default_map.h \ lemon/bits/edge_set_extender.h \ lemon/bits/mingw32_time.h \ lemon/bits/traits.h \ lemon/bits/ugraph_extender.h \ lemon/bits/utility.h \ lemon/bits/vector_map.h
• ## lemon/bits/graph_extender.h

 r2115 #include #include #include #include #include #include ///\ingroup graphbits }; /// \ingroup graphbits /// /// \brief Extender for the UGraphs template class UGraphExtender : public Base { public: typedef Base Parent; typedef UGraphExtender Graph; typedef typename Parent::Node Node; typedef typename Parent::Edge Edge; typedef typename Parent::UEdge UEdge; // UGraph extension int maxId(Node) const { return Parent::maxNodeId(); } int maxId(Edge) const { return Parent::maxEdgeId(); } int maxId(UEdge) const { return Parent::maxUEdgeId(); } Node fromId(int id, Node) const { return Parent::nodeFromId(id); } Edge fromId(int id, Edge) const { return Parent::edgeFromId(id); } UEdge fromId(int id, UEdge) const { return Parent::uEdgeFromId(id); } Node oppositeNode(const Node &n, const UEdge &e) const { if( n == Parent::source(e)) return Parent::target(e); else if( n == Parent::target(e)) return Parent::source(e); else return INVALID; } Edge oppositeEdge(const Edge &e) const { return Parent::direct(e, !Parent::direction(e)); } using Parent::direct; Edge direct(const UEdge &ue, const Node &s) const { return Parent::direct(ue, Parent::source(ue) == s); } // Alterable extension typedef AlterationNotifier NodeNotifier; typedef AlterationNotifier EdgeNotifier; typedef AlterationNotifier UEdgeNotifier; protected: mutable NodeNotifier node_notifier; mutable EdgeNotifier edge_notifier; mutable UEdgeNotifier uedge_notifier; public: NodeNotifier& getNotifier(Node) const { return node_notifier; } EdgeNotifier& getNotifier(Edge) const { return edge_notifier; } UEdgeNotifier& getNotifier(UEdge) const { return uedge_notifier; } class NodeIt : public Node { const Graph* graph; public: NodeIt() {} NodeIt(Invalid i) : Node(i) { } explicit NodeIt(const Graph& _graph) : graph(&_graph) { _graph.first(static_cast(*this)); } NodeIt(const Graph& _graph, const Node& node) : Node(node), graph(&_graph) {} NodeIt& operator++() { graph->next(*this); return *this; } }; class EdgeIt : public Edge { const Graph* graph; public: EdgeIt() { } EdgeIt(Invalid i) : Edge(i) { } explicit EdgeIt(const Graph& _graph) : graph(&_graph) { _graph.first(static_cast(*this)); } EdgeIt(const Graph& _graph, const Edge& e) : Edge(e), graph(&_graph) { } EdgeIt& operator++() { graph->next(*this); return *this; } }; class OutEdgeIt : public Edge { const Graph* graph; public: OutEdgeIt() { } OutEdgeIt(Invalid i) : Edge(i) { } OutEdgeIt(const Graph& _graph, const Node& node) : graph(&_graph) { _graph.firstOut(*this, node); } OutEdgeIt(const Graph& _graph, const Edge& edge) : Edge(edge), graph(&_graph) {} OutEdgeIt& operator++() { graph->nextOut(*this); return *this; } }; class InEdgeIt : public Edge { const Graph* graph; public: InEdgeIt() { } InEdgeIt(Invalid i) : Edge(i) { } InEdgeIt(const Graph& _graph, const Node& node) : graph(&_graph) { _graph.firstIn(*this, node); } InEdgeIt(const Graph& _graph, const Edge& edge) : Edge(edge), graph(&_graph) {} InEdgeIt& operator++() { graph->nextIn(*this); return *this; } }; class UEdgeIt : public Parent::UEdge { const Graph* graph; public: UEdgeIt() { } UEdgeIt(Invalid i) : UEdge(i) { } explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { _graph.first(static_cast(*this)); } UEdgeIt(const Graph& _graph, const UEdge& e) : UEdge(e), graph(&_graph) { } UEdgeIt& operator++() { graph->next(*this); return *this; } }; class IncEdgeIt : public Parent::UEdge { friend class UGraphExtender; const Graph* graph; bool direction; public: IncEdgeIt() { } IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { _graph.firstInc(*this, direction, n); } IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) : graph(&_graph), UEdge(ue) { direction = (_graph.source(ue) == n); } IncEdgeIt& operator++() { graph->nextInc(*this, direction); return *this; } }; /// \brief Base node of the iterator /// /// Returns the base node (ie. the source in this case) of the iterator Node baseNode(const OutEdgeIt &e) const { return Parent::source((Edge)e); } /// \brief Running node of the iterator /// /// Returns the running node (ie. the target in this case) of the /// iterator Node runningNode(const OutEdgeIt &e) const { return Parent::target((Edge)e); } /// \brief Base node of the iterator /// /// Returns the base node (ie. the target in this case) of the iterator Node baseNode(const InEdgeIt &e) const { return Parent::target((Edge)e); } /// \brief Running node of the iterator /// /// Returns the running node (ie. the source in this case) of the /// iterator Node runningNode(const InEdgeIt &e) const { return Parent::source((Edge)e); } /// Base node of the iterator /// /// Returns the base node of the iterator Node baseNode(const IncEdgeIt &e) const { return e.direction ? source(e) : target(e); } /// Running node of the iterator /// /// Returns the running node of the iterator Node runningNode(const IncEdgeIt &e) const { return e.direction ? target(e) : source(e); } // Mappable extension template class NodeMap : public MapExtender > { public: typedef UGraphExtender Graph; typedef MapExtender > Parent; NodeMap(const Graph& graph) : Parent(graph) {} NodeMap(const Graph& graph, const _Value& value) : Parent(graph, value) {} NodeMap& operator=(const NodeMap& cmap) { return operator=(cmap); } template NodeMap& operator=(const CMap& cmap) { Parent::operator=(cmap); return *this; } }; template class EdgeMap : public MapExtender > { public: typedef UGraphExtender Graph; typedef MapExtender > Parent; EdgeMap(const Graph& graph) : Parent(graph) {} EdgeMap(const Graph& graph, const _Value& value) : Parent(graph, value) {} EdgeMap& operator=(const EdgeMap& cmap) { return operator=(cmap); } template EdgeMap& operator=(const CMap& cmap) { Parent::operator=(cmap); return *this; } }; template class UEdgeMap : public MapExtender > { public: typedef UGraphExtender Graph; typedef MapExtender > Parent; UEdgeMap(const Graph& graph) : Parent(graph) {} UEdgeMap(const Graph& graph, const _Value& value) : Parent(graph, value) {} UEdgeMap& operator=(const UEdgeMap& cmap) { return operator=(cmap); } template UEdgeMap& operator=(const CMap& cmap) { Parent::operator=(cmap); return *this; } }; // Alteration extension Node addNode() { Node node = Parent::addNode(); getNotifier(Node()).add(node); return node; } UEdge addEdge(const Node& from, const Node& to) { UEdge uedge = Parent::addEdge(from, to); getNotifier(UEdge()).add(uedge); getNotifier(Edge()).add(Parent::direct(uedge, true)); getNotifier(Edge()).add(Parent::direct(uedge, false)); return uedge; } void clear() { getNotifier(Edge()).clear(); getNotifier(UEdge()).clear(); getNotifier(Node()).clear(); Parent::clear(); } void erase(const Node& node) { Edge edge; Parent::firstOut(edge, node); while (edge != INVALID ) { erase(edge); Parent::firstOut(edge, node); } Parent::firstIn(edge, node); while (edge != INVALID ) { erase(edge); Parent::firstIn(edge, node); } getNotifier(Node()).erase(node); Parent::erase(node); } void erase(const UEdge& uedge) { getNotifier(Edge()).erase(Parent::direct(uedge, true)); getNotifier(Edge()).erase(Parent::direct(uedge, false)); getNotifier(UEdge()).erase(uedge); Parent::erase(uedge); } UGraphExtender() { node_notifier.setContainer(*this); edge_notifier.setContainer(*this); uedge_notifier.setContainer(*this); } ~UGraphExtender() { uedge_notifier.clear(); edge_notifier.clear(); node_notifier.clear(); } }; /// \ingroup graphbits /// /// \brief Extender for the BpUGraphs template class BpUGraphExtender : public Base { public: typedef Base Parent; typedef BpUGraphExtender Graph; typedef typename Parent::Node Node; typedef typename Parent::UEdge UEdge; using Parent::first; using Parent::next; using Parent::id; class ANode : public Node { friend class BpUGraphExtender; public: ANode() {} ANode(const Node& node) : Node(node) { LEMON_ASSERT(Parent::aNode(node) || node == INVALID, typename Parent::NodeSetError()); } ANode(Invalid) : Node(INVALID) {} }; void first(ANode& node) const { Parent::firstANode(static_cast(node)); } void next(ANode& node) const { Parent::nextANode(static_cast(node)); } int id(const ANode& node) const { return Parent::aNodeId(node); } class BNode : public Node { friend class BpUGraphExtender; public: BNode() {} BNode(const Node& node) : Node(node) { LEMON_ASSERT(Parent::bNode(node) || node == INVALID, typename Parent::NodeSetError()); } BNode(Invalid) : Node(INVALID) {} }; void first(BNode& node) const { Parent::firstBNode(static_cast(node)); } void next(BNode& node) const { Parent::nextBNode(static_cast(node)); } int id(const BNode& node) const { return Parent::aNodeId(node); } Node source(const UEdge& edge) const { return aNode(edge); } Node target(const UEdge& edge) const { return bNode(edge); } void firstInc(UEdge& edge, bool& direction, const Node& node) const { if (Parent::aNode(node)) { Parent::firstFromANode(edge, node); direction = true; } else { Parent::firstFromBNode(edge, node); direction = static_cast(edge) == INVALID; } } void nextInc(UEdge& edge, bool& direction) const { if (direction) { Parent::nextFromANode(edge); } else { Parent::nextFromBNode(edge); if (edge == INVALID) direction = true; } } class Edge : public UEdge { friend class BpUGraphExtender; protected: bool forward; Edge(const UEdge& edge, bool _forward) : UEdge(edge), forward(_forward) {} public: Edge() {} Edge (Invalid) : UEdge(INVALID), forward(true) {} bool operator==(const Edge& i) const { return UEdge::operator==(i) && forward == i.forward; } bool operator!=(const Edge& i) const { return UEdge::operator!=(i) || forward != i.forward; } bool operator<(const Edge& i) const { return UEdge::operator<(i) || (!(i.forward(edge)); edge.forward = true; } void next(Edge& edge) const { if (!edge.forward) { Parent::next(static_cast(edge)); } edge.forward = !edge.forward; } void firstOut(Edge& edge, const Node& node) const { if (Parent::aNode(node)) { Parent::firstFromANode(edge, node); edge.forward = true; } else { Parent::firstFromBNode(edge, node); edge.forward = static_cast(edge) == INVALID; } } void nextOut(Edge& edge) const { if (edge.forward) { Parent::nextFromANode(edge); } else { Parent::nextFromBNode(edge); edge.forward = static_cast(edge) == INVALID; } } void firstIn(Edge& edge, const Node& node) const { if (Parent::bNode(node)) { Parent::firstFromBNode(edge, node); edge.forward = true; } else { Parent::firstFromANode(edge, node); edge.forward = static_cast(edge) == INVALID; } } void nextIn(Edge& edge) const { if (edge.forward) { Parent::nextFromBNode(edge); } else { Parent::nextFromANode(edge); edge.forward = static_cast(edge) == INVALID; } } Node source(const Edge& edge) const { return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); } Node target(const Edge& edge) const { return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); } int id(const Edge& edge) const { return (Parent::id(static_cast(edge)) << 1) + (edge.forward ? 0 : 1); } Edge edgeFromId(int id) const { return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0); } int maxEdgeId() const { return (Parent::maxUEdgeId(UEdge()) << 1) + 1; } bool direction(const Edge& edge) const { return edge.forward; } Edge direct(const UEdge& edge, bool direction) const { return Edge(edge, direction); } int edgeNum() const { return 2 * Parent::uEdgeNum(); } int uEdgeNum() const { return Parent::uEdgeNum(); } Node oppositeNode(const UEdge& edge, const Node& node) const { return source(edge) == node ? target(edge) : source(edge); } Edge direct(const UEdge& edge, const Node& node) const { return Edge(edge, node == Parent::source(edge)); } Edge oppositeEdge(const Edge& edge) const { return Parent::direct(edge, !Parent::direction(edge)); } int maxId(Node) const { return Parent::maxNodeId(); } int maxId(BNode) const { return Parent::maxBNodeId(); } int maxId(ANode) const { return Parent::maxANodeId(); } int maxId(Edge) const { return maxEdgeId(); } int maxId(UEdge) const { return Parent::maxUEdgeId(); } Node fromId(int id, Node) const { return Parent::nodeFromId(id); } ANode fromId(int id, ANode) const { return Parent::fromANodeId(id); } BNode fromId(int id, BNode) const { return Parent::fromBNodeId(id); } Edge fromId(int id, Edge) const { return Parent::edgeFromId(id); } UEdge fromId(int id, UEdge) const { return Parent::uEdgeFromId(id); } typedef AlterationNotifier ANodeNotifier; typedef AlterationNotifier BNodeNotifier; typedef AlterationNotifier NodeNotifier; typedef AlterationNotifier EdgeNotifier; typedef AlterationNotifier UEdgeNotifier; protected: mutable ANodeNotifier anode_notifier; mutable BNodeNotifier bnode_notifier; mutable NodeNotifier node_notifier; mutable EdgeNotifier edge_notifier; mutable UEdgeNotifier uedge_notifier; public: NodeNotifier& getNotifier(Node) const { return node_notifier; } ANodeNotifier& getNotifier(ANode) const { return anode_notifier; } BNodeNotifier& getNotifier(BNode) const { return bnode_notifier; } EdgeNotifier& getNotifier(Edge) const { return edge_notifier; } UEdgeNotifier& getNotifier(UEdge) const { return uedge_notifier; } class NodeIt : public Node { const Graph* graph; public: NodeIt() { } NodeIt(Invalid i) : Node(INVALID) { } explicit NodeIt(const Graph& _graph) : graph(&_graph) { graph->first(static_cast(*this)); } NodeIt(const Graph& _graph, const Node& node) : Node(node), graph(&_graph) { } NodeIt& operator++() { graph->next(*this); return *this; } }; class ANodeIt : public Node { friend class BpUGraphExtender; const Graph* graph; public: ANodeIt() { } ANodeIt(Invalid i) : Node(INVALID) { } explicit ANodeIt(const Graph& _graph) : graph(&_graph) { graph->firstANode(static_cast(*this)); } ANodeIt(const Graph& _graph, const Node& node) : Node(node), graph(&_graph) {} ANodeIt& operator++() { graph->nextANode(*this); return *this; } }; class BNodeIt : public Node { friend class BpUGraphExtender; const Graph* graph; public: BNodeIt() { } BNodeIt(Invalid i) : Node(INVALID) { } explicit BNodeIt(const Graph& _graph) : graph(&_graph) { graph->firstBNode(static_cast(*this)); } BNodeIt(const Graph& _graph, const Node& node) : Node(node), graph(&_graph) {} BNodeIt& operator++() { graph->nextBNode(*this); return *this; } }; class EdgeIt : public Edge { friend class BpUGraphExtender; const Graph* graph; public: EdgeIt() { } EdgeIt(Invalid i) : Edge(INVALID) { } explicit EdgeIt(const Graph& _graph) : graph(&_graph) { graph->first(static_cast(*this)); } EdgeIt(const Graph& _graph, const Edge& edge) : Edge(edge), graph(&_graph) { } EdgeIt& operator++() { graph->next(*this); return *this; } }; class UEdgeIt : public UEdge { friend class BpUGraphExtender; const Graph* graph; public: UEdgeIt() { } UEdgeIt(Invalid i) : UEdge(INVALID) { } explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { graph->first(static_cast(*this)); } UEdgeIt(const Graph& _graph, const UEdge& edge) : UEdge(edge), graph(&_graph) { } UEdgeIt& operator++() { graph->next(*this); return *this; } }; class OutEdgeIt : public Edge { friend class BpUGraphExtender; const Graph* graph; public: OutEdgeIt() { } OutEdgeIt(Invalid i) : Edge(i) { } OutEdgeIt(const Graph& _graph, const Node& node) : graph(&_graph) { graph->firstOut(*this, node); } OutEdgeIt(const Graph& _graph, const Edge& edge) : Edge(edge), graph(&_graph) {} OutEdgeIt& operator++() { graph->nextOut(*this); return *this; } }; class InEdgeIt : public Edge { friend class BpUGraphExtender; const Graph* graph; public: InEdgeIt() { } InEdgeIt(Invalid i) : Edge(i) { } InEdgeIt(const Graph& _graph, const Node& node) : graph(&_graph) { graph->firstIn(*this, node); } InEdgeIt(const Graph& _graph, const Edge& edge) : Edge(edge), graph(&_graph) {} InEdgeIt& operator++() { graph->nextIn(*this); return *this; } }; /// \brief Base node of the iterator /// /// Returns the base node (ie. the source in this case) of the iterator Node baseNode(const OutEdgeIt &e) const { return Parent::source((Edge&)e); } /// \brief Running node of the iterator /// /// Returns the running node (ie. the target in this case) of the /// iterator Node runningNode(const OutEdgeIt &e) const { return Parent::target((Edge&)e); } /// \brief Base node of the iterator /// /// Returns the base node (ie. the target in this case) of the iterator Node baseNode(const InEdgeIt &e) const { return Parent::target((Edge&)e); } /// \brief Running node of the iterator /// /// Returns the running node (ie. the source in this case) of the /// iterator Node runningNode(const InEdgeIt &e) const { return Parent::source((Edge&)e); } class IncEdgeIt : public Parent::UEdge { friend class BpUGraphExtender; const Graph* graph; bool direction; public: IncEdgeIt() { } IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { graph->firstInc(*this, direction, n); } IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) : graph(&_graph), UEdge(ue) { direction = (graph->source(ue) == n); } IncEdgeIt& operator++() { graph->nextInc(*this, direction); return *this; } }; /// Base node of the iterator /// /// Returns the base node of the iterator Node baseNode(const IncEdgeIt &e) const { return e.direction ? source(e) : target(e); } /// Running node of the iterator /// /// Returns the running node of the iterator Node runningNode(const IncEdgeIt &e) const { return e.direction ? target(e) : source(e); } template class ANodeMap : public MapExtender > { public: typedef BpUGraphExtender Graph; typedef MapExtender > Parent; ANodeMap(const Graph& graph) : Parent(graph) {} ANodeMap(const Graph& graph, const _Value& value) : Parent(graph, value) {} ANodeMap& operator=(const ANodeMap& cmap) { return operator=(cmap); } template ANodeMap& operator=(const CMap& cmap) { Parent::operator=(cmap); return *this; } }; template class BNodeMap : public MapExtender > { public: typedef BpUGraphExtender Graph; typedef MapExtender > Parent; BNodeMap(const Graph& graph) : Parent(graph) {} BNodeMap(const Graph& graph, const _Value& value) : Parent(graph, value) {} BNodeMap& operator=(const BNodeMap& cmap) { return operator=(cmap); } template BNodeMap& operator=(const CMap& cmap) { Parent::operator=(cmap); return *this; } }; public: template class NodeMap { public: typedef BpUGraphExtender Graph; typedef Node Key; typedef _Value Value; /// The reference type of the map; typedef typename ANodeMap<_Value>::Reference Reference; /// The const reference type of the map; typedef typename ANodeMap<_Value>::ConstReference ConstReference; typedef True ReferenceMapTag; NodeMap(const Graph& _graph) : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {} NodeMap(const Graph& _graph, const _Value& _value) : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {} NodeMap& operator=(const NodeMap& cmap) { return operator=(cmap); } template NodeMap& operator=(const CMap& cmap) { checkConcept, CMap>(); const typename Parent::Notifier* notifier = Parent::getNotifier(); Edge it; for (graph.first(it); it != INVALID; graph.next(it)) { Parent::set(it, cmap[it]); } return *this; } ConstReference operator[](const Key& node) const { if (Parent::aNode(node)) { return aNodeMap[node]; } else { return bNodeMap[node]; } } Reference operator[](const Key& node) { if (Parent::aNode(node)) { return aNodeMap[node]; } else { return bNodeMap[node]; } } void set(const Key& node, const Value& value) { if (Parent::aNode(node)) { aNodeMap.set(node, value); } else { bNodeMap.set(node, value); } } class MapIt : public NodeIt { public: typedef NodeIt Parent; explicit MapIt(NodeMap& _map) : Parent(_map.graph), map(_map) {} typename MapTraits::ConstReturnValue operator*() const { return map[*this]; } typename MapTraits::ReturnValue operator*() { return map[*this]; } void set(const Value& value) { map.set(*this, value); } private: NodeMap& map; }; class ConstMapIt : public NodeIt { public: typedef NodeIt Parent; explicit ConstMapIt(const NodeMap& _map) : Parent(_map.graph), map(_map) {} typename MapTraits::ConstReturnValue operator*() const { return map[*this]; } private: const NodeMap& map; }; class ItemIt : public NodeIt { public: typedef NodeIt Parent; explicit ItemIt(const NodeMap& _map) : Parent(_map.graph) {} }; private: const Graph& graph; ANodeMap<_Value> aNodeMap; BNodeMap<_Value> bNodeMap; }; template class EdgeMap : public MapExtender > { public: typedef BpUGraphExtender Graph; typedef MapExtender > Parent; EdgeMap(const Graph& graph) : Parent(graph) {} EdgeMap(const Graph& graph, const _Value& value) : Parent(graph, value) {} EdgeMap& operator=(const EdgeMap& cmap) { return operator=(cmap); } template EdgeMap& operator=(const CMap& cmap) { Parent::operator=(cmap); return *this; } }; template class UEdgeMap : public MapExtender > { public: typedef BpUGraphExtender Graph; typedef MapExtender > Parent; UEdgeMap(const Graph& graph) : Parent(graph) {} UEdgeMap(const Graph& graph, const _Value& value) : Parent(graph, value) {} UEdgeMap& operator=(const UEdgeMap& cmap) { return operator=(cmap); } template UEdgeMap& operator=(const CMap& cmap) { Parent::operator=(cmap); return *this; } }; Node addANode() { Node node = Parent::addANode(); getNotifier(ANode()).add(node); getNotifier(Node()).add(node); return node; } Node addBNode() { Node node = Parent::addBNode(); getNotifier(BNode()).add(node); getNotifier(Node()).add(node); return node; } UEdge addEdge(const Node& source, const Node& target) { UEdge uedge = Parent::addEdge(source, target); getNotifier(UEdge()).add(uedge); std::vector edges; edges.push_back(direct(uedge, true)); edges.push_back(direct(uedge, false)); getNotifier(Edge()).add(edges); return uedge; } void clear() { getNotifier(Edge()).clear(); getNotifier(UEdge()).clear(); getNotifier(Node()).clear(); getNotifier(BNode()).clear(); getNotifier(ANode()).clear(); Parent::clear(); } void erase(const Node& node) { UEdge uedge; if (Parent::aNode(node)) { Parent::firstFromANode(uedge, node); while (uedge != INVALID) { erase(uedge); Parent::firstFromANode(uedge, node); } } else { Parent::firstFromBNode(uedge, node); while (uedge != INVALID) { erase(uedge); Parent::firstFromBNode(uedge, node); } } getNotifier(Node()).erase(node); Parent::erase(node); } void erase(const UEdge& uedge) { std::vector edges; edges.push_back(direct(uedge, true)); edges.push_back(direct(uedge, false)); getNotifier(Edge()).erase(edges); getNotifier(UEdge()).erase(uedge); Parent::erase(uedge); } BpUGraphExtender() { anode_notifier.setContainer(*this); bnode_notifier.setContainer(*this); node_notifier.setContainer(*this); edge_notifier.setContainer(*this); uedge_notifier.setContainer(*this); } ~BpUGraphExtender() { uedge_notifier.clear(); edge_notifier.clear(); node_notifier.clear(); anode_notifier.clear(); bnode_notifier.clear(); } }; }
• ## lemon/edge_set.h

 r2115 #include #include #include /// \ingroup graphs
• ## lemon/full_graph.h

 r2115 #include #include #include ///\ingroup graphs ///\file ///\brief FullGraph class. ///\brief FullGraph and FullUGraph classes. }; /// \brief Base of the FullUGrpah. /// /// Base of the FullUGrpah. class FullUGraphBase { int _nodeNum; int _edgeNum; public: typedef FullUGraphBase Graph; class Node; class Edge; public: FullUGraphBase() {} ///Creates a full graph with \c n nodes. void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; } /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Because it is a /// static size graph the node's of the graph can be indiced /// by the range from 0 to \e nodeNum()-1 and the index of /// the node can accessed by the \e index() member. Node operator()(int index) const { return Node(index); } /// \brief Returns the index of the node. /// /// Returns the index of the node. Because it is a /// static size graph the node's of the graph can be indiced /// by the range from 0 to \e nodeNum()-1 and the index of /// the node can accessed by the \e index() member. int index(const Node& node) const { return node.id; } typedef True NodeNumTag; typedef True EdgeNumTag; ///Number of nodes. int nodeNum() const { return _nodeNum; } ///Number of edges. int edgeNum() const { return _edgeNum; } /// Maximum node ID. /// Maximum node ID. ///\sa id(Node) int maxNodeId() const { return _nodeNum-1; } /// Maximum edge ID. /// Maximum edge ID. ///\sa id(Edge) int maxEdgeId() const { return _edgeNum-1; } /// \brief Returns the node from its \c id. /// /// Returns the node from its \c id. If there is not node /// with the given id the effect of the function is undefinied. static Node nodeFromId(int id) { return Node(id);} /// \brief Returns the edge from its \c id. /// /// Returns the edge from its \c id. If there is not edge /// with the given id the effect of the function is undefinied. static Edge edgeFromId(int id) { return Edge(id);} Node source(Edge e) const { /// \todo we may do it faster return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2); } Node target(Edge e) const { int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; return Node(e.id - (source) * (source - 1) / 2); } /// \brief Node ID. /// /// The ID of a valid Node is a nonnegative integer not greater than /// \ref maxNodeId(). The range of the ID's is not surely continuous /// and the greatest node ID can be actually less then \ref maxNodeId(). /// /// The ID of the \ref INVALID node is -1. /// \return The ID of the node \c v. static int id(Node v) { return v.id; } /// \brief Edge ID. /// /// The ID of a valid Edge is a nonnegative integer not greater than /// \ref maxEdgeId(). The range of the ID's is not surely continuous /// and the greatest edge ID can be actually less then \ref maxEdgeId(). /// /// The ID of the \ref INVALID edge is -1. ///\return The ID of the edge \c e. static int id(Edge e) { return e.id; } /// \brief Finds an edge between two nodes. /// /// Finds an edge from node \c u to node \c v. /// /// If \c prev is \ref INVALID (this is the default value), then /// It finds the first edge from \c u to \c v. Otherwise it looks for /// the next edge from \c u to \c v after \c prev. /// \return The found edge or INVALID if there is no such an edge. Edge findEdge(Node u, Node v, Edge prev = INVALID) const { if (prev.id != -1 || u.id <= v.id) return Edge(-1); return Edge(u.id * (u.id - 1) / 2 + v.id); } typedef True FindEdgeTag; class Node { friend class FullUGraphBase; protected: int id; Node(int _id) { id = _id;} public: Node() {} Node (Invalid) { id = -1; } bool operator==(const Node node) const {return id == node.id;} bool operator!=(const Node node) const {return id != node.id;} bool operator<(const Node node) const {return id < node.id;} }; class Edge { friend class FullUGraphBase; protected: int id;  // _nodeNum * target + source; Edge(int _id) : id(_id) {} public: Edge() { } Edge (Invalid) { id = -1; } bool operator==(const Edge edge) const {return id == edge.id;} bool operator!=(const Edge edge) const {return id != edge.id;} bool operator<(const Edge edge) const {return id < edge.id;} }; void first(Node& node) const { node.id = _nodeNum - 1; } static void next(Node& node) { --node.id; } void first(Edge& edge) const { edge.id = _edgeNum - 1; } static void next(Edge& edge) { --edge.id; } void firstOut(Edge& edge, const Node& node) const { int src = node.id; int trg = 0; edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); } /// \todo with specialized iterators we can make faster iterating void nextOut(Edge& edge) const { int src = source(edge).id; int trg = target(edge).id; ++trg; edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); } void firstIn(Edge& edge, const Node& node) const { int src = node.id + 1; int trg = node.id; edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); } void nextIn(Edge& edge) const { int src = source(edge).id; int trg = target(edge).id; ++src; edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); } }; typedef UGraphExtender > ExtendedFullUGraphBase; /// \ingroup graphs /// /// \brief An undirected full graph class. /// /// This is a simple and fast undirected full graph implementation. /// It is completely static, so you can neither add nor delete either /// edges or nodes. /// /// The main difference beetween the \e FullGraph and \e FullUGraph class /// is that this class conforms to the undirected graph concept and /// it does not contain the loop edges. /// /// \sa FullUGraphBase /// \sa FullGraph /// /// \author Balazs Dezso class FullUGraph : public ExtendedFullUGraphBase { public: typedef ExtendedFullUGraphBase Parent; /// \brief Constructor FullUGraph() { construct(0); } /// \brief Constructor FullUGraph(int n) { construct(n); } /// \brief Resize the graph /// /// Resize the graph. The function will fully destroy and build the graph. /// This cause that the maps of the graph will reallocated /// automatically and the previous values will be lost. void resize(int n) { Parent::getNotifier(Edge()).clear(); Parent::getNotifier(UEdge()).clear(); Parent::getNotifier(Node()).clear(); construct(n); Parent::getNotifier(Node()).build(); Parent::getNotifier(UEdge()).build(); Parent::getNotifier(Edge()).build(); } }; class FullBpUGraphBase { protected: int _aNodeNum; int _bNodeNum; int _edgeNum; public: class NodeSetError : public LogicError { virtual const char* exceptionName() const { return "lemon::FullBpUGraph::NodeSetError"; } }; class Node { friend class FullBpUGraphBase; protected: int id; Node(int _id) : id(_id) {} public: Node() {} Node(Invalid) { id = -1; } bool operator==(const Node i) const {return id==i.id;} bool operator!=(const Node i) const {return id!=i.id;} bool operator<(const Node i) const {return id 0) { node.id = 2 * _aNodeNum - 2; } else { node.id = 2 * _bNodeNum - 1; } } void next(Node& node) const { node.id -= 2; if (node.id == -2) { node.id = 2 * _bNodeNum - 1; } } void first(UEdge& edge) const { edge.id = _edgeNum - 1; } void next(UEdge& edge) const { --edge.id; } void firstFromANode(UEdge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); edge.id = (node.id >> 1) * _bNodeNum; } void nextFromANode(UEdge& edge) const { ++(edge.id); if (edge.id % _bNodeNum == 0) edge.id = -1; } void firstFromBNode(UEdge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); edge.id = (node.id >> 1); } void nextFromBNode(UEdge& edge) const { edge.id += _bNodeNum; if (edge.id >= _edgeNum) edge.id = -1; } static int id(const Node& node) { return node.id; } static Node nodeFromId(int id) { return Node(id); } int maxNodeId() const { return _aNodeNum > _bNodeNum ? _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1; } static int id(const UEdge& edge) { return edge.id; } static UEdge uEdgeFromId(int id) { return UEdge(id); } int maxUEdgeId() const { return _edgeNum - 1; } static int aNodeId(const Node& node) { return node.id >> 1; } static Node fromANodeId(int id) { return Node(id << 1); } int maxANodeId() const { return _aNodeNum; } static int bNodeId(const Node& node) { return node.id >> 1; } static Node fromBNodeId(int id) { return Node((id << 1) + 1); } int maxBNodeId() const { return _bNodeNum; } Node aNode(const UEdge& edge) const { return Node((edge.id / _bNodeNum) << 1); } Node bNode(const UEdge& edge) const { return Node(((edge.id % _bNodeNum) << 1) + 1); } static bool aNode(const Node& node) { return (node.id & 1) == 0; } static bool bNode(const Node& node) { return (node.id & 1) == 1; } static Node aNode(int index) { return Node(index << 1); } static Node bNode(int index) { return Node((index << 1) + 1); } typedef True NodeNumTag; int nodeNum() const { return _aNodeNum + _bNodeNum; } int aNodeNum() const { return _aNodeNum; } int bNodeNum() const { return _bNodeNum; } typedef True EdgeNumTag; int uEdgeNum() const { return _edgeNum; } }; typedef BpUGraphExtender ExtendedFullBpUGraphBase; /// \ingroup graphs /// /// \brief An undirected full bipartite graph class. /// /// This is a simple and fast bipartite undirected full graph implementation. /// It is completely static, so you can neither add nor delete either /// edges or nodes. /// /// \sa FullUGraphBase /// \sa FullGraph /// /// \author Balazs Dezso class FullBpUGraph : public ExtendedFullBpUGraphBase { public: typedef ExtendedFullBpUGraphBase Parent; FullBpUGraph() { Parent::construct(0, 0); } FullBpUGraph(int aNodeNum, int bNodeNum) { Parent::construct(aNodeNum, bNodeNum); } /// \brief Resize the graph /// void resize(int n, int m) { Parent::getNotifier(Edge()).clear(); Parent::getNotifier(UEdge()).clear(); Parent::getNotifier(Node()).clear(); Parent::getNotifier(ANode()).clear(); Parent::getNotifier(BNode()).clear(); construct(n, m); Parent::getNotifier(ANode()).build(); Parent::getNotifier(BNode()).build(); Parent::getNotifier(Node()).build(); Parent::getNotifier(UEdge()).build(); Parent::getNotifier(Edge()).build(); } }; } //namespace lemon
• ## lemon/grid_ugraph.h

 r2115 #include #include #include #include
• ## lemon/list_graph.h

 r2115 ///\ingroup graphs ///\file ///\brief ListGraph class. ///\brief ListGraph, ListUGraph classes. #include #include #include #include typedef GraphExtender ExtendedListGraphBase; /// \ingroup graphs /// \addtogroup graphs /// @{ ///A list graph class. }; ///@} /**************** Undirected List Graph ****************/ typedef UGraphExtender > ExtendedListUGraphBase; /// \addtogroup graphs /// @{ ///An undirected list graph class. ///This is a simple and fast erasable undirected graph implementation. /// ///It conforms to the ///\ref concept::UGraph "UGraph" concept. /// ///\sa concept::UGraph. /// ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract() ///haven't been implemented yet. /// class ListUGraph : public ExtendedListUGraphBase { public: typedef ExtendedListUGraphBase Parent; /// \brief Add a new node to the graph. /// /// \return the new node. /// Node addNode() { return Parent::addNode(); } /// \brief Add a new edge to the graph. /// /// Add a new edge to the graph with source node \c s /// and target node \c t. /// \return the new undirected edge. UEdge addEdge(const Node& s, const Node& t) { return Parent::addEdge(s, t); } /// \brief Changes the target of \c e to \c n /// /// Changes the target of \c e to \c n /// /// \note The Edge's and OutEdge's /// referencing the changed edge remain /// valid. However InEdge's are invalidated. void changeTarget(UEdge e, Node n) { Parent::changeTarget(e,n); } /// Changes the source of \c e to \c n /// /// Changes the source of \c e to \c n /// ///\note The Edge's and InEdge's ///referencing the changed edge remain ///valid. However OutEdge's are invalidated. void changeSource(UEdge e, Node n) { Parent::changeSource(e,n); } /// \brief Contract two nodes. /// /// This function contracts two nodes. /// /// Node \p b will be removed but instead of deleting /// its neighboring edges, they will be joined to \p a. /// The last parameter \p r controls whether to remove loops. \c true /// means that loops will be removed. /// /// \note The Edges /// referencing a moved edge remain /// valid. void contract(Node a, Node b, bool r = true) { for(IncEdgeIt e(*this, b); e!=INVALID;) { IncEdgeIt f = e; ++f; if (r && runningNode(e) == a) { erase(e); } else if (source(e) == b) { changeSource(e, a); } else { changeTarget(e, a); } e = f; } erase(b); } }; class ListBpUGraphBase { public: class NodeSetError : public LogicError { virtual const char* exceptionName() const { return "lemon::ListBpUGraph::NodeSetError"; } }; protected: struct NodeT { int first_edge, prev, next; }; struct UEdgeT { int aNode, prev_out, next_out; int bNode, prev_in, next_in; }; std::vector aNodes; std::vector bNodes; std::vector edges; int first_anode; int first_free_anode; int first_bnode; int first_free_bnode; int first_free_edge; public: class Node { friend class ListBpUGraphBase; protected: int id; explicit Node(int _id) : id(_id) {} public: Node() {} Node(Invalid) { id = -1; } bool operator==(const Node i) const {return id==i.id;} bool operator!=(const Node i) const {return id!=i.id;} bool operator<(const Node i) const {return id> 1].next; } void firstBNode(Node& node) const { node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1; } void nextBNode(Node& node) const { node.id = bNodes[node.id >> 1].next; } void first(Node& node) const { if (first_anode != -1) { node.id = (first_anode << 1); } else if (first_bnode != -1) { node.id = (first_bnode << 1) + 1; } else { node.id = -1; } } void next(Node& node) const { if (aNode(node)) { node.id = aNodes[node.id >> 1].next; if (node.id == -1) { if (first_bnode != -1) { node.id = (first_bnode << 1) + 1; } } } else { node.id = bNodes[node.id >> 1].next; } } void first(UEdge& edge) const { int aNodeId = first_anode; while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { aNodeId = aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1; } if (aNodeId != -1) { edge.id = aNodes[aNodeId].first_edge; } else { edge.id = -1; } } void next(UEdge& edge) const { int aNodeId = edges[edge.id].aNode >> 1; edge.id = edges[edge.id].next_out; if (edge.id == -1) { aNodeId = aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1; while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { aNodeId = aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1; } if (aNodeId != -1) { edge.id = aNodes[aNodeId].first_edge; } else { edge.id = -1; } } } void firstFromANode(UEdge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); edge.id = aNodes[node.id >> 1].first_edge; } void nextFromANode(UEdge& edge) const { edge.id = edges[edge.id].next_out; } void firstFromBNode(UEdge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); edge.id = bNodes[node.id >> 1].first_edge; } void nextFromBNode(UEdge& edge) const { edge.id = edges[edge.id].next_in; } static int id(const Node& node) { return node.id; } static Node nodeFromId(int id) { return Node(id); } int maxNodeId() const { return aNodes.size() > bNodes.size() ? aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; } static int id(const UEdge& edge) { return edge.id; } static UEdge uEdgeFromId(int id) { return UEdge(id); } int maxUEdgeId() const { return edges.size(); } static int aNodeId(const Node& node) { return node.id >> 1; } static Node fromANodeId(int id) { return Node(id << 1); } int maxANodeId() const { return aNodes.size(); } static int bNodeId(const Node& node) { return node.id >> 1; } static Node fromBNodeId(int id) { return Node((id << 1) + 1); } int maxBNodeId() const { return bNodes.size(); } Node aNode(const UEdge& edge) const { return Node(edges[edge.id].aNode); } Node bNode(const UEdge& edge) const { return Node(edges[edge.id].bNode); } static bool aNode(const Node& node) { return (node.id & 1) == 0; } static bool bNode(const Node& node) { return (node.id & 1) == 1; } Node addANode() { int aNodeId; if (first_free_anode == -1) { aNodeId = aNodes.size(); aNodes.push_back(NodeT()); } else { aNodeId = first_free_anode; first_free_anode = aNodes[first_free_anode].next; } if (first_anode != -1) { aNodes[aNodeId].next = first_anode << 1; aNodes[first_anode].prev = aNodeId << 1; } else { aNodes[aNodeId].next = -1; } aNodes[aNodeId].prev = -1; first_anode = aNodeId; aNodes[aNodeId].first_edge = -1; return Node(aNodeId << 1); } Node addBNode() { int bNodeId; if (first_free_bnode == -1) { bNodeId = bNodes.size(); bNodes.push_back(NodeT()); } else { bNodeId = first_free_bnode; first_free_bnode = bNodes[first_free_bnode].next; } if (first_bnode != -1) { bNodes[bNodeId].next = (first_bnode << 1) + 1; bNodes[first_bnode].prev = (bNodeId << 1) + 1; } else { bNodes[bNodeId].next = -1; } first_bnode = bNodeId; bNodes[bNodeId].first_edge = -1; return Node((bNodeId << 1) + 1); } UEdge addEdge(const Node& source, const Node& target) { LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); int edgeId; if (first_free_edge != -1) { edgeId = first_free_edge; first_free_edge = edges[edgeId].next_out; } else { edgeId = edges.size(); edges.push_back(UEdgeT()); } if ((source.id & 1) == 0) { edges[edgeId].aNode = source.id; edges[edgeId].bNode = target.id; } else { edges[edgeId].aNode = target.id; edges[edgeId].bNode = source.id; } edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge; edges[edgeId].prev_out = -1; if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) { edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId; } aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId; edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge; edges[edgeId].prev_in = -1; if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) { edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId; } bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId; return UEdge(edgeId); } void erase(const Node& node) { if (aNode(node)) { int aNodeId = node.id >> 1; if (aNodes[aNodeId].prev != -1) { aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next; } else { first_anode = aNodes[aNodeId].next >> 1; } if (aNodes[aNodeId].next != -1) { aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev; } aNodes[aNodeId].next = first_free_anode; first_free_anode = aNodeId; } else { int bNodeId = node.id >> 1; if (bNodes[bNodeId].prev != -1) { bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next; } else { first_bnode = bNodes[bNodeId].next >> 1; } if (bNodes[bNodeId].next != -1) { bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev; } bNodes[bNodeId].next = first_free_bnode; first_free_bnode = bNodeId; } } void erase(const UEdge& edge) { if (edges[edge.id].prev_out != -1) { edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; } else { aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out; } if (edges[edge.id].next_out != -1) { edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; } if (edges[edge.id].prev_in != -1) { edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; } else { bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in; } if (edges[edge.id].next_in != -1) { edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; } edges[edge.id].next_out = first_free_edge; first_free_edge = edge.id; } void clear() { aNodes.clear(); bNodes.clear(); edges.clear(); first_anode = -1; first_free_anode = -1; first_bnode = -1; first_free_bnode = -1; first_free_edge = -1; } }; typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase; /// \ingroup graphs /// /// \brief A smart bipartite undirected graph class. /// /// This is a bipartite undirected graph implementation. /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" /// concept. /// \sa concept::BpUGraph. /// class ListBpUGraph : public ExtendedListBpUGraphBase {}; /// @} } //namespace lemon
• ## lemon/min_cut.h

 r2115 #include #include #include #include template #else template , typename _Traits =
• ## lemon/smart_graph.h

 r2115 ///\ingroup graphs ///\file ///\brief SmartGraph class. ///\brief SmartGraph and SmartUGraph classes. #include #include #include #include #include #include #include /**************** Undirected List Graph ****************/ typedef UGraphExtender > ExtendedSmartUGraphBase; /// \ingroup graphs /// /// \brief A smart undirected graph class. /// /// This is a simple and fast undirected graph implementation. /// It is also quite memory efficient, but at the price /// that it does support only limited (only stack-like) /// node and edge deletions. /// Except from this it conforms to /// the \ref concept::UGraph "UGraph" concept. /// \sa concept::UGraph. /// /// \todo Snapshot hasn't been implemented yet. /// class SmartUGraph : public ExtendedSmartUGraphBase { }; class SmartBpUGraphBase { public: class NodeSetError : public LogicError { virtual const char* exceptionName() const { return "lemon::SmartBpUGraph::NodeSetError"; } }; protected: struct NodeT { int first; NodeT() {} NodeT(int _first) : first(_first) {} }; struct UEdgeT { int aNode, next_out; int bNode, next_in; }; std::vector aNodes; std::vector bNodes; std::vector edges; public: class Node { friend class SmartBpUGraphBase; protected: int id; Node(int _id) : id(_id) {} public: Node() {} Node(Invalid) { id = -1; } bool operator==(const Node i) const {return id==i.id;} bool operator!=(const Node i) const {return id!=i.id;} bool operator<(const Node i) const {return id 0) { node.id = 2 * aNodes.size() - 2; } else { node.id = 2 * bNodes.size() - 1; } } void next(Node& node) const { node.id -= 2; if (node.id == -2) { node.id = 2 * bNodes.size() - 1; } } void first(UEdge& edge) const { edge.id = edges.size() - 1; } void next(UEdge& edge) const { --edge.id; } void firstFromANode(UEdge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); edge.id = aNodes[node.id >> 1].first; } void nextFromANode(UEdge& edge) const { edge.id = edges[edge.id].next_out; } void firstFromBNode(UEdge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); edge.id = bNodes[node.id >> 1].first; } void nextFromBNode(UEdge& edge) const { edge.id = edges[edge.id].next_in; } static int id(const Node& node) { return node.id; } static Node nodeFromId(int id) { return Node(id); } int maxNodeId() const { return aNodes.size() > bNodes.size() ? aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; } static int id(const UEdge& edge) { return edge.id; } static UEdge uEdgeFromId(int id) { return UEdge(id); } int maxUEdgeId() const { return edges.size(); } static int aNodeId(const Node& node) { return node.id >> 1; } static Node fromANodeId(int id) { return Node(id << 1); } int maxANodeId() const { return aNodes.size(); } static int bNodeId(const Node& node) { return node.id >> 1; } static Node fromBNodeId(int id) { return Node((id << 1) + 1); } int maxBNodeId() const { return bNodes.size(); } Node aNode(const UEdge& edge) const { return Node(edges[edge.id].aNode); } Node bNode(const UEdge& edge) const { return Node(edges[edge.id].bNode); } static bool aNode(const Node& node) { return (node.id & 1) == 0; } static bool bNode(const Node& node) { return (node.id & 1) == 1; } Node addANode() { NodeT nodeT; nodeT.first = -1; aNodes.push_back(nodeT); return Node(aNodes.size() * 2 - 2); } Node addBNode() { NodeT nodeT; nodeT.first = -1; bNodes.push_back(nodeT); return Node(bNodes.size() * 2 - 1); } UEdge addEdge(const Node& source, const Node& target) { LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); UEdgeT edgeT; if ((source.id & 1) == 0) { edgeT.aNode = source.id; edgeT.bNode = target.id; } else { edgeT.aNode = target.id; edgeT.bNode = source.id; } edgeT.next_out = aNodes[edgeT.aNode >> 1].first; aNodes[edgeT.aNode >> 1].first = edges.size(); edgeT.next_in = bNodes[edgeT.bNode >> 1].first; bNodes[edgeT.bNode >> 1].first = edges.size(); edges.push_back(edgeT); return UEdge(edges.size() - 1); } void clear() { aNodes.clear(); bNodes.clear(); edges.clear(); } typedef True NodeNumTag; int nodeNum() const { return aNodes.size() + bNodes.size(); } int aNodeNum() const { return aNodes.size(); } int bNodeNum() const { return bNodes.size(); } typedef True EdgeNumTag; int uEdgeNum() const { return edges.size(); } }; typedef BpUGraphExtender ExtendedSmartBpUGraphBase; /// \ingroup graphs /// /// \brief A smart bipartite undirected graph class. /// /// This is a simple and fast bipartite undirected graph implementation. /// It is also quite memory efficient, but at the price /// that it does not support node and edge deletions. /// Except from this it conforms to /// the \ref concept::BpUGraph "BpUGraph" concept. /// \sa concept::BpUGraph. /// class SmartBpUGraph : public ExtendedSmartBpUGraphBase {}; /// @} } //namespace lemon
• ## test/bipartite_matching_test.cc

 r2115 #include #include #include #include
• ## test/max_matching_test.cc

 r2115 #include "test_tools.h" #include #include #include
• ## test/ugraph_test.cc

 r2115 #include #include #include #include #include #include #include #include #include
Note: See TracChangeset for help on using the changeset viewer.