在Haskell中读取GraphML [英] Reading GraphML in Haskell

问题描述

我试图将包含单个有向图的GraphML文件读入Haskell中。 rel =nofollow> Data.Graph 为了使用 Math.Combinatorics.Graph 模块。 p>

然而，我找不到任何模块允许我读取GraphML文件，产生一个 Data.Graph 。我找到的一个相关模块是 ForSyDe.Backend.GraphML 。但是，这似乎是特定于 ForSyDe DSL，我目前无法想出一种方法来使用它来读取一个普通的 Data.Graph 。

你能指点我一个库让我阅读GraphML，最好是有关如何使用它的一些示例代码？

解决方案

经过一周多的搜索之后，我认为目前没有GraphML解析器库存在。因此，我写了我自己的最小解析器。

假设我们有这个GraphML：

 <？xml version =1.0encoding =UTF-8？> 
< graphml xmlns =http://graphml.graphdrawing.org/xmlns
 xmlns：xsi =http://www.w3.org/2001/XMLSchema-instance
 xsi：schemaLocation =http://graphml.graphdrawing.org/xmlns 
 http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd\"> 
< graph id =Gedgedefault =undirected> 
< node id =n0/> 
< node id =n1/> 
< node id =n2/> 
< node id =n3/> 
< edge id =e1source =n0target =n1/> 
< edge id =e1source =n1target =n2/> 
< edge id =e1source =n1target =n3/> 
< edge id =e1source =n3target =n0/> 
< /图表> 
< / graphml> 
  

我创建了这个基于HXT的解析器，它能够解析GraphML的最小子集（刚够创建 Data.Graph ）。以下文件的 main 函数表示如何使用它的示例：它会打印图中节点的列表（另请参阅

  { - ＃LANGUAGE箭头，NoMonomorphismRestriction＃ - } 
导入Text.XML.HXT.Core 
将限定的Data.Graph导入为DataGraph 
 
 data Graph = Graph 
 {graphId :: String，
 nodes :: [String]，
 edges :: [（String，String）]  - （Source，target）
} 
 deriving（ Show，Eq）
 
 atTag tag = deep（isElem>>> hasName标签）
 
 parseEdges = atTagedge>>> 
 proc e  - > do 
 source<  -  getAttrValuesource - < e 
 target<  -  getAttrValuetarget - < e 
 returnA  - < （来源，目标）
 
 parseNodes = atTag节点>>> 
 proc n  - > do 
 nodeId<  -  getAttrValueid - < n 
 returnA  - < nodeId 
 
 parseGraph = atTag图形>>> 
 proc g  - > do 
 graphId<  -  getAttrValueid - < g 
节点<  -  listA parseNodes  - < g 
 edges<  -  listA parseEdges  - < g 
 returnA  - < Graph {graphId = graphId，nodes = nodes，edges = edges} 
 
 getEdges = atTagedge>>> getAttrValuesource
 
  - 获取Graph中单个节点的目标
 getTargets :: String  - >图表 - > [String] 
 getTargets source graph = map snd $ filter（（== source）.fst）$ edges图形
 
  - 将图形节点转换为Data.Graph可用的
 getDataGraphNode :: Graph  - >字符串 - > （String，String，[String]）
 getDataGraphNode图节点=（节点，节点，getTargets节点图）
 
  - 将Graph实例转换为Data.Graph列表（节点， nodeid，edge）元组
 getDataGraphNodeList :: Graph  - > [（String，String，[String]）] 
 getDataGraphNodeList graph = map（getDataGraphNode graph）（nodes graph）
 $ b $ main :: IO（）
 main = do 
 graph<  -  runX（readDocument [withValidate no]foo.graphml>>> parseGraph）
  - 将Graph结构转换为Data.Graph可导入的元组列表
 let graphEdges = getDataGraphNodeList $头图
  - 转换为Data.Graph 
 let（graph，vertexMap）= DataGraph.graphFromEdges'graphEdges 
  - 如何处理图形：打印顶点
 print $ map（（\（vid，_，_） - > vid）。vertexMap）（DataGraph.vertices graph）
  




I'm trying to read a GraphML file containing a single directed Graph into a Haskell Data.Graph in order to run an analysis using the Math.Combinatorics.Graph module.

However, I can't find any module that allows me to read a GraphML file, producing a Data.Graph. One related module I found is ForSyDe.Backend.GraphML. However, this seems to be specific to the ForSyDe DSL and I currently can't think of a way to use it to read a plain Data.Graph.

Could you point me to a library allowing me to read GraphML, preferably with some example code on how to use it?

解决方案

After more than a week of searching, I assume there is currently no GraphML parser library in existence. Therefore I wrote my own minimal parser.

Let's assume we have this GraphML:

<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"  
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
     http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
  <graph id="G" edgedefault="undirected">
    <node id="n0"/>
    <node id="n1"/>
    <node id="n2"/>
    <node id="n3"/>
    <edge id="e1" source="n0" target="n1"/>
    <edge id="e1" source="n1" target="n2"/>
    <edge id="e1" source="n1" target="n3"/>
    <edge id="e1" source="n3" target="n0"/>
  </graph>
</graphml>

I created this HXT-based parser that's able to parse a minimal subset of GraphML (just enough to create a Data.Graph of the above GraphML). The main function of the following file represents an example of how to use it: It prints the list of nodes in the graph (also see this related question ).

{-# LANGUAGE Arrows, NoMonomorphismRestriction #-}
import Text.XML.HXT.Core
import qualified Data.Graph as DataGraph

data Graph = Graph
  { graphId :: String,
    nodes :: [String],
    edges :: [(String, String)] -- (Source, target)
  }
  deriving (Show, Eq)

atTag tag = deep (isElem >>> hasName tag)

parseEdges = atTag "edge" >>>
  proc e -> do
      source <- getAttrValue "source" -< e
      target <- getAttrValue "target" -< e
      returnA -< (source, target)

parseNodes = atTag "node" >>>
  proc n -> do
      nodeId <- getAttrValue "id" -< n
      returnA -< nodeId

parseGraph = atTag "graph" >>>
  proc g -> do
      graphId <- getAttrValue "id" -< g
      nodes <- listA parseNodes -< g
      edges <- listA parseEdges -< g
      returnA -< Graph{graphId=graphId, nodes=nodes, edges=edges}

getEdges = atTag "edge" >>> getAttrValue "source"

-- Get targets for a single node in a Graph
getTargets :: String -> Graph -> [String]
getTargets source graph = map snd $ filter ((==source).fst) $ edges graph

-- Convert a graph node into a Data.Graph-usable
getDataGraphNode :: Graph -> String -> (String, String, [String])
getDataGraphNode graph node = (node, node, getTargets node graph)

-- Convert a Graph instance into a Data.Graph list of (node, nodeid, edge) tuples
getDataGraphNodeList :: Graph -> [(String, String, [String])]
getDataGraphNodeList graph = map (getDataGraphNode graph) (nodes graph)

main :: IO()
main = do
    graphs <- runX (readDocument [withValidate no] "foo.graphml" >>> parseGraph)
    --  Convert Graph structure to Data.Graph-importable tuple list
    let graphEdges = getDataGraphNodeList $ head graphs
    -- Convert to a Data.Graph
    let (graph, vertexMap) = DataGraph.graphFromEdges' graphEdges
    -- Example of what to do with the Graph: Print vertices
    print $ map ((\ (vid, _, _) -> vid) . vertexMap) (DataGraph.vertices graph)

这篇关于在Haskell中读取GraphML的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！