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

[Raphael Clifford]

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