Re: [igraph] line graph + multiple edges + newbie

[Tamás Nepusz]

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
> address@hidden (mailto:address@hidden)
> https://lists.nongnu.org/mailman/listinfo/igraph-help