在 Haskell 中阅读 GraphML

我正在尝试将包含单个有向图的 GraphML 文件读入 HaskellData.Graph http://hackage.haskell.org/package/containers-0.2.0.1/docs/Data-Graph.html为了使用运行分析Math.Combinatorics.Graph http://hackage.haskell.org/package/HaskellForMaths-0.1.8/docs/Math-Combinatorics-Graph.html module.

但是，我找不到任何允许我读取 GraphML 文件、生成Data.Graph。我发现的一个相关模块是ForSyDe.Backend.GraphML http://hackage.haskell.org/package/ForSyDe-3.1.1/docs/ForSyDe-Backend-GraphML.html。然而，这似乎是特定于ForSyDeDSL，我目前想不出一种方法来使用它来读取普通文本Data.Graph.

您能否为我指出一个允许我阅读 GraphML 的库，最好提供一些有关如何使用它的示例代码？

经过一个多星期的搜索，我认为目前不存在 GraphML 解析器库。因此我编写了自己的最小解析器。

假设我们有这个 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>

我创建了这个基于 HXT 的解析器，它能够解析 GraphML 的最小子集（刚好足以创建一个Data.Graph http://hackage.haskell.org/package/containers-0.2.0.1/docs/Data-Graph.html上述 GraphML 的一部分）。这main以下文件的函数代表了如何使用它的示例：它打印图中的节点列表（另请参阅这个相关问题 https://stackoverflow.com/questions/21192423/haskell-data-graph-graphfromedges-example ).

{-# 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)