Thanks, that's great. How can I handle the multiple edges problem? A typical input file might look like
a b 1 a b 4 a c 2 b c 2 b c 7 etc. Will Read_Ncol just do the right thing? Raphael On 6 September 2012 20:29, Tamás Nepusz <[email protected]> wrote: > Hi Raphael, > > If I understand correctly, the line graph according to your definition is > essentially a subgraph of the standard line graph -- you only need to remove > the u-v edges from the line graph that correspond to cases when edge u in the > original graph ha a weight larger than edge v. You can then make use of the > linegraph() function of igraph and remove the unnecessary edges: > > weights = g.es["weight"] > lg = g.linegraph() > edges_to_remove = [idx for idx, (u, v) in enumerate(lg.get_edgelist()) if > weights[u] >= weights[v]] > lg.delete_edges(edges_to_remove) > > A few tricks that are used in the above code and that are worth knowing: > > 1. The vertices of lg are ordered in the same way as the edges of g; in other > words, vertex i in lg corresponds to edge i in g > 2. It is usually better to pre-fetch the whole weight vector into a Python > list (see the "weights" list above) than fetching the weights one by one > (say, like g.es[u]["weight"] <= g.es[v]["weight"]). > 3. Also, if you make modifications to a graph, try to make them in one batch. > That's why we are collecting the indices of edges to remove first and then > delete the edges in one step. > > For educational purposes, I'm also showing how to code this without using > g.linegraph() and list comprehensions: > > edges_in_h = [] > weights = g.es["weight"] > for edge_index, (u, v) in enumerate(g.get_edgelist()): > edges_incident_on_v = g.incident(v, mode="out") > for other_edge_index in edges_incident_on_v: > if weights[edge_index] < weights[other_edge_index]: > edges_in_h.append((edge_index, other_edge_index)) > h = Graph(g.ecount(), edges_in_h) > > Note the weights list which pre-fetches the edge weights again, and note that > we are collecting the new edges of h into a vector before creating the graph > (again, in a single step in the end). The above snippet is untested but shows > the general idea. > > -- > T. > > > On Thursday, 6 September 2012 at 21:15, Raphael Clifford wrote: > >> Hi, >> >> I am still pretty new at igraph and am stuck doing something that I >> feel ought to be simple. >> >> I would like to do pretty much exactly what linegraph() does but with >> a couple of twists. From the manual linegraph() on a directed graph >> is defined as follows >> >> "The line graph L(G) of an undirected graph is defined as follows: L(G) has >> one vertex for each edge in G and two vertices in L(G) are connected iff >> their >> corresponding edges in the original graph share an end point. >> >> The line graph of a directed graph is slightly different: two vertices are >> connected by a directed edge iff the target of the first vertex’s >> corresponding >> edge is the same as the source of the second vertex’s corresponding edge." >> >> In my case the original graph is directed, the edges have weights and >> there can be multiple edges. New definition: Two vertices are >> connected by a directed edge iff the target of the first vertex's >> corresponding edge is the same as the source of the second vertex's >> corresponding edge AND the weight of the second vertex's corresponding >> edge is larger than the weight of the first vertex's corresponding >> edge. >> >> In principle this is a simple change to make but I don't fully >> understand the syntax yet of igraph+python. I would like something >> like the following >> >> #Read in the graph. >> #First problem is that it seems multiple edges are not supported? >> g = Read_Ncol("test.ncol", weights= True, directed = True) >> # Set the new line graph to have the same number of nodes as g has edges >> h = Graph.(g.ecount()) >> >> for e in g.es (http://g.es): >> for vnext in g.neighbors(e[1], mode = OUT): >> if (weight of edge e < weight of edge (e[1], vnext)): >> h.add_edges(ID of edge e, ID of (v, vnext)) >> >> The second problem is just that I don't understand the syntax well >> enough to see how to write this loop correctly using igraph. >> >> Any help is much appreciated. >> >> Raphael >> >> _______________________________________________ >> igraph-help mailing list >> [email protected] (mailto:[email protected]) >> https://lists.nongnu.org/mailman/listinfo/igraph-help > > > > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
