Databases
StackOverflow2013
Postsdbo
PORemoving an edge from a graph
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PORemoving an edge from a graph
    primarykey
    data
    text
    <p>I would like to remove some edges from a graph generated using Boost graph library.</p> <p>I use Boost's <code>boost::mt19937</code> to generate random numbers from 1 to N(number of vertices) as shown below, and add random edges.</p> <pre><code>#include "stdafx.h" #include &lt;ctime&gt; #include &lt;iostream&gt; #include &lt;utility&gt; // for std::pair #include &lt;algorithm&gt; #include &lt;time.h&gt; #include &lt;boost/graph/adjacency_list.hpp&gt; #include "boost/graph/topological_sort.hpp" #include &lt;boost/graph/graph_traits.hpp&gt; #include &lt;boost/graph/graphviz.hpp&gt; #include "boost/generator_iterator.hpp" #include "boost/random.hpp" // ---------------------------------------------- // Reading the number of vertices from the user. //----------------------------------------------- int read_int(std::string const &amp; initmsg, std::string const &amp; repeatmsg) { std::cout &lt;&lt; initmsg; for (std::string line; std::getline(std::cin, line); ) { std::istringstream iss(line); int res; if (iss &gt;&gt; res &gt;&gt; std::ws &amp;&amp; iss.get() == EOF) { return res; } std::cout &lt;&lt; repeatmsg; } std::cerr &lt;&lt; "Unexpected end of input! Aborting.\n"; std::exit(1); } int main() { using namespace std; using namespace boost; typedef boost::mt19937 RNGType; //Assignign a property value to first vertex, (i.e) the name typedef property&lt;vertex_name_t, std::string&gt; VertexNameProperty; // Defifning the type of gprah(undirected) typedef adjacency_list&lt; listS, vecS, undirectedS, VertexNameProperty &gt; undigraph; // a vertex iterator to iterate through the vertex to get the property vale typedef graph_traits&lt;undigraph&gt;::vertex_iterator vertex_iter; std::pair&lt;vertex_iter, vertex_iter&gt; vp; int const N = read_int("Number of vertices: ", "I did not understand, try again. Number of vertices: "); // Creating a instance g of unigraph undirected graph undigraph g; //Assigining property(name) to graph vertex property_map&lt;undigraph, vertex_name_t&gt;::type name = get(vertex_name, g); typedef graph_traits&lt;undigraph&gt;::vertex_descriptor Vertex; Vertex u1; u1=add_vertex(g); name[u1] = "Controller"; // Creatng other vertices in the graph by iterating for(Vertex p = 1; p &lt;= N-1; ++p) { p=add_vertex(g); } // Priting out the controller vp = vertices(g); std::cout &lt;&lt; "The name of the first vertex is " &lt;&lt; name[*vp.first]&lt;&lt;" and the output graph is:" &lt;&lt;std::endl; // -------------------------------------------------------------- // Generating a random edges from a vertex, maximum edges are four // Using Mersenne twister- A Pseudo random generator algorithm // Mersenne twister gives un-distributed random numbers //---------------------------------------------------------------- RNGType rng( time(0) ); boost::uniform_int&lt;&gt; one_to_four( 1, (N-1) ); boost::variate_generator&lt; RNGType, boost::uniform_int&lt;&gt; &gt;gen(rng, one_to_four); for(int i =0; i&lt;(N-1); i++) { int k = 0; while(k&lt;(N-1)) { int n = gen(); // Adding edges onto graph if(!boost::edge(i, n, g).second &amp;&amp; !boost::edge(n, i, g).second) { add_edge(i, n, g); k++; } } // removing edges that direct to same vertex graph } write_graphviz(cout, g); return 0; } </code></pre> <p>But I get the output for the above if I have 4 vertices as follow:</p> <pre><code>graph G 0; 1; 2; 3; 4; 0--1 ; 0--2 ; 0--2 ; 0--2 ; 1--3 ; 2--1 ; 2--4 ; 3--2 ; 3--2 ; 3--4 ; } </code></pre> <p>But as it can be seen, the edges, <code>(0,2) and (3,2)</code> are repeated. And for larger graphs, sometimes for ex: <code>(1,3) and (3,1)</code> exists and they both are same as it is undirected graph. How can I remove these vertices. I know Boost has something called <code>remove_edge_if()</code>, But I didn't find any precise example to support my case.</p> <p>Any help would be really appreciated.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USSpaniard89
    1. USSpaniard89
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload