COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/list_ugraph.h @ 2115:4cd528a30ec1

Last change on this file since 2115:4cd528a30ec1 was 2115:4cd528a30ec1, checked in by Balazs Dezso, 13 years ago

Splitted graph files

File size: 3.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_LIST_UGRAPH_H
20#define LEMON_LIST_UGRAPH_H
21
22///\ingroup graphs
23///\file
24///\brief ListUGraph classes.
25
26#include <lemon/list_graph.h>
27#include <lemon/bits/base_extender.h>
28#include <lemon/bits/ugraph_extender.h>
29
30#include <vector>
31#include <list>
32
33namespace lemon {
34
35  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
36  ExtendedListUGraphBase;
37
38  /// \ingroup graphs
39
40  ///An undirected list graph class.
41
42  ///This is a simple and fast erasable undirected graph implementation.
43  ///
44  ///It conforms to the
45  ///\ref concept::UGraph "UGraph" concept.
46  ///
47  ///\sa concept::UGraph.
48  ///
49  ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
50  ///haven't been implemented yet.
51  ///
52  class ListUGraph : public ExtendedListUGraphBase {
53  public:
54    typedef ExtendedListUGraphBase Parent;
55    /// \brief Add a new node to the graph.
56    ///
57    /// \return the new node.
58    ///
59    Node addNode() { return Parent::addNode(); }
60
61    /// \brief Add a new edge to the graph.
62    ///
63    /// Add a new edge to the graph with source node \c s
64    /// and target node \c t.
65    /// \return the new undirected edge.
66    UEdge addEdge(const Node& s, const Node& t) {
67      return Parent::addEdge(s, t);
68    }
69    /// \brief Changes the target of \c e to \c n
70    ///
71    /// Changes the target of \c e to \c n
72    ///
73    /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
74    /// referencing the changed edge remain
75    /// valid. However <tt>InEdge</tt>'s are invalidated.
76    void changeTarget(UEdge e, Node n) {
77      Parent::changeTarget(e,n);
78    }
79    /// Changes the source of \c e to \c n
80    ///
81    /// Changes the source of \c e to \c n
82    ///
83    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
84    ///referencing the changed edge remain
85    ///valid. However <tt>OutEdge</tt>'s are invalidated.
86    void changeSource(UEdge e, Node n) {
87      Parent::changeSource(e,n);
88    }
89    /// \brief Contract two nodes.
90    ///
91    /// This function contracts two nodes.
92    ///
93    /// Node \p b will be removed but instead of deleting
94    /// its neighboring edges, they will be joined to \p a.
95    /// The last parameter \p r controls whether to remove loops. \c true
96    /// means that loops will be removed.
97    ///
98    /// \note The <tt>Edge</tt>s
99    /// referencing a moved edge remain
100    /// valid.
101    void contract(Node a, Node b, bool r = true) {
102      for(IncEdgeIt e(*this, b); e!=INVALID;) {
103        IncEdgeIt f = e; ++f;
104        if (r && runningNode(e) == a) {
105          erase(e);
106        } else if (source(e) == b) {
107          changeSource(e, a);
108        } else {
109          changeTarget(e, a);
110        }
111        e = f;
112      }
113      erase(b);
114    }
115  };
116
117} //namespace lemon
118 
119
120#endif
Note: See TracBrowser for help on using the repository browser.